[TOC]
基于红黑树实现的 TreeMap 提供了平均和最差时间复杂度均为 O(logn) 的增删改查操作，该集合最大的特点就是 Key 的有序性。TreeMap 继承了 SortedMap 和 NavigableMap，SortedMap 表示 Key 是有序不可重复的，支持获取头尾 Key-Value 元素，或者根据 Key 指定范围获取子集合等。插入的 Key 必须实现 Comparable 接口或提供额外的 Comparator 比较器，所以 Key 不允许为 null。NavigableMap 继承了 SortedMap，根据指定的搜索条件返回最匹配的 Key-Value 元素。
不同于 HashMap 的是 TreeMap 并非一定要重写 hashCode 和 equals 方法来达到 Key 去重的目的。HashMap 是依靠 hashCode 和 equals 来去重的，而 TreeMap 依靠 Comparable 或 Comparator 来实现去重。 TreeMap 对 Key 进行排序时，如果比较器不为空就会优先使用比较器的 compare 方法，如果比较器为空就会使用 Key 实现的自然排序 Comparable 接口的 compareTo 方法，如果两者都不满足就会抛出异常。
TreeMap 通过 put 和 deleteEntry 实现红黑树增加和删除节点的操作。插入新节点的规则有三个：① 需要调整的新节点总是红色的。② 如果插入新节点的父节点是黑色的，不需要调整。③ 如果插入新节点的父节点是红色的，由于红黑树中不能出现相邻的红色，则进入循环判断，通过重新着色或左右旋转来调整。TreeMap 的插入操作就是按照 Key 的对比往下遍历，大于比较节点值的向右查找，小于的向左查找，先按照二叉查找树的特性操作，无需关心节点颜色与树的平衡，后续会重新着色和旋转，保持红黑树的特性。
TreeMap 是线程不安全的集合，在多线程操作时需要添加互斥机制，或者把对象放在 Collections.synchronizedMap() 中实现同步。在 JDK 7 之后的 HashMap、TreeSet、ConcurrentHashMap 也都是使用红黑树的方式管理节点。如果只是对单个元素进行排序，使用 TreeSet 即可。TreeSet 的底层就是 TreeMap，Value 共享一个静态的 Object 对象。