1. 定义

散列表（hash table），又称哈希表，常应用于存储、搜索、加密等场合。

散列表通过一个散列函数 \(h(k)\) ，将一个很大的（甚至趋向于无穷的）集合 \(U\) 映射到一个小得多的有序表 \(T\) 中，极大的压缩了存储空间，且搜索一个关键字的平均时间复杂度为 \(O(1)\)（尽管最坏情况的时间复杂度为 \(O(n)\)，但对于一个设计合理的散列表，是可以尽量避免出现最坏的情况）

2. 基本术语

散列函数和散列地址

记录存储位置 \(p\) 于其关键字 \(k\) 之间建立一个确立对应关系 \(h\)，使得 \(p=h(k)\) ，则称 \(h\) 为散列函数，\(p\) 为散列地址。
冲突

多个不同的关键字映射到同一内存空间，产生冲突的关键字又称关键词

3. 散列函数设计

散列函数的设计是散列表的灵魂所在。

3.1. 参考因素

散列表的大小。
装填因子 \(\alpha\)，即关键字集合大小与散列表大小的比值，该值影响冲突产生的可能性，一般取0.7~0.8（java中默认设置为0.75，一说因为其符合泊松分布，一说其符合红黑树的最佳装填因子，但貌似都没有直接理论证明这一取值，莫衷一是，总之当做一个经验的取值就可以了）。
关键字的分布情况，一般要把关键字转换成数值形式，才能统计其分布情况。
计算散列函数所需的时间。
关键字的查找频率。

3.2. 性质

确定性

如果两个散列值是不相同的，那么这两个散列值的原始输入也是不相同的
不可逆性

只可以由关键字推出散列地址，而不能由散列地址推出关键字
混淆性

输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性（改变每一位，都会使输出的每一位都有50%的概率改变）的散列函数会产生一个完全不同的散列值
均匀性

每个关键字都尽可能平均地分布在散列表中，使得每个关键字尽量不产生冲突

3.3. 设计方法

3.3.1. 直接寻址法

取关键字或关键字的某个线性函数值为散列地址。即\(h(k) = ak + b\)，其中\(a\)和\(b\)为常数（这种散列函数叫做自身函数）

但这种方法并不符合散列函数的性质，所以一般不采用这种方法

具体的设计方法：

初始化。

对于输入长度为 \(n\) 的数值型集合 \(U\)，将其映射到长度为 \(m\) 的散列表 \(T\) 中。

确定 \(m\) 的大小。 \[ m = 2n \] 确定 \(a\) 和 \(b\)

就是将 \([0, m]\) 线性地映射到 \([a, b]\) 中，解线性方程组即可。

例子。

\(U=\{11684, 11559, 11629, 11192, 11835, 11763, 11707, 11359, 11009, 11723\}\)，按上面计算， \(m=20,a=0.023, b=-253.23\)，其散列地址为 \(\{15,12,14,4,19,17,16,8,0,16\}\)

3.3.2. 数字分析法

分析集合中所有关键字的每一位的取值情况，取差异程度最大的几位或其组合，作为散列地址

应用例子：图书馆中的图书编码，其ISBN号对于同一出版社的前几位都是相同的，所以可以利用后几位的组合来构造对应的散列函数

具体的设计方法：

初始化。

对于输入长度为 \(n\) 的数值型集合 \(U\)，将其映射到长度为 \(m\) 的散列表 \(T\) 中。

确定采用什么进制进行运算。

为了尽可能地利用空间以及后续的运算，我们取二进制数运算。

确定 \(m\) 的大小。

装载因子取 \(0.75\)，即 \(m\) 约为 \(n\) 的1.3倍，而 \(m\) 又应为2的整次数幂。故\(m\)的取值公式如下 \[ m = 2 ^ {\lceil \log_2 n /0.75 \rceil } \] 确定取多少位。

设需要取 \(b\) 位，则 \(b = 2 ^ {\lceil \log_2 m \rceil }\)

确定散列地址。

即计算 \(U\) 中元素每一位的信息熵，然后取信息熵较大的 \(b\) 位。因为取二进制数，故取信息熵较大几位的计算简化为对每个元素的每一位分别求和，然后减去 \(n/2\)，取绝对值，最后取数值较小的 \(b\) 位作为散列地址 例子。

\(U=\{11684, 11559, 11629, 11192, 11835, 11763, 11707, 11359, 11009, 11723\}\)，按上面计算， \(m=16\)，应取二进制的 \(\{6,9,7,10\}\) 位，其散列地址为 \(\{8,0,3,13,5,14,13,7,0,11\}\)

3.3.3. 平方取中法

一个数平方后的中间几位数和数的每一位都相关，故对一个数平方后取其中间几位或其组合，作为散列地址。

具体设计方法：

初始化。

