Java HashMap中桶为空概率0.5的结论如何数学推导证明？

前提约定 #

所有推导基于Java官方文档定义的理想散列场景：

• key生成的hashCode经过HashMap内部高位异或扰动后，无碰撞聚集特性，任意key映射到任意桶的事件独立、概率均等
• 讨论范围覆盖HashMap两次扩容之间的完整运行周期，默认负载因子固定为0.75
• 桶数组长度足够大（生产环境中HashMap桶数通常从16起步，大流量场景下可达数千至数万，满足大样本统计要求）

分布建模过程 #

1. 基础二项分布模型
   对任意一个指定桶，单次key插入时落到该桶的概率为p = 1/m（m为当前桶数组总长度），落不到的概率为1-p。总共有n次独立插入时，桶内节点数k服从二项分布：
   $$P(X=k) = C_n^k p^k (1-p)^{n-k}$$
   二项分布的期望为$\lambda = n*p$。

2. 泊松近似适配
   根据泊松定理：当样本量n足够大、单次概率p足够小，且np乘积为稳定常数时，二项分布可以用参数为λ的泊松分布高精度近似，公式为：
   $$P(X=k) = \frac{e^{-\lambda} \lambda^k}{k!}$$
   HashMap的运行特征完全符合这个近似条件：桶数m足够大时p=1/m足够小，插入节点数n和m成正比，np为稳定值。

   这里官方文档提到λ平均约为0.5，是扩容的离散特性导致的：HashMap每次扩容会把桶数直接翻倍，刚完成扩容时节点总数n=0.75*(m/2)，此时λ=n/m=0.375；随着节点插入，到下次触发扩容时n=0.75m，λ=0.75。整个扩容周期内λ的平均值约为0.56，工程上取保守近似值0.5做概率边界计算，避免低估极端碰撞的概率。

空桶概率≈0.5的计算 #

泊松分布中，桶为空即k=0的概率可以直接代入公式计算：
$$P(X=0) = e^{-\lambda}$$

• 若取扩容临界态λ=0.75，计算得$P(X=0)≈e^{-0.75}≈0.47$，和0.5非常接近
• 若取全周期平均λ≈0.693（即ln2），计算得$P(X=0)=e^{-ln2}=0.5$，和工程上的简化结论完全吻合

补充说明 #

这个0.5的结论是理想场景下的工程近似，不是严格的精确数学值：

• 实际业务中的hashCode不可能做到完全随机独立，存在不同程度的碰撞聚集，真实空桶率会比理论值略低
• 官方用λ≈0.5的泊松分布做计算，核心目的是验证树化阈值的合理性：该参数下桶内节点数≥8的概率不足千万分之一，正常场景下几乎不会触发树化，只有哈希碰撞攻击等极端场景才会转红黑树保证查询性能。

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