为什么Map的桶中超过8个才转为红黑树

一、为什么要转换

• 每次遍历一个链表，平均查找的时间复杂度是 O(n)，n 是链表的长度
• 链表还不是很长，O(n) 和 O(log(n)) 的区别不大
• 如果链表越来越长，那么这种区别便会有所体现
• 为了提升查找性能，需要把链表转化为红黑树的形式

二、为什么要经历转换过程

• TreeNodes 需要占用的空间大约是普通 Nodes 的两倍
• 只有当包含足够多的 nodes 时才会转成 TreeNodes
• 是否足够多就是由 TREEIFY_THRESHOLD 的值决定的
• 当桶中节点数由于移除或者 resize 变少后，又会变回普通的链表的形式
• 默认链表长度达到8就转成红黑树，而当长度降到6就转换回去
• 如果 hashCode 分布良好 红黑树这种形式很少会被用到
• 当长度为 8 的时候 概率仅为 0.00000006，这是一个小于千万分之一的概率 通常我们的 Map 里是不会存储这么多的数据的
• 防止用户自己实现了不好的哈希算法时链表过长，导致查询效率低
• 转为红黑树是一种保底策略，用来保证极端情况下查询的效率
• 通常情况下并没有必要转为红黑树，所以就选择了概率非常小，也就是长度为 8 的概率
• 如果平时开发中发现 HashMap 或是 ConcurrentHashMap 内部出现了红黑树的结构 往往就说明我们的哈希算法出了问题