TreeMap解读
TreeMap解读
引言：
- TreeMap基于红黑树实现，是有序的key-value集合
- TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法比如返回有序的key集合。
- TreeMap 实现了Cloneable接口，意味着它能被克隆。
- TreeMap 实现了java.io.Serializable接口，意味着它支持序列化。
- TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
- TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
- TreeMap非同步，即线程不安全，迭代器是fail-fast机制。
一、构造器以及方法
- 构造器
// 默认构造函数。使用该构造函数，TreeMap中的元素按照自然排序进行排列。
TreeMap()
// 创建的TreeMap包含Map
TreeMap(Map<? extends K, ? extends V> copyFrom)
// 指定Tree的比较器
TreeMap(Comparator<? super K> comparator)
// 创建的TreeMap包含copyFrom
TreeMap(SortedMap<K, ? extends V> copyFrom)
- 暴露方法
Entry<K, V> ceilingEntry(K key)
K ceilingKey(K key)
void clear()
Object clone()
Comparator<? super K> comparator()
boolean containsKey(Object key)
NavigableSet<K> descendingKeySet()
NavigableMap<K, V> descendingMap()
Set<Entry<K, V>> entrySet()
Entry<K, V> firstEntry()
K firstKey()
Entry<K, V> floorEntry(K key)
K floorKey(K key)
V get(Object key)
NavigableMap<K, V> headMap(K to, boolean inclusive)
SortedMap<K, V> headMap(K toExclusive)
Entry<K, V> higherEntry(K key)
K higherKey(K key)
boolean isEmpty()
Set<K> keySet()
Entry<K, V> lastEntry()
K lastKey()
Entry<K, V> lowerEntry(K key)
K lowerKey(K key)
NavigableSet<K> navigableKeySet()
Entry<K, V> pollFirstEntry()
Entry<K, V> pollLastEntry()
V put(K key, V value)
V remove(Object key)
int size()
SortedMap<K, V> subMap(K fromInclusive, K toExclusive)
NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive)
NavigableMap<K, V> tailMap(K from, boolean inclusive)
SortedMap<K, V> tailMap(K fromInclusive)
二、继承图
在代码上的体现为：
java.lang.Object
↳ java.util.AbstractMap<K, V>
↳ java.util.TreeMap<K, V>
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}
由上，得出：
- TreeMap实现继承于AbstractMap，并且实现了NavigableMap接口
- TreeMap的本质是R-B Tree(红黑树)，它包含几个重要的成员变量： root, size, comparator。
- root 是红黑数的根节点。它是Entry类型，Entry是红黑数的节点，它包含了红黑数的6个基本组成成分：key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)。Entry节点根据key进行排序，Entry节点包含的内容为value。 红黑数排序时，根据Entry中的key进行排序；Entry中的key比较大小是根据比较器comparator来进行判断的。size是红黑数中节点的个数。
红黑树的具体实现看我的下一期博文！
三、TreeMap内部结构
先罗列内部数据结构的概况：
- 核心：红黑树实现
- 完善：比较器、迭代器、排序方式等等
1、Entry
下面开始从源码解读TreeMap，首先是节点： Entry
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
//代替value
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
//key相同、value相同即为=
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
//根据key和value共同计算hashCode
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
小结：
- TreeMap内部的树节点是Entry，该类的成员有key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)，其中，颜色默认都是黑色（BLACK）。
- Entry其实就是红黑树节点。
2、基本操作与实现
① 红黑树操作
//左旋
private void rotateLeft(Entry<K,V> p) { ... }
//右旋
private void rotateRight(Entry<K,V> p) { ... }
//插入
public V put(K key, V value) { ... }
//插入修正，确保插入节点后该树还是红黑树
private void fixAfterInsertion(Entry<K,V> x) { ... }
//删除
private void deleteEntry(Entry<K,V> p) { ... }
//删除修正
private void fixAfterDeletion(Entry<K,V> x) { ... }
② 构造器底层实现
// 带Map的构造函数，Map会成为TreeMap的子集
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
// 带SortedMap的构造函数，SortedMap会成为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) {
}
}
// 默认构造函数
public TreeMap() {
comparator = null;
}
// 带比较器的构造函数
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
上面的构造器的实现并不难理解，其中通过Map去创建treeMap，则是将map中的元素全部添加到treeMap中去
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
//通过遍历添加
put(e.getKey(), e.getValue());
}
而通过有序的Sortedmap去构造TreeMap，则是调用 buildFromSorted,以下贴出源码：
// 根据已经一个排好序的map创建一个TreeMap
// 将map中的元素逐个添加到TreeMap中，并返回map的中间元素作为根节点。
//递归调用之后，返回一个middle节点作为treeMap的root节点
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
int redLevel,
Iterator it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
if (hi < lo) return null;
// 获取中间元素
int mid = (lo + hi) / 2;
Entry<K,V> left = null;
// 若lo小于mid，则递归调用获取(middel的)左孩子。
if (lo < mid) //mid -1
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal);
// 获取middle节点对应的key和value
K key;
V value;
if (it != null) {
if (defaultVal==null) {
Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
key = entry.getKey();
value = entry.getValue();
} else {
key = (K)it.next();
value = defaultVal;
}
} else { // use stream
key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
// 创建middle节点
Entry<K,V> middle = new Entry<K,V>(key, value, null);
// 若当前节点的深度=红色节点的深度，则将节点着色为红色。
if (level == redLevel)
middle.color = RED;
// 设置middle为left的父亲，left为middle的左孩子
if (left != null) {
middle.left = left;
left.parent = middle;
}
if (mid < hi) {
// 递归调用获取(middel的)右孩子。 //mid+1
Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
it, str, defaultVal);
// 设置middle为left的父亲，left为middle的左孩子
middle.right = right;
right.parent = middle;
}
return middle;
}
buildFromSorted的理解：
- buildFromSorted是通过递归将SortedMap中的元素逐个关联。
- buildFromSorted返回middle节点(中间节点)作为root。
- buildFromSorted**添加到红黑树中时，只将level == redLevel的节点设为红色。**第level级节点，实际上是buildFromSorted转换成红黑树后的最底端(假设根节点在最上方)的节点；只将红黑树最底端的阶段着色为红色，其余都是黑色。
③ 相关entry操作
TreeMap的 firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry() 原理都是类似的；下面以firstEntry()来进行详细说明
我们先看看firstEntry()和getFirstEntry()的代码：
public Map.Entry<K,V> firstEntry() {
return exportEntry(getFirstEntry());
}
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
这里我们有一个疑问？ firstEntry()与getFirstEntry()都是获取第一个节点，为什么要多此一举呢？
目的： 防止用户修改返回的entry，即返回的entry是不可修改的。
既然知道原因了，那么接下来我们就从源码中探索它是怎么实现的。
I.getFirstEntry()
final Entry<K,V> getFirstEntry()；
返回的是一个entry，我们可以调用entry内部的 getKey()、getValue()来获取key和value值，以及调用setValue()来修改value的值。
II. firstEntry()
firstEntry()返回的是exportEntry封装后的entry，我们看看是怎么封装的。
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
return e == null? null :
new AbstractMap.SimpleImmutableEntry<K,V>(e);
}
//SimpleImmutableEntry为AbstractMap的静态内部类
public static class SimpleImmutableEntry<K,V>
implements Entry<K,V>, java.io.Serializable
{
private static final long serialVersionUID = 7138329143949025153L;
private final K key;
private final V value;
public SimpleImmutableEntry(K key, V value) {
this.key = key;
this.value = value;
}
public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
//如果强行调用setValue则会抛出不支持的异常。
public V setValue(V value) {
throw new UnsupportedOperationException();
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
return eq(key, e.getKey()) && eq(value, e.getValue());
}
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
public String toString() {
return key + "=" + value;
}
}
根据上述源码，我们可以懂得：
- 通过AbstractMap的Sim…对entry节点进行封装，对外只暴露封装后的entry，只有getKey、getValue操作。
- 强行执行Set，则会抛出不支持的异常。
④ 相关key操作
在解读TreeMap中，我不按照解读HashMap或者List之类集合的方式，而是采用 方法名相关性进行解读，即XXKey(),XXEntry()等操作进行分类解读。好了，继续解读！
TreeMap的**firstKey()、lastKey()、lowerKey()、higherKey()、floorKey()、ceilingKey()**原理都是类似的；下面以ceilingKey()来进行详细说明
ceilingKey(K key)的作用是“返回大于/等于key的最小的键值对所对应的KEY，没有的话返回null”，它的代码如下：
public K ceilingKey(K key) {
return keyOrNull(getCeilingEntry(key));
}
static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
return e == null? null : e.key;
}
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
// 情况一：若“p的key” > key。
// 若 p 存在左孩子，则设 p=“p的左孩子”；
// 否则，返回p
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
// 情况二：若“p的key” < key。
} else if (cmp > 0) {
// 若 p 存在右孩子，则设 p=“p的右孩子”
if (p.right != null) {
p = p.right;
} else {
// 若 p 不存在右孩子，则找出 p 的后继节点，并返回
// 注意：这里返回的 “p的后继节点”有2种可能性：第一，null；第二，TreeMap中大于key的最小的节点。
// 理解这一点的核心是，getCeilingEntry是从root开始遍历的。
// 若getCeilingEntry能走到这一步，那么，它之前“已经遍历过的节点的key”都 > key。
// 能理解上面所说的，那么就很容易明白，为什么“p的后继节点”有2种可能性了。
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
// 情况三：若“p的key” = key。
} else
return p;
}
return null;
}
⑤ 相关Values操作
values() 返回**“TreeMap中值的集合”**，values()的实现代码如下：
public Collection<V> values() {
//封装成collection
Collection<V> vs = values;
return (vs != null) ? vs : (values = new Values());
}
// ”TreeMap的值的集合“对应的类，它集成于AbstractCollection
class Values extends AbstractCollection<V> {
// 返回迭代器
public Iterator<V> iterator() {
return new ValueIterator(getFirstEntry());
}
// 返回个数
public int size() {
return TreeMap.this.size();
}
// "TreeMap的值的集合"中是否包含"对象o"
public boolean contains(Object o) {
return TreeMap.this.containsValue(o);
}
// 删除"TreeMap的值的集合"中的"对象o"
public boolean remove(Object o) {
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
if (valEquals(e.getValue(), o)) {
deleteEntry(e);
return true;
}
}
return false;
}
// 清空删除"TreeMap的值的集合"
public void clear() {
TreeMap.this.clear();
}
}
小结：我们可以知道Values类就是一个集合。而 AbstractCollection 实现了除 size() 和 iterator() 之外的其它函数，因此只需要在Values类中实现这两个函数即可。这一部分内容可以类比我的上一篇解读hashMap的values、keySet，基本上的实现原理是一样的，都是采用内部类将key、value封装成集合并且返回。
⑥ 迭代器、entrySet等的操作
采用内部类将key、value封装成集合并且返回，而迭代器则是封装了treeMap的节点迭代遍历的实现，从而称为迭代器。这部分比较简单，如果想要深入了解这一部分操作的读者，可以参考我的博文中关于 hashMap的解读，其中有详细讲解。
⑦ NavigableSubMap与反向TreeMap（descendingMap）
*先讲作用：*它是一个抽象集合类，为2个子类——"(升序)AscendingSubMap"和"(降序)DescendingSubMap"而服务；因为NavigableSubMap实现了许多公共API。它的最终目的是实现下面的一系列函数：
headMap(K toKey, boolean inclusive)
headMap(K toKey)
subMap(K fromKey, K toKey)
subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
tailMap(K fromKey)
tailMap(K fromKey, boolean inclusive)
navigableKeySet()
descendingKeySet()
descendingMap：
descendingMap() 的作用是返回当前TreeMap的反向的TreeMap。所谓反向，就是排序顺序和原始的顺序相反。
我们已经知道TreeMap是一颗红黑树，而红黑树是有序的。TreeMap的排序方式是通过比较器，在创建TreeMap的时候，若指定了比较器，则使用该比较器；否则，就使用Java的默认比较器。而获取TreeMap的反向TreeMap的原理就是将比较器反向即可，即获取反向比较器。从而将整个treeMap反向排序。
四、总结
TreeMap的源码解读其实很好理解，只要抓住几个核心：
- TreeMap的重要核心是红黑树数据结构，基于红黑树的底层实现。
- TreeMap与HashMap的迭代器、键、值集的实现都是采用内部类的方法，其中迭代器也是封装了遍历过程
- TreeMap是有序的键值集合，通过comparator比较器实现顺序的比较，而比较器其实就是一个排序的规则而已，我们自己也可以实现比较器从而按照我们的规则排序treeMap。
- TreeMap的反向map的原理就是获取反向规则的比较器，再进行排序，得到反向规则下的treeMap。
最后补充说明，如果读者想要深入了解TreeMap的底层，建议关注我的博文——《红黑树解读与Java实现》