JDK 1.8 为什么让 HashMap 桶链表树化

JDK 1.7 及之前主要用链表解决哈希冲突；冲突集中时，链表会让查找从接近 $O(1)$ 退化到 $O(n)$ 。JDK 1.8 保留链表的低成本优势，同时在冲突严重时引入红黑树，通常改善查找成本。特殊 key 的 hash 完全相同且无法有效比较时，不能把所有查询都保证为 $O(\log n)$ 。

为什么阈值是 8#

在负载因子 0.75 的条件下，一个桶中出现 8 个以上元素的概率很低，因此 8 是在链表遍历成本与红黑树维护成本之间取得的折中。数组长度不足 64 时，HashMap 会优先扩容而不是立即树化。

为什么不全部使用红黑树#

红黑树节点占用更多内存，还需要维护平衡和旋转。元素较少时，链表遍历反而更简单，所以 HashMap 采用链表与红黑树的混合结构。扩容拆分后的树桶节点数不超过 6 时退化为链表；普通删除路径还会看树结构，不能统一说“删除到 6 就退化”。

ConcurrentHashMap 的差异#

JDK 1.8 的 ConcurrentHashMap 也使用红黑树，但树化过程需要并发控制：它通过 synchronized 锁住当前桶的头节点，并由 TreeBin 管理树根和读写状态。

对碰撞攻击的缓解#

攻击者可以构造大量 hashCode 相同的 key，使桶退化成超长链表。树化能降低查找退化的影响；服务端仍应限制请求参数数量，容器也应配置合理的参数上限。