1.TreeMap简介
TreeMap是通过红黑树来实现一个有序的key-value集合的。
TreeMap是基于红黑树实现的，该映射可以根据他的键的自然顺序进行排序，也可以根据为构造函数提供的比较器进行排序。
TreeMap的基本操作containsKey,get,put,remove的时间复杂度是log(n),另外TreeMap是非同步的。
2.TreeMap数据结构
TreeMap的继承关系
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}
1.由继承关系可知，TreeMap继承与AbstractMap,并且实现了Navigable接口。
2.TreeMap的本质是红黑树，它包含几个重要的成员变量，root,size,comparator。其中root是红黑树的节点，他的类型是Entry，它包含key，value,left(左孩子)，right(右孩子)，parent(父节点)，color(颜色)。Entry节点根据key进行排序；可以是自然排序，也可以根据比较器来进行排序；size是红黑树节点中的个数。
3.TreeMap源码分析
3.1红黑树相关
//红黑树的节点颜色--红色
private static final boolean RED = false;
//红黑树的节点颜色--黑色
private static final boolean BLACK = true;
//红黑树左旋
private void rotateLeft(Entry<K,V> p) { ... }
//红黑树右旋
private void rotateRight(Entry<K,V> p) { ... }
//红黑树插入操作
public V put(K key, V value) { ... }
//红黑树插入修正操作，保证在进行插入之后，任然是一颗红黑树
private void fixAfterInsertion(Entry<K,V> x) { ... }
//红黑色的删除操作
private void deleteEntry(Entry<K,V> p) { ... }
//红黑树删除修正操作，保证在进行删除之后，任然是一颗红黑树
private void fixAfterDeletion(Entry<K,V> x) { ... }
3.2TreeMap的构造函数
1.默认构造函数
public TreeMap() {
comparator = null;
}
2.带比较器的构造函数
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
3.有Map的构造函数
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
其中putAll()会把m中的所有元素添加到TreeMap中，其中putAll的源码如下：
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
3.3TreeMap中与Entry相关的函数
与Entry相关的函数
//以下与Entry相关的函数原理大同小异
firstEntry()
lastEntry()
lowerEntry()
higherEntry()
floorEntry()
ceilingEntry()
pollFirstEntry()
pollLastEntry()
再次以firstEntry()为例子进行说明：
public Map.Entry<K,V> firstEntry() {
return exportEntry(getFirstEntry());
}
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
firstEntry()和getFirstEntry()都是用于获取第一个节点。firstEntry()是对外接口，getFirstEntry()是对内接口。为什么外界不直接调用getFirstEntry()来实现，而是通过调用firstEntry()来获取第一个Entry呢？这样做的目的是为了防止用户修改返回的Entry.
3.4TreeMap中与Key相关的函数
//以下与key有关的函数原理类似
firstKey()
lastKey()
lowerKey()
higherKey()
floorKey()
ceilingKey()
//该函数返回大于/等于key的最小的键值对所对应的key，没有的话就返回null
public K ceilingKey(K key) {
return keyOrNull(getCeilingEntry(key));
}
static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
return e == null? null : e.key;
}
