Wafer's Note

Shenzhen is great!

0%

HashMap 的 loadFactor 为什么是 0.75

发表于
本文字数： 3.9k 阅读时长 ≈ 4 分钟

之前看各大面经的时候搜索到了这个问题，切实感觉到如果刨根问底的问，自己还真不能抵挡住这种攻势，现在闲暇时间又心血来潮地想起来这个问题，就打算好好弄懂弄透，也希望能在将来面试的时候做好准备。

本文基于这个 StackOverflow 回答进一步推导，并给出详细解答步骤

1. loadFactor 是什么

loadFactor 翻译为 负载因子，是 HashMap 负载程度的一个度量，所谓负载程度即 HashMap 持有的元素数量和 HashMap 大小的比值

当 HashMap 中的元素数量大于 capacity * loadFactor 时，HashMap 就要扩容，并进行重新 hash

那么，我们可以得出一个重要结论，loadFactor 是为了让 HashMap 尽可能 不满 而存在的

众所周知，HashMap 越空越好，这样插入和查找都能尽可能接近常数级别

那么接下来的一个重要问题就是：HashMap 什么时候是空的？通过这个问题，我们就可以一步一步推导出 loadFactor 的值

2. HashMap 什么时候不是很满

我们调整 loadFactor 的根本目标在于，要让元素的插入时间缩短到最少，也就是说，元素最好不要发生碰撞

只要元素在插入时不发生碰撞，那么我们的 HashMap 就不算特别的满

这是一个很重要的结论，通过它，我们成功地把 HashMap 满不满的问题，转换到了插入元素是否碰撞的问题

3. 插入元素的碰撞几率

插入元素是否碰撞，这是一个概率事件，有可能碰撞，也可能不碰撞

对于一个未知的元素，它有可能插入到 HashMap 的任何一个位置，因此，对于未知的元素插入，碰撞是等可能的，而一个元素是否碰撞和它之后的元素是否碰撞并无关系，因此是 独立的

为什么是独立的？因为 HashMap 采用拉链法解决碰撞，碰撞的元素不占用数组空间，因此一个元素是否碰撞和它前一个元素是否碰撞没有关系

在这里，我们要引入一个假设，上面我们提到的 HashMap 不是很满，但是 loadFactor 也不应该让一个 HashMap 过于空，太空的 HashMap 会造成空间的浪费；
假如一个元素的插入正好导致它碰撞，那么说明这个 HashMap 肯定不是特别空旷，而且当元素插入就碰撞时，恰好说明我们需要扩大 HashMap，而不是修改元素的 hash() 方法

因此，我们有单个元素插入碰撞的概率为

p=1sp = \frac{1}{s}

4. HashMap 在插入过程中不发生碰撞的概率

得到单个元素插入发生碰撞的概率之后，我们来考虑整个 HashMap 在插入过程中不发生碰撞的概率

对于一个 ss 大小的 Hashmap，我们插入 nn 个元素，这个操作属于等可能独立事件的重复操作，满足 二项分布，因此我们可以得出，在这个重复插入操作中，没有碰撞的概率为：

P(0)=Cn0×(1s)0×(1−1s)n−0=(1−1s)n\begin{aligned} P(0) & = C_n^0 \times (\frac{1}{s})^0 \times (1 - \frac{1}{s})^{n - 0} \\ & = (1 - \frac{1}{s})^n \end{aligned}

5. 什么叫“HashMap 很可能不满”

假如一个 HashMap，它在插入元素的过程中，如果它一次碰撞都没有发生，说明它没有满；

上面我们得到了这个事件的概率，如果这个事件发生的概率很大，那么就说明 HashMap 很可能不满

所以，若 P(0)≤0.5P(0) \le 0.5，则说明 HashMap 很可能没有满

则有

(1−1s)n≥12\begin{aligned} (1 - \frac{1}{s})^n \ge \frac{1}{2} \end{aligned}

其中 nn 代表 HashMap 中元素的个数，ss 代表 HashMap 的数组大小

6. loadFactor 的计算过程

HashMap 中 loadFactor 即为 n/sn/s，首先求出 nn，对于上面的式子取对数，则有

