YSMull

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

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

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


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


## 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;


$P(X=k) = \binom{m}{k}p^k(1-p)^{m-k}$

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

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

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