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

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

对话

回答这个问题前，先看一组对话。

我：请问HashMap中什么时候会出现红黑树？

小Z：当哈希冲突严重时，链表长度大于8

我：很好，那么什么时候会哈希冲突严重

小Z：当集合中节点足够多时

我：HashMap不是会自动扩容吗？当负载达到0.75时触发扩容，使负载降低到0.75/2=0.375，如此反复，因此负载会稳定在0.375-0.75之间。怎么会冲突严重呢？

小Z：这。。。如果有人攻击呢？使所有key落在一个槽位上？

我：的确，只有hash相同内容不同的key才能叠加到一个槽位上，这便是著名的HASH DOS攻击

因此，回答这个问题前，要先知道什么时候链表长度大于8？

源码描述

其实HashMap源码里，作者Doug Lea已经给出了说明

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的概率不到千万分之一。

计算过程

首先为什么λ=0.5？

记节点总数size=m，数组长度length=n。在扩容系数为0.75的情况下，size/length=m/n=0.75时会触发扩容。扩容后length=2n，此时size/length=m/2n=0.375。因此在扩容机制下，负载始终在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时，可以近似推导为泊松公式。所以当数组很大时，就有了源码中的结果。

结论

正常情况下，链表长度大于8的概率不到千万分之1，谁会使用这么大的集合？显然作者并不想使用红黑树。红黑树的作用仅仅是特殊情况下的兜底措施。

如：

令hashCode==1，这样所有节点都会落在同一个槽位，哈希表退化成链表。
令扩容阈值loadFactor=10，一个长度为n的数组，最多可以容纳n*10个节点，相当于一个槽位能分到10个，那必然会转红黑树了。
防HASH DOS攻击

因此下面这个回答本身没错，只是在HashMap1.8里实现不了。

红黑树是一种特殊的平衡二叉树，其时间复杂度是O(log n)，链表的时间复杂度是O(n)。在n比较小时，二者差距不大，而转红黑树会额外消耗性能，因此阈值不应过小。另外阈值过大，红黑树的存在就失去了意义。因此8是一个合适的临界值。

附录

HASH DOS攻击

hash dos攻击就是利用哈希表在哈希碰撞时产生的链表来攻击的方法，这种攻击会使哈希表退化成链表，使得系统运行巨慢。

具体操作是，批量产生大量hash相同内容不同的key，写入到哈希表中，这些key会落在同一个槽位，使得产生很长的链表。

一个可能的实现是利用String的hashCode方法，在Java中，String的hashCode方法可以表示为

$hash(s) = s[0]*31^{(n-1)} + s[1]*31^{(n-2)} + ... + s[n-1]$

是对字符数组中的每个元素乘以31的k次方再求和实现的，k只和数组长度和字符索引位有关。

如果能找到两个hash值相同的字符串s1和s2，那么在相同的位数时，对他们的任意排列组合，都会获得相同的哈希值。

Java中也确实存在这样的字符串，如

hash(Aa)=hash(BB)=2112

hash(AaAa)=hash(BBAa)=hash(BBBB)=hash(AaBB)=2031744

hash(AaAaAa)=hash(BBBBBB)=hash(BBAaBB)=hash(AaBBAa)=…=1952508096

当有n位时，就有2的n次方种组合

$2\times2\times...\times2=2^n$

那么想实现10万个key来攻击，只要n=17即可

$n=log_2100000=16.6$

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

对话

源码描述

计算过程

结论

附录

HASH DOS攻击

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

参考资料