谈谈 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 = \frac{1}{n}$，这个分布列为二项分布，记为 $X\sim b(m,p)$，我们有 $E(X) = mp$
当 m 很大的时候，我们可以用泊松分布做近似，设 $\lambda = E(X)$，则

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

使用泊松分布近似，取$\lambda = \frac{n}{2} \times \frac{1}{n} = 0.5$，计算结果在源码的注释里已经给出:

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