阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方，欢迎指正~
转载请注明出处https://blog.lzoro.com。
前言
开门见山，山外有山，山外有山...
先简单介绍下TreeMap，来看下类关系图。
image
怎么说呢，TreeMap就是一个有序的键值对集合（这介绍有够简单的）。
TreeMap实现了NavigableMap接口， 而NavigableMap则是通过sortedMap间接继承了Map接口，它定义了一系列导航方法，这些Map之外的方法算是和HashMap的不同，另外的不同点还在于顺序性。
关于TreeMap和HashMap的异同点，在接下来的每个章节都可能会提到。
如果还未了解过HashMap的，可以移步这里Java源码阅读之HashMap - JDK1.8和这里Java源码阅读之红黑树在HashMap中的应用 - JDK1.8。
接下来，请坐好，准备发车了。
基础
老规矩，不想上来就整一大堆复杂晦涩的方法，还是先从变量了解起。
成员变量
/**
* comparator用来保持treemap的顺序性
* 如果是null，则采取自然顺序
*
* @serial
*/
private final Comparator<? super K> comparator;
/**
* 红黑树根节点
*/
private transient Entry<K,V> 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<K, ? extends V> 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<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;
/**
* 根据给定的key/value/parent创建一个新的单元节点（黑）
* 子树为null
*
*/
Entry(K key, V value, Entry<K,V> 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<K,V> p) {
//null节点忽略
if (p != null) {
//取出p的右子树
Entry<K,V> 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<K,V> p) {
//null节点忽略
if (p != null) {
//取出p的左子树l
Entry<K,V> 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<K,V> 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<K,V> 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<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 {
//祖父节点左子树为红色
//入股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<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry<K,V> 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<K,V> 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<K,V> 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<K,V> 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<K,V> 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
* <tt>entrySet()</tt> collection, and calls this map's <tt>put</tt>
* operation once for each entry returned by the iteration.
*
* <p>Note that this implementation throws an
* <tt>UnsupportedOperationException</tt> if this map does not support
* the <tt>put</tt> 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<K,V> 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<K,V> 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<K,V> 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<K,V> 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<K,V> 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<K,V> 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<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方法
/**
* 通过comparator获取元素的版本.从genEntry分离出来(整洁美观性能beautiful~)
* (对于大多数方法来说它是不值得的,因为大多数方法较少依赖于比较器性能，但是在这里它就是酱紫的呀，它是值得的)
*/
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;
}
查找元素的方法还是比较简单易懂的，但是不能漏掉deleteEntry这个查找后删除的方法，其实这里的deleteEntry就是红黑树的节点删除操作了，之前也貌似也分析过，这里还是把代码和注释贴来，也许你跟我一样也是小懒蛋呢（科普一下：优秀的懒人会有创新的，因为不想重复劳动）
/**
* 删除p节点，然后处理删除平衡
*/
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.
//内部严谨的话，拷贝p的后置节点给p，然后将p指向后置节点
//左右子树都存在的情况
if (p.left != null && p.right != null) {
//获取后置节点
Entry<K,V> 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<K,V> 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 <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
//t为null，则直接返回null
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;
//ch指向t
Entry<K,V> 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<K,V> 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<K,V> 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<K, V> 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<Map.Entry<K,V>> entrySet() {
EntrySet es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
}
来看一下EntrySet的数据结构，它是TreeMap的内部类，并且继承了AbstractSet,并实现了相关方法，用过Set的小伙伴应该相熟悉。
// TreeMap.java 1057行
//Entry定义
class EntrySet extends AbstractSet<Map.Entry<K,V>> {
/**
* 返回迭代器
*/
public Iterator<Map.Entry<K,V>> 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<K,V> 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<K,V> 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<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
}
}
单从上面的源码看来，entrySet其实也没什么好分析的，不过Set里面还是有很多方法在平时会用到的，之后找个时间，专门开一篇分析Set好了。
天色已晚，各位小伙伴下车洗洗睡吧。
总结
嗯，没有总结，都在上面了。
image
溜了溜了。给个赞呗。
网友评论