为什么HashMap链表转红黑树的阈值是8

在JDK1.8中，HashMap引入了红黑树结构。当链表（不包括头结点）长度>=8，且数组长度> = 64时，会触发链表转红黑树的逻辑，以提升查询效率。那么为什么是8？又是怎么计算的？

结论

红黑树是一种特殊的平衡二叉树，其时间复杂度是O(log n)，链表的时间复杂度是O(n)。在n比较小时，二者差距不大，而转红黑树会额外消耗性能，因此阈值不应过小。
在哈希函数选择适当的情况下，链表长度超过8的概率不到千万分之一，因此阈值不应过大。
红黑树本身比普通节点要大，并且在增加或删除节点时需要通过自旋维持自身结构，所以在数组长度<64时，尽量先通过扩容拆分链表。

源码描述

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the requency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter f about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing ranularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million

翻译下：

因为树节点的大小是普通节点的两倍左右，所以只有当桶中的节点足够多的时候才使用它。当因为删除或扩容，导致桶中节点足够少的时候，又会将树节点转换回普通节点。在使用分布良好的哈希函数时，树节点是十分罕见的。理想情况下，哈希函数是随机的，此时桶中节点出现的个数遵循泊松分布。在默认扩容系数为0.75的情况下，泊松分布的参数平均是0.5。尽管因为粒度调整存在很大差异。忽略差异，列表大小k出现的期望是(exp(-0.5) * pow(0.5, k) /factorial(k))

泊松分布公式为

$P(X=k)=\frac{e^{-\lambda}{\lambda^k}}{k!}\qquad (k=0,1,2...)$

其中λ表示单位时间内事件发生的次数（可以理解为随机事件的概率），k表示随机事件发生的次数

代入λ=0.5，k=8

$P(X=k)=\frac{e^{-0.5}{0.5^8}}{8!}=0.00000006$

可见，hash函数离散良好的情况下，链表长度达到的8的概率不到千万分之一。所以正常不会转红黑树，红黑树只是极端情况下的兜底措施（比如重写了离散不好的hashCode方法）。

为什么要这么算

首先为什么是0.5？

记节点总数size=m，数组长度length=n。在扩容系数为0.75的情况下，size/length=m/n=0.75时会触发扩容。扩容后length=2n，此时size/length=m/2n=0.375。因此在扩容机制下，size/length始终在0.375~0.75之间。因此取中间值m/n=0.5。即map中平均有数组长度一半的节点数。

在hash函数足够离散的情况下，节点落在任意桶内可以看做一个随机事件，概率p=1/n。

因此，对于任意桶来说，节点有多少次落在该桶内，相当于连续执行m次随机事件，由于概率不变，因此符合二项分布。

下面公式表示进行m次试验，其中有k次成功的概率，单次成功的概率为p

$P_k=C_n^k(1-p)^{m-k}p^k \qquad (k=0,1,2...)$

代入m=n/2，p=1/n，上述公式可以改写成

$P_k=C_n^k(1-\frac{1}{n})^{\frac{n}{2}-k}(\frac{1}{n})^k \qquad (k=0,1,2...)$

分别取n=64,128,256，k=0,12,…计算，可得

	n=64	n=128	n=256
k=0	0.604	0.605	0.605
k=1	0.306	0.305	0.304
k=2	0.075	0.075	0.075
k=3	0.011	0.012	0.012
k=4	0.001	0.001	0.001
…	…	…	…

结果与源码中很接近。

又由于当二项分布n→∞, p→0时，可以近似推导为泊松公式。所以当数组很大时，就有了源码中的结果。

计算代码

Java实现的二项分布、泊松分布

public class PoissonTest {
    /**
     * 计算二项分布
     * 往length个盒子里投球，连续投times次，任意盒子中出现k个球的概率
     * @param length    盒子数
     * @param times     执行次数
     * @param k         执行成功的次数
     * @return          成功k次的概率
     */
    private double binomial(int length, int times, int k) {
        double p = (float) 1 / length;
        double pk = Math.pow(1 - p, times - k) * Math.pow(p, k) * factorial(times + 1 - k, times) / factorial(k);
        return pk;
    }


    /**
     * 返回n的阶乘
     */
    private int factorial(int n){
        return factorial(1, n);
    }

    /**
     * 返回从begin到end的阶乘
     * begin > end，返回1
     * begin = end，返回begin
     * begin < end，返回 begin * ... * end
     */
    private int factorial(int begin, int end){
        if (begin > end){
            return 1;
        } else if (begin == end){
            return begin;
        } else {
            for (int i = begin + 1; i <= end ; i++) {
                begin = begin * i;
            }
            return begin;
        }
    }


    /**
     * 计算泊松分布
     * @param lambda    随机事件成功的概率
     * @param k         随机事件发生的次数
     * @return          随机事件发生k次的概率
     */
    private double poisson(double lambda, int k) {
        double expect = (Math.exp(-lambda) * Math.pow(lambda, k)) / factorial(k);
        return expect;
    }
}

参考资料

泊松分布