TreeMap（有序）
TreeMap简介
TreeMap 是一个有序的key-value集合，它是通过红黑树实现的，因为红黑树是平衡的排序二叉树，红黑树是有序的，所以TreeMap是有序的，所有操作其实就是对红黑树的操作。
1、继承于AbstractMap，实现了NavigableMap接口，意味着它支持一系列的导航方法，提供了"边界"处理，以及提供了一个逆序迭代器，比如返回有序的key集合。
2、实现了Cloneable接口，意味着它能被克隆。
3、实现了java.io.Serializable接口，意味着它支持序列化。
4、TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) ，因为红黑树的这些操作时间复杂度是 log(n)。
5、iterator 方法返回的迭代器是fail-fast（快速失败）的，List和Map的迭代器都是快速失败的。
6、相比于HashMap，TreeMap删除和插入后可能需要调整树结构满足红黑树的规则，需要耗费性能，所以HashMap性能好一些，也就是TreeMap的有序是需要时间来支持的。
排序方式
TreeMap的映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
new TreeMap可以指定排序，即实现 Comparator（Java最基础的 interface）。
自然排序：TreeMap的所有key必须实现那Comparable接口，而且所有key应该是同一个类的对象，否则将会抛出ClassCaseException。
定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中所有key进行排序。采用定制排序时不要求Map的key实现Comparable接口。
一个实现了Comparable接口的类，可以让其自身的对象和其他对象进行比较。也就是说，同一个类的两个对象之间要想比较，对应的类就要实现Comparable接口，并实现compareTo()方法
一个类如果实现Comparable接口，那么他就具有了可比较性，意思就是说它的实例之间相互直接可以进行比较。
Map<Integer, Object> map = new TreeMap<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
每一个插入的key-value，对于红黑树都是Entry节点
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;
/**
* 用key，value和父节点构造一个Entry，默认为黑色
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
对于TreeMap的put\get\remove等操作，实际上就是操作红黑树。
get方法
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p. value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
// 如果比较器为空，只是用key作为比较器查询
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
// 取得root节点
Entry<K,V> p = root;
// 从root节点开始查找，根据比较器判断是在左子树还是右子树，一直查找到
// while 比较最后得到节点,
while (p != null) {
int cmp = k.compareTo(p.key );
if (cmp < 0)
p = p. left;
else if (cmp > 0)
p = p. right;
else
return p;
}
return null;
}
final Entry<K,V> getEntryUsingComparator(Object key) {
K k = (K) key;
Comparator<? super K> cpr = comparator ;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key );
if (cmp < 0)
p = p. left;
else if (cmp > 0)
p = p. right;
else
return p;
}
}
return null;
}
从get看到while拿到值就知道效率不如HashMap了。
put\remove方法
put\remove，添加或者删除节点之后，红黑树可能平衡保持稳定，那就什么都不用做；
可能不再稳定，某个分支链条过长，查询效率变低，那就需要通过左旋、右旋来调整节点，继续保持稳定，这个时候对应的源码方法就是fixAfterInsertion、fixAfterDeletion等。
put和remove的源码我就不分析了，第一个是看不懂，就算花费大量时间看懂后，过段时间又忘了，对于做后端开发的人来说，这个性价比不高，如果从事文件系统、存储系统的开发，那这些就更重要一些。