simple uniform hashing assumption下哈希槽占用概率推导疑问

你计算的1 - ((n-1)/n)^m是「指定槽至少被1个键占用」的严格概率，和m/n不相等的核心原因是你看到的结论是简单均匀哈希假设下的简化表述/近似结果，两者对应不同的统计维度，本质不存在矛盾。 #

两者的差异来源 #

1. 严格概率的定义就是你计算的结果 #

简单均匀哈希（SUHA）的核心定义是：每个键独立、等概率哈希到n个槽的任意一个，不同键的哈希结果互不影响。按你定义的样本空间（所有m元哈希值组合），事件A（指定槽至少被占1次）的概率确实是：
P(A) = 1 - P(所有m个键都没落到指定槽) = 1 - ((n-1)/n)^m
这个计算是完全正确的。

2. m/n的实际含义 #

教材里提到的「指定槽被占用的概率为m/n」是两种场景下的简化表述：

• 小负载因子近似：当哈希表的负载因子α = m/n远小于1时，对严格概率做泰勒展开：
  1 - (1-1/n)^m ≈ 1 - (1 - m/n + o(m/n)) = m/n
  高阶小项可以忽略，因此可以近似认为指定槽被占用的概率约为m/n。
• 期望占用数的简化表述：大部分场景下这个结论其实是指「指定槽的期望键数为m/n」，用指示变量可以直接推导：
  • 定义指示变量X_i，第i个键落到指定槽时取1，否则取0，可得E[X_i] = 1/n
  • 指定槽的总键数X = X₁ + X₂ + … + Xₘ
  • 根据期望的线性性质，E[X] = ΣE[X_i] = m/n
    很多教材为了表述方便，直接把这个期望结果简化为「被占用的概率」，和你计算的事件概率不是同一个统计量。

验证实验设计 #

你可以按如下步骤做模拟实验验证两个结果：

• 固定槽数n、键数m，重复≥1e5次独立实验，每次实验随机生成m个独立的0~n-1的整数作为哈希值
• 统计维度1：指定槽至少有1个键的实验次数占总实验数的比例，结果会趋近于1 - ((n-1)/n)^m
• 统计维度2：每次实验指定槽的键数的平均值，结果会趋近于m/n

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