前面介绍过ConcurrentSkipListMap,支持排序(基于跳表)，线程安全的Map。现在介绍一种同样支持排序，但是非线程安全，使用更频繁的类-TreeMap。
红黑树
TreeMap支持排序的原理在于底层使用红黑树，本篇不详细手撕红黑树，简易的分析下原理。
下面基于《算法 4》定义的红黑树的特点，
- 根节点必为黑色；
- 节点分为红色或者黑色；
- 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
- 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
- 新加入到红黑树的节点为红色节点；
为保证每次操作之后，这些特性不变，需要维护该平衡，该算法的的核心操作如下:
下面就插入的几种情况画图分析：
-
变色：在不违反上述红黑树规则特点情况下，将红黑树某个 node 节点颜色由红变黑，或者由黑变红。
如果插入之后的父节点（10）和父节点同级的节点(20)都为红色，则将父级节点都变为黑的。父级节点的父级节点(19)变为红色，则以（19）节点为起点重新自平衡。
红黑树-插入-变色 - 如果插入节点为左节点，则进行右旋。 右旋：顺时针旋转两个节点，让一个节点被其左子节点取代，而该节点成为左子节点的右子节点。
红黑树-插入-右旋
3.如果插入节点为右节点，则先对父级节点进行左旋，再对祖父节点进行右旋。 左旋: 逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点。
红黑树-插入-左右旋
TreeMap 源码分析
一 、TreeMap 数据结构
先看下 TreeMap 的定义
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
- TreeMap 继承了 AbstractMap，所以它是一个 Map，即一个 key-value 集合。并且它是一个有序的，通过 红黑树（R-B tree) 实现
- TreeMap 实现了 NavigableMap 接口，意味着它一系列的导航定位以及导航操作的方法。
-
TreeMap 实现了 Cloneable 接口，可被克隆，实现了 Serializable 接口，可序列化。
再来看下 TreeMap 的主要成员
// 比较器 用于保存map的排序，为空时 使用key的自然顺序排序
private final Comparator<? super K> comparator;
// 红黑树的 根节点
private transient Entry<K,V> root;
// 红黑树中 节点个数 容器大小
private transient int size = 0;
// 红黑树 调整次数 快速失败(fail-fast) 关键
private transient int modCount = 0;
// 定义的红黑树的节点颜色-红色
private static final boolean RED = false;
// 定义的红黑树的节点颜色-黑色
private static final boolean BLACK = true;
Entry是个内部类
static final class Entry<K,V> implements Map.Entry<K,V> {
K key; // 当前节点的key
V value; // 当前节点的值
Entry<K,V> left; // 左子节点
Entry<K,V> right; // 右子节点
Entry<K,V> parent; // 父节点
boolean color = BLACK; // 颜色
下面画下类图和数据结构图
TreeMap 类图
[图片上传失败...(image-fd9ac7-1609665042157)].png)
二、TreeMap 构造方法
TreeMap 有4个构造方法
// 默认构造方法， 按照 key 的自然顺序排序
public TreeMap() {
comparator = null;
}
// 传入比较器的构造方法 按照该规则排序
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
//传入一个map对象创建TreeMap，按照key的自然顺序排序
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
// 遍历逐个插入
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
// 传入一个按照特定方式排好序了的map，创建一个新的TreeMap, 线性时间
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
三、 put插入方法
插入是map的核心方法，TreeMap 的插入也就是向红黑树里面插入， 大概分为两大步，1.插入新值，2.平衡红黑树。
先来看第一步 插入新值:
public V put(K key, V value) {
Entry<K,V> t = root;
// 如果跟节点为空 新建个节点 并赋值给root
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
// 插入新值的 父节点
Entry<K,V> parent;
// 区分比较器：是用自定义的 还是使用key自带的
Comparator<? super K> cpr = comparator;
if (cpr != null) {
// 使用二分法查找
do {
parent = t;
// 使用自定义比较器 进行对比遍历到的key和新key
cmp = cpr.compare(key, t.key);
// 对比结果小于0 说明往左子树继续查找
if (cmp < 0)
// 将当前节点置为 左子节点
t = t.left;
// 大于0 说明需要往右子树继续查找
else if (cmp > 0)
// 将当前节点置为 右子节点
t = t.right;
else
// 找到了 直接更新改节点的value
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
// 使用key的比较器 步骤同上
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 说明上面没有找到 得需要插入一个新值
Entry<K,V> e = new Entry<>(key, value, parent);
// 基于新值和父节点的对比 插入到左边还是右边
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 插入之后 以插入的节点 对红黑树进行自平衡 符合红黑树的规则
// 涉及到上面提到的 【变色】 【左旋】 【右旋】
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
大概步骤如下：
- 根节点为空，则构建一个节点做完跟节点,并返回。
- 以根节点为起点，使用二分搜索法，找到一样的则替换值，并返回。
- 未找到则在正确位置的叶子节点插入子节点。
- 然后进行调整。
下面看下插入之后，自平衡红黑树：
private void fixAfterInsertion(Entry<K,V> x) {
// 新节点 都是红色
x.color = RED;
//只有父级节点为红色时 才需要调整
while (x != null && x != root && x.parent.color == RED) {
// 如果父节点 是左节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
// 获取父节点的父节点的右子节点 如果也是红色 则执行变色操作
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
// 将父节点和叔父节点设置为黑色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
// 将祖父节点 设置为 红色
setColor(parentOf(parentOf(x)), RED);
// 将祖父节点置为当前节点 继续循环调整
x = parentOf(parentOf(x));
} else {
// 如果当前节点为右节点
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
// 先对父节点左旋
rotateLeft(x);
}
// 对祖父节点进行右旋
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
// 父节点 是右节点
} else {
// 父节点 和 叔父节点都是 红色 变色操作
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
// 如果是当前节点是左节点 现在对父节点 进行右旋转
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
// 对祖父节点 进行左旋
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
// 跟节点 黑色
root.color = BLACK;
}
就是根据父节点，叔父节点，祖父节点的位置和颜色，然后变色，左旋，右旋操作。
四、 get方法
获取方法就跟二叉搜索树一样，二分法查找。
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
// 使用自定义的比较器 查找
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
// 使用默认的比较器 查找
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
// 从root开始遍历查找
Entry<K,V> p = root;
// 典型的二分查找
// 小: 则继续往左边找
// 大：则继续往右边找
// 相等： 返回
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
// 使用自定义的 比较器 也是使用而二分查找法
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
五、TreeMap的遍历
TreeMap提供多种遍历方法:map.values(), map.keySet()，map.entrySet()，map.forEach(),都挺简单的遍历，特别的是还提供逆序/方向遍历，刚兴趣的同学可以去了解下。
总结
本文简单介绍了TreeMap基本特点和几个方法，没有说到删除方法，很多情况需要考虑，打算放到算法分析红黑树的时候再细讲。有错误或者不清楚的地方还请评论指出。
量变引发质变，经常进步一点点，期待蜕变的自己。
