代码小工蚁的#《算法图解》#学习笔记-C5散列表
C5 散列表hash tables

一、散列函数hash function

散列函数“将输入映射到数字”（maps strings to numbers）
散列函数要满足的要求：
相同的输入，得到相同的输出。
最理想的情况是：不同的输入映射不同的数字。
不同的输入得到相同的输出，这种现象称为碰撞（Collision，冲突）。

散列表（hash table哈希表），也称为散列映射hash maps、映射maps、字典dictionaries和关联数组associative arrays

映射函数叫做散列函数，用来确定元素的存储位置
存放记录的数组叫做散列表

二、散列表应用

1、快速查找数据
python中的散列表用字典来实现，字典中的键映射对应的值。如：

# 创建空字典
word_maps = dict()
word_maps = {}

word_maps['ant'] = '蚂蚁'
word_maps["AntsPi"] = '代码小工蚁'

print(word_maps['ant'])
print(word_maps["AntsPi"])  # 返回：代码小工蚁
# 会出错KeyError，字典中没有antspi这个键（区分大小写的！）
# print(word_maps["antspi"])
# 可以改用get方法并指定默认返回值
print(word_maps.get('antspi','要注意大小写'))  # 返回：要注意大小写
print(word_maps['AntsPi'])

2、防止重复
防止重复示例：检查投票人

#coding=utf-8

# 防止重复投票示例

voted = {}
def check_voter(name):
    if voted.get(name):
        print('kick out!')
    else:
        voted[name] = True
        print('let vote!')

if __name__ == '__main__':
    while True:
        print('\n')
        check = input('Input voter name.\n(q to quit): ')
        if check.lower() == 'q':
            break
        else:
            check_voter(check)

此例中用散列表（字典）存储是否已投票，检查速度比数组要快。

3、数据缓存
大型网站使用缓存加速技术。缓存的数据存储在散列表中。

网站缓存代码示例：

# 仅作示例用（不运行）

# 创建缓存空字典
cache = {}

def get_page(url):
    # 判断url是否已存在于字典中
    if cache.get(url):
        return cache[url]  # 已有，则直接读取缓存
    else:
        data = get_data_from_server(url)  # 没有，则从服务器上读取数据
        cache[url] = data  # 创建对应缓存
        return data
        

三、冲突与性能

在平均情况下，散列表查找、插入、删除操作的运行时间为：O(1)
在最糟情况下，散列表所有操作的运行时间都为O(n)
要避开最糟情况，需要避免冲突。关键因素有：
（1）填装因子要低：发生冲突的可能性越小，散列表的性能越高。
经验规则是：一旦填装因子大于0.7，就调整散列表的长度。
（2）良好的散列函数：良好的散列函数让数组中的值呈均匀分布。
可以使用安全散列算法（Secure Hash Algorithm，缩写为SHA）。

python中的散列函数可以查看一下文章：
利用Python 生成hash值 https://blog.csdn.net/cmzsteven/article/details/65628789