1.定义

Hash Table又叫做散列表是数据结构里非常重要的一种，其设计构想是把需要保存的数据当作唯一的key，对每一个key通过一个特定的函数映射为一个具体的数值，这个数值代表存储结构中特定的位置，那么我们通过构造这样的一个表，要查询某个key的时候，就只需要访问特定的位置就可以了，这样查找效率大大提高了，在没有冲突的情况下查找效率是O(1).

这是构造哈希表的初衷，方便查找，但是我们也不能不考虑到映射值冲突的情况，例如，我们要考虑存储这样一些keys：atan, blow, cali, data, efif, above,

heaven, ikey, clock, lemon, moledy, nobody, cooccola, puppy, quick, ruby, shrieen,

tanzey,umong, vertic, wrick, xixily, yellow,zoom存储到一个string arr[26][2]的二维数组里，我们设计一个映射函数是这样的：h(keys) = key[0] – ‘a’; 不难发现，以a开头的atan,above分别存储在arr[0][0],arr[0][1]两个位置，b,d,e,f,h,I,c,等开头的词也顺序存储在对应的顺序表相应的位置里，但是cali,clock,coocoola有三个词，当第三个词同样找到arr[2][]的时候，发现已经没有位置了，这时候就发生了collision。

再如，我们要存储一个对象集合{18，23，11，20，2，7，27，30，42，15，36}，我们采用取余运算来映射对象，h(key) = key % 17。这里的17是我们符号表的大小，也就是我们设计一个arr[17]的表来存储对象的映射数值，那么是否取余运算的操作数都一定要是表的大小呢，不一定，但是为了使映射均匀，我们一般取表大小范围内合适的质数，17就是一个质数（因为质数除了1和本身以外没有因数，因此其他数与质数取余是分布均匀的）。尽管取余是常见的函数，但是上面也出现了2，36，都对17取余数为2，collision发生了。而hash table主要的问题就是要解决collision，我们需要设计一种好的映射函数解决collision。

2.设计散列函数

设计一个好的映射函数或者hash函数或者散列函数（我们就叫散列函数吧），有两个条件：

-计算简单，提高转化速度

-关键词对应的地址空间分布均匀，尽量减少冲突

有以下几种构造散列函数的方法：

-直接定址法：取关键词的某个线性函数值为散列地址：

H(key) = a *key + b (a,b 都是常数)

比如我们要保存1990 到2020年每年出生的人口总数，出生年份是key，我们可以设计一个大小为30的散列表用于保存以下散列函数构造的散列值：

H(key) = key – 1990

-数字取余法，上面已经给出了一个列子。

-数字分析法：分析数字关键字在各个位上的变化情况，取比较随机的位作为散列地址

比如：如果以手机号码为key，可以取后4位作为地址：

散列函数为：h(key) = atoi(key+7)

Key是一个11位的数字，atoi（key）是把character key转化为整数key，

Key+7表示从一开始的key的位置往后移动7位，取的是后四位。

-折叠法：把关键词分割成位数相同的几个部位，然后叠加：

比如我们可以把key 56793542分成542+793+056=1391,最后再去取后三位：391。

-平方取中法：顾名思义就是将key做一个平方计算，取中间几位作为地址。

3.处理collision的方法

通常有两种方法：开放地址法（open addressing），即重新找个地址存储；

另一种是链式存储法，就是把冲突的链接到一个统一的地方存储。

开放地址法：使用探测法面对冲突

如果发生了第i次冲突，探测法试探的下一个地址将增加di 如基本公式是：

Hi(key)= (h(key)+di)mod tablesize (1

di 的不同决定了不同的解决冲突的方案：线性探测，平方探测，双散列。

线性探测将di 设计为一个线性探测，比如di =i，

例如第一次探测到冲突了，那么就在原基础上加上i，如果没有冲突则存储数据，如果再有冲突，就在第二次探测的基础上再加上i。

平方探测将di 设计为+/-i2

双散列将di 设计为另一个散列函数：di = i*h2(key)

下面我们举例说明不同的探测法：

1． [endif]线性探测例子：{47,11,79,29,84,54,20,30}这样一个对象集合，我们的散列表设计为长度是13，散列函数设计为：h(key) = key % 11, di = i; 那么第一次我们把47插入arr[3],同理arr[0] = 11,arr[2] =79,arr[7] = 29,直到探测84的时候发现arr[7]已经被29站位了，所以第二次探测+2往后走，arr[8]=84，其他数字以此类推。

从上面的线性探测图中可以看出（脑补一下），如果数量足够大的时候，常常发生冲突的概率变大的时候，比如84后面有很多冲突的时候，那么按照现行探测的设计，有冲突我们就往后一个存储，这样下去就很容易发线一些数就成堆的存储，也就是容易聚集，存储就不太均衡。

平方探测法（quadratic probing）和上面雷同，只是在与第一次如果探测到冲突的时候，首先+1的平方，如果还有冲突，那么我们减1的平方探测，如果继续冲突，那么我们+2的平方，如果继续冲突，减2的平方探测，以此类推。

看起来二次探测好像也没有什么特别的，只是变化了探测的步数，但是二次探测也是有很多坑的，比如我们使用二次探测去对{5,6,7,8,11}使用h(key) = key mod 5,

我们可以算出arr[0] = 5, arr[1] = 6, arr[2] =7, arr[3] = 8,但是呢，当我们存储11的时候因为arr[1]已经存储6了，所以我们将探测11+1 再对5取模为2，而arr[2]已经存储了7了，所以我们继续探测11-1 对5取模为0，也是冲突，再探测11+2*2 对5取模为0，再探测11-2*2 对5取模为2,继续下去，我们会发现就一直在0，2之间跳来跳去，无法探测到剩下的空间。这也是二次探测的一个缺陷。

这里提一个定理显示：如果散列表的长度设计为4k+3，其中k是常数，的时候，也就是表的长度为质数时，平方探测法就可以探测到整个散列表的空间。

双散列（double hashing）: di设计为i*h2(key)，h2(key)是另一个散列函数探测序列为：h2(key),2h2(key),3h2(key),… nh2(key).....，且对任意的key，h2(key) != 0

探测序列还应该保证所有的散列存储单元都应该能被探测到，为了保证所有的存储单元能够被探测到，我们可以选择一下的形式：h2(key) = p – (key mod p), p< tablesize, p,tablesize都是质数。

当我们的散列表元素太多了，比如表长13，已经快满了，这个时候查找效率就会降低，有时为了提高查找效率，我们需要扩容，也就是改变散列表的长度，比如长度改变为29，但是这个时候并不是说直接改变散列表长度就可以了，必须rehashing，也就是所有的元素必须重新计算散列地址再存储。

分离链接法（separating chaining）：也就是把冲突的元素都串在一起，放在一个单向链表中去。

比如我们的关键字序列是{47，7，29，11，16，92，22，8，3，50，37，89，94，21}，散列函数为h(key) = key mod 11;

我们要哪个分离链接法处理冲突就如22，11都是余数为0的，都存储在一个链表里：