7.9. 改进的冲突解决¶
7.9.1. 按步长的线性探测¶
我们怎样才能避免主聚集？一种可能的改进是使用线性探测，但以某个不为 1 的常数 \(c\) 跳过槽位。这样，探测函数就是 \(\textbf{p}(K, i) = ci\) ，于是探测序列中的第 \(i\) 个槽位将是 \((\textbf{h}(K) + ic) \mod M\) 。这样一来，起始位置相邻的记录就不会遵循相同的探测序列。
好的探测序列的一个性质是，它会在回到起始位置之前遍历哈希表中的所有槽位。显然，线性探测（每次都把槽位"跳过"一个）能够做到这一点。遗憾的是，并非所有 \(c\) 的取值都能实现这一点。例如，如果 \(c = 2\) 且表中包含偶数个槽位，那么任何起始位置在偶数槽位中的键，其探测序列都只会遍历偶数槽位。同样，起始位置在奇数槽位中的键，其探测序列也只会遍历奇数槽位。因此，表长与线性探测常数的这种组合实际上把记录分成两个集合，分别存储在哈希表中两个不相交的区域里。只要表中这两个区域包含的记录数相同，这就并不太重要。然而，仅凭偶然，很可能有一个区域会变得比另一个更满，导致那些记录出现更多冲突、性能更差。另一个区域则记录更少，因而性能更好。但系统的整体性能会下降，因为较满一侧增加的成本超过了较空一侧性能的提升。
常数 \(c\) 必须与 \(M\) 互素，才能生成访问表中所有槽位的线性探测序列（也就是说， \(c\) 与 \(M\) 不能有公因子）。对于大小为 \(M = 10\) 的哈希表，如果 \(c\) 取 1、3、7 或 9 中的任意一个，那么对任意键，探测序列都会访问所有槽位。当 \(M = 11\) 时， \(c\) 取 1 到 10 之间的任意值，都会为每个键生成访问所有槽位的探测序列。
现在你可以练习使用不同步长的线性探测。
7.9.2. 伪随机探测¶
考虑 \(c = 2\) 且我们希望插入一条键为 \(k_1\) 的记录、使得 \(\textbf{h}(k_1) = 3\) 的情形。 \(k_1\) 的探测序列是 3、5、7、9，依此类推。如果另一个键 \(k_2\) 的起始位置在槽位 5，那么它的探测序列将是 5、7、9，依此类推。 \(k_1\) 与 \(k_2\) 的探测序列以某种方式联系在一起，从而助长了聚集。换句话说，取值 \(c > 1\) 的线性探测并不能解决主聚集问题。我们希望能找到一种探测函数，它不会以这种方式把键联系在一起。我们更希望 \(k_1\) 的探测序列在序列的第一步之后，不应与 \(k_2\) 的探测序列相同。相反，它们的探测序列应当分道扬镳。
理想的探测函数会从未访问过的槽位中随机选择探测序列上的下一个位置；也就是说，探测序列应当是哈希表位置的一个随机排列。遗憾的是，我们实际上无法随机选择探测序列中的下一个位置，因为这样在查找键时就无法复现同一个探测序列。不过，我们可以采用一种类似的做法，称为 伪随机探测 。在伪随机探测中，探测序列中的第 \(i\) 个槽位是 \((\textbf{h}(K) + r_i) \mod M\) ，其中 \(r_i\) 是 1 到 \(M-1\) 这些数的随机排列中的第 \(i\) 个值。所有插入和查找都必须使用同一组随机数序列。探测函数将是 \(\textbf{p}(K, i) = \textbf{Permutation}[i]\) ，其中 Permutation 是一个长度为 \(M\) 的数组，在位置 Permutation[0] 中存储值 0，并在槽位 1 到 \(M - 1\) 中存储 1 到 \(M - 1\) 这些值的一个随机排列。
下面是伪随机探测的练习。
伪随机探测在哈希函数中展现出另一个理想特性。
7.9.3. 二次探测¶
另一种能消除主聚集的探测函数称为 二次探测 。这里探测函数是某个二次函数 \(\textbf{p}(K, i) = c_1 i^2 + c_{2}i + c_3\) ，其中 \(c_1\) 、 \(c_2\) 和 \(c_3\) 是某些选定的常数。
最简单的变体是 \(\textbf{p}(K, i) = i^2\) （即 \(c_1 = 1\) 、 \(c_2 = 0\) ，以及 \(c_3 = 0\)）。于是探测序列中的第 \(i\) 个值将是 \((\textbf{h}(K) + i^2) \mod M\) 。
现在你可以练习二次探测。
二次探测有一个问题：它的探测序列通常不会访问哈希表中的所有槽位。
对于许多哈希表大小，这个探测函数只会遍历相对较少数量的槽位。如果该循环上的所有槽位恰好都已满，这就意味着该记录根本无法插入！一个更现实的例子是含 105 个槽位的表。从任意给定槽位开始的探测序列只会访问表中另外 23 个槽位。如果这 24 个槽位恰好都已满，即使表中其他槽位为空，该记录也无法插入，因为探测序列会不断命中同样的这 24 个槽位。
幸运的是，二次探测有可能以较低的成本取得良好结果。探测函数与表长的正确组合会访问表中许多槽位。特别地，如果哈希表大小是素数，且探测函数为 \(\textbf{p}(K, i) = i^2\) ，那么表中至少一半的槽位会被访问。因此，如果表的装填程度不到一半，我们就能确定会找到一个空闲槽位。另一种做法是，如果哈希表大小是 2 的幂，且探测函数为 \(\textbf{p}(K, i) = (i^2 + i)/2\) ，那么探测函数会访问表中的每一个槽位。
7.9.4. 双重哈希¶
伪随机探测和二次探测都能消除主聚集。所谓主聚集，是指多个键的探测序列有相当长一段重叠的情形。然而，如果两个键哈希到同一个起始位置，那么对于我们目前见过的每一种冲突解决方法，它们都会始终遵循相同的探测序列。例如，伪随机探测和二次探测生成的探测序列完全由起始位置决定，而与原始键值无关。这是因为对于这些冲突解决方法，函数 p 忽略了它的输入参数 \(K\) 。如果哈希函数在某个特定起始位置产生了一个聚集，那么在伪随机探测和二次探测下，这个聚集依然存在。这个问题称为 次聚集 。
为了避免次聚集，我们需要让探测序列在决策过程中利用原始键值。一个简单的做法是回到使用固定步长的线性探测作为探测函数，但让这个步长由第二个哈希函数 \(\textbf{h}_2\) 决定。于是，探测序列将具有 \(\textbf{p}(K, i) = i * \textbf{h}_2(K)\) 的形式。这种方法称为 双重哈希 。
\(h_2\) 有一些重要的限制。最重要的是， \(h_2\) 返回的值绝不能为零（或 \(M\)），因为那样会立即导致无限循环，使探测序列毫无进展。然而，一个好的双重哈希实现还应确保所有探测序列常数都与表长 \(M\) 互素。例如，如果哈希表大小是 100，而线性探测的步长（由函数 \(h_2\) 生成）是 50，那么探测序列上就只会有一个槽位。反之，如果哈希表大小是 101（一个素数），那么任何小于 101 的步长都会访问表中的每一个槽位。
这一点很容易做到。一种方法是选择 \(M\) 为素数，并让 \(\textbf{h}_2\) 返回一个落在范围 \(1 <= \textbf{h}_2(k) <= M - 1\) 内的值。我们可以通过使用这个第二哈希函数来做到这一点： \(\textbf{h}_2(k) = 1 + (k \mod (M-1))\) 。另一种方法是令 \(M = 2^m\) ，其中 \(m\) 为某个值，并让 \(\textbf{h}_2\) 返回一个介于 1 和 \(2^m\) 之间的奇数值。我们可以用这个第二哈希函数得到该结果： \(\textbf{h}_2(k) = (((k/M) \mod (M/2)) * 2) + 1\) 。 [1]
现在你可以试一试。