nln⁡(1−1s)≥−ln⁡2n≤−ln⁡2ln⁡(1−1s)n≤−ln⁡2ln⁡s−1sn≤ln⁡2ln⁡ss−1\begin{aligned} n\ln(1 - \frac{1}{s}) & \ge -\ln2 \\ n & \le \frac{-\ln2}{\ln(1 - \frac{1}{s})} \\ n & \le \frac{-\ln2}{\ln\frac{s-1}{s}} \\ n & \le \frac{\ln2}{\ln\frac{s}{s-1}} \end{aligned}

所以，当 n≤ln⁡2ln⁡2s2s−1n \le \frac{\ln2}{\ln\frac{2s}{2s-1}} 时，HashMap 很可能不满，所以

ns≤ln⁡2sln⁡ss−1\frac{n}{s} \le \frac{\ln2}{s\ln\frac{s}{s-1}}

当 s→∞s \to \infty 时，有

loadFactor=lim⁡s→∞ln⁡2sln⁡ss−1\begin{aligned} loadFactor & = \lim_{s \to \infty}\frac{\ln2}{s\ln\frac{s}{s-1}} \end{aligned}

对于分母的式子有

lim⁡s→∞sln⁡ss−1\begin{aligned} \lim_{s \to \infty}s\ln\frac{s}{s-1} \end{aligned}

从形式上来看，当 s→∞s \to \infty 时，2s2s−1→0\frac{2s}{2s-1} \to 0，则上式为 ∞⋅0\infty \cdot 0 型，应转换为 0∞\frac{0}{\infty} 或者 ∞0\frac{\infty}{0} 计算，对 ss 取倒数，有：
令 s=1ts = \frac{1}{t}：

lim⁡t→01tln⁡1t1t−1=lim⁡t→01tln⁡1t1−tt=lim⁡t→01tln⁡11−t=lim⁡t→0ln⁡11−tt⋯(⋆)\begin{aligned} & \lim_{t \to 0} \frac{1}{t} \ln\frac{\frac{1}{t}}{\frac{1}{t} - 1} \\ & = \lim_{t \to 0}\frac{1}{t} \ln\frac{\frac{1}{t}}{\frac{1-t}{t}} \\ & = \lim_{t \to 0} \frac{1}{t}\ln\frac{1}{1-t} \\ & = \lim_{t \to 0} \frac{\ln\frac{1}{1-t}}{t} \cdots (\star) \\ \end{aligned}

遇见 x→0x \to 0，就要想 等价无穷小，对于 ln⁡\ln 可以构造 ln⁡(1+x)∼x\ln(1 + x) \sim x，则有：

ln⁡11−t=ln⁡1−t+t1−t=ln⁡1+t1−t\begin{aligned} & \ln\frac{1}{1-t} \\ & = \ln\frac{1-t+t}{1-t} \\ & = \ln 1 + \frac{t}{1-t} \end{aligned}

则 (⋆)(\star)式则有

lim⁡t→0t1−tt=lim⁡t→011−t=1∴loadFactor=lim⁡s→∞ln⁡2sln⁡ss−1=lim⁡s→∞ln⁡21=ln⁡2∼0.693\begin{aligned} & \lim_{t \to 0} \frac{\frac{t}{1-t}}{t} \\ & = \lim_{t \to 0} \frac{1}{1-t} \\ & = 1 \\ \\ \therefore loadFactor & = \lim_{s \to \infty}\frac{\ln2}{s\ln\frac{s}{s-1}} \\ & = \lim_{s \to \infty} \frac{\ln2}{1} \\ & = \ln2 \\ & \sim 0.693 \end{aligned}

7. 为什么是 0.75

从上面的计算来看，loadFactor 取 ln⁡2\ln2 时，能够让 HashMap 尽可能不满

但是在实际中，HashMap 碰撞与否，其实是与 hashCode() 的设计有很大关系，因此 JDK 设计者在平衡空间利用和性能方面给了一个更高的经验数字。

8. 总结

当然，这只是一家之言，你也可以从其他方面解释 0.75 这个值如何如何；

其实这种刨根问底的问题，终究希望考察你的 能力 而不是 记忆，只要你能给出自己的解释，而不是被问住，呆若木鸡，就能通过面试。