Java哈希表平方探测中最长允许碰撞链的取值依据探究

首先要明确：教授提到的n=(m-1)/2（m为大质数）并非单纯的效率阈值，而是由平方探测的数学特性决定的正确性上限，核心和二次剩余的数论结论相关：

• 平方探测的探测序列是 h(k) + i² mod m（i=0,1,2,...），当m是形如4k+3的大质数时，数学上可证明：i² mod m的不同取值仅有(m+1)/2个（包含i=0时的0）。这意味着，平方探测最多只能覆盖哈希表中一半的槽位。
• 当碰撞链长度超过(m-1)/2时，探测序列会开始重复遍历已检查过的槽位，此时即使哈希表仍有空槽，平方探测也可能无法找到它，直接导致插入失败——这不是效率下降的问题，而是算法无法正常工作的问题。

至于“是否是唯一正确或最优”：

• 从正确性角度，这个值是严格的安全上限：超过它，平方探测的探测序列会进入循环，失去找到空槽的能力，所以必须在碰撞链长度达到这个值前扩容，或者换用其他探测方法（比如双重探测，它的探测序列能覆盖整个哈希表，无此限制）。
• 从工程实践的最优性角度，多数哈希表实现会在负载因子达到0.5左右时触发扩容，这和(m-1)/2对应的负载因子（当碰撞链长度接近这个值，表的负载因子也接近0.5）相呼应——因为负载因子超过0.5后，平方探测的冲突概率会急剧上升，查询和插入的时间复杂度会快速偏离O(1)。

这个结论的理论基础来自数论中的二次剩余定理，针对形如4k+3的质数，二次剩余的数量恰好是(m+1)/2，这直接决定了平方探测的覆盖范围。

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