基于质数的二次探测函数仅在特定质数容量下遍历所有位置

你的测试结果差异完全对应两类质数的数学特性：4k+3型质数（3、7、11、23）和4k+1型质数（5、13、17），这和二次探测的序列覆盖性直接相关：

1. 平方剩余的数量限制 #

对于任意质数p，模p的平方剩余（即能表示为某个整数平方模p的数）共有(p+1)/2个（包含0）。比如：

• p=5（4k+1）：平方剩余为0、1、4，仅占总位置的3/5
• p=7（4k+3）：平方剩余为0、1、2、4，占总位置的4/7

2. 4k+3型质数的特殊性质 #

当p是4k+3型质数时，-1是模p的非二次剩余——这意味着如果x是二次剩余，那么-x一定不是二次剩余。因此如果你的hash_probe是双向二次探测（交替使用哈希值+i²和哈希值-i²计算探测索引），两个方向的序列不会重复，最终能覆盖全部(p+1)/2 + (p-1)/2 = p个位置。

而对于4k+1型质数，-1是模p的二次剩余，存在整数j使得j² ≡ -1 mod p，此时i² ≡ -(j*i)² mod p，导致双向探测的序列出现重复，无法覆盖所有位置。

你可能的理解误区 #

你可能误以为只要容量是质数，二次探测就一定能遍历所有位置，但实际上：

• 单方向二次探测（仅用哈希值+i²）无论质数类型，最多只能覆盖(p+1)/2个位置；
• 双向二次探测仅在4k+3型质数下才能遍历全部位置，4k+1型质数做不到。

验证示例 #

以p=5（4k+1）、初始哈希值0为例：
双向探测序列为：0→1→4→4（重复）→1（重复），仅能覆盖0、1、4三个位置，无法触及2、3。

以p=7（4k+3）、初始哈希值0为例：
双向探测序列为：0→1→6→4→2→5→3，正好遍历全部7个位置。

解决办法 #

如果需要二次探测覆盖整个哈希表，两种可行方案：

• 优先选择4k+3型质数作为容量，搭配双向二次探测逻辑；
• 改用双重哈希探测（(哈希值 + i*h2(k)) mod 容量），只要h2(k)与容量互质，就能遍历所有位置，对质数类型无限制。

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