java map 红黑树_Java源码阅读之TreeMap(红黑树) - JDK1.8

阅读优秀的源码是提升编程技巧的重要手段之一。

如有不对的地方，欢迎指正~

转载请注明出处https://blog.lzoro.com。

前言

开门见山，山外有山，山外有山...

先简单介绍下TreeMap，来看下类关系图。

image

怎么说呢，TreeMap就是一个有序的键值对集合(这介绍有够简单的)。

TreeMap实现了NavigableMap接口， 而NavigableMap则是通过sortedMap间接继承了Map接口，它定义了一系列导航方法，这些Map之外的方法算是和HashMap的不同，另外的不同点还在于顺序性。

关于TreeMap和HashMap的异同点，在接下来的每个章节都可能会提到。

接下来，请坐好，准备发车了。

基础

老规矩，不想上来就整一大堆复杂晦涩的方法，还是先从变量了解起。

成员变量

/**

* comparator用来保持treemap的顺序性

* 如果是null，则采取自然顺序

*

* @serial

*/

private final Comparator super K> comparator;

/**

* 红黑树根节点

*/

private transient Entry root;

/**

* 键值对数量

*/

private transient int size = 0;

/**

* 结构修改次数

*/

private transient int modCount = 0;

从变量可以简单看出treemap跟HashMap有点类似，而不同点在于

HashMap

1、基于哈希桶+链表/红黑树实现

2、无序的

TreeMap

1、基于红黑树实现

2、有序的，通过指定的comparator或者自然顺序

接下来看下构造函数

构造函数

/**

* 空参构造，利用自然排序构造一个空的tree map

* 所有的key，必须实现Comparable接口

* 与此同时，所以的key必须具备可比性，{@code k1.compareTo(k2)}不能抛出{@code ClassCastException}

* 假如你试图放一个违反约束的key到map里面，如：放一个string类型的key到原先存储interger类型key的map里面，将会抛出{@code

*/

public TreeMap() {

comparator = null;

}

/**

* 根据给定的comparator构造一个空的/新的map

* 所有插入到map的key通过comparator比较器必须具备可比性

*(因为提供了comparator比较器，所以key可以不用实现Comparable接口)

*

*

* @param comparator comparator如果为null,则使用自然顺序

*/

public TreeMap(Comparator super K> comparator) {

this.comparator = comparator;

}

/**

* 根据给定个的map和key的自然顺序构造一个空的treemap

*

* 关于key的约束同上。

*

* 方法的时间复杂度为n*log(n)

*

* @param m 要放到treemap中的map

* @throws ClassCastException key不具备可比/排序性则抛此异常

* @throws NullPointerException 指定的map是null则抛NPE

*/

public TreeMap(Map extends K, ? extends V> m) {

comparator = null;

//调用putAll存放m，后续分析

putAll(m);

}

/**

* 根据给定是sortedMap，利用相同的排序方式构造一个新的treemap

*

* 方法以限行时间运行

*

* @param m sortedmap

* @throws NullPointerException 指定的map是null则抛NPE

*/

public TreeMap(SortedMap m) {

//获取sortedmap的comparator

comparator = m.comparator();

try {

//调用buildFromSorted来存放m

buildFromSorted(m.size(), m.entrySet().iterator(), null, null);

} catch (java.io.IOException cannotHappen) {

} catch (ClassNotFoundException cannotHappen) {

}

}

看完了上面几个构造函数，让人印象比较深刻的是对于key的约束说明

不指定comparator时，存放到map里的key必须实现Comparable接口

这里约束目的就是为了利用可比性来维护treemap的顺序性。

上面构造函数中putAll和buildFromSorted没有跟进做具体分析，放置在功能方法里一并介绍。

红黑树

看完变量和构造函数，本来想直接分析功能方法，但是仔细一看，虽然TreeMap里红黑树的代码跟HashMap本质上是一样的，但是代码的结构还是有较大区别，所以先拿来来赏析。(我觉得TreeMap的红黑树代码可读性比HashMap来的高多了)

节点定义

依然是利用一个静态内部类来定义树节点，这里跟HashMap中的定义类似，还是比较浅显易懂，不做太多分析。

