TreeMap
下文中提到的比较大小，>0,<0 都是指key用比较器比较大小
简介
TreeMap是一个有序的Map，是基于红黑树实现的。排序根据Map创建时传入的Comaprable或Comparator实现排序，如果没有传，则默认按插入数据的顺序。
TreeMap 的get,containsKey,get,put,remove 操作使用的时间为log(n)，因为每次查找都是从树的根节点开始一层一层向下查找，
TreeMap也是非线程安全的，所以，如果想使用线程安全的sorted map 可以用如下代码获取
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...))
和大多数非线程安全的集合一样，如果在迭代器创建后修改了TreeMap的结构，会抛出ConcurrentModificationException异常。
内部有一个比较器Comparator comparator 维护TreeMap的内部数据顺序，如果比较器为空，那么TreeMap的存储顺序就按插入的顺序存储。
有一个根节点 Entry root 内部包含父节点，左子节点，右子节点 颜色是否是黑色。entry是TreeMap中的元素节点，所有这些节点按red-black tree 排列，形成了TreeMap。
size 记录当前map中节点的个数
modCount 记录Treemap的结构性修改。
部分代码讲解
- getEntry
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
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;
}
上面这段代码的意思，从根节点开始找，如果比较值<0 ,证明当前节点的key大了（按照comparable比较），
则向树的左子节点查找，如果比较值>0，则向树的右子节点上查找。知道查找到为止。
其中函数中getEntryUsingComparator()的比较思路也是这样。
- getCeilingEntry
// 获取当前值对应的entry,如果没有找到，则返回在map中比key大一点的entry
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
// 如果p比查找的节点大
if (cmp < 0) {
// 如果当前节点的左子节点不为空，向这个节点的左边查找
if (p.left != null)
p = p.left;
else
// 如果当前节点的左子节点为空，那么比查找值大一点的就是p这个节点
return p;
} else if (cmp > 0) { // 如果p比查找的节点小。向右查找
if (p.right != null) { // 如果p的右子节点不为空，继续向有查找
p = p.right;
} else {
// 如果右节点为空，这就麻烦了，要从p网上找，直到父节点为空
// 或者找到了父节点的右子节点不在p到父（父...）节点的路径上
// 拿笔在纸上画一画就明白了
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p;
}
return null;
}
和上面的逻辑类似，寻找给定key对应的entry，如果没找到，则返回比给定key小的最大的key对应的entry
- getFloorEntry
final Entry<K,V> getFloorEntry(K key) {
Entry<K,V> p = root;
while (p != null) { // 如果根节点为空直接返回null
int cmp = compare(key, p.key);
if (cmp > 0) { // 如果p.key比给定的key小，则向右找
if (p.right != null)
p = p.right;
else
return p;
} else if (cmp < 0) { // 如果p.key比给定的key大，则向左找
if (p.left != null) {
p = p.left;
} else {
// 如果p的左子节点为空，那么就要一直往上找，一直找到一个一个节点，其左子节点，
// 一直找到一个节点，不在p到其父（父...）节点的连线上。
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p;
}
return null;
}
下面到了最精彩的地方了，那就是put方法，这是TreeMap的核心，
本质上是向红黑树上插入一个节点。建议先看一下红黑树插入数据的操作，这样会很容易明白这段逻辑。
put的核心就是代码中最后的fixAfterInsertion(e)
- put
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) { // 如果根节点为空，直接将值插到根节点
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) { // 如果比较器不为空，根据比较器比较key的大小，确定要插入entry的存放位置
do {
parent = t; // 和查找相同，根据比较器返回的值，
// 确定要插入的值放到左子节点的分支还是右子节点的分支
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value); // 如果找到了之前存放过该key的节点，直接替换其中的值
} while (t != null);
}
else {
// 如果没有没有比较器，则key 不可以为空，且必须实现了Comparable接口
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
// 和上面的比较类似
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 如果上面没有查找到，这时候树上的指针已经移动到parent节点，
// 当前key与parent节点比较大小确定新增的节点放到左子节点还是右子节点
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 根据红黑树的定义改变相应节点的颜色，旋转某个节点
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
未完，待续