今天来看看Map家族的另一名大将——TreeMap。前面已经介绍过Map家族的两名大将，分别是HashMap，LinkedHashMap。HashMap可以高效查找和存储元素，LinkedHashMap可以在高效查找的基础上对元素进行有序遍历，那么TreeMap又有什么特点呢？别急别急，看完这篇你就知道了。
本篇主要从以下几个方面对TreeMap进行介绍：
1、TreeMap的特性以及使用栗子
2、TreeMap继承结构简介
3、TreeMap源码分析
本篇预计食用10分钟，请各位食客合理分配时间。
一、TreeMap的特性以及使用栗子
1. 键值不允许重复
2. 默认会对键进行排序，所以键必须实现Comparable接口或者使用外部比较器
3. 查找、移除、添加操作的时间复杂度为log(n)
4. 底层使用的数据结构是红黑树
没错，又是让你欲仙欲死的红黑树，不过不要慌，跟之前介绍HashMap时的红黑树是一毛一样的，所以这一篇里，不打算再做介绍啦，如果对红黑树的内容有些遗忘了，可以动动小手，往前面翻一翻。
先来看一个TreeMap的使用小栗子。
public class TreeMapTest { static void main(String[] args){ TreeMap<String,Integer> grades = new TreeMap<>(); grades.put("Frank",100); grades.put("Alice",95); grades.put("Mary",90); grades.put("Bob",85); grades.put("Jack",1)">); System.out.println(grades); System.out.println(grades.subMap("Bob","Jack")); System.out.println(grades.subMap("Bob",true,"Jack",1)">true)); System.out.println(grades.ceilingEntry("Bob")); System.out.println(grades.ceilingKey("Bob")); System.out.println(grades.higherEntry("Bob")); System.out.println(grades.higherKey("Bob")); System.out.println(grades.headMap("Bob")); System.out.println(grades.headMap("Bob",1)">)); System.out.println(grades.tailMap("Bob")); System.out.println(grades.tailMap("Bob",1)">)); System.out.println(grades.containsKey("Bob")); System.out.println(grades.containsValue(90)); System.out.println(grades.descendingMap()); System.out.println(grades.descendingKeySet()); } }
输出如下：
{Alice=95,Bob=85,Frank=100,Jack=90,Mary=90}
{Bob=85,Frank=100}
Bob=85
Bob
Frank=100
Frank
{Alice=95}
{Alice=95,Bob=85}
true
{Mary=90,Alice=95}
[Mary,Jack,Frank,Bob,Alice]
可以看到，放入TreeMap中的元素默认按键值升序排列，这里的键值类型为String，使用String的CompareTo方法进行比较和排序。subMap返回当前Map的子Map，headMap和tailMap也是如此，
二、TreeMap继承结构简介
TreeMap继承自AbstractMap，实现了NavigableMap接口，继承关系图如下：
对于AbstractMap相信大家已经不陌生了，HashMap也是继承自AbstractMap，里面有对Map接口的一些默认实现。这里我们可以看到两个新的接口——SortedMap和NavigableMap。SortedMap接口继承自Map接口，从名字就能看出。SortedMap相比Map接口，憎加了排序的功能，内部的方法也不多，简单了解一下就好了
NavigableMap接口继承自SortedMap接口，主要提供一下导航方法：
说了这么多没啥营养的，接下来还是讲讲真正的干货吧。
三、TreeMap源码分析
JDK 1.8中的TreeMap源码有两千多行，还是比较多的。所以本文并不打算逐句分析所有的源码，而是挑选几个常用的内部类和方法进行分析。这些方法实现的功能分别是查找、遍历、插入、删除等，其他的方法小伙伴们有兴趣可以自己分析。TreeMap实现的核心部分是关于红黑树的实现，其绝大部分的方法基本都是对底层红黑树增、删、查操作的一个封装。就像前面所说，只要弄懂了红黑树原理，TreeMap 就没什么秘密了。关于红黑树的原理，可以参考前面关于HashMap红黑树的文章，本篇文章不会对此展开讨论。
TreeMap的主要数据结构是红黑树，而这红黑树结构的承载者便是内部类Entry，先来看看这个Entry类：
final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,1)"> left; Entry<K,1)"> right; Entry<K,1)"> parent; boolean color = BLACK; /** * 构造函数*/ Entry(K key,V value,Entry<K,1)"> parent) { this.key = key; this.value = value; this.parent = parent; } public K getKey() { return key; } V getValue() { value; } V setValue(V value) { V oldValue = this.value; oldValue; } 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()); } int hashCode() { int keyHash = (key==null ? 0 : key.hashCode()); int valueHash = (value== : value.hashCode()); return keyHash ^ valueHash; } String toString() { return key + "=" + value; } }
其实内部的结构也很简单，主要有key，value和三个分别指向左孩子，右孩子，父节点的引用，以及用来标识颜色的color成员变量。再来看看TreeMap中的几个重要的成员变量：
* 外部比较器 */ private final Comparator<? super K> comparator; transient Entry<K,1)"> root; * 键值对数量 transient int size = 0; int modCount = 0boolean RED = ; boolean BLACK = * 键值对集合 transient EntrySet entrySet; * 键的集合 transient KeySet<K> navigableKeySet; * 倒序Map transient NavigableMap<K,V> descendingMap;
comparator用于对map中的键进行排序，root指向红黑树的根节点，size表示键值对的数量，modCount相信已经不陌生了，表示内部结构被修改的次数，RED和BLACK是两个内部常量，即红黑两种颜色，false表示红，true表示黑。entrySet是键值对的集合，navigableKeySet是键的集合，最后一个descendingMap是当前map的一个倒序map。
在TreeMap中有很多内部类，可以先看图了解一下：
前前后后一共18个内部类，不过不要慌，其实里面跟迭代器相关的类就占了一半多（10个），跟子Map相关的类占4个，剩下4个就是跟内部集合相关的了。接下来还是一起来看看那些最常用的方法吧：
// 插入元素 V put(K key,V value) { TreeMap.Entry<K,V> t = root; if (t == null) { 检查类型以及key是否为null 如果外部比较器为null，且key也为null则会抛出空指针异常 如果TreeMap未设置外部比较器，且传入的对象未实现Comparable接口 则会抛出ClassCastException异常 compare(key,key); type (and possibly null) check 如果根节点不存在，则用传入的键值对信息生成一个根节点 root = new TreeMap.Entry<>(key,value,1)">); size = 1; modCount++; ; } cmp; TreeMap.Entry<K,1)"> split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != do { 如果外部比较器不为空，则依次与各节点进行比较 parent = t; cmp = cpr.compare(key,t.key); if (cmp < 0) 小于则与左孩子比较 t = t.left; else if (cmp > 0) 大于则与右孩子比较 t = t.right; else 找到相等的key则替换其value t.setValue(value); 一直循环，直到待比较的节点为null } while (t != ); } else { 如果外部比较器为null 如果key为null则抛出空指针 if (key == ) throw new NullPointerException(); 如果key未实现comparable接口则会抛出异常 @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? ) key; 跟上面逻辑类似，只是用key的compareTo方法进行比较，而不是用外部比较器的compare方法 parent = k.compareTo(t.key); ) t = t.setValue(value); } 生成键值对 TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key,parent); 连接到当前map的左孩子位置或者右孩子位置 ) parent.left = e; parent.right = 插入后的调整 fixAfterInsertion(e); size++; modCount++; ; }
其实这里的逻辑跟HashMap中TreeNode的插入逻辑十分类似，也是先找到要插入的位置，然后再进行结构调整。这里的结构调整即红黑树的结构调整，在前面HashMap中已经详细介绍过了，这里就不重复介绍了，调整过程是完全一样的。
* 插入后的调整 void fixAfterInsertion(TreeMap.Entry<K,1)"> x) { 将插入的节点初始化为红色节点 x.color = RED; 如果x不为null且x不是根节点，且x的父节点是红色，此时祖父节点一定为黑色 while (x != null && x != root && x.parent.color == RED) { 如果x的父节点为祖父节点的左孩子 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { y指向x的叔叔节点 TreeMap.Entry<K,V> y = rightOf(parentOf(parentOf(x))); 如果叔叔节点也是红色，则进行变色处理 if (colorOf(y) == RED) { 父节点变成黑色 setColor(parentOf(x),BLACK); 叔叔节点变成黑色 setColor(y,1)"> 祖父节点变成黑色 setColor(parentOf(parentOf(x)),RED); 将x指向祖父节点，继续往上调整 x = parentOf(parentOf(x)); } { 如果叔叔节点是黑色节点 如果x是父节点的右孩子 if (x == rightOf(parentOf(x))) { 将x指向其父节点 x = parentOf(x); 左旋 rotateLeft(x); } 将x的父节点置为黑色 将x的祖父节点置为红色 将祖父节点右旋 rotateRight(parentOf(parentOf(x))); } } 这里类似操作 TreeMap.Entry<K,1)"> leftOf(parentOf(parentOf(x))); RED) { setColor(parentOf(x),BLACK); setColor(y,BLACK); setColor(parentOf(parentOf(x)),RED); x = leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x),RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK; }
说完了插入，再来看看删除操作。
删除节点 V remove(Object key) { 先找到该key对应的键值对 TreeMap.Entry<K,V> p = getEntry(key); if (p == ) 如果未找到则返回null ; V oldValue = p.value; 找到后删除该键值对 deleteEntry(p); oldValue; }
final TreeMap.Entry<K,1)"> getEntry(Object key) { 为了性能，卸载了比较器的版本 if (comparator != getEntryUsingComparator(key); NullPointerException(); @SuppressWarnings("unchecked") Comparable<? ) key; TreeMap.Entry<K,1)"> 使用compareTo方法进行查找 while (p != int cmp = k.compareTo(p.key); ) p = p.left; p.right; else p; } ; } 使用比较器的getEntry版本。 从getEntry分离以获得性能。 （对于大多数方法而言，这不值得做，这些方法较少依赖于比较器性能，但在这里是值得的。） getEntryUsingComparator(Object key) { @SuppressWarnings("unchecked") K k = (K) key; Comparator<? 使用比较器进行二分查找 ) { TreeMap.Entry<K,1)"> root; ) { cpr.compare(k,p.key); ) p = p.left; p.right; p; } } * 删除节点，并调整红黑树以保持它的平衡 void deleteEntry(TreeMap.Entry<K,1)"> p) { modCount++; size--; 如果p的左右孩子均不为空，则找到p的后继节点，并且将p指向该后继节点 if (p.left != null && p.right != successor(p); p.key = s.key; p.value = s.value; p = s; } p has 2 children 修复替补节点 用替补节点替换待删除的节点后，需要对其原来所在位置结构进行修复 TreeMap.Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != ) { replacement.parent = p.parent; if (p.parent == ) root = replacement; if (p == p.parent.left) p.parent.left = p.parent.right = replacement; p.left = p.right = p.parent = ; 如果p的颜色是黑色，则进行删除后的修复 if (p.color == BLACK) fixAfterDeletion(replacement); } ) { root = ; } BLACK) fixAfterDeletion(p); if (p.parent != p.parent.left) p.parent.left = ; p.parent.right) p.parent.right = ; p.parent = ; } } } * 返回指定节点的后继节点 static <K,V> TreeMap.Entry<K,V> successor(TreeMap.Entry<K,1)"> t) { if (t.right != t.right; 如果右子树不为空，则找到右子树的最左节点作为后继节点 while (p.left != p; } { TreeMap.Entry<K,1)"> t.parent; TreeMap.Entry<K,V> ch = t; 如果右子树为空且当前节点为其父节点的左孩子，则直接返回 如果为其父节点的右孩子，则一直往上找，直到找到根节点或者当前节点为其父节点的左孩子时，用其做为后继节点 null && ch == p.right) { ch = p; p = p.parent; } p; } } * 进行删除后的结构修复 * @param x void fixAfterDeletion(TreeMap.Entry<K,1)">while (x != root && colorOf(x) == BLACK) { 如果x是父节点的左孩子 leftOf(parentOf(x))) { sib指向x的兄弟节点 TreeMap.Entry<K,V> sib = rightOf(parentOf(x)); 如果sib是红色，则进行变色处理 if (colorOf(sib) == 兄弟节点改为黑色 setColor(sib,1)"> 父节点改为红色 父节点左旋 rotateLeft(parentOf(x)); sib指向x的父节点的右孩子 sib = rightOf(parentOf(x)); } 如果sib的左孩子和右孩子都是黑色，则进行变色处理 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { 将sib置为红色 x指向其父节点 x = parentOf(x); } 如果sib的右孩子是黑色而左孩子是红色，则变色右旋 if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib),BLACK); setColor(sib,RED); rotateRight(sib); sib = rightOf(parentOf(x)); } 变色左旋 root; } } else { symmetric 跟上面操作类似 TreeMap.Entry<K,1)"> leftOf(parentOf(x)); 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,1)">if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib),RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib,BLACK); setColor(leftOf(sib),BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x,BLACK); }
嗯，对比一下HashMap的删除操作，核心步骤是完全一样的，所以可以对照前面的HashMap红黑树详解进行食用。
到此，这一篇就很水的讲完啦= =
最近这段时间烦心事比较多，对发展方向也考虑了很多，想做的事情很多，反而让我止步不前，不过很多事情是急不来的，还是好好写写博客，多做总结分享吧。
机会只留给有准备的人。