static final class Entry implements Map.Entry {

K key;

V value;

Entry left;

Entry right;

Entry parent;

boolean color = BLACK;

/**

* 根据给定的key/value/parent创建一个新的单元节点(黑)

* 子树为null

*

*/

Entry(K key, V value, Entry parent) {

this.key = key;

this.value = value;

this.parent = parent;

}

/**

* 返回key

*

* @return the key

*/

public K getKey() {

return key;

}

/**

* 返回跟key关联的value

*

* @return the value associated with the key

*/

public V getValue() {

return value;

}

/**

* 替换跟key关联的value

*

* @return 返回旧值

*/

public V setValue(V value) {

V oldValue = this.value;

this.value = value;

return oldValue;

}

/**

* 比较

*/

public boolean equals(Object o) {

if (!(o instanceof Map.Entry))

return false;

Map.Entry,?> e = (Map.Entry,?>)o;

return valEquals(key,e.getKey()) && valEquals(value,e.getValue());

}

/**

* hashcode

*/

public int hashCode() {

int keyHash = (key==null ? 0 : key.hashCode());

int valueHash = (value==null ? 0 : value.hashCode());

return keyHash ^ valueHash;

}

/**

* toString

*/

public String toString() {

return key + "=" + value;

}

}

左旋

这里的左旋跟HashMap还是比较相近的，不同点在于HashMap的入参多了一个root来用以指向根节点，而在TreeMap中，root是一个成员变量。

private void rotateLeft(Entry p) {

//null节点忽略

if (p != null) {

//取出p的右子树

Entry r = p.right;

//用r的左子树替换p的右子树

p.right = r.left;

//如果r的左子树存在的话

//则将r的左子树的父节点指向p

if (r.left != null)

r.left.parent = p;

//r的父节点指向p的父节点

//实质上，就是r替换了p的位置

r.parent = p.parent;

//如果p节点不存在父节点

if (p.parent == null)

//那么替换了p节点后的r就是根节点

root = r;

else if (p.parent.left == p)

//如果p的父节点存在且p是左子树

//则将替换p后的r设置为左子树

p.parent.left = r;

else

//否则设置为右子树

p.parent.right = r;

//p变成r的左子树

r.left = p;

//修改引用

p.parent = r;

}

}

右旋

private void rotateRight(Entry p) {

//null节点忽略

if (p != null) {

//取出p的左子树l

Entry l = p.left;

//用l的右子树替换p的左子树

p.left = l.right;

//如果l人右子树存在

//则将l的右子树的父节点指向p

if (l.right != null) l.right.parent = p;

//交换l和p的位置

l.parent = p.parent;

//如果p的父节点不存在

if (p.parent == null)

//那么替换了p节点后的l就是根节点

root = l;

else if (p.parent.right == p)

//如果p的父节点存在，且p是原右子树

//则将替换p后的l设置为右子树

p.parent.right = l;

//否则设置为左子树

else p.parent.left = l;

//修改引用

l.right = p;

p.parent = l;

}

}

插入平衡

插入平衡方法的实现就是我所说的，我觉得比HashMap可读性强的方法。TreeMap把节点的关系操作封装成独立方法了，比如获取父节点、左子树、右子树等，会让含义很清晰，如果类似于HashMap是通过引用方式的话，很容易源码看着看着就晕乎乎了。

/** From CLR */

