C语言哈希表search函数是否存在越界及搜索不存在值时死循环问题

你的担忧是完全合理的，我们分别对应你的两个疑问逐一分析：

1. 是否会出现无限循环？ #

是的，当哈希表被完全填满（数组中没有NULL元素，所有位置要么存有效数据，要么存删除标记的dummy项）时，搜索不存在的key必然会进入无限循环。
原因很简单：while的退出条件是遇到hashArray[hashIndex] == NULL，如果整个数组都没有NULL值，这个条件永远无法触发，代码会一直循环遍历整个数组，永远不会返回。
你可以自己做个测试：往SIZE=20的表里插满20个不同的key，再搜索一个不存在的key，程序会直接卡住。

2. 是否存在非法内存访问/缓冲区越界？ #

这部分没有问题。
代码里每次++hashIndex之后都会执行hashIndex %= SIZE，这会保证hashIndex的取值永远在[0, SIZE-1]的合法下标范围内，访问hashArray[hashIndex]不会出现越界。

隐藏的额外问题 #

这个实现用了dummyItem作为删除标记（软删除），key设为-1，存在一个小缺陷：如果业务中存在合法的key=-1的数据，会和删除标记冲突，导致搜索异常。另外如果全表都是有效数据+删除标记、没有NULL值，还是会触发前面说的无限循环问题。

修复方案 #

• 给搜索、删除的循环加遍历次数限制，最多遍历SIZE次就退出，避免无限循环：

struct DataItem *search(int key) {
   int hashIndex = hashCode(key);  
   int cnt = 0;
   while(hashArray[hashIndex] != NULL && cnt < SIZE) {
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex]; 
      ++hashIndex;
      hashIndex %= SIZE;
      cnt++;
   }        
   return NULL;        
}

• 控制哈希表的负载因子，比如当填充率超过70%时就对数组进行扩容，永远保留一定的NULL空位，从根源上避免无限循环的触发条件。
• 如果允许业务使用key=-1，可以把删除标记的标识改到结构体其他字段，避免和业务key冲突。

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