TreeMap
基于红黑树（Red-Black tree）的 NavigableMap 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的Comparator 进行排序，具体取决于使用的构造方法。
一、红黑树的介绍
红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接*衡的。
红黑树的5个性质：
- 每个结点要么是红的要么是黑的。
- 根结点是黑的。
- 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
- 如果一个结点是红的，那么它的两个儿子都是黑的。
- 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
注意，此实现不是同步的（非线程安全的）。如果多个线程同时访问一个映射，并且其中至少一个线程从结构上修改了该映射，则其必须 外部同步。（结构上的修改是指添加或删除一个或多个映射关系的操作；仅改变与现有键关联的值不是结构上的修改。）这一般是通过对自然封装该映射的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用Collections.synchronizedSortedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的不同步访问，如下所示：
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
collection（由此类所有的“collection 视图方法”返回）的 iterator 方法返回的迭代器都是 快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器自身的 remove 方法，否则在其他任何时间以任何方式进行修改都将导致迭代器抛出
ConcurrentModificationException。因此，对于并发的修改，迭代器很快就完全失败，而不会冒着在将来不确定的时间发生不确定行为的风险。
TreeMap:
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
从继承关系可以看出，TreeMap继承了AbstractMap，实现了NavigableMap接口，意味着它支持一系列的导航方法，比如返回有序的key集合。它还实现了Cloneable接口，意味着它能被克隆。另外也实现了Serializable接口，表示它支持序列化。
TreeMap 的API：
Entry实体类：
/------------------- Red-black树-------------------------------/
private static final boolean RED = false;
private static final boolean BLACK = true;
//实现了Map.Entry<K,V> 的getKey()，getValue(),setValue(),equals(),hashCode()
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;//左子节点
Entry<K,V> right = null; //右子节点
Entry<K,V> parent; //父节点
boolean color = BLACK; //树的颜色，默认为黑色
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;
}
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;
}
}
构造函数：
/*********************** 构造方法 **************************/
//使用键的自然顺序构造一个新的、空的树映射
public TreeMap() {
comparator = null; //比较器
}
//构造一个新的、空的树映射，该映射根据给定比较器进行排序
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
//构造一个与给定映射具有相同映射关系的新的树映射，该映射根据其键的自然顺序进行排序。
public TreeMap(Map<? extends K, ? extends V> m) { //Map 键的自然顺序进行排序
comparator = null;
putAll(m);
}
// 构造一个与指定有序映射具有相同映射关系和相同排序顺序的新的树映射。
public TreeMap(SortedMap<K, ? extends V> m) { // 比较方法：新SortMap树的comparator
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
属性：
private final Comparator<? super K> comparator; ////比较器
private transient Entry<K,V> root = null;//实体对象
private transient int size = 0;//红黑树节点个数，即Entry数
private transient int modCount = 0;//修改次数
private transient EntrySet entrySet = null;
private transient KeySet<K> navigableKeySet = null;
private transient NavigableMap<K,V> descendingMap = null;
TreeMap有四个构造函数，这里分析一下第三个构造函数，内部调用了putAll方法，我们看一下putAll方法：
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
//如果map是Sorted子类
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator c = ((SortedMap)map).comparator();
//按照键的自然顺序进行排序。
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {// 将map中的元素逐个添加到TreeMap中，
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
//否则调用AbstractMap 的putAll()
super.putAll(map);
}
/* ----------------------AbstractMap 的putAll()-----------------*/
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
/* ----------------------AbstractMap 的putAll()-----------------*/
其他方法：：
未完待续