[toc]
java中还有一个有序的Map是TreeMap，虽然相对于HashMap，其出镜率并不高，但是我们在某些场景下也会用到，另外这个TreeMap完全是基于红黑树的一种实现，分析其源码有利于对红黑树概念的理解。
1.类结构及其成员变量
1.1 类结构
TreeMap的类继承结构如下图：
image.png
可以看到，TreeMap继承了AbstractMap，此外实现了NavigableMap、Cloneable和Serializable接口。而NavigableMap接口又继承了SortedMap。这与ConcurrentSkipListMap的情况类似，因而也是有序的。
/**
* A Red-Black tree based {@link NavigableMap} implementation.
* The map is sorted according to the {@linkplain Comparable natural
* ordering} of its keys, or by a {@link Comparator} provided at map
* creation time, depending on which constructor is used.
*
* <p>This implementation provides guaranteed log(n) time cost for the
* {@code containsKey}, {@code get}, {@code put} and {@code remove}
* operations. Algorithms are adaptations of those in Cormen, Leiserson, and
* Rivest's <em>Introduction to Algorithms</em>.
*
* <p>Note that the ordering maintained by a tree map, like any sorted map, and
* whether or not an explicit comparator is provided, must be <em>consistent
* with {@code equals}</em> if this sorted map is to correctly implement the
* {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
* precise definition of <em>consistent with equals</em>.) This is so because
* the {@code Map} interface is defined in terms of the {@code equals}
* operation, but a sorted map performs all key comparisons using its {@code
* compareTo} (or {@code compare}) method, so two keys that are deemed equal by
* this method are, from the standpoint of the sorted map, equal. The behavior
* of a sorted map <em>is</em> well-defined even if its ordering is
* inconsistent with {@code equals}; it just fails to obey the general contract
* of the {@code Map} interface.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access a map concurrently, and at least one of the
* threads modifies the map structurally, it <em>must</em> be synchronized
* externally. (A structural modification is any operation that adds or
* deletes one or more mappings; merely changing the value associated
* with an existing key is not a structural modification.) This is
* typically accomplished by synchronizing on some object that naturally
* encapsulates the map.
* If no such object exists, the map should be "wrapped" using the
* {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the map: <pre>
* SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
*
* <p>The iterators returned by the {@code iterator} method of the collections
* returned by all of this class's "collection view methods" are
* <em>fail-fast</em>: if the map is structurally modified at any time after
* the iterator is created, in any way except through the iterator's own
* {@code remove} method, the iterator will throw a {@link
* ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
* arbitrary, non-deterministic behavior at an undetermined time in the future.
*
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw {@code ConcurrentModificationException} on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <em>the fail-fast behavior of iterators
* should be used only to detect bugs.</em>
*
* <p>All {@code Map.Entry} pairs returned by methods in this class
* and its views represent snapshots of mappings at the time they were
* produced. They do <strong>not</strong> support the {@code Entry.setValue}
* method. (Note however that it is possible to change mappings in the
* associated map using {@code put}.)
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
*
* @author Josh Bloch and Doug Lea
* @see Map
* @see HashMap
* @see Hashtable
* @see Comparable
* @see Comparator
* @see Collection
* @since 1.2
*/
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
}
其注释大意为：
TreeMap是一个基于红黑树的NavigableMap实现，可以根据Comparable实现自然排序，或者Comparator排序，至于根据哪个排序取决于构造函数。
这个实现对containsKey、get、put、remove提供了恒定的时间复杂度log(n)。这个算法是对Cormen、Leiserson和Rivest算法的改进。
请注意，TreeMap与任何排序的map一样，维护的顺序，以及是否提供显示比较必须与equals方法一致，以便排序的map能够正确实现。之所以这样，是因为map接口是根据equals的操作定义的，但是排序之后的map使用compareTo或者compare方法执行比较，因此从排序map的角度来看，此方法认为相等的两个key是相等的。排序后的map的行为是明确定义的，即使其排序与equals不一致，它也只是无法遵守map的一般约定。
需要注意的是，这个实现是非同步的。如果多线程并发访问，最后一个线程修改了这个map的结构，它必须在外部进行同步。结构的修改是指添加或者删除一个或者多个映射。使用key进行更新不是属于结构修改。这是通常通过封装TreeMap对象来实现。
如果这个对象不存在，那么应该使用Collections.synchronizedSortedMap方法。最好是在创建的时候完成，以防止不同步的访问。如下：
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
这个类的所有集合视图方法返回的集合的iterator的迭代器都是fail-fast的。如果在迭代器被映射之后的任何时间对结构进行修改，除非通过迭代器自己的remove方法，否则将抛出ConcurrentModificationException，因此，面对并发修改，迭代器将快速失败，而不是冒着未来不确定的时间产生任意不确定的风险。
注意，迭代器的fail-fast并不是一个担保的行为，因为通常来说，存在不同步修改的并发修改的情况下，不可能做出任何严格的保证，快速失败的迭代器将会最大努力的抛出ConcurrentModificationException。因此，编写任何依赖于此异常的程序代码以确保其正确性都是错误的。迭代器的快速失败机制仅仅用于检测错误。
此类中的方法返回的所有Entry对其视图均表示生成map的快照，他们不支持Entry.setValue方法，不过请注意，可以使用put更改关联map中的映射。
另外，TreeMap还是java集合框架的成员。
1.2 成员变量
由于TreeMap并不涉及线程安全和扩容，因此成员变量非常简单：
/**
* The comparator used to maintain order in this tree map, or
* null if it uses the natural ordering of its keys.
*
* @serial
*/
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
/**
* The number of entries in the tree
*/
private transient int size = 0;
/**
* The number of structural modifications to the tree.
*/
private transient int modCount = 0;
comparator 是用于进行比较的比较器。root指向根节点，由于红黑树是一个树形结构，因此不再需要数组之类的结构来存储。size用于存放tree中元素的长度。modCount则是在fail-fast机制所依赖的。
2. 核心内部类Entry
TreeMap是基于红黑树的数据结构，TreeMap实现了Map.Entry接口。具有key、value、left、right、parent等属性。
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;
}
/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
* called
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
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());
}
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;
}
}
这个类的结构也非常简单，需要注意的是，其hashCode方法，实际上是keyHash ^ valueHash。虽然key和value都不支持为空，但是还做了特殊处理。
3.基本原理之红黑树
在要搞懂红黑树之前，我们需要先弄清楚，二叉搜索树（Binary Search Tree）和平衡二叉树（AVL树）是什么，之后再来理解红黑树(RB树)。
3.1 二叉搜索树（Binary Search Tree）
定义：它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
二叉搜索树的概念看起来复杂，实际上非常简单，要求就一个，任意节点，其值大于左节点，小于右节点。
如下就是一个二叉搜索树：
二叉搜索树
如果这个二叉搜索树比较平衡的话，其查找的时间复杂度为(log n)。
但是需要注意的是，二叉搜索树如果使用不当非常容易退化为链表，导致时间复杂度退化为n。为了解决这个问题，就出现了平衡二叉树（AVL树）。
3.2 平衡二叉树（AVL Tree）
平衡二叉树实际上是二叉搜索树的一种特殊情况。但是其带有平衡条件。要求每个节点的左右子树的高度绝对值最多为1（平衡因子）。
平衡二叉树通过一系列平衡操作，左旋、右旋等，来保证了平衡二叉树的平衡性。
平衡二叉树
这样就将查询的时间复杂度恒定在(log n)。但是代价就是在插入和删除的时候会带来非常高的时间消耗。将插入和删除的时间复杂度都变成了(log n)。
3.3 红黑树
红黑树是平衡二叉树的一个变种，其也是在二叉搜索树上进化而来，但是其转置是根据红黑标记而来。而不是像平衡二叉树那样做统一的要求。其平衡性相对平衡二叉树要低。颜色规则为：
- 1.任意节点的颜色要么黑色，要么红色。
- 2.根节点是黑色。
- 3.如果一个节点为红色，其子节点一定是黑色。（不能允许有两个连续向连的红色节点）
-
4.任意节点到其下面的空节点，（空接点为黑色）。的路径上，黑色节点的数量相同。
通过从根节点到空节点的任意路径进行颜色约束，红黑树可以确保没用一条路径比其他路径的长度多出2倍。因此红黑树是一个近似平衡的树。（节点的平衡因子不能大于1）
红黑树
红黑树是一个近似平衡的二叉树。也是采用旋转的方式来实现。但是由于其的近似特性，不用旋转到AVL树那种完全平衡的二叉树。AVL树一定是保证左边节点都是满的，如果存在不满的情况一定会出现在右侧。因此AVL树要保证平衡性，旋转的过程会更加复杂，耗时会更长。
实际上这也是大多数集合框架底层采用红黑树的原因。其插入和删除的效率高于AVL数，但是检索效率不会低多少。
4.构造函数
4.1 TreeMap()
支持空的构造函数：
public TreeMap() {
comparator = null;
}
4.2 TreeMap(Comparator<? super K> comparator)
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
此方法只是传入了一个比较器。
4.3 TreeMap(Map<? extends K, ? extends V> m)
从其他map中put
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
内部通过putAll方法实现。
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
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;
}
}
super.putAll(map);
}
如果为SortedMap的子类，则通过Sorted的方法实现。buildFromSorted。反之则通过父类的方法，遍历之后再插入。
4.4 TreeMap(SortedMap<K, ? extends V> m)
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) {
}
}
通过buildFromSorted 实现sorted的插入。
5.重要方法
下面对TreeMap的一些重要方法的源码进行分析：
5.1 get
get方法：
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
实际上调用的是getEntry方法 ：
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
//如果比较器为空
if (comparator != null)
return getEntryUsingComparator(key);
//如果key为空 则返回NPE异常 key不支持为空
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
//key是可比较的
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
//如果不为空则根据比较结果左右遍历
while (p != null) {
int cmp = k.compareTo(p.key);
//小于0则左树遍历
if (cmp < 0)
p = p.left;
//大于0则右树遍历
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
5.2 put
put源码：
public V put(K key, V value) {
Entry<K,V> t = root;
//t为root节点，如果t为空
if (t == null) {
//可比较性校验
compare(key, key); // type (and possibly null) check
//直接在root节点创建
root = new Entry<>(key, value, null);
//增加计数器和modCount
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
//比较器
Comparator<? super K> cpr = comparator;
if (cpr != null) {
//如果比较器不为空则循环遍历
do {
parent = t;
//比较
cmp = cpr.compare(key, t.key);
//小于0左树遍历
if (cmp < 0)
t = t.left;
//大于0右树遍历
else if (cmp > 0)
t = t.right;
//反之则直接修改值
else
return t.setValue(value);
} while (t != null);
}
else {
//如果key为空 则NPE异常
if (key == null)
throw new NullPointerException();
@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;
}
上述即是put方法。
5.3 remove
reomve方法源码如下：
public V remove(Object key) {
//通过get方法找到p
Entry<K,V> p = getEntry(key);
//如果p为null则没找到 直接返回null
if (p == null)
return null;
//将oldValue存储并返回，然后通过deleteEntry删除节点
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
操作逻辑在deleteEntry中：
private void deleteEntry(Entry<K,V> p) {
//增加modCount次数和减少size
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
//如果左右都不为空
if (p.left != null && p.right != null) {
//后继节点 左右和父节点三个节点进行判断 按这个顺序取 之后将p的key和value改为后继节点
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
//将p和后继节点合并
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
//替换节点 p的左 右 只要不为空 按这个次序
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//如果还有替换节点
if (replacement != null) {
// Link replacement to parent
//将p的parent指向这个节点
replacement.parent = p.parent;
//如果parent为null 则将root指向它
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
//将p的指征都清空 以便GC回收
p.left = p.right = p.parent = null;
//颜色检测
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
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;
}
}
}
5.4 fixAfterInsertion
这是在insert之后，进行红黑树颜色校验：
/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
//先将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;
}
根据红黑树的规则，对颜色进行check，并修改为对应的颜色。
5.5 fixAfterDeletion
fixAfterDeletion是在删除元素之后再进行平衡的方法：
/** From CLR */
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
通过上述代码根据红黑树的规则进行检查。
6.总结
本文对TreeMap的源码进行了分析，实际上，再分析了前的HashMap和ConcurrentHashMap的源码之后，TreeMap的源码要相对简单得多。其核心就是红黑树，然后左右旋转。关于红黑树的具体操作，本文并没有进行描述。
红黑树是一种比平衡二叉树在插入和删除上效率更好，检索的时候效率与平衡二叉树基本一致的数据结构，相比平衡二叉树，在插入和删除从操作上可以节约时间。这也是为什么HashMap底层会引入红黑树的原因之一。红黑树会大量应用于操作系统底层的各种数据结构。
**需要注意的是，TreeMap不支持key为null的情况，但是支持value为null。这介于HashMap和concurrentHashMap之间。