private void fixAfterInsertion(Entry x) {

//新节点都为红色

x.color = RED;

//x存在且c不是根节点且x的父节点为红色

while (x != null && x != root && x.parent.color == RED) {

//如果x的父节点是祖父节点的左子树的话

if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {

//取出祖父节点的右子树

Entry y = rightOf(parentOf(parentOf(x)));

//判断祖父节点右子树是否为红色

if (colorOf(y) == RED) {

//红色

//将父节点变成黑色

setColor(parentOf(x), BLACK);

//祖父节点的右子树变成黑色

setColor(y, BLACK);

//祖父节点变成红色

setColor(parentOf(parentOf(x)), RED);

//将x的引用指向祖父节点

x = parentOf(parentOf(x));

} else {

//祖父节点右子树为黑色

//x节点是父节点的右子树

if (x == rightOf(parentOf(x))) {

//x引用指向父节点

x = parentOf(x);

//左旋

rotateLeft(x);

}

//将x的父节点变成黑色

setColor(parentOf(x), BLACK);

//x的祖父节点变成红色

setColor(parentOf(parentOf(x)), RED);

//右旋

rotateRight(parentOf(parentOf(x)));

}

} else {

//如果x的父节点是祖父节点的右子树的话

//取出祖父节点的左子树

Entry 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 {

//祖父节点左子树为红色

//入股x是父节点的左子树

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;

}

删除平衡

删除平衡也是类似的，代码书写比较规范，为了凸显我懒，就不添加注释了，把代码贴出来，有缘人自行参悟。

/** From CLR */

private void fixAfterDeletion(Entry x) {

while (x != root && colorOf(x) == BLACK) {

if (x == leftOf(parentOf(x))) {

Entry sib = rightOf(parentOf(x));

if (colorOf(sib) == RED) {

setColor(sib, BLACK);

setColor(parentOf(x), RED);

rotateLeft(parentOf(x));

sib = rightOf(parentOf(x));

}

if (colorOf(leftOf(sib)) == BLACK &&

colorOf(rightOf(sib)) == BLACK) {

setColor(sib, RED);

x = parentOf(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;

}

} else { // symmetric

Entry sib = leftOf(parentOf(x));

if (colorOf(sib) == RED) {

setColor(sib, BLACK);

setColor(parentOf(x), RED);

rotateRight(parentOf(x));

sib = leftOf(parentOf(x));

}

if (colorOf(rightOf(sib)) == BLACK &&

colorOf(leftOf(sib)) == BLACK) {

setColor(sib, RED);

x = parentOf(x);

} else {

if (colorOf(leftOf(sib)) == BLACK) {

setColor(rightOf(sib), BLACK);

setColor(sib, RED);

rotateLeft(sib);

sib = leftOf(parentOf(x));

}

setColor(sib, colorOf(parentOf(x)));

setColor(parentOf(x), BLACK);

setColor(leftOf(sib), BLACK);

rotateRight(parentOf(x));

x = root;

}

}

}

setColor(x, BLACK);

}

罗列TreeMap的红黑树相关代码，是想说明TreeMap里面的实现比起HashMap可读性更为强一些，但是其实质都是一样的，所以上面关于插入平衡和删除平衡的过程这里不再细说，之前格子的Java源码阅读之红黑树在HashMap中的应用 - JDK1.8这篇博客里面有过步骤的相关描述，也有一些图解，有兴趣的可以了解一下。

功能方法

接下来看下相关功能方法，看下我们平时所使用的方法内部是怎么实现的。

put

将指定的键值对存放到TreeMap，不同于HashMap将元素通过HashCode分散到哈希桶里面，TreeMap是通过比较器/自然顺序的形式将元素存放到红黑树中来保证有序性。

下面开始分析put方法。

/**

* 存放指定的键值对

* 如果指定的key存在，旧的value将会被新的替换

*

* @param key key with which the specified value is to be associated

* @param value value to be associated with the specified key

*

* @return 旧的value值{@code key}, 如果之前不存在，则返回null

* (返回null也有可能key对应的值是null)

* @throws ClassCastException 指定的key不具备可比性的话则抛此异常

* @throws NullPointerException 使用自然排序时指定的key为null/comparator不允许null的key，则抛NPE

*

*/

public V put(K key, V value) {

//根节点

Entry t = root;

//如果根节点还不存在(TreeMap是空的)

if (t == null) {

//这里的比较做一个类型检查

//可能null

compare(key, key); // type (and possibly null) check

//初始化一个节点

root = new Entry<>(key, value, null);

//size + 1

size = 1;

//修改计数 + 1

modCount++;

//返回null

return null;

}

//如果TreeMap不为空

//定义比较值

int cmp;

//定义父节点

Entry parent;

// 分离Comparator和比较路径

Comparator super K> cpr = comparator;

//如果存在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

//如果找到相同的key，则替换值后返回

return t.setValue(value);

} while (t != null);

}

//不存在比较器，则采用自然顺序比较

else {

//自然顺序比较不允许key为null

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 e = new Entry<>(key, value, parent);

//根据比较结果，来决定将节点放置在左边还是右边

if (cmp < 0)

parent.left = e;

else

parent.right = e;

//插入平衡

fixAfterInsertion(e);

//size + 1

size++;

//修改计数 + 1

modCount++;

//返回null(执行到这一步，证明未找到相同的key，如果有，则在上面就return了)

return null;

}

看完了put的，再把之前构造函数中的未加分析的putAll一并阅读(完全无违和感)。

/**

* 将指定map中的元素都存放到当前treemap

*

* @param map map

* @throws ClassCastException key不合法(参照构造函数章节)

* @throws NullPointerException 指定的map为null/或者存在null的key且treemap不允许null-key的情况下抛出NPE

*/

public void putAll(Map extends K, ? extends V> map) {

//获取大小

int mapSize = map.size();

//treemap为空且指定的map不为空并且map是可排序的map

if (size==0 && mapSize!=0 && map instanceof SortedMap) {

//获取Comparator

Comparator> c = ((SortedMap,?>)map).comparator();

//判断Comparator是否跟当前的一致

if (c == comparator || (c != null && c.equals(comparator))) {

//操作计数 + 1

++modCount;

try {

//调用buildFromSorted进行处理

buildFromSorted(mapSize, map.entrySet().iterator(),

null, null);

} catch (java.io.IOException cannotHappen) {

} catch (ClassNotFoundException cannotHappen) {

}

return;

}

}

//调用父类的putAll

super.putAll(map);

}

通过分析以上的代码，可以看出putAll里面的逻辑还是比较简单的，一是判断当前treemap是否为空，且给定map的大小合法，并且是给定的map是SortedMap的实例if (size==0 && mapSize!=0 && map instanceof SortedMap)。

如果是，则取出比较器判断后调用buildFromSorted进行处理

如果不是，则调用父类的putAll进行处理。

这里留有两个疑问，buildFromSorted和父类的putAll究竟做了哪些处理来完成集合元素的存放呢？

下面一步步分析，先从父类的putAll看起 。

/**

* {@inheritDoc}

* 嗯，懒得翻译了，反正我翻译水平也比较差。

*

* @implSpec

* This implementation iterates over the specified map's

* entrySet() collection, and calls this map's put

* operation once for each entry returned by the iteration.

*

*

Note that this implementation throws an

* UnsupportedOperationException if this map does not support

* the put operation and the specified map is nonempty.

*

* @throws UnsupportedOperationException {@inheritDoc}

* @throws ClassCastException {@inheritDoc}

* @throws NullPointerException {@inheritDoc}

* @throws IllegalArgumentException {@inheritDoc}

*/

public void putAll(Map extends K, ? extends V> m) {

for (Map.Entry extends K, ? extends V> e : m.entrySet())

put(e.getKey(), e.getValue());

}

是不是一目了然了。如果上面提到的判断if (size==0 && mapSize!=0 && map instanceof SortedMap)不成立，则调用父类的putAll方法：通过循环，将元素一个个放到treemap当中，这里的放置put就是在本章节开头分析的put方法。

那么，还剩下一个疑问，如果上面的判断成立，buildFromSorted又做了哪些操作呢？

/**

*

* 线性时间的树构造算法(根据排序数据)

* 可以从迭代器/流当中接受键值对

* 有很多方法入参，但是似乎还是比其他选择更好(PS:我也不知道其他选择是什么)

*

* 该方法接受的4种格式说明：

*

* 1) Map.Entries迭代器. (it != null, defaultVal == null).

* 2) key的迭代器. (it != null, defaultVal != null).

* 3) 交替序列化的键值对流.(it == null, defaultVal == null).

* 4) 序列化的键流. (it == null, defaultVal != null).

*

* 假设调用此方法前comparator已经被设置

*

* @param size 键/或者键值对的数量

* @param it 不为null的话, 新的entries通过这个迭代器创建

* @param str 不为null的话, 新的entries通过序列化流来创建

* 准确点说，it和str必须一个不为null

* @param defaultVal 不为null的话, 会作为默认值

* @throws java.io.IOException 读取流时可能会抛出NPE，如果str为null则不会发生这种情况

* @throws ClassNotFoundException 读取对象是可能抛此异常.如果str为null则不会发生这种情况

*/

private void buildFromSorted(int size, Iterator> it,

java.io.ObjectInputStream str,

V defaultVal)

throws java.io.IOException, ClassNotFoundException {

//设置size

this.size = size;

//调用buildFromSorted来确定root

//分割线之后继续分析

//这里有个小插曲computeRedLevel

//computeRedLevel是根据节点数量来计算完全二叉树的层级

//其实从名字看来，可以理解为计算红色节点的层级

root = buildFromSorted(0, 0, size-1, computeRedLevel(size),

it, str, defaultVal);

}

---------------------------------------------------

/**

* 计算红色节点所在层级

* (完全二叉树的层级)

* 从0开始

*

*/

private static int computeRedLevel(int sz) {

int level = 0;

for (int m = sz - 1; m >= 0; m = m / 2 - 1)

level++;

return level;

}

---------------------------------------------------

//个是buildFromSorted的实际实现方法

/**

* 递归的、真正的实现方法(之前是帮助方法).

* 跟之前的方法比较，相同的参数命名具有相同的意义

* 增加的参数说明在下方

*

* 假定在调用此方法之前已经设置了树图的比较器和大小字段。(它忽略了这两个字段)。

*

* @param level 当前树的层级. 初始化调用应该为0.

* @param lo 子树的首个节点索引. 初始化应该为0.

* @param hi 子树的尾节点索引. 初始化应该为size - 1

* @param redLevel 节点该为红色的层级，必须以size和computeRedLevel计算出来的相等

*/

@SuppressWarnings("unchecked")

private final Entry buildFromSorted(int level, int lo, int hi,

int redLevel,

Iterator> it,

java.io.ObjectInputStream str,

V defaultVal)

throws java.io.IOException, ClassNotFoundException {

/*

* 策略: 根节点是最接近中间节点的元素. 为了得到它,首先我们必须递归构建完整的左子树,以便抓取所有的元素

* 然后我们可以继续处理右子树

*

* lo和li参数是为当前子树提取迭代器/流的最小和最大指标，

* 它们实际上没有索引，我们只是按顺序处理，确保items被按相应的顺序处理。

*

*/

//如果hi小于lo，

if (hi < lo) return null;

//mid=(lo+hi)/2; - 无符号右移

int mid = (lo + hi) >>> 1;

//左子树

Entry left = null;

//如果lo小于mid

//递归构造左子树

if (lo < mid)

left = buildFromSorted(level+1, lo, mid - 1, redLevel,

it, str, defaultVal);

// extract key and/or value from iterator or stream

//从迭代器/流中获取键值对

K key;

V value;

//使用迭代器

if (it != null) {

//没有有默认值

if (defaultVal==null) {

Map.Entry,?> entry = (Map.Entry,?>)it.next();

key = (K)entry.getKey();

value = (V)entry.getValue();

} else {

//有默认值

key = (K)it.next();

value = defaultVal;

}

} else { // use stream

//使用流

key = (K) str.readObject();

value = (defaultVal != null ? defaultVal : (V) str.readObject());

}

//创建节点

Entry middle = new Entry<>(key, value, null);

// color nodes in non-full bottommost level red

//非null节点且是红色层级的，染色成红色

if (level == redLevel)

middle.color = RED;

//判断左子树是否为null

if (left != null) {

//指向左子树

middle.left = left;

//修改引用

left.parent = middle;

}

//递归构造右子树

if (mid < hi) {

Entry right = buildFromSorted(level+1, mid+1, hi, redLevel,

it, str, defaultVal);

middle.right = right;

right.parent = middle;

}

//到递归的最外层的话这里的middle就是最终的根节点

return middle;

}

到这里，关于TreeMap的put相关方法就分析完毕了，有几个要点梳理一下

1、put方法根据比较器/自然顺序将元素放置到红黑树特定位置后，进行插入平衡

2、putAll实际上有两种情况，一个是迭代取出元素调用父类的put，另外是调用buildFromSorted完成TreeMap构造

3、调用buildFromSorted的前提是，入参必须是SortedMap的实例(还有其他限制，详见上面的if条件)

4、buildFromSorted里面有一个computeRedLevel，是用来计算红色节点层级(也可以理解为计算完全二叉树层级)

5、实际实现buildFromSorted的方法，是一个递归调用的过程，通过middle，递归构造左右子树来完成整棵树的构建。

Go On，下面是remove的方法。

remove

/**

* 如果存在的话，根据指定的key从treemap中移除指定的键值对

*

* @param key 要移除的键值对的key

* @return 和{@code key}相关联的旧值

* 如果{@code key}.没有映射的话为{@code null}，返回null的时候也有可能和key相关联的是null

* @throws ClassCastException 指定的key无法和map中的key进行比较，则抛此异常

* @throws NullPointerException 指定的key是null且该treemap采取自然排序/comparator不允许null的key时，抛NPE

*/

public V remove(Object key) {

//根据key获取指定元素节点

Entry p = getEntry(key);

//为null则返回

if (p == null)

return null;

//取出旧节点的值

V oldValue = p.value;

//删除元素

deleteEntry(p);

//返回旧值

return oldValue;

}

从源码可以看出，remove方法体里面有两个关键调用，getEntry和deleteEntry，深入了解一下。

/**

* 根据给定给定key，返回元素，如果没存在，则返回null

*

* @throws ClassCastException 指定的key无法与map中的比较时，抛出此异常

* @throws NullPointerException 指定的key是null且该treemap采取自然排序/comparator不允许null的key时，抛NPE

*/

final Entry getEntry(Object key) {

// Offload comparator-based version for sake of performance

// 判断是否存在comparator

if (comparator != null)

//如果comparator存在的话，调用getEntryUsingComparator

return getEntryUsingComparator(key);

if (key == null)

throw new NullPointerException();

@SuppressWarnings("unchecked")

Comparable super K> k = (Comparable super K>) key;

Entry 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方法

/**

* 通过comparator获取元素的版本.从genEntry分离出来(整洁美观性能beautiful~)

* (对于大多数方法来说它是不值得的,因为大多数方法较少依赖于比较器性能，但是在这里它就是酱紫的呀，它是值得的)

*/

final Entry getEntryUsingComparator(Object key) {

@SuppressWarnings("unchecked")

K k = (K) key;

//取出比较器

Comparator super K> cpr = comparator;

if (cpr != null) {

Entry 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;

}

查找元素的方法还是比较简单易懂的，但是不能漏掉deleteEntry这个查找后删除的方法，其实这里的deleteEntry就是红黑树的节点删除操作了，之前也貌似也分析过，这里还是把代码和注释贴来，也许你跟我一样也是小懒蛋呢(科普一下：优秀的懒人会有创新的，因为不想重复劳动)

/**

* 删除p节点，然后处理删除平衡

*/

private void deleteEntry(Entry p) {

//首先，现实相关计数处理

modCount++;

size--;

// If strictly internal, copy successor's element to p and then make p

// point to successor.

//内部严谨的话，拷贝p的后置节点给p，然后将p指向后置节点

//左右子树都存在的情况

if (p.left != null && p.right != null) {

//获取后置节点

Entry s = successor(p);

//后置节点的相关值赋值给p

p.key = s.key;

p.value = s.value;

//p指向s

p = s;

} // p has 2 children

// Start fixup at replacement node, if it exists.

//开始在替换节点进行修正

//如果p的左右子树都存在一个的话，则p在上面的条件分支里已经指向s了

//取出替换节点

Entry replacement = (p.left != null ? p.left : p.right);

//判断替换节点是否存在

if (replacement != null) {

// Link replacement to parent

//修改父节点引用

replacement.parent = p.parent;

//如果p不存在父节点，那么替换p的replacement节点就是根节点了

//很好，登基了(朕一日不死，你们就都是太子)

if (p.parent == null)

root = replacement;

//如果p是父节点的左子树

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节点的相关引用置为null，以便后面的删除平衡处理

p.left = p.right = p.parent = null;

// Fix replacement

//如果p节点是黑色节点的话，则进行删除平衡

if (p.color == BLACK)

fixAfterDeletion(replacement);//这个方法在开头的红黑树说明有，或者可以参考我的另外一篇hashmap红黑树博客

//如果替换节点不存在，且p的父节点也不存在

} else if (p.parent == null) { // return if we are the only node.

//则证明p的唯一的节点，返回null

root = null;

} else { // No children. Use self as phantom replacement and unlink.

//p有父节点，但是没有子节点了

//判断p的颜色是否为黑

if (p.color == BLACK)

//如果是，进行删除平衡

fixAfterDeletion(p);

//p的父节点存在

//判断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;

}

}

}

//获取后置节点

/**

* 返回后置节点如果存在的话，如果不存在，返回null

*/

static TreeMap.Entry successor(Entry t) {

//t为null，则直接返回null

if (t == null)

return null;

//右子树存在

else if (t.right != null) {

//取出右子树

Entry p = t.right;

//循环，遍历并循环取左子树，取出最后一个

while (p.left != null)

p = p.left;

return p;

} else {

//左子树存在

//取出父节点

Entry p = t.parent;

//ch指向t

Entry ch = t;

//现在的ch(t)是p的子树

//循环(只要父节点存在，且ch(t)节点是父节点的右子树的话)

while (p != null && ch == p.right) {

ch = p;

p = p.parent;

}

return p;

}

}

//可以看出来，取出后置节点是这么处理的：

1、如果t的右子树存在的话，就一路向左下遍历，直到null

2、如果t的左子树存在的话，就一路向向上遍历(t必须是父节点的右子树)，直到不符合情况

get

(⊙o⊙)…

如果仔细看了remove章节的话，其实这个章节可以略过了。

因为get属于门面方法，实际实现也是由getEntry提供的。

public V get(Object key) {

Entry p = getEntry(key);

return (p==null ? null : p.value);

}

containsKey/containsValue

判断TreeMap是否存在对应的key或者对应的value。

判断key比较简单，跟上面get章节是相同道理的，根据key去获取元素，并判断元素是否为null。

判断value跟判断key不一样，但是逻辑也很清晰，首先取出首个元素，然后循环迭代，用指定value和每个元素的value做比较，相同则返回。

public boolean containsKey(Object key) {

return getEntry(key) != null;

}

--------------------------------------------------

public boolean containsValue(Object value) {

//迭代判断

for (Entry e = getFirstEntry(); e != null; e = successor(e))

if (valEquals(value, e.value))

return true;

return false;

}

forEach

循环迭代，并对每个元素做指定的操作(action)。

这里的循环迭代跟上面的containsValue是一样的，不通点在于containsValue是对每个元素执行判断，而forEach是对每个元素执行相应的action。

@Override

public void forEach(BiConsumer super K, ? super V> action) {

Objects.requireNonNull(action);

int expectedModCount = modCount;

for (Entry e = getFirstEntry(); e != null; e = successor(e)) {

action.accept(e.key, e.value);

if (expectedModCount != modCount) {

throw new ConcurrentModificationException();

}

}

}

entrySet

本来不打算把这个拿出来分析的，因为完整的分析篇幅实在是太长了。

但是既然都这么长了，还在乎差这一截吗~

这个方法我们用的也是相对比较频繁的，单看entrySet方法根本没什么好看的，很简单，内部有一个entrySet变量，如果未初始化，则new一个，如果已初始化，则返回。

public Set> entrySet() {

EntrySet es = entrySet;

return (es != null) ? es : (entrySet = new EntrySet());

}

来看一下EntrySet的数据结构，它是TreeMap的内部类，并且继承了AbstractSet,并实现了相关方法，用过Set的小伙伴应该相熟悉。

// TreeMap.java 1057行

//Entry定义

class EntrySet extends AbstractSet> {

/**

* 返回迭代器

*/

public Iterator> iterator() {

//这里调用的getFirstEntry方法，之前分析过

//获取了首节点元素后，创建一个EntryIterator

//这里迭代器相关代码不贴了，有兴趣的可以自行了解

//TreeMap 1238行

return new EntryIterator(getFirstEntry());

}

/**

* 判断是否包含元素o

*/

public boolean contains(Object o) {

if (!(o instanceof Map.Entry))

return false;

Map.Entry,?> entry = (Map.Entry,?>) o;

Object value = entry.getValue();

Entry p = getEntry(entry.getKey());

return p != null && valEquals(p.getValue(), value);

}

/**

* 移除元素o

*/

public boolean remove(Object o) {

if (!(o instanceof Map.Entry))

return false;

Map.Entry,?> entry = (Map.Entry,?>) o;

Object value = entry.getValue();

Entry p = getEntry(entry.getKey());

if (p != null && valEquals(p.getValue(), value)) {

deleteEntry(p);

return true;

}

return false;

}

public int size() {

return TreeMap.this.size();

}

public void clear() {

TreeMap.this.clear();

}

public Spliterator> spliterator() {

return new EntrySpliterator(TreeMap.this, null, null, 0, -1, 0);

}

}

单从上面的源码看来，entrySet其实也没什么好分析的，不过Set里面还是有很多方法在平时会用到的，之后找个时间，专门开一篇分析Set好了。

天色已晚，各位小伙伴下车洗洗睡吧。

总结

嗯，没有总结，都在上面了。

image

溜了溜了。给个赞呗。