哈希冲突与开放地址法

装填因子（Load Factor）

假设哈希表空间大小为m，填入表中元素个数是n，则称$\alpha = n / m$为哈希表的装填因子。

当哈希表元素太多，即装填因子$\alpha$太大时，查找效率会下降。采用开放地址法时，实用最大装填因子一般取$0.5 \le \alpha \le 0.85$。当装填因子过大时，解决的方法是加倍扩大哈希表，这个过程叫作再散列（rehashing）。

再散列的过程需要遍历原哈希表，把所有的关键字重新散列到新数组中。为什么需要重新散列呢？因为长度扩大以后，散列的规则也随之改变。经过扩容，原本拥挤的哈希表重新变得稀疏，原有的关键字也重新得到了尽可能均匀的分配。

装填因子也是影响产生哈希冲突的因素之一。当不同的关键字可能会映射到同一个散列地址上，就导致了哈希冲突（collision），即$h(key_i) = h(key_j),\ key_i \ne key_j$，因此需要某种冲突解决策略。

例如有12个数据对象的集合{18, 23, 11, 20, 2, 7, 27, 30, 42, 15, 34, 35}，哈希表的大小为17，哈希函数选择h(key) = key % size。

在插入最后一个关键字35之前，都没有产生任何冲突。但是h(35) = 1，位置已有对象，就导致了冲突。

常用的处理冲突的思路有两种：

1. 开放地址法（open addressing）：一旦产生了冲突，就按某种规则去寻找另一空地址。开放地址法主要有线性探测法、平方探测法（二次探测法）和双散列法。

2. 分离链接法：将相应位置上有冲突的所有关键字存储在同一个单链表中。

线性探测法（Linear Probing）

当产生冲突时，以增量序列1, 2, 3, ..., N - 1循环试探下一个存储地址，其中N为哈希表表长。

例如序列{47, 7, 29, 11, 9, 84, 54, 20, 30}，哈希表表长为13，哈希函数h(key) = key % 11，用线性探测法处理冲突。

线性探测法

线性探测法的缺陷在于容易出现聚集现象。

平方探测法（Quadratic Probing）

平方探测法也称为二次探测法，以增量序列$1^2, -1^2, 2^2, -2^2, \dots, q^2, -q^2\ (q \le \lfloor N/2 \rfloor)$循环试探下一个存储地址。

例如序列{47, 7, 29, 11, 9, 84, 54, 20, 30}，哈希表表长为11，哈希函数h(key) = key % 11，用平方探测法处理冲突。

平方探测法

但是只要还有空间，平方探测法就一定能找到空闲位置吗？

例如对于以下哈希表，插入关键字11，哈希函数h(key) = key % 5，用平方探测法处理冲突。

对关键字11进行平方探测的结果一直在下标0和2之间波动，永远无法达到其它空的位置。

但是有定理证明，如果哈希表长度是满足$4k + 3\ (k \in Z^+)$形式的素数时，平方探测法就可以探查到整个哈希表空间。

双散列探测法（Double Hashing）

设定另一个哈希函数$h_2(key)$，探测序列为$h_2(key),\ 2h_2(key),\ 3h_2(key), \dots$。

探测序列应该保证所有的散列存储单元都应该能够被探测到，选择以下形式有良好的效果：