内容来自《收割Offer:互联网大厂面经》

一方面红黑树的查找效率为 O(logn)，优于链表的 O(n)，另一方面红黑树占用的内存空间大于链表，同时当键值对数量较少时链表的遍历查询与红黑树的搜索效率差异不大。综合空间和时间的考量，哈希冲突元素的个数达到某个阈值时红黑树和链表数据结构才会互相转化。HashMap 的源码如下：

    Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (<http://en.wikipedia.org/wiki/Poisson_distribution>) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. 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 的泊松分布，即

由此可知，链表长度为8的概率为0.00000006，此时树化。一方面遍历长度小于8的链表的时间效率尚可接受；另一方面每个桶的树化概很小，节约了内存空间。红黑树退化为链表的阈值为 6，中间留有空间，可以防止链表和红黑树之间的频繁转换。

泊松分布（poisson distribution）是一种离散型概率分布，通常用于描述一个固定时间内事件发生次数的概率分布，如在一个小时内某个网站访问此时、一天内某个交通路口的车辆通过次数等。