今天打算继续Java回望系列，上文讲到HashMap在Java8中得到了提升，引入了红黑树，今天就来具体聊下。
红黑树的基本概念
基于二叉树，红黑树引入了”颜色”这一概念。对于每个节点，都有颜色，红黑树要满足如下4个规则：
- 节点颜色非黑即红
- 根节点总是黑色的
- 从根节点到任意一个叶子节点，都不允许有连续的两个红色节点
- 从根节点到任意一个叶子节点，黑色节点的高度都相同
当在节点发生插入/删除的时候，不满足以上任意一条规则时，就会发生红黑树的自我调整。主要通过以下三种方式：
- 改变节点颜色
- 右旋
- 左旋
引入红黑树的好处
之所以使用红黑树来实现HashMap，我想是因为在老的实现中，有一个问题不可避免，那就是：
如果继续使用拉链法，那么在发生hash冲突的时候，会将大量的entry都聚集在同一个链表上。这就导致了数据不平衡，那么在搜索时，搜索成本会提升。
反观红黑树，我们都知道它会在插入时进行旋转，来保证节点的平衡，从而能使搜索、插入、删除的时间复杂度维持在O(logN)。
hashMap中的红黑树
需要注意的是，Java8中，只有在某个节点链表长度大于8的时候，才会将链表转换为红黑树。
参考：