对于输入长度为 \(n\) 的数值型集合 \(U\)，将其映射到长度为 \(m\) 的散列表 \(T\) 中。

确定采用什么进制进行运算。

采用十进制即可。

确定 \(m\) 的大小。 \[ m = 10 ^ {\lceil \log_{10} n / 0.75 \rceil} \] 确定取多少位。

设需要取 \(b\) 位，则 \(b = 10 ^ {\lceil \log_{10} m \rceil }\)

确定散列地址。

计算集合中最小值的位数，取中间的 \(b\) 位作为

例子。

\(U=\{11684, 11559, 11629, 11192, 11835, 11763, 11707, 11359, 11009, 11723\}\)，按上面计算， \(m=100,b=2\)，其散列地址为 \(\{68,55,62,19,83,76,70,35,0,72\}\)

3.3.4. 折叠求和法

将关键字切割成位数相同的几部分，然后去这几部分之和（舍去进位），作为散列地址。

具体设计方法：

初始化。

对于输入长度为 \(n\) 的数值型集合 \(U\)，将其映射到长度为 \(m\) 的散列表 \(T\) 中。

确定采用什么进制进行运算。

采用十进制即可。

确定 \(m\) 的大小。 \[ m = 10 ^ {\lceil \log_{10} n / 0.75 \rceil} \] 确定每一部分有多少位

设需要取 \(b\) 位，则 \(b = 10 ^ {\lceil \log_{10} m \rceil }\)

确定散列地址。

每 \(b\) 位切成一部分，对每部分进行求和，并舍去进位，最终结果作为散列地址。

例子。

\(U=\{11684, 11559, 11629, 11192, 11835, 11763, 11707, 11359, 11009, 11723\}\)，按上面计算， \(m=100,b=2\)，其散列地址为 \(\{1,75,46,4,54,81,25,73,20,41\}\)

3.3.5. 除留余数法

假设散列表长度为 \(m\)，则选取一个不大于 \(m\) 的数 \(q\)，用 \(q\) 去除关键词，所得余数作为散列地址，即 \[ h(k) = k \bmod q \] 这种方法计算简单，应用最广。

具体设计方法：

初始化。

对于输入长度为 \(n\) 的数值型集合 \(U\)，将其映射到长度为 \(m\) 的散列表 \(T\) 中。

确定采用什么进制进行运算。

采用十进制即可。

确定 \(m\) 和 \(q\) 的大小。

\(m\) 约为 \(n\) 的1.3倍且不太接近「2的整数次幂」的素数（但为了设计方便，直接去不大于「2的整数次幂」的素数既可），\(q\)一般选不大于 \(m\) 的最大素数。取素数是为了增加随机性以减少冲突，但目前并没有直接证明这一结论的方法，当成一个经验取值即可。

例子。

\(U=\{11684, 11559, 11629, 11192, 11835, 11763, 11707, 11359, 11009, 11723\}\)，按上面计算， \(m=q=13\)，其散列地址为 \(\{10,2,7,12,5,11,7,10,11,10\}\)

3.3.6. 乘留小数法

散列函数为 \[ h(k) = \lfloor m(kA- \lfloor kA \rfloor) \rfloor,(0<A<1) \] 具体设计方法：

初始化。

对于输入长度为 \(n\) 的数值型集合 \(U\)，将其映射到长度为 \(m\) 的散列表 \(T\) 中。

确定采用什么进制进行运算。

为了后序计算方便，采用二进制。

确定 \(m\) 的大小。

该方法可以忽略 \(m\) 对结果的影响，使得 \(m\) 可以取2的整数次幂，即 \[ m = 2 ^ {\lceil \log_2 n /0.75 \rceil } \] 确定\(A\) 的大小。

算法导论第11章推导之处， \(A\) 应为形如 \(s/2^w\) 的分数，其中，\(w\) 为最大关键字的位数，\(0<s<2^w\)

为什么要这样取值呢？首先，我们注意到，按上述取值，\(kA = \frac{sk}{2^w}\)，令 \(sk=r_1 2^w + r_0\)，其中 \(r_1\) 为整数部分，\(r_0/2^w\) 为小数部分，该小数部分即为 \(kA- \lfloor kA \rfloor\) 的取值。

特别地，有理论认为 \(A\) 的理想取值应当接近\((\sqrt5 - 1) / 2 \approx 0.618\) （个人认为该取值接近于黄金分割率），故问题转化为为求 \(s\)

例子。

\(U=\{11684, 11559, 11629, 11192, 11835, 11763, 11707, 11359, 11009, 11723\}\)，按上面计算， \(m=16,w=14, s=10125\)，其散列地址为 \(\{7,3,8,7,12,4,11,10,5,9\}\)

3.3.7. 全域散列法

