TreeMap继承AbstractMap，实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合， NavigableMap则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法 。 TreeMap中同时也包含了如下几个重要的属性：
PRivate final Comparator<? super K> comparator; //比较器private transient Entry<K,V> root = null; //TreeMap红-黑节点，为TreeMap的内部类 private transient int size = 0; //容器大小 private transient int modCount = 0; //TreeMap修改次数 private static final boolean RED = false; //红黑树的节点颜色–红色 private static final boolean BLACK = true; //红黑树的节点颜色–黑色
对于实体节点Entry是TreeMap的内部类，是通过红黑树实现的。
红黑树顾名思义就是节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树二叉树而言我们必须增加如下规则：
1、每个节点都只能是红色或者黑色
2、根节点是黑色
3、每个叶节点（NIL节点，空节点）是黑色的。
4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。所以红黑树它是复杂而高效的，其检索效率O(log n)。下图为一颗典型的红黑二叉树。
对于红黑二叉树而言它主要包括三大基本操作：左旋、右旋、着色。
左旋 右旋
（图片来自：http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html）
本节参考文献：http://baike.baidu.com/view/133754.htm?fr=aladdin-----百度百科
注：由于本文主要是讲解Java中TreeMap，所以并没有对红黑树进行非常深入的了解和研究，如果诸位想对其进行更加深入的研究Lz提供几篇较好的博文：
1、红黑树系列集锦
2、红黑树数据结构剖析
3、红黑树
TreeMap特点
TreeMap是非线程安全的。 可以采用这种方式将TreeMap设置为同步的：Map m = Collections.synchronizedSortedMap(new TreeMap(…));TreeMap是用键来进行升序顺序来排序的。通过Comparable 或 Comparator来排序。 TreeMap是SortedMap接口的基于红黑树的实现。此类保证了映射按照升序顺序排列关键字， 根据使用的构造方法不同，可能会按照键的类的自然顺序进行排序，或者按照创建时所提供的比较器（自定义）进行排序。 public class Person1 implements Comparable<Person1>{ private int age; private String name; public Person1(String name, int age) { this.name = name; this.age = age; } @Override public int compareTo(Person1 o) { return this.age-o.age; } @Override public String toString() { return name+":"+age; }}123456789101112131415161718192021222324123456789101112131415161718192021222324 测试代码：
Map<Person1,Integer> map = new TreeMap<>(); Person1 person1 = new Person1("zzh",18); Person1 person2 = new Person1("jj",17); Person1 person3 = new Person1("QQ",19); map.put(person1, 1); map.put(person2, 2); map.put(person3, 3); for(Entry<Person1, Integer> entry:map.entrySet()) { System.out.println(entry.getKey()+":"+entry.getValue()); }12345678910111234567891011 测试结果：
jj:17:2zzh:18:1qq:19:3123123 只要自定义键的类实现了Comparable接口就可以使用TreeMap的排序功能， 首先引用类Person2：
public final class Person2{ private int age; private String name; public Person2(String name, int age) { this.name = name; this.age = age; } @Override public String toString() { return name+":"+age; } //getter and setter方法省略....}1234567891011121314151617181912345678910111213141516171819 测试代码：
Map<Person2,Integer> map2 = new TreeMap<>(new Comparator<Person2>(){ @Override public int compare(Person2 o1, Person2 o2) { if(o1 == null || o2 == null) return 0; return o1.getAge()-o2.getAge(); } }); Person2 p1 = new Person2("zzh",18); Person2 p2 = new Person2("jj",17); Person2 p3 = new Person2("qq",19); map2.put(p1, 1); map2.put(p2, 2); map2.put(p3, 3); for(Entry<Person2, Integer> entry:map2.entrySet()) { System.out.println(entry.getKey()+":"+entry.getValue()); }1234567891011121314151617181912345678910111213141516171819 输出结果：
jj:17:2zzh:18:1qq:19:3123123 可以看到Person2中并没有实现Comparable接口，但是想要和Person1一样能够和TreeMap合作，只需要在创建TreeMap的构造函数中声明一个Comparator接口的实现，譬如上面的例子所示。 3. 由所有此类的“collection 视图方法”所返回的迭代器都是快速失败的。 这点和HashMap一样，所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其结构性的修改，这是迭代器会立马感知到，并且立刻抛出ConcurrentModificationException异常，而不是等待迭代完成之后才告诉你已经出错。注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。 快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。 因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测 bug。 4. 和HashMap一样，如果插入重复的元素，后面的元素会覆盖前面的。 5. 键不可以为null（如果比较器对null做了处理，就可以为null）,但是值可以为null。 如上面的案例中，加入：
Person2 p4 = new Person2(null,19); map2.put(p4, 4);1212 在打印map2的时候就不会报错。 6. TreeMap对containsKey、get、put 和 remove 操作提供了保证的 log(n) 时间开销。 TreeMap提供了很多方法方便大小使用，譬如containsKey, get, put,remove，entrySet等Map通用的方法，也包括fisrtEntry, firstKey, cellingKey, lowerKey等方法。
HashMap与TreeMap的区别
实现方式 HashMap:基于哈希表实现。使用HashMap要求添加的键类明确定义了hashCode（）和equals（）[可以重写hashCode（）和equals（）],为了优化HashMap空间的使用，您可以调优初始容量和负载因子。 （1）HashMap（）： 构建一个空的哈希映像 （2）HashMap（Map m）： 构建一个哈希映像，并且添加映像m的所有映射 （3）HashMap（int initialCapacity）： 构建一个拥有特定容量的空的哈希映像 （4）HashMap（int initialCapacity, float loadFactor）： 构建一个拥有特定容量和加载因子的空的哈希映像 TreeMap:基于红黑树实现。TreeMap没有调优选项，因为该树总处于平衡状态。 （1）TreeMap（）：构建一个空的映像树 （2）TreeMap（Map m）： 构建一个映像树，并且添加映像m中所有元素 （3）TreeMap（Comparator c）： 构建一个映像树，并且使用特定的比较器对关键字进行排序 （4）TreeMap（SortedMap s）： 构建一个映像树，添加映像树s中所有映射，并且使用与有序映像s相同的比较器排序用途 HashMap：适用于在Map中插入、删除和定位元素。 TreeMap：适用于按自然顺序或自定义顺序遍历键（key)。 HashMap通常比TreeMap快一点（树和哈希表的数据结构使然），建议多使用HashMap,在需要排序的Map时候才用TreeMap.
