采用线性探测的哈希表无空项时会触发无限循环吗？

你提的这个问题戳中了线性探测哈希表实现里一个很容易忽略的细节——如果哈希表的所有条目都被完全占用，这段search代码确实会陷入无限循环。下面来拆解原因、你可能遗漏的要点，以及解决思路：

为什么会无限循环？ #

我们先拆解这段代码的逻辑：

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里没有任何NULL条目时，while(hashArray[hashIndex] != NULL)的条件永远为真。如果遍历了一圈都没找到目标key，代码会一直重复++hashIndex和取模操作，绕着数组循环，永远跳不出while循环。

为什么有人觉得这种情况“永远不会发生”？ #

这是因为规范的线性探测哈希表实现都会通过「负载因子控制+扩容」来避免表被完全填满：

• 负载因子 = 当前元素数量 / 哈希表容量（SIZE），行业里通常会把阈值设为0.7~0.8左右。
• 当元素数量接近这个阈值时，就会触发扩容（比如把SIZE翻倍，重新计算所有元素的哈希值并插入新表），确保哈希表永远不会被完全占满。

在这种正确的实现逻辑下，表全满的情况确实不会出现，所以这段代码的作者可能默认了“哈希表永远有空位”这个前提。

你可能遗漏的要点 #

1. 边界情况的防护缺失
   这段代码没有处理“表已满且目标key不存在”的极端场景，工程实现中必须补上这个防护。最简单的方式是记录起始哈希位置，当遍历回到起点时，说明整个表都查过了，直接退出循环返回NULL：

   struct DataItem *search(int key) { 
       int hashIndex = hashCode(key); 
       int startIndex = hashIndex; // 记录起始位置
       while(hashArray[hashIndex] != NULL) { 
           if(hashArray[hashIndex]->key == key) 
               return hashArray[hashIndex]; 
           ++hashIndex; 
           hashIndex %= SIZE; 
           // 绕回起点，说明遍历完整个表都没找到
           if(hashIndex == startIndex)
               break;
       } 
       return NULL; 
   }
   

2. 插入逻辑的配套约束
   即使search加了防护，插入操作也必须保证不会把表填到全满。比如插入时如果发现表已满（或者达到负载因子阈值），要么直接返回插入失败，要么触发扩容，不能强行插入导致表被完全占用。

总结 #

这段代码的问题在于它依赖“哈希表永远有空位”的理想假设，但实际工程中这个假设不成立。要么通过扩容机制从根源避免表满，要么在search函数中添加遍历次数的限制，防止无限循环。

内容的提问来源于stack exchange，提问作者deftextra