可扩展哈希溢出桶需回溯处理的概率计算问询

结论 #

每次桶溢出时，需要回溯处理的概率是 1/(2^N)，也可以写成你推测的2/(2^(N+1))形式，分母为2的N+1次方。

推导逻辑 #

可扩展哈希中，当桶容纳满N条记录后，插入新记录会导致溢出，此时会将该桶的哈希前缀长度加1，拆分为两个对应前缀末尾为0和1的新桶。只有当这N+1条记录（含导致溢出的新记录）的新增哈希位全为0或全为1时，所有记录会挤入同一个新桶，拆分无效，触发回溯。

假设哈希函数是均匀随机的，每个位取0/1的概率各为1/2且相互独立：

• N+1条记录全取0的概率为 (1/2)^(N+1)
• N+1条记录全取1的概率为 (1/2)^(N+1)
• 将两种情况的概率相加，得到总回溯概率：2*(1/2)^(N+1) = 1/(2^N)

关于你观察到的桶数规律 #

你提到的N=2、3、4对应桶数6、14、28，这是插入过程中累积的桶数量，和单次溢出的回溯概率没有直接线性关联。桶数增长是回溯、正常拆分、记录插入等多个环节共同作用的结果，属于特定插入阶段的统计值，不能直接用来推导概率公式。

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