6. 冲突解决¶

6.1. 冲突解决¶

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

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

Java
C++

   // 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\) 个偏移量。

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

Java
C++

   // 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