链表退化至o(n)时get()性能骤降，jdk 1.8通过链表长度≥8且数组容量≥64才转红黑树来优化；红黑树兼顾效率与稳定性，但要求key实现comparable或传入comparator，否则树化失败。
链表退化到 O(n) 时，get() 就真的变慢了
当多个 key 的哈希值撞到同一个桶（bucket），JDK 1.7 和早期 1.8 都会用链表串起来。如果这个链表长度达到 1000，get() 就得从头比对，最坏要遍历 1000 次 —— 这不是理论风险，是真实可复现的性能断崖。
- 典型诱因：自定义
hashCode()返回固定值（比如return 1;），或被恶意构造哈希碰撞攻击 - 现象：压测时 CPU 飙高、响应延迟突增，但
HashMap大小看起来正常，容易误判为 GC 或锁竞争问题 - JDK 1.8 的应对：链表长度 ≥
TREEIFY_THRESHOLD（默认 8）且数组容量 ≥MIN_TREEIFY_CAPACITY（默认 64）时，才转红黑树 —— 两个条件缺一不可，避免小表过早树化
为什么选红黑树，而不是 AVL 或跳表
红黑树不是“最平衡”的树，但它是“够快又够稳”的务实选择。AVL 树旋转更频繁，插入/删除开销大；跳表在 Java 标准库中无原生支持，且内存局部性差。
- 红黑树查找、插入、删除最坏都是
O(log n)，链表是O(n)；n=1000 时，log₂1000 ≈ 10，性能差距接近百倍 - 它允许一定程度的不平衡（黑高相等即可），所以旋转次数比 AVL 少，更适合写少读多的哈希表场景
- Java 中
TreeMap也是红黑树实现，复用成熟逻辑，减少维护成本
树化和退化的阈值不是拍脑袋定的
阈值设为 8 和 6，背后有泊松分布建模支撑：正常哈希分布下，链表长度 ≥ 8 的概率已低于千万分之一。这意味着绝大多数桶根本不会触发树化。
- 树化条件：
binCount >= TREEIFY_THRESHOLD(8)且tab.length >= MIN_TREEIFY_CAPACITY(64) - 退化条件：红黑树节点数 ≤
UNTREEIFY_THRESHOLD(6)，扩容时也会检查并可能退化 - 注意：不是“长度到 8 就立刻树化”，而是插入第 8 个元素后，在
treeifyBin()中判断容量再决定；容量不够就先扩容，不树化
别忽略红黑树对 key 的隐含要求
红黑树内部靠 compareTo() 或 compare() 排序，而 HashMap 的 get() 在树中查找时，既要看哈希值，也要能比较 key 大小 —— 这意味着：如果 key 没实现 Comparable，又没传 Comparator，树化会失败，回退为链表。
- 常见错误：用自定义类作 key，只重写了
hashCode()和equals()，但没实现Comparable - 现象：链表明明超长，却始终没变成红黑树，
node instanceof TreeNode始终为 false - 解决：要么让 key 实现
Comparable，要么初始化HashMap时传入Comparator（极少用，慎用）
O(n) 拉到 O(log n)，但代价是每个节点多存颜色位、结构更复杂、小数据量时反而不如链表轻量 —— 所以 JDK 设计者死守 8/6 这组阈值，不多不少。真正要注意的，其实是你的 hashCode() 是否均匀，以及 key 类型是否满足树化前提。 
