使用线性探测的散列 table 中没有空条目？

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;        
}

我不明白的是，如果hashArray中的所有条目都已被一个键占用，那么while循环不应该变成无限循环吗？或者这永远不会发生？有什么我想念的吗？

Answer 1

确实，如果hashArray中的所有条目都被占用，这就是死循环。此代码假定 hashArray 永远不会被完全占用。

使用探测的哈希 table 应该有一些最小比例的空闲槽，否则它会回退到探测许多元素并且探测的长度可能会很长。所以还有一个原因要保证数组永远不会被占满

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

Answer 2

如您所说，如果所有单元格都已满且 key 不存在于 table 中，此实现将陷入循环。这是应该起作用的实现：

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;        
}

但是，应该实施策略来避免让散列 table 的占用水平超过特定阈值。请记住，散列 table 的主要目的是 提供恒定的平均（摊销）操作时间 ，与存储在散列中的元素数量无关。因此，如果哈希table在线性探测哈希中的占用率很高，则搜索时间将是存储元素的函数，这就破坏了使用哈希的主要目标。

使用线性探测的散列 table 中没有空条目？

No empty entries in hash table using linear probing?

c

hashtable

data-structures