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

理想情况下使用随机的哈希码，容器中节点分布在hash桶中的频率遵循泊松分布，按照泊松分布的计算公式计算出了桶中元素个数和频率的对照表，可以看到链表中元素个数为8时的概率已经非常非常小，所以根据概率统计选择了8。        元素个数小于8，查询成本高，新增成本低。        元素个数大于8，查询成本低，新增成本高。 可以参考一下官方的文档

lg8=3。而链表平均查找n/2  链表在8平均查找4而红黑树评价3。

首先出结论：和hashcode碰撞次数的泊松分布有关，主要是为了寻找一种时间和空间的平衡。 红黑树中的TreeNode是链表中的Node所占空间的2倍，虽然红黑树的查找效率为o(logN)，要优于链表的o(N)，但是当链表长度比较小的时候，即使全部遍历，时间复杂度也不会太高。固，要寻找一种时间和空间的平衡，即在链表长度达到一个阈值之后再转换为红黑树。 之所以是8，是因为Java的源码贡献者在进行大量实验发现，hash碰撞发生8次的概率已经降低到了0.00000006，几乎为不可能事件，如果真的碰撞发生了8次，那么这个时候说明由于元素本身和hash函数的原因，此次操作的hash碰撞的可能性非常大了，后序可能还会继续发生hash碰撞。所以，这个时候，就应该将链表转换为红黑树了，也就是为什么链表转红黑树的阈值是8。 最后，红黑树转链表的阈值为6，主要是因为，如果也将该阈值设置于8，那么当hash碰撞在8时，会反生链表和红黑树的不停相互激荡转换，白白浪费资源。 over~打字好累。

二楼已经有标答了

同问，搜了一下说是基于概率统计，感觉这种说法有点玄

同问

画个完全二叉树就明白了

同问，之前面试被问到了😢一脸懵逼