本篇文章为你整理了3、TreeMap源码解析（treeset源码分析）的详细内容，包含有treemap原理图 treeset源码分析 treemap submap treemap sortedmap 3、TreeMap源码解析，希望能帮助你了解 3、TreeMap源码解析。
3 成员变量
private final Comparator ? super K comparator; //排序器，如果空，按照key的字典顺序来排序（升序）；comparator为空时用Comparable的排序接口
private transient Entry K,V root; //根节点
private transient int size = 0; //树中entry个数 ，即红黑树大小
private transient int modCount = 0; //数结构被修改的次数的
* Fields initialized to contain an instance of the entry set view
* the first time this view is requested. Views are stateless, so
* theres no reason to create more than one.
private transient EntrySet entrySet;
private transient KeySet K navigableKeySet;
private transient NavigableMap K,V descendingMap;
* Dummy value serving as unmatchable fence key for unbounded
* SubMapIterators
private static final Object UNBOUNDED = new Object();
private static final boolean RED = false; //红节点 默认false
private static final boolean BLACK = true; // 黑节点 默认true
4 内部类Entry
它是组成树的节点的类型
static final class Entry K,V implements Map.Entry K,V {
K key; // key
V value; //value
Entry K,V left; //左孩子
Entry K,V right; //右孩子
Entry K,V parent; //父节点
boolean color = BLACK; //默认黑色
//根据 key value 父节点创建新节点
Entry(K key, V value, Entry K,V parent) {
this.key = key;
this.value = value;
this.parent = parent;
public K getKey() {
return key;
public V getValue() {
return value;
//替换value，返回旧value
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
// 重写equals方法：key 和 value的引用都相等
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry ?,? e = (Map.Entry ?,?
return valEquals(key,e.getKey()) valEquals(value,e.getValue());
//重写hashCode方法，返回 key 和 value的hashCode 的异或运算结构
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
public String toString() {
return key + "=" + value;
5 构造函数
// 构造函数一：不指定排序器。按照key的字典顺序来排序（升序）
public TreeMap() {
comparator = null;
// 构造函数二：指定排序器
public TreeMap(Comparator ? super K comparator) {
this.comparator = comparator;
//构造函数三：构造并返回跟参数m有相同键值映射结构的treeMap（m变为红黑树）
public TreeMap(Map ? extends K, ? extends V m) {
comparator = null;
putAll(m);
//构造函数四：构造并返回跟参数m（有序的）有相同键值映射结构的treeMap
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) {
Comparator Integer类型倒序排序
public static void main(String[] args) {
TreeMap treeMap = new TreeMap Integer ,String (new ComparatorObj());
treeMap.put(2,"ss");
treeMap.put(3,"sss");
System.out.println(treeMap);
static class ComparatorObj implements Comparator Integer {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1; //倒序排序
输出结果：
2022-07-11 18:02:23,871 [INFO] main: {3=sss, 2=ss}
6 重要方法分析
6.1 get方法分析
（实际调用getEntry(Object key)）
get(Object key)方法是对接口Map的方法实现
get(Object key)方法转为对getEntry(Object key)方法的实现分析：算法思想是根据key的自然顺序(或者比较器顺序)对二叉查找树进行查找，直到找到满足k.compareTo(p.key) == 0的entry，再返回entry的value。
源码分析如下：
public V get(Object key) {
Entry K,V p = getEntry(key); //根据key找到entry，再返回其value
return (p==null ? null : p.value);
//重点分析该方法
final Entry K,V getEntry(Object key) {
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException(); //key非空校验
@SuppressWarnings("unchecked")
Comparable ? super K k = (Comparable ? super K ) key; //自然顺序，使用Comparable的排序接口
Entry K,V p = root;
while (p != null) { //从根节点开始 循环遍历
int cmp = k.compareTo(p.key); //compareTo：左边减去右边
if (cmp 0) //参数key值小于父节点key
p = p.left; //取左子节点
else if (cmp 0)
p = p.right; //参数key值大于父节点key，取右子节点
else
return p; //key相等，则直接返回当前entry
return null;
查询方法说明：
在while循环外，创建动态游标节点，游标首次指向root节点，以游标!=null作为循环条件
在while循环内，根据compareTo结果，取游标的左子节点或右子节点，作为新的游标
找到满足k.compareTo(p.key) == 0的entry，退出循环
//提供自定义排序器的查询找方法，原理类似
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); //cpr.compare 第一个参数减去第二个参数
if (cmp 0)
p = p.left;
else if (cmp 0)
p = p.right;
else
return p;
return null;
6.2 put方法分析
public V put(K key, V value) {
Entry K,V t = root;
// 情况一：根节点为空，将当前key value作为root
if (t == null) {
compare(key, key); //key为null则抛异常
root = new Entry (key, value, null);//初始化root
size = 1; //叶子个数+1
modCount++; // 结构修改次数自增
return null; //新叶子，所以old value 为空
// 情况二：如果找到key相同的，则更新value ，过程类似get方法
int cmp;
Entry K,V parent;
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);
//情况三：没有相同的key，则添加新叶子。
//经过上面的两种遍历，完成了二分法查找，找到适合插入的地方：parent。
Entry K,V e = new Entry (key, value, parent); //创建新的entry
//确定新增叶子作为parent的左孩子还是右孩子，插入的动作完成
if (cmp 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e); //插入完成后，对二叉树进行调整
size++;
modCount++;
return null;
//这个方法实际上是对key做null检查，如果是null会抛出异常（测试代码验证过）
public TreeMap(Comparator ? super K comparator) {
this.comparator = comparator;
put方法说明：
如果root为空，则新增的entry作为root
遍历搜索是否存在相同的key，存在则替换value。这过程也是二叉排序树的二分查找法：找到了作为插入点的parent。
插入操作：找到parent，并将其left或者right指向新的entry。
如果是插入，则需要对红黑树进行结构调整。 （插入：节点默认为红色，root节点：设置为黑色，覆盖节点：颜色保持不变）
维护成员变量：size，modCount。
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; //在遍历外面，确保root一定是黑色
方法说明：
新增的节点默认为红色，并从树末端往上遍历
如果新增节点的父亲是红色，则需要进行结构调整
结构调整这部分有点复杂，回头再深入理解todo
6.4 删除方法remove()解析
知识回顾：
二叉排序树的删除过程：（情况一，treeMap用后继代替，其实用前驱或者后继是一样的）
源码如下：
// 调用getEntry(key)找到对应entry，调用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;
//执行删除操作
private void deleteEntry(Entry K,V p) {
//先对全局变量modCount、size 进行调整
modCount++;
size--;
//情况1：左右孩子都不为空：后继节点代替
if (p.left != null p.right != null) {
Entry K,V s = successor(p); //寻找后继 （另外分析）
//将删除点的key、value、引用分别更新为代替节点
p.key = s.key;
p.value = s.value;
p = s; //
//情况2：有1个孩子
Entry K,V replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
replacement.parent = p.parent; //左孩子父亲更新删除节点的父亲
//父亲为root，则后继变为新的root
if (p.parent == null)
root = replacement;
//左孩子顶上
else if (p == p.parent.left)
p.parent.left = replacement;
//右孩子顶上
else
p.parent.right = replacement;
// 删除节点的left、right、parent置空：被移除出树
p.left = p.right = p.parent = null;
// 删除黑色节点：调整结构
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { //删除root节点
root = null;
} else { // 情况1：没孩子
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;
删除说明：
删除过程遵从二叉排序树的删除特点（1、有一个孩子则孩子顶上；2两个孩子就用后继顶上，没有孩子则直接移除）
节点删除，即left、right、parent置空；删除后，需要更新父亲节点的的左孩子或右孩子
考虑是否需要更新全局变量root节点
只有删除点是BLACK的时候，才会触发调整函数，因为删除RED节点不会破坏红黑树的任何约束，而删除BLACK节点会破坏规则4。
6.5 删除调整函数fixAfterDeletion()解析
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);
说明：结构调整这部分有点复杂，回头再深入理解todo
6.6 寻找后继函数successor()解析
//寻找任意节点后继
static K,V TreeMap.Entry K,V successor(Entry K,V t) {
if (t == null)
return null;
//情况1：右孩子不为空，向后代遍历：找到右孩子中孙子最小的那个节点（不断寻找left，直至为空）
else if (t.right != null) {
Entry K,V p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
// 情况2：右孩子为空，向祖先遍历，当任意节点是它父亲的左孩子时，则该节点的父亲为t的后继
Entry K,V p = t.parent;
Entry K,V ch = t;
while (p != null ch == p.right) {
ch = p;
p = p.parent;
return p;
寻找后继的算法说明：
对于任意k：
情况一：k的右孩子不为空，向后代遍历：找到右孩子的子孙子中辈分最低的左孩子（不断寻找left，直至为空）
情况二：key的右孩子为空，向祖先遍历：当任意节点是它父亲的左孩子时，则该节点的父亲为t的后继
右孩子不为空的后继寻找：
右孩子为空为空的后继寻找：
7 解惑：
1 TreeMap支持key自定义排序，而红黑树对key的固定的排序规则，两者如何兼容的?
支持key自定义排序：指通过自定义的排序器，计算出任意key相对其它key的大小关系
红黑树对key的固定的排序：指按照红黑树的数据结构（二叉排序树+红黑节点规则），来组织key的树状结构，其中二叉排序的大小关系是根据排序器的计算出来的
两者不冲突
以上就是3、TreeMap源码解析（treeset源码分析）的详细内容，想要了解更多 3、TreeMap源码解析的内容，请持续关注盛行IT软件开发工作室。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。