m槽链式哈希表插入3个键后形成长度3的链的概率求解

你的计算结果是对的，逻辑也没问题，换两种方式拆解验证更清晰：

• 分步概率法：

  • 第一个键可落在任意槽位，概率为1（无论选哪个槽，只要后两个键和它同槽即可）
  • 第二个键必须与第一个键哈希到同一槽位，概率为 1/m
  • 第三个键同样需与前两个键哈希到同一槽位，概率为 1/m
  • 总概率为 1 * 1/m * 1/m = 1/m²，也就是你推导的 m/m³（化简后等价）

• 组合计数法：

  • 简单均匀哈希下，3个键共有 m³ 种可能的哈希映射组合（每个键有m个槽位可选）
  • 满足三个键都落在同一槽位的组合有 m 种（每个槽位对应一种三个键都选它的情况）
  • 因此概率为 m/m³ = 1/m²，和分步计算结果一致

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