Java HashMap为什么在jdk8引入红黑树#

在JDK8之前，HashMap的内部实现主要依赖于数组+链表的结构 当多个元素的哈希值相同的时候（也就是发生哈希冲突的时候），这些元素会被存储在同一个桶里面，形成一个链表。 但这种实现方式在特定情况下会导致性能问题。

JDK8之前的问题#

1. 时间复杂度退化： 在最坏情况下（大量元素哈希到同一个桶），查找，插入和删除操作的时间复杂度会从理想的O(1)退化为O(n)，其中n是链表的长度
2. 哈希冲突攻击： 恶意攻击者可以构造大量哈希冲突的数据，使得HashMap的性能急剧下降，导致潜在的拒接服务攻击。

红黑树的引入#

JDK8对HashMap进行了优化，引入了红黑树来解决上面的问题：

• 性能提升： 当一个桶中的元素数量超过一定阈值的时候，链表会被转换成红黑树。红黑树是一种自平衡的二叉搜索树，即使在最坏的情况下，它查找，插入和删除操作的时间复杂度也能保持在O（logn)，大大提高了性能。

• 阈值机制：

  • 当桶中元素超过8个的时候，链表转换为红黑树
  • 当桶中元素少于6个的时候，红黑树会退化回链表

• 安全性增强： 通过引入红黑树，即使面对哈希冲突的攻击，HashMap也能保持相对稳定的性能，提高系统安全性

为什么选择红黑树#

平衡性： 红黑树是一种近似平衡的二叉搜索树，能保证最坏情况下的O(logn)的性能。

内存占用： 相比AVL树等其它平衡树，红黑树的平衡条件较为宽松，旋转操作更少，内存占用更小。

实现更好的复杂度与性能平衡