系列文章目录
Java集合类源码分析（一）：Java集合类总览
Java集合类源码分析（二）：List接口之ArrayList实现类
Java集合类源码分析（三）：List接口之ArrayList实现类
Java集合类源码分析（四）：List接口之Vector实现类
Java集合类源码分析（五）：Map接口之HashMap实现类
Java集合类源码分析（六）：Map接口之HashTable实现类
Java集合类源码分析（七）：Map接口之LinkedHashMap实现类
Java集合类源码分析（八）：Map接口之TreeMap实现类
一、概念要点
TreeMap是基于红黑树实现的，红黑树是一种特殊的二叉排序树，关于二叉排序树及红黑树后续另写博文讲解。红黑树通过一些限制，使其不会出现二叉树排序树中极端的一边倒的情况，相对二叉排序树而言，这自然提高了查询的效率。
红黑树的基本概念提一下：
- 每个节点都只能是红色或者黑色
- 根节点是黑色
- 每个叶节点（NIL节点，空节点）是黑色的。
- 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
-
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
正是这些性质的限制，使得红黑树中任一节点到其子孙叶子节点的最长路径不会长于最短路径的2倍，因此它是一种接近平衡的二叉树。
二、TreeMap继承结构图
三、关键代码分析
1. 存储结构
TreeMap的排序是基于对key的排序实现的，它的每一个Entry代表红黑树的一个节点，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;
}
}
2.构造方法
/**
* 采用无参构造方法，不指定比较器，这时候，排序的实现要依赖key.compareTo()方法，
* 因此key必须实现Comparable接口，并覆写其中的compareTo方法
*/
public TreeMap() {
comparator = null;
}
/**
* 采用带比较器的构造方法，这时候，排序依赖该比较器，key可以不用实现Comparable接口。
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* 该构造方法同样不指定比较器，调用putAll方法将Map中的所有元素加入到TreeMap中
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
/**
* 首先将比较器指定为m的比较器，这取决于生成m时调用构造方法是否传入了指定的构造器，而后调用buildFromSorted方法，
* 将SortedMap中的元素插入到TreeMap中，由于SortedMap中的元素师有序的，实际上它是根据SortedMap创建的TreeMap，
* 将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) {
}
}
3.操作方法
/**
* 将map中的全部节点添加到TreeMap中
* 如果Map里的元素是排好序的，就调用buildFromSorted方法来拷贝Map中的元素，
* 而如果Map中的元素不是排好序的，就调用AbstractMap的putAll(map)方法，将Map中的元素一个个put（插入）到TreeMap中的，
* 主要因为Map中的元素是无序存放的，因此要一个个插入到红黑树中，使其有序存放，并满足红黑树的性质。
*/
public void putAll(Map<? extends K, ? extends V> map) {
// 获取map的大小
int mapSize = map.size();
// 如果TreeMap的大小是0,且map的大小不是0,且map是已排序的“key-value对”
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
// 如果TreeMap和map的比较器相等；
// 则将map的元素全部拷贝到TreeMap中，然后返回！
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
// 调用AbstractMap中的putAll();
// AbstractMap中的putAll()又会调用到TreeMap的put()
super.putAll(map);
}
final Entry<K,V> getEntry(Object key) {
// 判断比较器是否为空
if (comparator != null)
// 根据自定义的比较器来返回结果
return getEntryUsingComparator(key);
// 比较器为空
// key为空，抛出异常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// 取得K自身实现了比较接口
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
// 根据Comparable接口的compareTo函数来查找元素
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;
}
/**
* 插入操作即对应TreeMap的put方法，put操作实际上只需按照二叉排序树的插入步骤来操作即可，插入到指定位置后，再做调整，
* 使其保持红黑树的特性
*/
public V put(K key, V value) {
Entry<K,V> t = root;
// 若红黑树为空，则插入根节点
if (t == null) {
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
// 找出(key, value)在二叉排序树中的插入位置。
// 红黑树是以key来进行排序的，所以这里以key来进行查找。
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
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);
}
// 为（key-value）新建节点
Entry<K,V> e = new Entry<K,V>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 插入新的节点后，调用fixAfterInsertion调整红黑树。
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
/**
* 删除操作及对应TreeMap的deleteEntry方法，deleteEntry方法同样也只需按照二叉排序树的操作步骤实现即可，
* 删除指定节点后，再对树进行调整即可
*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
if (p.left != null && p.right != null) {
Entry<K,V> s = successor (p);
p.key = s.key;
p.value = s.value;
p = s;
}
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null;
} else {
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
四、TreeMap关注要点
- TreeMap是根据key进行排序的，它的排序和定位需要依赖比较器或覆写Comparable接口，也因此不需要key覆写hashCode方法和equals方法，就可以排除掉重复的key，而HashMap的key则需要通过覆写hashCode方法和equals方法来确保没有重复的key。
- TreeMap的查询、插入、删除效率均没有HashMap高，一般只有要对key排序时才使用TreeMap。
-
TreeMap的key不能为null，而HashMap的key可以为null。
参考：【Java集合源码剖析】TreeMap源码剖析
![LinkedList类注释翻译、源码分析[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)