|
java TreeMap源码解析详解
在介绍TreeMap之前，我们来了解一种数据结构：排序二叉树。相信学过数据结构的同学知道，这种结构的数据存储形式在查找的时候效率非常高。
如图所示，这种数据结构是以二叉树为基础的，所有的左孩子的value值都是小于根结点的value值的，所有右孩子的value值都是大于根结点的。这样做的好处在于：如果需要按照键值查找数据元素，只要比较当前结点的value值即可（小于当前结点value值的，往左走，否则往右走），这种方式，每次可以减少一半的操作，所以效率比较高。在实现我们的TreeMap中，使用的是红黑树（一种优化了的二叉排序树）。
一、TreeMap的超接口
TreeMap主要继承了类AbstractMap（一个对Map接口的实现类）和 NavigableMap（主要提供了对TreeMap的一些高级操作例如：返回第一个键或者返回小于某个键的视图等）。主要的一些操作有：put添加元素到集合中，remove根据键值或者value删除指定元素，get根据指定键值获取某个元素，containsValue查看是否包含某个指定的值，containsKey 查看是否包含某个指定的key数值等。
二、构造函数
TreeMap 的构造函数主要有以下几种：
private final Comparator<? super K> comparator;
public TreeMap() {comparator = null;}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
因为在我们的内部存储结构中，是需要对两个节点的元素的键值进行比较的，所以就必须要实现Comparable接口来具有比较功能。第一个构造函数默认无参，内部将我们的比较器赋值为null，表明：在内部集合中不需要接受来自外部传入的比较器，默认使用Key的比较器（例如：Key是Integer类型就会默认使用它的比较器）。第二种构造函数就是从外部传入指定的比较器，指定TreeMap内部在对键进行比较的时候使用我们从外部传入的比较器。
三、内部存储的基本原理
从源码中摘取部分代码，能说明内部结构即可。
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int modCount = 0;
//静态成员内部类
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
.........
}
从代码中，我们可以很容易的看出来，内部包含一个 comparator 比较器（或值被置为Key的比较器，或是被置为外部传入的比较器），根结点 root （指向红黑树的跟结点），记录修改次数 modCount （用于对集合结构性的检查和前面文章说的一样），还有一个静态内部类（其实可以理解为一个树结点），其中有存储键和值的key和value，还有指向左孩子和右孩子的“指针”，还有指向父结点的“指针”，最后还包括一个标志 color（这个暂时不用知道）。也就是说，一个root指向树的跟结点，而这个跟根结点又链接为一棵树，最后通过这个root可以遍历整个树。
四、put添加元素到集合中
在了解了TreeMap的内部结构之后，我们可以看看他是怎么将一个元素结点挂到整棵树上的。由于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) {
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);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comps-cn-hangzhou.aliyuncs.com/jb/2426819-f1fd59b151fbac8472b39c7de4f02344.png" title="">
第三种情况，找到待删结点的后继结点将后继结点替换到待删结点并删除后继结点（将问题转换为删除后继结点，通过前面两种可以解决）
找到后继结点
替换待删结点
删除后继结点
下面我们看代码：
/*代码虽多，我们一点一点看*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
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;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
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;
}
}
}
首先，判断待删结点是否具有两个孩子，如果有调用函数 successor返回后继结点，并且替换待删结点。对于这条语句：Entry>K,V< replacement = (p.left != null ? p.left : p.right); ，我们上述的三种情况下replacement的取值值得研究，如果是第一种情况（叶子结点），那么replacement取值为null，进入下面的判断，第一个if过，第二个判断待删结点是否是根结点（只有根结点的父结点为null），如果是说明整个树只有一个结点，那么直接删除即可，如果不是根结点就说明是叶子结点，此时将父结点赋值为null然后删除即可。
对于第二种情况下（只有一个孩子结点时候），最上面的if语句是不做的，如果那一个结点是左孩子 replacement为该结点，然后将此结点跳过父结点挂在待删结点的下面，如果那一个孩子是右孩子，replacement为该结点，同样操作。
第三种情况（待删结点具有两个孩子结点），那肯定执行最最上面的if语句中代码，找到后继结点替换待删结点（后继结点一定没有左孩子），成功的将问题转换为删除后继结点，又因为后继结点一定没有左孩子，整个问题已经被转换成上述两种情况了，（假如后继结点没有右孩子就是第一种，假如有就是第二种）所以replacement = p.right，下面分情况处理。删除方法结束。
小结一下，删除结点难点在于删除指定键值的结点，主要分为三种情况，叶子结点，一个孩子结点，两个孩子结点。而对于不同的情况，jdk编写者将最难的两个孩子结点转换为前两种较为简单的方式，可见大神之作。钦佩。
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！ | 
转播
