为什么HashMap桶(链表)的长度超过8才会转换成红黑树

时间:2025-04-13 13:51:54
要想知道为什么设置为 8,那首先我们就要知道为什么要转换:
1.为什么要转换:
每次遍历一个链表,平均查找的时间复杂度是 O(n),n 是链表的长度。而红黑树可以把查询的时间复杂度始终控制在 O(log(n)) 。最初链表还不是很长,所以可能 O(n) 和 O(log(n)) 的区别不大,但是如果链表越来越长,那么这种区别便会有所体现。所以为了提升查找性能,需要把链表转化为红黑树的形式。
2.为什么要设为8:
解决这个问题前,我们还要知道一个点:转换为红黑树以后,TreeNodes的大小是常规Nodes的两倍。所以当链表长度比较小时,链表的查询效率还ok,并且占的空间还小,根本没必要转换为红黑树。但是当链表越来越长时,就不得不牺牲空间了转换为红黑树了,因为链表太长的话,查询效率实在是太低了,即便红黑树占空间是链表的两倍,为了查询效率,也只能这样了。
那为什么非得为8呢,链表长度为7,9,不行吗?
这个问题官方文档给出了回答:
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 frequency of nodes in bins follows a Poisson distribution (/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 里面是不会存储这么多的数据的,所以通常情况下,并不会发生从链表向红黑树的转换。
所以说如果一个桶里面的链表长度超过了8,那么很有可能是用户的哈希算法实现有问题。
链表长度超过 8 就转为红黑树的设计,更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长,从而导致查询效率低, 而此时转为红黑树更多的是一种保底策略,用来保证极端情况下查询的效率。