前面的章节中，我们利用数据集中元素的相对位置信息来提高查找算法的性能。
比方知道列表是有序的，能够使用二分查找。本节我们走得更远一些，创建一个数据结构，使得查找性能提高到O(1)。称为哈希查找。
要做到这种性能，我们要知道元素的可能位置。假设每一个元素就在他应该在的位置上，那么要查找的时候仅仅须要一次比較得到有没有的答案，但以下将会看到。不是这么回事。
哈希表是这样一种数据集合，元素的保存的时候就存在easy找到位置上。哈希表表中每个位置，一般称为槽位，每个槽位都能保存一个数据元素并以一个整数命名(从0開始)。这样我们就有0号槽位。1号槽位等等。起始时。哈希表里没有数据，槽位是空的。这样在构建哈希表的时候，能够把槽位值都初始化为None，图4显示一个大小为11的哈希表，或者是说有m个槽位的哈希表。m从0到10.
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcHl0aG9uMjAxNA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
图中元素和保存的槽位之间的映射关系，称为哈希函数，哈希函数接受一个元素作为參数，返回一个0到m-1的整数作为槽位名。假如我们有一个整数集54，26，93。17，77和31，我们的第一个哈希函数就能够用“余数法”。简单地将元素除以表的大小，返回余数作为哈希值。(h(item)=item%11)。表4是上述整数集的哈希值。
|
Table 4: Simple Hash Function Using Remainders |
|
|
Item |
Hash Value |
|
54 |
10 |
|
26 |
4 |
|
93 |
5 |
|
17 |
6 |
|
77 |
0 |
|
31 |
9 |
注意余数法一般以某种形式存于全部哈希函数中。由于它的结果一定在槽位范围内。
一旦哈希值计算出来，就要把元素插入到哈希表中指定的位置。
如图5所看到的，注意6槽位和11槽位是空的，这就要引入满载因子的概念，一般表述为：
λ=元素数量/哈希表容量
这里。就是
λ=6/11
如今当我们要查找的时候，仅仅要简单地用哈希函数计算出槽位值。然后到表中检查是否存在就能够了，这个查找动作是O(1),由于计算哈希值的时间。以及到表中查找的时间是个常数。假设每件东西都各守其位。我们就发现了一个常数级的查找算法。
或许你已经注意到，这个技术仅在每一个元素相应一个位置时有效，比如，上面的样例中假设添加一个44。那么它的哈希值是0。可是77的值也是0。这时问题就出来了。2个值相应同一个槽位，这被称为“collision”，非常明显，collision给哈希技术造成了困难，我们随后具体讨论。
哈希函数
对给定的数据集，哈希函数将每一个元素映射为单个的槽位。称为“完美哈希函数”，假设我们知道元素和集合固定不变。那么构造一个完美哈希函数或许是可能的。坏消息是对一个随意数据集合，没有一个系统的方法来构造完美哈希函数，好消息是。哈希函数不完美也能提供不错的性能。
假设一定要完美的哈希函数，一种方法是做大哈希表，以保证每一个元素都有自己的索引。
尽管在数据不多的情况下可行，可是假设数据非常大就不可行。
比方，假设数据项是8位号码，这就须要十亿个槽位。要是我们只用来保存25个学生的号码，就太费了。
我们的目标是：collision最少，计算简单，分布均匀。有几种扩展余数法的方案，以下讨论当中几个。
折叠法：这样的方法把元素分成相等的几片（最后一片可能不相等）。然后再把碎片拼起来作为哈希值。比方我们的数据项是号码436-555-4601，那么应该把号码分成2个一组，然后加起来，即43+65+55+46+01，得到210 。如果哈希表有11个槽位。那么再一步用11除210来得到槽位。即210%11=1。所以号码436-555-4601的哈希值是1 。有些折叠法多了一步，在相加之前，把数据位顺序反转，在上面的样例中。即 43+56+55+64+01=219 计算219 % 11=10。
还有一种算法叫做“平方取中法”，先计算元素的平方值，再从中提取几位数字。比如，对元素44。先计算442=1936。提取中间两位93，然后再取余数法，得到5（93%11=5）
|
Table 5: Comparison of Remainder and Mid-Square Methods 表5 余数法与平方取中法的比較 |
||
|
Item |
Remainder |
Mid-Square |
|
54 |
10 |
3 |
|
26 |
4 |
7 |
|
93 |
5 |
9 |
|
17 |
6 |
8 |
|
77 |
0 |
4 |
|
31 |
9 |
6 |
对于字符类元素也能创建哈希函数，单词cat能够看成一个数字串
>>> ord('c')
99
>>> ord('a')
97
>>> ord('t')
116
我们把这三个数字加起来，用余数法计算哈希值。
以下是一个计算字符串哈希值的函数：
Listing 1
defhash(astring, tablesize):
sum=0
for pos inrange(len(astring)):
sum=sum+ord(astring[pos])
returnsum%tablesize
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcHl0aG9uMjAxNA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
有意思的是，上述算法中。同样字母不同顺序的单词得到的哈希值相等，解决的方法是加上字母的位置作为重量。图7显示了使用位置作为重量因子。改动后的哈希函数作为练习。
你也能够思考几种计算哈希值的方法，但必需要记住，哈希函数必需要简单高效。不能成为计算的主要负担。假设哈希函数太复杂，计算槽位名的时间超过了简单的顺序查找或二分查找的时间。那么哈希函数还有什么意义呢？