前面我们分别讲了Map接口的两个实现类HashMap和LinkedHashMap，本章我们讲一下Map接口另一个重要的实现类TreeMap，TreeMap或许不如HashMap那么常用，但存在即合理，它也有自己的应用场景，TreeMap可以实现元素的自动排序。
一. TreeMap概述TreeMap存储K-V键值对，通过红黑树（R-B tree）实现；
TreeMap继承了NavigableMap接口，NavigableMap接口继承了SortedMap接口，可支持一系列的导航定位以及导航操作的方法，当然只是提供了接口，需要TreeMap自己去实现；
TreeMap实现了Cloneable接口，可被克隆，实现了Serializable接口，可序列化；
TreeMap因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过Key值的自然顺序进行排序；
二. 红黑树回顾因为TreeMap的存储结构是红黑树，我们回顾一下红黑树的特点以及基本操作，红黑树的原理可参考关于红黑树(R-B tree)原理，看这篇如何。下图为典型的红黑树：
红黑树规则特点：
节点分为红色或者黑色；
根节点必为黑色；
叶子节点都为黑色，且为null；
连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
新加入到红黑树的节点为红色节点；
红黑树自平衡基本操作：
变色：在不违反上述红黑树规则特点情况下，将红黑树某个node节点颜色由红变黑，或者由黑变红；
左旋：逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点
右旋：顺时针旋转两个节点，让一个节点被其左子节点取代，而该节点成为左子节点的右子节点
三. TreeMap构造我们先看一下TreeMap中主要的成员变量
/** * 我们前面提到TreeMap是可以自动排序的，默认情况下comparator为null，这个时候按照key的自然顺序进行排 * 序，然而并不是所有情况下都可以直接使用key的自然顺序，有时候我们想让Map的自动排序按照我们自己的规则， * 这个时候你就需要传递Comparator的实现类 */ private final Comparator<? super K> comparator; /** * TreeMap的存储结构既然是红黑树，那么必然会有唯一的根节点。 */ private transient Entry<K,V> root; /** * Map中key-val对的数量，也即是红黑树中节点Entry的数量 */ private transient int size = 0; /** * 红黑树结构的调整次数 */ private transient int modCount = 0;上面的主要成员变量根节点root是Entry类的实体，我们来看一下Entry类的源码
static final class Entry<K,V> implements Map.Entry<K,V> { //key,val是存储的原始数据 K key; V value; //定义了节点的左孩子 Entry<K,V> left; //定义了节点的右孩子 Entry<K,V> right; //通过该节点可以反过来往上找到自己的父亲 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; } /** * 获取节点的key值 */ public K getKey() {return key;} /** * 获取节点的value值 */ 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; } }Entry静态内部类实现了Map的内部接口Entry，提供了红黑树存储结构的Java实现，通过left属性可以建立左子树，通过right属性可以建立右子树，通过parent可以往上找到父节点。
大体的实现结构图如下：
TreeMap构造函数：
//默认构造函数，按照key的自然顺序排列 public TreeMap() {comparator = null;} //传递Comparator具体实现，按照该实现规则进行排序 public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;} //传递一个map实体构建TreeMap,按照默认规则排序 public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); } //传递一个map实体构建TreeMap,按照传递的map的排序规则进行排序 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方法put方法为Map的核心方法，TreeMap的put方法大概流程如下：
