HashMap什么情况下会转换成红黑树?

发布时间 2023-04-14 14:23:37作者: 18sui

HashMap 只有当链表中的元素个数大于8 (此时 node有9个),并且数组的长度大于等于64时才会将链表转为红黑树;

为什么是8,而不是7,不是9?

说到底还是因为性能,红黑树的查找速度很快,增删慢,链表的增删快,查找相对慢,但是链表长度没超过8的时候,

对查找的性能影响没那么大;超过8之后链表的查询速度就会比红黑树慢很多,就将链表转成红黑树,不过链表长度超过8的概率很小

HashMap源码如下

In usages with well-distributed user hashCodes, tree bins 
are rarely used.  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

上面这段话的意思是,如果 hashCode 分布良好,也就是 hash 计算的结果离散好的话,那么红黑树这种形式是很少会被用到的,

因为各个值都均匀分布,很少出现链表很长的情况。在理想情况下,链表长度符合泊松分布,各个长度的命中概率依次递减,

当长度为 8 的时候,概率仅为 0.00000006。这是一个小于千万分之一的概率,通常我们的 Map 里面是不会存储这么多的数据的,

所以通常情况下,并不会发生从链表向红黑树的转换。