线性探测哈希表两类数据集哈希碰撞数差异巨大的原因探究

1. 碰撞计数的定义：探测冲突而非哈希值冲突 #

你的代码中，collisionsAmount在每次进入while (hashElems[hashId] != nil)循环时递增，这统计的是线性探测过程中遇到已占用槽位的总次数，并非仅指两个元素哈希值相同的情况。只要元素的初始哈希槽被占用，或者探测路径上的槽被占用，都会被计入碰撞——这意味着哈希分布越不均匀，探测步数越多，碰撞数就越高。

2. MIT单词列表的哈希分布天生偏斜 #

Java String.hashCode()的计算方式是：hashCode = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]，对于自然语言单词：

• 单词由小写字母组成，开头字符（权重最高的部分）的频率分布极不均衡（比如s、t、a开头的单词占比远高于其他字母）；
• 单词长度集中在3-10位，31的幂次会让开头字符的差异主导哈希值的高位，但当你计算key % m时（尤其是m是2的幂，因为你的哈希表每次扩容翻倍），key%m等价于取哈希值的低log2(m)位——而自然语言单词的哈希值低几位的重复率远高于随机字符串；
• 大量单词的哈希值经过key%m后会集中在少数槽位，导致这些槽位及其相邻区域被快速填满。

3. 线性探测的聚集效应放大了碰撞 #

线性探测的特性是，当一个槽位被占用，后续冲突的元素会依次占用相邻槽位，形成聚集块。一旦聚集块形成，后续哈希值指向该块内任意槽位的元素，都需要探测整个聚集块的长度才能找到空槽——每一步探测都会被计入碰撞，最终导致碰撞数呈累积式增长，甚至达到百万级。

4. 随机整数字符串的哈希分布更均匀 #

随机整数转换的字符串，其内容是无规律的数字序列，对应的String.hashCode()分布几乎完全均匀：

• 数字字符的ASCII码分布均匀，且整数本身是随机生成的，因此哈希值的各个位都没有明显偏斜；
• key%m后，元素会均匀分散到所有槽位，线性探测的步数极少，因此碰撞数始终维持在低位。

验证建议 #

你可以做两个小实验验证上述结论：

• 统计两类数据集的key%m结果分布，看MIT单词是否集中在少数槽位；
• 修改碰撞计数逻辑，只在hashElems[hashId] != nil && hashElems[hashId].hashCode() == key时递增，对比真实哈希值冲突的次数——你会发现两类数据集的真实哈希冲突数差距远没有探测冲突数这么大。

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