散列表算法又称为Hash list（哈希表）。散列表由散列函数和一个数组组成。通过像散列函数输入一个值，散列函数返回另外一个值（这个值是数据在数组中的索引）。算法的复杂度是O(1)。

对于同样的输入，散列表必须返回同样的输出，这一点很重要。如果不是这样的，就无法找到你在散列表中添加的元素！

练习：请问下面哪些散列函数是一致的？

5.1    f(x)   =     1   #无论输入是什么，都返回1

5.2    f(x)   =      rand()   #每次都返回一个随机数

5.3    f(x)   =      next_empty_slot()  #返回散列表中下一个空位置的索引

5.4    f(x)   =       len(x)         #将字符串的长度用作索引

5.1和5.4是；5.2和5.3都不是。

散列表的应用还被用于创建电话簿；DNS解析；和防止重复。

基本用法：

python提供的散列表实现为字典，使用函数dict来创建散列表，也可以用快捷方式一对花括号“{}”来代替。

将散列表用于查电话号码

一个人只能投一票,一个人不能投重复的票。

投票 网页服务器的缓存

仅当URL不在缓存中，你才让服务器做些处理，并将处理生成的数据存储到缓存中，再返回它。这样，当下次有人请求该URL时，你就直接发送缓存中的数据，而不用再让服务器进行处理了。

小结：

散列表适合用于：

模拟映射关系；防止重复；缓存/记住数据，以免服务器再通过处理来生成它们。

冲突：

如果一个散列函数给出的规则让元素不是均匀的在置在数组中，就会产生冲突，那么先放入的元素会在身后创建一个链表来存放后边来的元素。

性能：

散列表、数组和链表的比较

在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点！但最糟糕的情况下，散列表的各种操作速度都很慢。因此，在使用散列表的时候，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有：

较低的装填因子（0.0-1.0），经验规则：一旦装填因子大于0.7，就该调整散列表的长度；

良好的散列函数，良好的散列函数让数组中的值呈均匀分布，糟糕的散列函数让值扎堆，导致大量冲突。

装填因子：散列表包含的元素数  /  位置总数

练习：

假设你有四个处理字符串的散列函数。

A. 不管输入是什么，都返回1。

B. 将字符串的长度用作索引。

C. 将字符串的第一个字符用作索引。即将所有以a搭头的字符串都映射到散列表的同一位置，以此类推

D. 将每个字符都映射到一个整数：a = 2, b = 3, c = 5, d = 7, e = 11, f = 13, g = 17, 等等。对于给定的字符串，这个散列函数将其中每个字符对应的素数相加，再计算结果除以散列表长度的余数。例如，如果散列表的长度为10，字符串为bag,则索引为（3+2+17）%10 = 22 % 10 = 2。

在下面的每个示例中，上述哪个散列函数可实现均匀分布？假设散列表的长度为10。

5.5    将姓名和电话号码分别作为键和值的电话簿，其中联系人姓名为Esther、Ben、Bob和Dan。

5.6    电池尺寸到功率的映射，其中电池的尺寸为A、AA、AAA和AAAA。

5.7    书名到作者的映射，其中书名分别为Maus、Fun Home和Watchmen。

5.5    散列函数D可以实现均匀分布

5.6    散列函数B和D可以实现均匀分布

5.7    散列函数B、C和D可以实现均匀分布

小结：

你根本不用自己去实现散列表，因为你使用的编程语言提供了散列表实现。你可使用python提供的散列表，并假定能够获得平均情况下的性能：常量的时间。

散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型。你可能很快会发现自己经常在使用它。

---

你可以结合散列函数和数组来创建散列表。

冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。

散列表的查找、插入和删除速度都非常的快。

散列表适合用于模拟映射关系。

一旦装填因子超过0.7，就该调整散列表的长度。

散列表可用于缓存数据（例如，在Web服务器上）。

散列表非常适合用于防止重复。