15.6.1. 冲突解决¶

现在我们转向最常用的哈希形式：不使用分桶的 闭哈希 ，以及一种可能使用哈希表中任意槽位的 冲突解决策略 。

插入时，当记录的起始位置已被占用， 冲突解决 的目标是在哈希表中找到一个空闲槽位。我们可以把任何冲突解决方法看作是在生成一个可能容纳该记录的哈希表槽位序列。序列中的第一个槽位就是该键的起始位置。如果起始位置已被占用，那么冲突解决策略就转到序列中的下一个槽位。如果这个槽位也被占用，就必须再找另一个槽位，依此类推。这个槽位序列称为 探测序列 ，它由某个我们称为 p 的 探测函数 生成。插入的过程如下。

   // Insert e into hash table HT
   void hashInsert(Key k, Elem e) {
     int home;                     // Home position for e
     int pos = home = h(k);        // Init probe sequence
     for (int i=1; EMPTYKEY != (HT[pos]).key(); i++) {
       if (k == HT[pos].key()) {
         println("Duplicates not allowed");
         return;
       }
       pos = (home + p(k, i)) % M; // probe
     }
     HT[pos] = e;
   }

   // Insert e into hash table HT
   void hashInsert(const Key& k, const Elem& e) {
     int home;                     // Home position for e
     int pos = home = h(k);        // Init probe sequence
     for (int i=1; EMPTYKEY != (HT[pos]).key(); i++) {
       if (k == HT[pos].key()) {
         println("Duplicates not allowed");
         return;
       }
       pos = (home + p(k, i)) % M; // probe
     }
     HT[pos] = e;
   }

方法 hashInsert 首先检查该键的起始槽位是否为空。如果起始槽位已被占用，我们就用探测函数 \(\textbf{p}(k, i)\) 在表中定位一个空闲槽位。函数 p 有两个参数：键 \(k\) ，以及表示我们希望处于探测序列中哪个位置的计数 \(i\) 。也就是说，要得到键 \(K\) 的起始槽位之后探测序列中的第一个位置，我们调用 \(\textbf{p}(K, 1)\) 。对于探测序列中的下一个槽位，调用 \(\textbf{p}(K, 2)\) 。注意，探测函数返回的是相对于原始起始位置的偏移量，而不是哈希表中的槽位。因此， hashInsert 中的 for 循环在每次迭代时，把探测函数返回的值加到起始位置上，从而计算出表中的位置。对 p 的第 \(i\) 次调用返回要使用的第 \(i\) 个偏移量。

在哈希表中查找时，遵循插入记录时所遵循的同一探测序列。这样，不在其起始位置的记录也能被找到。查找过程的一种实现如下。

   // Search for the record with Key K
   boolean hashSearch(Key K, Elem e) {
     int home;              // Home position for K
     int pos = home = h(K); // Initial position is the home slot
     for (int i = 1;
          (K != (HT[pos]).key()) && (EMPTYKEY != (HT[pos]).key());
          i++) {
       pos = (home + p(K, i)) % M; // Next on probe sequence
          }
     if (K == (HT[pos]).key()) {   // Found it
       e = HT[pos];
       return true;
     }
     else { return false; }            // K not in hash table
   }

   // Search for the record with Key K
   bool hashSearch(const Key& K, Elem& e) const {
     int home;              // Home position for K
     int pos = home = h(K); // Initial position is the home slot
     for (int i = 1;
          (K != (HT[pos]).key()) && (EMPTYKEY != (HT[pos]).key());
          i++)
       pos = (home + p(K, i)) % M; // Next on probe sequence
     if (K == (HT[pos]).key()) {   // Found it
       e = HT[pos];
       return true;
     }
     else return false;            // K not in hash table
   }

插入和查找这两个例程都假定每个键的探测序列上至少有一个槽位为空。否则，在查找失败时它们会陷入无限循环。因此，哈希系统应当记录已存储记录的数量，并拒绝向只剩一个空闲槽位的表中插入。

冲突解决最简单的方法就是从起始槽位开始沿表向下移动，直到找到一个空闲槽位。这称为 线性探测 。简单线性探测的探测函数是 \(\textbf{p}(K, i) = i\) 。也就是说，探测序列上的第 \(i\) 个偏移量就是 \(i\) ，这意味着第 \(i\) 步只是沿表向下移动 \(i\) 个槽位。一旦到达表的底部，探测序列就回绕到表的开头（因为最后一步是对结果按表长取模）。线性探测的优点是，在探测序列回到起始位置之前，表中的所有槽位都可能成为插入新记录的候选。

Settings

Saving...
Server Error
Resubmit

你能看出为什么这可能不是解决冲突的最佳方法吗？

15.6.1.1. 线性探测的问题¶

虽然在考虑冲突解决策略时，线性探测很可能是首先想到的办法，但它并不是唯一可行的办法。探测函数 p 为我们提供了许多进行冲突解决的选择。事实上，线性探测是最糟糕的冲突解决方法之一。下一个幻灯片展示了主要问题。

Settings

Saving...
Server Error
Resubmit

同样，冲突解决机制的理想行为是：表中的每个空槽位都有相等的概率接收下一条插入的记录（假设表中每个槽位最初被哈希到的概率相等）。线性探测把元素聚集到一起的这种倾向称为 主聚集 。小聚集往往会合并成大聚集，使问题变得更糟。反对主聚集的理由是它会导致很长的探测序列。