采用双重哈希解决冲突的哈希表合适大小的正确计算方法

你提到的表长取质数是双重哈希正常工作的核心前提——本质原因是双重哈希的探测序列公式为h(k,i) = (h1(k) + i * h2(k)) mod m，如果m不是质数，一旦h2(k)和m存在大于1的公约数，探测序列会提前进入循环，根本覆盖不到所有表槽，不是单纯为了减少冲突。具体容量计算按以下规则执行即可：

1. 初始容量计算：先按负载因子算下界，再匹配质数 #

双重哈希属于开放寻址法，负载因子α = 实际存储元素数n / 表长m，不同场景下α的硬阈值不同，先根据场景算出m的最小下界，再找大于等于这个下界的最小质数作为初始表长：

• 无删除操作的静态/低写入场景：α最大阈值取0.7，下界为ceil(n / 0.7)。这个阈值下平均探测长度不到2次，性能和链地址法相当。
• 有频繁删除（用墓碑标记处理删除）的场景：α最大阈值取0.5，下界为ceil(n / 0.5)。墓碑会占用探测路径抬升探测成本，必须留足冗余。
• 低延迟要求的实时场景：α最大阈值压到0.3~0.4，下界为ceil(n / 0.3)，保证最坏情况下探测长度不超过5次。

举个例子：你预估要存1000个元素、无删除操作，算出来下界是ceil(1000/0.7)=1429，往上找第一个质数是1433，初始表长取1433就符合要求。

2. 动态扩缩容的容量规则 #

如果是支持动态调整大小的哈希表，不要每次刚好卡阈值选质数，避免频繁扩缩容带来的性能抖动：

• 扩容触发：当实际负载达到对应场景的α阈值时，新表长取大于当前表长2倍的最小质数。比如当前表长是1433，触发扩容时2倍值为2866，往上找第一个质数是2879，直接取2879即可，不要选刚好卡n/0.7的更小质数。
• 缩容触发：当实际负载低于对应场景α阈值的1/4时，新表长取大于当前表长1/2的最小质数，避免缩容后短时间内又触发扩容。

3. 表长选取的配套校验规则 #

选好质数表长后，必须配合满足两个要求，不然选对质数也会出现异常：

• 第二哈希函数h2(k)的返回值必须和m互质。最稳妥的实现是让h2(k)的返回值范围落在[1, m-1]区间内——因为m是质数，这个区间内的所有整数都和m互质，能保证探测序列覆盖所有表槽，不会提前循环。
• 绝对不能让h2(k)返回0，否则探测序列会永远停在h1(k)对应的槽位，直接出现插入失败、查询死循环的问题。

4. 避坑提醒 #

不要为了省内存刻意选小于计算下界的质数，一旦负载超过阈值，探测长度会呈指数级上升，双重哈希的性能衰减比线性探测更明显。如果是不会扩容的固定容量哈希表，直接选大于下界的最小质数即可，不需要留2倍扩容冗余。

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