JDK8后,链表长度为什么到8的时候转红黑树

若桶中链表元素个数大于等于8时,链表转换成树结构;若桶中链表元素个数小于等于6时,树结构还原成链表。

理想情况下使用随机的哈希码,容器中节点分布在hash桶中的频率遵循泊松分布;
依照泊松分布计算出hash桶中元素个数与概率如下:
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

因此原因有2

  • 1.桶的长度超过8的概率非常非常小。所以作者是根据
    概率统计而选择了8作为阀值。
  • 2.之所以没有直接使用红黑树的结构,是因为红黑树的节点比链表节点大,占用空间更大,而且链表比较短的时候查询也足够快,因此没必要直接使用红黑树的结构。
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容