7. 改进的冲突解决¶
7.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.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.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.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]
现在你可以试一试。
