Java集合汇总源码分解：TreeMap源码分解
副标题#e#
媒介
本文不规划延续前几篇的气势气魄（对所有的源码插手注释），因为要领略透TreeMap的所有源码，对博主来说，确实需要淹灭大量的时间和经验，今朝看来不大大概有这么多时间的投入，故这里意在通过于阅读源码对TreeMap有个宏观上的掌握，并就个中一些要领的实现做较量深入的阐明。
红黑树简介
TreeMap是基于红黑树实现的，这里只对红黑树做个简朴的先容，红黑树是一种非凡的二叉排序树，关于二叉排序树，拜见：http://blog.csdn.net/ns_code/article/details/19823463，红黑树通过一些限制，使其不会呈现二叉树排序树中极度的一边倒的环境，相对二叉排序树而言，这自然提高了查询的效率。
二叉排序树的基天性质如下：
1、每个节点都只能是赤色可能玄色
2、根节点是玄色
3、每个叶节点（NIL节点，空节点）是玄色的。
4、假如一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能呈现相邻的两个赤色结点。
5、从任一节点到其每个叶子的所有路径都包括沟通数目标玄色节点。
正是这些性质的限制，使得红黑树中任一节点到其子孙叶子节点的最长路径不会长于最短路径的2倍，因此它是一种靠近均衡的二叉树。
本栏目
说到红黑树，自然难免要和AVL树比拟一番。对较量而言，AVL树是严格的均衡二叉树，而红黑树不算严格意义上的均衡二叉树，只是靠近均衡，不会让树的高度如BST极度环境那样便是节点的个数。其实能用到红黑树的处所，也都可以用AVL树来实现，但红黑树的应用却很是遍及，而AVL树则很少被利用。在执行插入、删除操纵时，AVL树需要调解的次数一般要比红黑树多（红黑树的旋转调解最多只需三次），效率相对较低，且红黑树的统计机能较AVL树要好，虽然AVL树在查询效率上大概更胜一筹，但实际上也高不了几多。
红黑树的插入删除操纵很简朴，就是纯真的二叉排序树的插入删除操纵。红黑树被认为较量失常的处所自然在于插入删除后对红黑树的调解操纵（旋转和着色），主要是环境分的许多，限于篇幅及博主的熟悉水平优先，这里不规划具体先容插入删除后调解红黑树的各类环境及其实现，我们有个宏观上的相识即可，如须具体相识，拜见算法导论或一些相关的资料。
TreeMap源码分解
存储布局
TreeMap的排序是基于对key的排序实现的，它的每一个Entry代表红黑树的一个节点，Entry的数据布局如下：
static final class Entryimplements Map.Entry{
// 键
K key;
// 值
V value;
// 左孩子
Entryleft = null;
// 右孩子
Entryright = null;
// 父节点
Entryparent;
// 当前节点颜色
boolean color = BLACK;
// 结构函数
Entry(K key, V value, Entryparent) {
this.key = key;
this.value = value;
this.parent = parent;
}
。。。。。
}
结构要领
先来看下TreeMap的结构要领。TreeMap一共有4个结构要领。
1、无参结构要领
public TreeMap() {
comparator = null;
}
回收无参结构要领，不指定较量器，这时候，排序的实现要依赖key.compareTo()要领，因此key必需实现Comparable接口，并覆写个中的compareTo要领。
2、带有较量器的结构要领
public TreeMap(Comparator comparator) {
this.comparator = comparator;
}
回收带较量器的结构要领，这时候，排序依赖该较量器，key可以不消实现Comparable接口。
3、带Map的结构要领
public TreeMap(Map m) {
comparator = null;
putAll(m);
}
该结构要领同样不指定较量器，挪用putAll要领将Map中的所有元素插手到TreeMap中。putAll的源码如下：
// 将map中的全部节点添加到TreeMap中
public void putAll(Map map) {
// 获取map的巨细
int mapSize = map.size();
// 假如TreeMap的巨细是0,且map的巨细不是0,且map是已排序的“key-value对”
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator c = ((SortedMap)map).comparator();
// 假如TreeMap和map的较量器相等；
// 则将map的元素全部拷贝到TreeMap中，然后返回！
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
// 挪用AbstractMap中的putAll();
// AbstractMap中的putAll()又会挪用到TreeMap的put()
super.putAll(map);
}
#p#分页标题#e#
显然，假如Map里的元素是排好序的，就挪用buildFromSorted要领来拷贝Map中的元素，这在下一个结构要领中会重点提及，而假如Map中的元素不是排好序的，就挪用AbstractMap的putAll(map)要领，该要领源码如下：
public void putAll(Map m) {
for (Map.Entry e : m.entrySet())
put(e.getKey(), e.getValue());
}
很明明它是将Map中的元素一个个put（插入）到TreeMap中的，主要因为Map中的元素是无序存放的，因此要一个个插入到红黑树中，使其有序存放，并满意红黑树的性质。
4、带有SortedMap的结构要领
public TreeMap(SortedMapm) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
首先将较量器指定为m的较量器，这取决于生成m时挪用结构要领是否传入了指定的结构器，尔后挪用buildFromSorted要领，将SortedMap中的元素插入到TreeMap中，由于SortedMap中的元素师有序的，实际上它是按照SortedMap建设的TreeMap，将SortedMap中对应的元素添加到TreeMap中。
#p#副标题#e#
插入删除
插入操纵即对应TreeMap的put要领，put操纵实际上只需凭据二叉排序树的插入步调来操纵即可，插入到指定位置后，再做调解，使其保持红黑树的特性。put源码的实现：
public V put(K key, V value) {
Entryt = root;
// 若红黑树为空，则插入根节点
if (t == null) {
// TBD:
// 5045147: (coll) Adding null to an empty TreeSet should
// 本栏目删除操纵及对应TreeMap的deleteEntry要领，deleteEntry要领同样也只需凭据二叉排序树的操纵步调实现即可，删除指定节点后，再对树举办调解即可。deleteEntry要领的实现源码如下：// 删除“红黑树的节点p”
private void deleteEntry(Entryp) {
modCount++;
size--;
if (p.left != null && p.right != null) {
Entrys = successor (p);
p.key = s.key;
p.value = s.value;
p = s;
}
Entryreplacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null;
} else {
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}后头的fixAfterDeletion要领即是节点删除后对树举办调解的要领，这里不做先容。其他许多要领这里不再一一先容。几点总结本文对TreeMap的阐明较前几篇文章有些浅尝辄止，TreeMap用的没有HashMap那么多，我们有个宏观上的把我和较量即可。1、TreeMap是按照key举办排序的，它的排序和定位需要依赖较量器或覆写Comparable接口，也因此不需要key覆写hashCode要领和equals要领，就可以解除去反复的key，而HashMap的key则需要通过覆写hashCode要领和equals要领来确保没有反复的key。2、TreeMap的查询、插入、删除效率均没有HashMap高，一般只有要对key排序时才利用TreeMap。3、TreeMap的key不能为null，而HashMap的key可觉得null。注：对TreeSet和HashSet的源码不再举办分解，二者别离是基于TreeMap和HashMap实现的，只是对应的节点中只有key，而没有value，因此对TreeMap和HashMap较量相识的话，对TreeSet和HashSet的领略就会很是容易。
