散列函数也称为散列映射、映射、字典、关联数组、哈希函数等。
概念：
散列的概念属于查找，它不以关键字的比较为基本操作，采用直接寻址技术。在理想情况下，查找的期望时间为O(1)。
hash函数就是把任意长的输入字符串变化成固定长的输出字符串的一种函数。输出字符串的长度称为hash函数的位数。
散列（Hashing）通过散列函数将要检索的项与索引（散列，散列值）关联起来，生成一种便于搜索的数据结构（散列表）。
算法图解介绍：
散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。即散列函数“将输入映射到数字”。
散列函数必须满足一些要求：
- 它必须是一致的。
- 它应将不同的输入映射到不同的数字。
例如1，假设你输入apple时得到的是4，那么每次输入apple时，得到的都必须为4。
例如2，如果一个散列函数不管输入是什么都返回1，那它就不是好的散列函数。最理想的情况是 将不同的输入映射到不同的数字。
以商品价格的图例说明散列表的结构：
假设apple、orange 价格如下表所示
| ----- | apple | orange |
|---|---|---|
| Price | 1.45￥/kg | 1.2￥/kg |
创建一个空数组：（None为数组初始值，这里仅为了记录方便写成None）
| 0 | 1 | 2 | 3 |
|---|---|---|---|
| None | None | None | None |
将 apple 输入散列函数，输出数字为0，并把它作为数组索引，将价格存入数组。
同样的，将 orange 输入 散列函数，输出数字为2，并把它作为数组索引，将价格存入数组。
| 0 | 1 | 2 | 3 |
|---|---|---|---|
| 1.49 | None | 1.2 | None |
现在我们查询apple的价格，将apple 输入 散列函数，输出索引值0，直接查询对应的数组值，即为apple的价格。
将商品名称作为输入给散列函数，散列函数给出对应的索引值，将商品对应的价格放入索引值对应的数组位置。可以在O(1)的时间复杂度下找到相应的结果，主要得益于以下几点：
散列表是一种包含额外逻辑的数据结果（散列函数），与数组和链表被直接映射到内存不同。
python提供函数 d i c t ( ) dict() dict()创建散列表（键值对）代码如下：
book = dict()
book["apple"] = 0.67
book["milk"] = 1.49
book["avocado"] = 1.60
print(book)
print(book["milk"])
运行结果：
{‘apple’: 0.67, ‘milk’: 1.49, ‘avocado’: 1.6}
1.49
散列表由键和值组成。在前面的散列表book中，键为商品名，值为商品价格。散列表将键映射到值。
假设你要创建一个电话簿，将姓名映射到电话号码。该电话簿需要提供如下功能：
1.添加联系人及其电话号码。
2.通过输入联系人来获悉其电话号码。
下面我们来使用散列表进行对电话簿的创建映射和查找。python代码：
phone_book = dict()
phone_book["wang"] = 13053205320
phone_book["shuai"] = 13956785678
print(phone_book["wang"])
运行结果：
13053205320
书中例子提到 DNS解析（DNS resolution）：将网址映射为IP地址。
假如你负责管理一个投票站，每个人只能投一票，如何避免重复投票呢？
voted = dict()
def checkname(name):
if voted.get(name):
print("kick them out!")
else:
voted[name] = True
print("let them vote!")
checkname("wang")
checkname("shuai")
checkname("wang")
运行结果：
let them vote!
let them vote!
kick them out!
缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中。
缓存的优点：
cache = {}
def get_page(url):
if cache.get(url):
return cache[url] # 返回缓存的数据
else:
data = get_data_from_server(url)
cache[url] = data # 先将数据保存到缓存中
return data
说明：仅当URL不在缓存中时，让服务器做这些处理，并将处理生成的数据存储到缓存中，再返回它。这样，当下次有人请求该URL时，你就可以直接发送缓存中的数据，而不用再让服务器进行处理，耗费资源。
给两个键分配的位置相同就是冲突，如何处理？
冲突例子如下：
在平均情况下，散列表执行各种操作的时间都为O(1)，O(1)被称为常量时间。
| ------ | 散列表（平均情况） | 散列表（最糟情况） | 数组 | 链表 |
|---|---|---|---|---|
| 查找 | O ( 1 ) O(1) O(1) | O ( n ) O(n) O(n) | O ( 1 ) O(1) O(1) | O ( n ) O(n) O(n) |
| 插入 | O ( 1 ) O(1) O(1) | O ( n ) O(n) O(n) | O ( n ) O(n) O(n) | O ( 1 ) O(1) O(1) |
| 删除 | O ( 1 ) O(1) O(1) | O ( n ) O(n) O(n) | O ( n ) O(n) O(n) | O ( 1 ) O(1) O(1) |
PS:散列表一般为平均情况，最糟情况较少，故默认为
O
(
1
)
O(1)
O(1)。
而要避免上述呈现的最糟的情况，就要避免冲突，那么就需要做好下面两点：
较低的填装因子与良好的散列函数
填装因子=散列表包含的元素数 / 位置总数
填装因子 >1 说明数量超过了数组的位置数。此时需要调整长度。
填装因子越低，发生冲突的可能性越小，散列表性能越高。一般情况下，填装因子大于0.7，就需要调整长度。
良好的散列函数让数组中的值呈均匀分布。糟糕的散列函数让值扎堆，导致大量的冲突。
拓展：SHA函数 可将其作为散列函数。
《算法图解》第五章
此部分学习算法内容已上传github：https://github.com/ShuaiWang-Code/Algorithm/tree/master/Chapter5