一、基本概念
在介绍TreeMap之前，我们来了解一种数据结构：二叉树。相信学过数据结构的同学知道，这种结构的数据存储形式在查找的时候效率非常高。
二叉树结构（源自百度百科）
二叉树结构又可再细分为二叉查找树 叉平衡树
二叉查找树
二叉查找树是一种有序的树，所有的左孩子的value值都是小于右孩子的value值的。这样做的好处在于：如果需要按照键值查找数据元素，只要比较当前结点的value值即可（小于当前结点value值的，往左走，否则往右走），这种方式，每次可以减少一半的操作，所以效率比较高。
比二叉查找树更进一步的是二叉平衡树，二叉平衡树除了保证有序外，还能够保持每个节点左右子树的高度相差不超过1。常见的平衡树有AVL树，Treap，红黑树，伸展树，等等。
红黑树是在每个节点上增加一个存储位表示节点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
在TreeMap中，即是使用了红黑树。(上篇文章的末尾，我们提到了HashMap在一个数组槽位里链表长度过长时，也会把链表转为红黑树来存储数据）
二、构造函数
先来看下TreeMap的构造方法。TreeMap一共有4个构造方法。
1、无参构造方法
public TreeMap() {comparator = null;}
采用无参构造方法，不指定比较器，这时候，排序的实现要依赖key.compareTo()方法，因此key必须实现Comparable接口，并覆写其中的compareTo方法。
2、带有比较器的构造方法
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
采用带比较器的构造方法，这时候，排序依赖该比较器，key可以不用实现Comparable接口。
3、带Map的构造方法
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
该构造方法同样不指定比较器，调用putAll方法将Map中的所有元素加入到TreeMap中。putAll的源码如下：
// 将map中的全部节点添加到TreeMap中
public void putAll(Map<? extends K, ? extends V> 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);
}
显然，如果Map里的元素是排好序的，就调用buildFromSorted方法来拷贝Map中的元素，这在下一个构造方法中会重点提及，而如果Map中的元素不是排好序的，就调用AbstractMap的putAll(map)方法，该方法源码如下：
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
很明显它是将Map中的元素一个个put（插入）到TreeMap中的，主要因为Map中的元素是无序存放的，因此要一个个插入到红黑树中，使其有序存放，并满足红黑树的性质。
4、带有SortedMap的构造方法
public TreeMap(SortedMap<K, ? extends V> m) {
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中。
三、内部存储的基本原理
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 = null;
// 右孩子
Entry<K,V> right = null;
// 父节点
Entry<K,V> parent;
// 当前节点颜色
boolean color = BLACK;
// 构造函数
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
从代码中，我们可以很容易的看出来，内部包含一个 comparator 比较器（或值被置为Key的比较器，或是被置为外部传入的比较器），根结点 root （指向红黑树的根节点），记录修改次数 modCount （用于对集合结构性的检查），还有一个静态内部类（其实可以理解为一个树结点），其中有存储键和值的key和value，还有指向左孩子和右孩子的“指针”，还有指向父结点的“指针”，最后还包括一个标志 color。也就是说，一个root指向树的根节点，而这个根结点又链接为一棵树，最后通过这个root可以遍历整个树。
四、put添加元素到集合中
在了解了TreeMap的内部结构之后，我们可以看看他是怎么将一个元素结点挂到整棵树上的。
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;
// 找出(key, value)在二叉排序树中的插入位置。
// 红黑树是以key来进行排序的，所以这里以key来进行查找。
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 = (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);
}
// 为（key-value）新建节点
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 插入新的节点后，调用fixAfterInsertion调整红黑树。
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
首先判断根结点是否是空的，如果是空的直接创建一个结点并将parent赋null，将其作为该树的根节点，返回null跳过余下代码。如果跟结点不是空的，就去判断 comparator 是否为null（也就是判断comparator的值是默认key的比较器还是外部传入的比较器），如果comparator的值是外部传入的，通过循环比较key的值计算将要添加的结点的位置（过程中如果发现有某个结点的key值和将要添加的key的值相等，说明这是修改操作，修改其value值返回旧value值）。
如果在创建对象的时候并没有从外部传入比较器，首先判断key的值是否为null（如果是就抛出空指针异常），那有人说：为什么要对key是否为空做判断呢？上面不是也没有做判断么？ 答案是：如果 comparator 是外部传入的，那么没问题，但是如果是key的默认比较器，那如果key为null 还要调用比价器 必然抛空指针异常。接下来做的事情和上面一样的。
程序执行到最后了，我们要知道一点的是：parent指向的是最后一个结点也就是我们将要添加的结点的父结点。最后根据key和value和parent创建一个节点，然后根据上面的判断确定此结点是左孩子还是右孩子。
这个方法中有一个 fixAfterInsertion(e); 调用这个函数可以将我们刚刚创建完成之后的树通过挪动重新构建成红黑树。
最后总结一下整个put方法的执行过程：
判断此树是否是空的，空树的操作就很简单了
判断比较器的来源做不同的操作（比较value值确定位置）
构建新结点挂上树
调用方法重构红黑树
其中，我们要区分一点的是，为什么有时候返回的null，有时候返回的是旧结点的value，主要区别还是在于，put方法作为添加元素和修改元素的两种功能，添加元素的时候统一返回的是null，修改元素的时候统一返回的是别修改之前的元素的value。
五、根据键的值删除结点元素
了解完put操作的实现后，我们再来看删除操作的实现。首先看remove方法：
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
删除的操作主要是两个操作的结合，一是获取指定元素getEntry(key)，一个是删除指定元素deleteEntry(p)。我们先看如何获取指定元素。
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;
}
这段代码不难理解，依然是根据比较器的来源分两种情况（由于两种情况下的处理方式类似，此处指具体说其中一种），p指向根结点root，循环遍历，比较key和当前循环到的key是否相等，不相等就根据大小向左或者向右，如果相等执行return p; 返回此结点。如果整棵树遍历完成之后，没有找到指定键值的结点就会返回null表示未找到该结点。这就是查找方法。
下面我们看看删除指定结点的方法。
在看代码之前我们先了解一下整体的思路，将要删除的结点可能有以下三种情况：
- 该结点为叶子结点，即无左孩子和右孩子
- 该结点只有一个孩子结点
- 该结点有两个孩子结点
第一种情况，直接将该结点删除，并将父结点的对应引用赋值为null
第二种情况，跳过该结点将其父结点指向这个孩子结点
情况二
第三种情况，找到待删结点的后继结点将后继结点替换到待删结点并删除后继结点（删除方式和第二种情况一样）
情况三
下面我们看代码：
/*代码虽多，我们一点一点看*/
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返回后继结点，就是大于待删除节点中最小的那个节点
源码如下：
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
对于这条语句：Entry>K,V< replacement = (p.left != null ? p.left : p.right); ，我们上述的三种情况下replacement的取值值得研究，如果是第一种情况（叶子结点），那么replacement取值为null，进入下面的判断，第一个if过，第二个判断待删结点是否是根结点（只有根结点的父结点为null），如果是说明整个树只有一个结点，那么直接删除即可，如果不是根结点就说明是叶子结点，此时将父结点赋值为null然后删除即可。
对于第二种情况下（只有一个孩子结点时候），最上面的if语句是不做的，如果那一个结点是左孩子 replacement为该结点，然后将此结点跳过父结点挂在待删结点的下面，如果那一个孩子是右孩子，replacement为该结点，同样操作。
第三种情况（待删结点具有两个孩子结点），那肯定执行最最上面的if语句中代码，找到后继结点替换待删结点（后继结点一定没有左孩子），成功的将问题转换为删除后继结点，又因为后继结点一定没有左孩子，整个问题已经被转换成上述两种情况了，（假如后继结点没有右孩子就是第一种，假如有就是第二种）所以replacement = p.right，下面分情况处理。删除方法结束。
总结：
本文对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的理解就会非常容易。
转自：https://blog.csdn.net/woshimaxiao1/article/details/83748227
网友评论