YSMull
<-- home

Java 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) = \binom{m}{k}p^k(1-p)^{m-k}\]

其中 $p = \frac{1}{n}$,这个分布列为二项分布,记为 $X\sim b(m,p)$,我们有 $E(X) = mp$
当 m 很大的时候,我们可以用泊松分布做近似,设 $\lambda = E(X)$,则

\[\binom{m}{k}p^k(1-p)^{m-k} \approx \frac{\lambda^k}{k!}e^{-\lambda}\]

有了以上结论,我们将情景换为 capacity 为 n 的 HashMap 往里面插入 n/2 个元素,假设 hash 是均匀分布的,设某个 bin 里元素的个数为 X,则

\[X\sim b(\frac{n}{2}, \frac{1}{n})\]

使用泊松分布近似,取$\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=7 的时候,概率已经小于百万分之一了。