通过精心设计的函数，不管输入怎样的关键字集合，其平均性能都能达到最优。

对于一个全域散列，应满足两个不同的关键字发生冲突的概率不大于 \(1/m\)

对于输入未知无限的集合，常见的全域散列函数有MD5和SHA等。

下面是算法导论中介绍了一种基于已知有限的集合的全域散列的设计方法：

设一个足够大的素数 \(p\)，使得任意的关键字 \(k \in [0, p-1]\)，又设 \(a \in Z^*_p=\{1,\dots , p-1\},b \in Z_p=\{0,1,\dots , p-1\}\) ，则散列函数 \[ h_{a,b}(k) = (ak+b) \bmod p \bmod m \] 为全域散列函数。

于是，我们进行如下取值设计即可：\(m=1.3n, p=max(U)+1, a=random(p-1), b=random(p-1),a \neq b\)

例如，\(U=\{11684, 11559, 11629, 11192, 11835, 11763, 11707, 11359, 11009, 11723\}\)，按上面计算， \(m=13,p=11836, a=4373,b=5874\)，其散列地址为 \(\{3,5,4,0,6,3,5,8,0,10\}\)

附：上述假设的证明如下：

设关键字 \(k,l \in Z_p\)，有 \[ \begin{array}{ll} r=(ak+b) \bmod p \\ s=(al+b) \bmod p \end{array} \] 因为 \(r-s \equiv a(k-l) \pmod p\) ，其中，\(a \equiv b \pmod n\) 表示\(a\)与\(b\)对模\(n\)同余

又 \(k,l<p\) 且 \(p\) 为素数，又 \(a \neq 0\) ，故 \(a(k-l) \bmod p \neq 0\) ，故 \((r-s) \bmod p \neq 0\) ，故 \(r \neq s\)。说明在模 \(p\) 的层面上，不同关键字不会发生冲突。

对于给定的结果对 \((r, s)\)，我们有 \[ \begin{array}{ll} a=(r-s)((k-l)^{-1}\bmod p) \bmod p \\ b=(r-ak) \bmod p \end{array} \] \(k\) 和 \(l\) 发生冲突的概率为 \(r \equiv s \bmod m\) 的概率。对于给定的 \(r\) 值，满足 \(s \neq r\) 且 \(s \equiv r \bmod m\) 的 \(s\) 的数目至多为 \[ \lceil p/m \rceil -1 \leq (p+m-1)/m-1 = (p-1)/m \] 又 \(r\) 的数目至多为 \(p-1\) ，故 \(s\) 和 \(r\) 发生冲突的概率至多为 \[ (p-1)/m/(p-1) = 1/m \] 故对于两个不同的关键字，其发生的冲突的概率不大于 \(1/m\)，故上述的散列函数式是全域的。

4. 冲突处理

4.1. 开放寻址法

散列表中每一个地址都是单一内存空间

当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。其公式为 \[ h_i = (h(k) + d_i) \bmod m \] 这种方式会出现散列表已满，无法插入的情况，所以需要进行溢出扩容处理。

4.1.1. 线性探测法

\[ d_i = 1,2,3,\dots ,m-1 \]

发生冲突时，从冲突地址顺序往下寻找下一个空地址；如果后面的地址都遍历完了都找不到空地址，则从表头开始查找。

这种方法容易造成关键字聚集的现象。

4.1.2. 二次探测法

\[ d_i = 1^2,-1^2,2^2,-2^2,\dots ,k^2,-k^2(k \leq m/2) \]

对线性探测的改进，缓解关键字聚集的问题，但仍然不可以完全避免聚集的现象，而且因为越往后，跳过的下标越多，则会造成散列表已满的假象。

4.1.3. 伪随机探测法

\[ d_i = random(i) \]

实际中，取随机数的处理方法是，把发生冲突地址不断地重新输入到哈希函数中，直到找到下一个空地址。如果随机到重复的散列地址时，则可能是散列表已满了。

4.2. 链地址法

散列表中每一个地址都是一个链表的头指针。

把具有相同散列地址的关键字放在同一单链表中，又称同义词链表。

5. 查找

按照冲突处理的方法，将关键字代入函数式中，走一遍插入的流程，直到找到与关键字值相同的地址。

下面列出上面各冲突处理的平均查找长度（其中 \(\alpha\) 为装填因子）

冲突处理方法	查找成功	查找失败
线性探测法	\(\frac{1}{2}(1+\frac{1}{1-\alpha})\)	\(\frac{1}{2}(1+\frac{1}{(1-\alpha)^2})\)
二次探测法伪随机探测法	\(-\frac{1}{\alpha}\ln (1-\alpha)\)	\(\frac{1}{1-\alpha}\)
链地址法	\(1+\frac{\alpha}{2}\)	\(\alpha+e^{-\alpha}\)