哈希表中使用线性探测避免空条目？

Question

我在尝试理解和实现使用线性探测的哈希表。在寻找一种实现方式时，我发现了这段代码用于搜索方法：

struct DataItem *search(int key) {
   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] != NULL) {

      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];

      //go to next cell
      ++hashIndex;

      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;        
}

我不明白的是如果哈希数组中的所有条目都已被一个键占用，那么 while 循环不应该变成无限循环吗？还是这永远不会发生？我有所遗漏吗？

- deftextra

Answer 1

正如您所说，如果所有单元格已经填满并且表中不存在key，则此实现会陷入循环。以下是应该可以工作的实现:

struct DataItem *search(int key) {
   //get the hash 
   int initialHashIndex = hashCode(key) % SIZE;

   //move in array until an empty 
   int hashIndex = initialHashIndex;
   while(hashArray[hashIndex] != NULL) {    
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];

      //go to next cell
      ++hashIndex;

      //wrap around the table
      hashIndex %= SIZE;

      //check if all the items are checked
      if (hashIndex == initialHashIndex)
          break;
   }

   return NULL;        
}

然而，应该采取措施避免哈希表的装载因子超过一定阈值。记住，哈希表的主要目的是提供常数平均（摊销）操作时间，与存储在哈希表中的元素数量无关。因此，在线性探查哈希中，如果哈希表占用率高，搜索时间将成为存储元素的函数，这将破坏使用哈希的主要目标。

- Amir

---

考虑加上 %SIZE，使得 int initialHashIndex = hashCode(key)%SIZE;（哈希码计算通常与当前哈希表大小无关）成为可能。 - chux - Reinstate Monica

Answer 2

如果hashArray中的所有条目都被占用，那么这将是一个无限循环。这段代码假定hashArray永远不会完全被占用。

使用探测的哈希表应该具有一定比例的空闲插槽，否则它将退回到为许多元素进行探测，并且探测的长度可能会非常长。因此，确保数组永远不会完全被占用还有另一个原因。

假设代码除了hashArray和hashArray的大小之外，还维护一个包含元素数量的字段。这样，如果占用插槽的比例超过或低于某个分数，它可以重新调整hashArray的大小。

- Gilles 'SO- stop being evil'