Java 集合深入理解 （十七） ：TreeMap源码研究如何达到快速排序和高效查找
2021/6/18 11:27:10
本文主要是介绍Java 集合深入理解 （十七） ：TreeMap源码研究如何达到快速排序和高效查找，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
前言
TreeMap是一个能比较元素大小的Map集合，会对传入的key进行了大小排序。其中，可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序；应用在需要排序的场景；其次说到排序的数据结构，肯定会想到PriorityQueue，也是排序的数据结构，但底层实现是数组，并采用最小顶堆的算法实现的；而我们的treemap则采用红黑树的方式进行存储数据，不采用最小顶堆算法（经过排序的完全二叉树）进行实现，具体看源码进行分析。
示例
public static void main(String[] args) {
System.out.println("----------------treemap---------------");
TreeMap< String, String> tm=new TreeMap<String, String>();
tm.put("9", "9");
tm.put("1", "1");
tm.put("3", "3");
tm.put("5", "5");
tm.put("8", "8");
tm.put("2", "2");
tm.keySet().forEach(k->{
System.out.println(k);
});
System.out.println("----------------treemap Comparator---------------");
TreeMap< String, String> tms=new TreeMap<String, String>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return Integer.valueOf(o1)>Integer.valueOf(o2)?1:-1;
}
});
tms.put("11", "11");
tms.put("23", "23");
tms.put("54", "54");
tms.put("25", "25");
tms.put("45", "45");
tms.put("99", "99");
tms.keySet().forEach(k->{
System.out.println(k);
});
}
----------------treemap---------------
1
2
3
5
8
9
----------------treemap Comparator---------------
11
23
25
45
54
99
从上面例子来看我们两种方式去实现的
- 对于treemap中添加数据时，就会转换成红黑树 并使用传入参数默认compareTo 方法进行对比数据
- 然后对于自定的对比标准，需要实现Comparator 类中的compare 方法
- 从这个小例子就可以看出 ，按照key进行排序，在迭代时可以快速的访问数据
红黑树
红黑树（RBT）的定义：它或者是一棵空树，是具有特殊性质的平衡二叉查找树
- 节点非红即黑。
- 根节点是黑色
- 所有null结点称为叶子节点，且认为颜色为黑色
- 所有红节点的子节点都为黑色
- 从任意节点到其叶子节点 的所有路径上都包含相同数目的黑节点。
如果单从实现功能来说，treemap可以采用顺序二叉查找树即可，当然也可以使用avl平衡二叉树实现。至于为什么使用红黑树实现，也在于红黑树的特殊性质来选择的。 很大一部分来说，应该是性质决定的
红黑树对平衡树的一种改进，任意一个节点，它的红黑树的间隔不超过一倍，但它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。
- 红黑树需要维持颜色变更，因此 插入和删除保持为 O（log n)）次；
- avl树需要维持任何节点的两个子树最大差别为1；因此总的来说，建树复杂度为O(NlogN)
- 红黑树是二叉排序树，因此可以采用中序遍历法，进行遍历出排序好的数据
比如如何插入结点 ，以及删除结点 维持红黑树的平衡，涉及到保持特性而做的左旋或者右旋，颜色的变化，可以看一下我这篇对红黑树的解析
特化的AVL树之红黑树学习及原理解析
整个treemap的实现就是基于红黑树而实现的，所以弄清楚红黑树的原理是研究源码的基础
注释分析
/**
*基于红黑树的{@link NavigableMap}实现。地图是根据{@linkplain可比自然图排序的它的键的}排序，或者由map提供的{@link Comparator}排序创建时间，取决于使用的构造函数。
*<p>此实现为{@code containsKey}、{@code get}、{@code put}和{@code remove}操作。算法是Cormen、Leiserson和Rivest的<em>算法简介</em>。
*
*<p>请注意，树映射维护的排序与任何排序的映射一样，以及无论是否提供显式比较器，都必须<em>一致如果要正确实现{@code Map}接口(请参阅{@code Comparable}或{@code Comparator}以获取
*<em>的精确定义与equals一致（这是因为{@code Map}接口是根据{@code equals}定义的操作，但排序映射使用其{@code执行所有键比较compareTo}（或{@code compare}）方法，因此
*从排序图的观点来看，这种方法是相等的。行为一个排序映射<em>的定义是</em>的，即使它的排序是与{@code equals}不一致；它就是不遵守总承包合同{@code Map}接口的。
*
*<p><strong>请注意，此实现不同步。</strong>如果多个线程同时访问一个映射，则线程在结构上修改映射，它必须同步外部(结构修改是添加或删除删除一个或多个映射；只是改变了相关的价值
*使用现有密钥不是结构修改。）这是通常通过在某个对象上同步来完成封装地图。如果不存在这样的对象，则应该使用
*{@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}方法。这最好在创建时完成，以防止意外对地图的非同步访问：<pre>SortedMap m=Collections.synchronizedSortedMap（新树映射（…））</预处理>
*
*<p>集合的{@code iterator}方法返回的迭代器所有此类的“集合视图方法”返回的<em>快速失败</em>：如果映射在迭代器是以任何方式创建的，除了通过迭代器自己的
*{@code remove}方法，迭代器将抛出一个{@链接ConcurrentModificationException}。因此，面对修改后，迭代器会快速而干净地失败，而不是冒着
*未来某个未定时间内的任意、不确定性行为。
*
*<p>请注意，不能保证迭代器的快速失败行为一般说来，不可能在未来作出任何硬性保证存在未同步的并发修改。失败快速迭代器
*尽最大努力抛出{@code ConcurrentModificationException}。因此，编写依赖于此的程序是错误的其正确性例外：<em>迭代器的快速失败行为应该只用于检测错误</em>
*
*<p>此类中的方法返回的所有{@code Map.Entry}对它的视图表示映射创建时的快照生产。它们不支持{@code Entry.setValue}方法(但是请注意，可以在使用{@code put}关联的映射。）
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
*
* @author Josh Bloch and Doug Lea
* @see Map
* @see HashMap
* @see Hashtable
* @see Comparable
* @see Comparator
* @see Collection
* @since 1.2
*/
全篇注释大概的意思在于
- 基于红黑树的NavigableMap 实现，可根据对象的键值进行排序，或者提供的Comparator 进行排序，构造函数时可以设置
- 树映射维护的排序与任何排序的映射一样，以及无论是否提供显式比较器，都必须实现Comparable 接口，定义好equals操作
- 这个实现是不同步的，多线程访问的情况下，会出现数据不一致的情况，因此最好使用Collections.synchronizedSortedMap} 方法控制同步
- 所提供的迭代器也会使用快速失败机制保证数据的安全性
- 不支持Entry.setValue 方法
接口实现
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
通过继承AbstractMap 对map的实现，说明treemap 是一个key-value的存储格式，并且具有map的基本操作 包括put等方法；然后实现NavigableMap ，这个接口 继承SortedMap 接口，会有很多排序的方法treemap实现，然后Cloneable 和Serializable 实现是可以被序列化的，所有集合都是可被序列，实现 serializble，我相信都会做transient 进行序列化传输时的优化
类的属性分析
/**
* 用于维护此树映射中的顺序的比较器，或
* 如果它使用密钥的自然顺序，则为null。
*
* @serial
*/
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
/**
* 树中的条目数
*/
private transient int size = 0;
/**
* 树的结构修改数。
*/
private transient int modCount = 0;
几个属性分析
- comparator 比较器，用于构成二叉排序树时，对比元素的大小
- size记录整个红黑树的数据大小
- modcount记录操作红黑树的修改大小
- root属性存储数据，是一个红黑树，记录好根结点，我们在根据root进行分析基本结点；包括我们需要存储的数据 key 和value值，然后构成 树的存储结构 左子树 ，右子树，父结点 、以及 红黑树所需属性颜色结点；
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;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
- 在结点中，构造方法中只有父结点，而子节点如何构造出来，是在使用时会将属性赋值，并没有提供方法进行设置
-
transient 非私有以简化嵌套类访问 避免传输时不必要的空间占用
被transient修饰的变量不参与序列化和反序列化；而且属性是实现了Serializable说明他能够被序列化和反序列化传输的；后来查阅了一些资料了解到：
，假如root的长度为10，而其中只有5个元素，那么在序列化的时候只需要存储5个元素，而数组中后面5个元素是不需要存储的。于是将elementData定义为transient，避免了Java自带的序列化机制，并定义了两个方法writeObject和readObject，实现了自己可控制的序列化 什么是writeObject 和readObject？可定制的序列化过程
构造方法分析
无参构造方法
public TreeMap() {
comparator = null;
}
当采用无参构造产生对象时，会将比较器设置为null,而采用key进行比较顺序
有参构造方法
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
采用外部传输比较器，当然比较器的类型和key值类型相同，也可以传空和无参构造相同；其中包括直接传入map，和传入 SortedMap 这个也是进行设置
查询操作
其中包含的方法有 size 、 containsKey 、containsValue、get 方法、以及获取 比较器 、 firstKey、lastKey 、getEntry 方法 getCeilingEntry 方法、getFloorEntry 方法、等等
getEntry(key)方法 根据 key来获取entry
该方法作为 containsKey(key) 和 get(key)方法 和 remove方法的基础， 从代码层面去看如何实现的
- containsKey 通过方法获取到数据判断是否为空，如果不为空则返回true
- get(key) 通过方法获取到结点数据
- remove（key） 则根据方法获取结点判断数据是否为空，在判断是否删除
从代码来看是两种 情况
- 走无比较器的逻辑则采用的是，获取 根节点，采用key的比较器进行比较获取到数据，不知道你们发现没有，这个看起来和平衡二叉树进行平衡，或者查找二叉树的结点很像
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;
- 走有比较器的情况，会走到 getEntryUsingComparator 方法中 这个方法和无设置比较器上的区别在与是否使用比较器进行对比。其他遍历方案是一样的。
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
getFirstEntry 方法 获取第一个数据
首先这里的获取第一个数据并不是树的root结点，而是获取的左子树的的左边结点，根据二叉排序树的性质来说，这里获取到的是整个树中值最小的结点
- 为什么抽象出这个方法，我们需要遍历整个红黑树，而在之前我在分析红黑树时，遍历红黑树可以采用前序中序 后续进行打印整个树，但这里不是采用的 二叉树的应用分治法进行处理的。而是获取首个结点，而这里的遍历方法就采用的时候获取到左边结点，在获取 比左边结点大的下一个数据。这样更方便代码阅读，虽然代码量相对于递归来看会麻烦一些
- getFirstEntry() 方法 获取到 最小结点
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
- containsValue(Object value)方法中 遍历所有数据进行 结合 getfirstentry方法和 successor方法的
public boolean containsValue(Object value) {
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
- successor(Entry<K,V> t) 方法获取当前结点的下一个结点
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;
}
}
- firstKey() 方法 这是在排序时需要获取的方法，结合 getFirstEntry 去获取到key值
public K firstKey() {
return key(getFirstEntry());
}
- firstEntry（）方法这里 导出的对象 是一个新的对象，并且是 natvigableMap api method 方法
public Map.Entry<K,V> firstEntry() {
return exportEntry(getFirstEntry());
}
- 这里面包括获取key的迭代器 keyIterator （），pollFirstEntry 导出 数据，都是来自这个方法的 ，我就分析了，如果各位感兴趣可以看看源码 ValueIterator
getLastEntry() 获取最大的数据
经过上面的解析查询数据，大概也知道了获取结尾的节点了把，上面的是left ，那这边肯定是right了，虽然源码没有通过lastentry去遍历查找key对象，但是我想也可以有这样的方法去查找
final Entry<K,V> getLastEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.right != null)
p = p.right;
return p;
}
- 当然上面有firstkey方法 ，那我们这里有lastKey 方法用获取 lastkey 和 lastEntry
public K lastKey() {
return key(getLastEntry());
}
public Map.Entry<K,V> lastEntry() {
return exportEntry(getLastEntry());
}
successor 和predecessor方法
这两个方法分别对应当前节点的下一个结点，和上一个结点，我在分析containsValue 方法时，分析过 successor 方法，可以看看上面，这里我就不多说
- predecessor 方法一看和successor 差别点 就在 于 判断左结点是否为空，
static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.left != null) {
Entry<K,V> p = t.left;
while (p.right != null)
p = p.right;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.left) {
ch = p;
p = p.parent;
}
return p;
}
}
平衡操作
put(K key, V value) 方法 用于添加数据
- 根节点为空，添加某个结点，默认结点则为黑色，并且当前结点的子结点及父结点都为空，将新结点赋值给根结点 ，这里就能看出 key值是一定不能为空的
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // key值判断是否为空
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
- 当根结点不为空时，这里先做的是二叉排序树进行插入结点 ，如果不清楚怎么二叉排序树，可以看看我之前分析的二叉排序树
二叉排序树学习构建方式及如何遍历二叉排序树
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 = (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);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
这里做了个拆分开 有比较器和无比较器的情况
- 由上图我们就可以看出破坏了红黑树的性质，我们肯定是要进行重新颜色平衡的，就涉及到下面的代码
fixAfterInsertion(e);
size++;
modCount++;
fixAfterInsertion 方法 （插入后固定 方法）
理解这个方法之前，你一定要理解红黑树是如何平衡的，要不然你可能有点蒙
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
- 把 当前插入结点变红 ，判断是否继续平衡，如果是插入我上面的结点则直接就平衡了，最后把根 结点染黑
x.color = RED;
- 这里判断平衡的方式，x == null || x == root || x.parent.color ！= RED 主要是判断 父结点是否为黑色，则该树就平衡，这样来看是不是和avl树对比起来简单很多
- colorOf(Entry<K,V> p)方法获取 到结点的颜色，parentOf(Entry<K,V> p)方法 获取到父结点的方法，setColor(Entry<K,V> p, boolean c) 设置 结点为某个颜色，leftOf(Entry<K,V> p) 获取该结点的左结点，以及rightOf(Entry<K,V> p) 获取结点的右子结点
private static <K,V> boolean colorOf(Entry<K,V> p) {
return (p == null ? BLACK : p.color);
}
private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
return (p == null ? null: p.parent);
}
private static <K,V> void setColor(Entry<K,V> p, boolean c) {
if (p != null)
p.color = c;
}
private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
return (p == null) ? null: p.left;
}
private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
return (p == null) ? null: p.right;
}
- 对于红黑树的平衡，是判断的是叔叔结点的颜色，代码不多但是要理解算法的含义很有必要的
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
- 父节点是祖父节点的左孩子 祖父节点的另一个子节点（叔叔节点）是红色
对策： 将当前节点的父节点和叔叔节点涂黑，祖父节点涂红，把当前节点指向祖父节点，从新的当前节点开始算法
n节点代表 当前节点 p 代表父亲节点 g 代表祖父节点 u代表叔叔节点
- 插入节点的父节点是红色 ，父节点是祖父节点的左孩子；叔叔节点是黑色，当前节点是其父节点的右孩子
对策： 以当前父节点为支点左旋，当前节点的左节点做为新的当前节点。
- 插入节点的父节点是红色 ，父节点是祖父节点的左孩子；叔叔节点是黑色，当前节点是其父节点的左孩子
对策：父节点变为黑色，祖父节点变红色，再父节点为支点进行右旋
左旋操作
在平衡的情况下涉及到结点进行左旋
public void rotateLeft(Node<E> x){
if(x!=null){
Node<E> y=x.right;//先取到Y
//1.把h作为X的右孩子 x.right=h
x.right=y.left;
//2.h不为空 ，则将h的父亲设置为 x
if(y.left!=null){
y.left.parent=x;
}
//3。把Y移到原来X的位置上 y的父亲修改为 x的父亲
y.parent=x.parent;
// 4.x父亲为空
if(x.parent==null){
//设置根节点为y节点
root=y;
}else{
//x父亲不为空，则需要判断 x是父亲的左孩子还是右孩子 将父的左孩子或者右孩子设置为y
if(x.parent.left==x){
x.parent.left=y;
}else if(x.parent.right==x){
x.parent.right=y;
}
}
//3.X作为Y的左孩子
y.left=x;
x.parent=y;
}
}
整个左旋操作还是很简单的，基本就是通过链表前后断链并重新链接实现的 需要结合代码看一下，在代码上备注了有的
- 先取到Y 把h作为X的右孩子 x.right=h
- h不为空 ，则将h的父亲设置为 x
- 把Y移到原来X的位置上 y的父亲修改为 x的父亲
- x父亲为空 设置根节点为y节点
- x父亲不为空，则需要判断 x是父亲的左孩子还是右孩子 将父的左孩子或者右孩子设置为y
- X作为Y的左孩子
右旋操作
public void rotateRight(Node<E> y) {
if (y != null) {
Node<E> yl = y.left;
//step1
y.left = yl.right;
if (yl.right != null) {
yl.right.parent = y;
}
// step2
yl.parent = y.parent;
if (y.parent == null) {
root = yl;
} else {
if (y.parent.left == y) {
y.parent.left = yl;
} else if (y.parent.right == y) {
y.parent.right = yl;
}
}
// step3
yl.right = y;
y.parent = yl;
}
}
右旋操作 和左旋操作很像
- 首先拿到 y的左节点 x 在拿到 x的右节点 i 用于右旋时，进行移动
- i不为空，则将 i的父节点 设置为 y
- 拿到 y的 父节点 判断是否为根节点 ，不为根节点 则 判断是否y为父节点的左节点 还是有节点 并将父节点的左节点 或右节点 设置为 x 将 x的父节点设置为y的父节点
- 最后将 x的右节点设置为y, y的父节点设置为x 就可以了
remove(Object key) 方法
该方法用来删除key值得某个结点，并返回老得value值
- 通过getEntry 获取到老得entry值，如果为null则直接返回，不为空继续调用deleteEntry 删除结点，并保持平衡
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
deleteEntry 方法
- 进行操作修改及size减少
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
- 在替换节点（如果存在）启动fixup。 主要是做一个替换结点，为后面得平衡做铺垫
Entry<K,V> replacement = (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;
// 取消链接，使它们可以由fixAfterDeletion使用。
p.left = p.right = p.parent = null;
// 修复替换
if (p.color == BLACK)
fixAfterDeletion(replacement);
}
- 只有一个root根结点时，则将root设置为空即可
else if (p.parent == null) { // return if we are the only node.
root = null;
}
- 没有孩子。将self用作幻像替换并取消链接。 这里做得也是 如果是黑结点 ，则需要先平衡在做 数据设置为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;
}
}
fixAfterDeletion 方法，用于平衡删除结点树
这个方法和使用来做删除结点得平衡树得操作，这里就是红黑树删除结点平衡操作
- 只要结点不是根结点 或者 结点得颜色为黑色，就会一直做平衡操作
while (x != root && colorOf(x) == BLACK) {
- 判断x结点为 父亲结点得左右结点
if (x == leftOf(parentOf(x))) {
- 获取到兄弟结点
Entry<K,V> sib = rightOf(parentOf(x));
- 兄弟结点为红色
- 对策：把父节点染成红色，兄弟节点染成黑色，对父节点进行左旋，重新设置x的兄弟节点
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
- 当前节点x 的兄弟节点是黑色 ，被删除节点是父节点的左孩子，兄弟节点的两个孩子都是黑色
对策：将x的兄弟节点设为红色，设置x的父节点为新的x节点
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
}
- 当前节点x 的兄弟节点是黑色 被删除节点是父节点的左孩子，兄弟的右孩子是黑色，左孩子是红色
对策：将x兄弟节点的左孩子设为黑色，将x兄弟节点设置红色，将x的兄弟节点右旋，右旋后，重新设置x的兄弟节点。
- 当前节点x 的兄弟节点是黑色 被删除节点是父节点的左孩子，兄弟节点的右孩子是红色
对策：把兄弟节点染成当前节点父节点颜色，把当前节点父节点染成黑色，兄弟节点右孩子染成黑色，再以当前节点的父节点为支点进行左旋，算法结算
else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
最后将结点设置为黑色
NavigableMap API方法
之前在查找方法中解析过firstEntry 方法和lastEntry 方法 和pollFirstEntry方法和pollLastEntry方法 继续下面的方法解析
getLowerEntry方法（寻找最接近的小于key的Entry，没有找到就返回为null）
作为排序接口的的实现，提供最接近key的方法，方便我们使用
final Entry<K,V> getLowerEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
} else {
if (p.left != null) {
p = p.left;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
这里在查找接近最小值时，利用二叉排序树的特性，如果是小于传入的值，则找右子树，如果等于是，就找父亲，就是最接近的值，while不断的循环找到个值；
System.out.println("----------------treemap lowerKey---------------");
TreeMap< String, String> tmss=new TreeMap<String, String>();
tmss.put("9", "9");
tmss.put("1", "1");
tmss.put("3", "3");
tmss.put("5", "5");
tmss.put("8", "8");
tmss.put("2", "2");
System.out.println(tmss.lowerKey("4"));
----------------treemap lowerKey---------------
3
System.out.println("----------------treemap lowerKey---------------");
TreeMap< String, String> tmss=new TreeMap<String, String>();
tmss.put("9", "9");
tmss.put("1", "1");
tmss.put("3", "3");
tmss.put("5", "5");
tmss.put("8", "8");
tmss.put("2", "2");
System.out.println(tmss.lowerKey("5"));
----------------treemap lowerKey---------------
3
getFloorEntry(K key)方法（从名字来看就是向下取整）
final Entry<K,V> getFloorEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
} else if (cmp < 0) {
if (p.left != null) {
p = p.left;
} else {
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;
}
根据代码进行分析出来我们在 这和getLowerEntry 不太一样的点在于，如果找到了值，就直接返回该值，没有找到才会向下走，这在代码逻辑上就能看到
System.out.println("----------------treemap floorKey---------------");
TreeMap< String, String> tmss=new TreeMap<String, String>();
tmss.put("9", "9");
tmss.put("1", "1");
tmss.put("3", "3");
tmss.put("5", "5");
tmss.put("8", "8");
tmss.put("2", "2");
System.out.println(tmss.floorKey("4"));
----------------treemap floorKey---------------
3
System.out.println("----------------treemap floorKey---------------");
TreeMap< String, String> tmss=new TreeMap<String, String>();
tmss.put("9", "9");
tmss.put("1", "1");
tmss.put("3", "3");
tmss.put("5", "5");
tmss.put("8", "8");
tmss.put("2", "2");
System.out.println(tmss.floorKey("5"));
----------------treemap floorKey---------------
5
getCeilingEntry方法和getHigherEntry方法
根据上两个方法来判断这两个方法 一个是向上取整，和上一个方法，我这里只分析一个，基本就能明白下个方法把，我分析一下getHigherEntry 方法，因为区别都是在于cmp=0时做的逻辑处理
final Entry<K,V> getHigherEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
System.out.println("----------------treemap ceilingKey---------------");
TreeMap< String, String> tmsss=new TreeMap<String, String>();
tmsss.put("9", "9");
tmsss.put("1", "1");
tmsss.put("3", "3");
tmsss.put("5", "5");
tmsss.put("8", "8");
tmsss.put("2", "2");
System.out.println(tmsss.ceilingKey("6"));
----------------treemap ceilingKey---------------
8
迭代器（PrivateEntryIterator）
这个迭代器，我们在分析其他方法时基本也了解整个迭代的操作流程，接下来进行继续分析一下
Entry<K,V> next;
Entry<K,V> lastReturned;
int expectedModCount;
如果您看过其他集合的迭代器，这个我相信很好理解，为什么这么说，next记录当前遍历的结点，lastretruned 记录上一个结点，并防止重复删除 ， expectedmmodcount 则保证数据安全性，快速失败机制，具体是不是我们看一下方法属性
hasNext 判断迭代是否相等
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e);
lastReturned = e;
return e;
}
nextEntry方法 中就是包含了 快速失败机制，及设置上一个结点信息，然后供删除时判断
其他的方法我不在过多的分析，各位如果有想法，可以自己去解析，其他的就比较简单
总结
经过分析treemap，使我也有很大的提升，希望这篇文章对你的提升也很大；如果各位时小白的话，可以按照搞清楚树，和排序二叉树 和avl树 红黑树，然后在来理解treemap，会理解很多，要不然恐怕很难理解其中的原理，共同学习成长，当然各位大牛，希望能指正一下我写的这篇文章，得到提升
这篇关于Java 集合深入理解 （十七） ：TreeMap源码研究如何达到快速排序和高效查找的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门：从零开始的编程之旅
- 2024-11-23Java创业入门：新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门：初学者的简单教程
- 2024-11-23JAVA副业入门：初学者的实战指南
