YSMull
<-- home

谈谈 HashMap 实现中的若干数学问题

1. 为什么长度必须是 2 的倍数

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

答:因为某一个结点散列后的 index 是根据 hash & (len - 1) 计算得到的。如果 len 为 2 的整数倍,那么其二进制表示为:

len     : ...0001000...000
len - 1 : ...0000111...111

那么一定有 index = hash & (len - 1) <= len - 1,且如果 hash 是均匀分布的,那么 index 也是均匀分布的。

2. 为什么 TREEIFY_THRESHOLD 定为 8

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

其实源码开头的注释里提到了,但是解释的不是很清楚。这里我试着来讲一下原因,先给出一个问题:

有 n 个抽屉,随机的往这些抽屉丢 m 个苹果,问某一个抽屉有 k 个苹果的概率。

设 X 为某个抽屉里的苹果数,即 X 是一个 m 重伯努利实验成功的次数,X 的分布列为
P(X=k)=(mk)pk(1p)mkP(X=k) = \binom{m}{k}p^k(1-p)^{m-k}
其中 p=1np = \frac{1}{n},这个分布列为二项分布,记为 Xb(m,p)X\sim b(m,p),我们有 E(X)=mpE(X) = mp
当 m 很大的时候,我们可以用泊松分布做近似,设 λ=E(X)\lambda = E(X),则
(mk)pk(1p)mkλkk!eλ\binom{m}{k}p^k(1-p)^{m-k} \approx \frac{\lambda^k}{k!}e^{-\lambda}
有了以上结论,我们将情景换为 capacity 为 n 的 HashMap 往里面插入 n/2 个元素,假设 hash 是均匀分布的,设某个 bin 里元素的个数为 X,则
Xb(n2,1n)X\sim b(\frac{n}{2}, \frac{1}{n})
使用泊松分布近似,取λ=n2×1n=0.5\lambda = \frac{n}{2} \times \frac{1}{n} = 0.5,计算结果在源码的注释里已经给出:

k P(X=k)
0 0.60653066
1 0.30326533
2 0.07581633
3 0.01263606
4 0.00157952
6 0.00001316
7 0.00000094
8 0.00000006

可以发现,当 k=8 的时候,概率已经小于百万分之一了。