哈希表平均填充率计算解析及扩容倍数对公式的影响

翻倍扩容时的公式推导逻辑 #

哈希表设定填充率达75%时触发翻倍扩容，这个平均填充率是两次扩容周期内的平均水平，推导逻辑如下：

1. 触发扩容时：哈希表当前容量为C，元素数量满足填充率75%，即元素数n = 0.75C。
2. 扩容完成后：容量变为2C，元素数量不变，此时填充率为n/(2C) = 0.75C/(2C) = 75%/2 = 37.5%。
3. 后续元素持续插入，直到填充率再次达到75%，这个周期内填充率是从37.5%线性增长到75%的。对于线性变化的数值，平均水平就是首尾值的平均值，因此平均填充率为：

   (75% + 37.5%)/2 = (75 + 75/2)/2 = 56.25% ≈ 56%
   

三倍扩容时的公式变化 #

如果改为三倍扩容，公式里的第一个2（扩容倍数）要替换为3，但第二个2（取首尾平均值的除数）保持不变：

1. 扩容完成后的初始填充率变为75%/3 = 25%。
2. 周期内填充率从25%线性增长到75%，平均填充率计算公式为：

   (75% + 25%)/2 = (75 + 75/3)/2 = 50%
   

本质是因为平均填充率始终是「扩容后初始填充率」和「触发扩容时填充率」的平均值，只有扩容倍数会影响前者的计算，取平均的逻辑不变。

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