用动态数组实现哈希表出现异常非空指针内存问题求助

这种诡异的内存问题真的能把人折腾疯，我当初手写哈希表的时候也踩过几乎一模一样的坑，咱们一点点拆解可能的原因：

1. 动态数组初始化没做彻底 #

这是最常见的坑！你用动态数组存储链表指针的时候，要是用malloc分配内存，那数组里的每个元素都是内存里的随机垃圾值，根本不是NULL——遍历的时候自然会看到一堆“不该存在的非零指针”。

• 解决办法：把malloc换成calloc，它会自动把分配的内存全部初始化为0（也就是NULL），这样数组里除了你插入的索引位置，其他地方都会是干净的空指针。
• 对比代码：
  错误示范：

  struct Node** table = malloc(sizeof(struct Node*) * capacity);
  

  正确操作：

  struct Node** table = calloc(capacity, sizeof(struct Node*));
  

2. 哈希索引计算藏着溢出/越界问题 #

你说插入生成的索引是16，但有没有可能哈希函数返回的是负数，或者取模操作因为整数溢出导致索引乱跳？

• 比如在C语言里，负数取模的结果也是负数，用这个负数当数组索引会直接越界，运气不好的话可能会写到数组内的其他位置（比如内存布局刚好让越界地址落在数组范围内），导致出现莫名的非零指针。
• 快速检查：确保哈希函数返回无符号整数，或者在取模前把哈希值转成非负的，比如：

  unsigned int hash_val = hash(key);
  int index = hash_val % capacity;
  

3. 查询逻辑的误判导致奇怪结果 #

你查询不存在的键dumbtest返回0，大概率是因为查询逻辑没处理好那些未初始化的垃圾指针：

• 比如你的查询函数可能是先拿到索引，然后直接遍历链表，但那个索引位置的指针是垃圾值，指向了一块随机内存，刚好那块内存里的value是0，就误返回了。
• 修正方向：查询时先判断链表头指针是不是NULL，如果是直接返回一个明确的“不存在”标记（比如用-1，别用0，因为0可能是合法的value值）。

4. 内存越界写入的隐性问题 #

有没有可能插入操作的时候，除了写入索引16的位置，还因为其他代码错误（比如链表节点内存分配溢出、数组下标计算错误），不小心写到了数组的其他位置？

• 比如创建链表节点时，malloc的大小算错了，导致节点数据溢出，覆盖了数组里的其他元素指针。

快速验证步骤 #

1. 先把数组分配改成calloc，看看那些非零项是不是直接消失——如果消失了，那就是初始化的锅，直接解决。
2. 在插入前后分别遍历数组，打印每个元素的地址，对比变化，就能知道是不是插入操作不小心改了其他位置。
3. 手动计算一下dumbtest的哈希索引，看看是不是落在了那些非零指针的位置，排查哈希函数的问题。

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