本文作者：黄海燕，叩丁狼高级讲师。原创文章，转载请注明出处。
前言
之前很多小伙伴问我怎么看源代码,还有就是越来越多的程序员都想要看源代码,搞懂底层原理,但是感觉源代码非常的晦涩难懂,不够直接和清晰,所以我希望这篇文章能够快速带同学们看懂java源码,更加深入的学习java,帮助小伙伴们节约学习的时间成本.
1.树的介绍
- 什么是树结构?其实就是一个节点下面有多个子节点,我们称之为树结构,如下图:
- 普通节点：拥有子节点的节点。
- 叶子节点：没有子节点的节点。
树结构
什么是二叉树?
-
二叉树就是一个节点最多只能有2个子节点,分为左节点和右节点,如下图:
二叉树结构
什么是排序二叉树?
- 若左子树不为空，则左子树所有节点的值小于根节点的值。
-
若右子树不为空，则右子树所有节点的值大于根节点的值。
如图:
排序二叉树.png
什么是红黑树?
红黑树其实是一个平衡排序二叉树,属于查询高效的树结构.请看下图:
普通排序二叉树vs红黑树
查询元素6普通的二叉树需要操作6次,红黑树只需要操作4次,所以红黑树查询更加高效.
1.TreeMap的结构介绍
1.1 结构关系
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
继承关系:
- 父类AbstractMap,让子类拥有基本Map的方法,比如增(put)删(remove)查(get)等方法.
实现关系:
- NavigableMap:父接口为SortedMap,所以NavigableMap为可排序接口,表示TreeMap但是一个排序的Map:
- Cloneable:标记型的接口，内部都没有方法和属性，实现 Cloneable来表示该对象能被克隆，能使用Object.clone()方法。如果没有实现 Cloneable的类对象调用clone()就会抛出CloneNotSupportedException。
- Serializable:标记型的接口，内部都没有方法和属性，实现Serializable表示可进行序列化和反序列化,表示能够使用在ObjectOutputStream.writeObject())和ObjectInputStream.readObject()
1.2 基本成员组成
/**
* 比较器:类似于一个"裁判",用于比较插入对象和树节点的内容大小
* 因为TreeMap是一个红黑树,红黑树是一个排序二叉树,插入元素的时候需要进行排序,排序可以使用比较器中的方式排序
*/
private final Comparator<? super K> comparator;
/**
* 根节点
*/
private transient Entry<K,V> root;
/**
* 树的元素个数
*/
private transient int size = 0;
/**
* 操作次数:增加和删除操作数都会加1,用于控制并发修改异常
*/
private transient int modCount = 0;
通过root根节点可以看出一个节点(元素)就是一个Entry对象,所以一个节点(元素)中包含多个数据.结构如下:
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;//颜色
节点表示如下:
树节点
1.3添加操作:
public V put(K key, V value) {
Entry<K, V> t = root;//和插入节点进行比较的树节点
//根节点为空
if (t == null) {
compare(key, key); //key比key,自己比较自己,目的是想要检查类型,确保传入了比较器或者是key实现了可比较接口
//创建了一个没有父节点的新的节点,作为根节点
root = new Entry<>(key, value, null);
size = 1;//元素个数为1
modCount++;//操作数+1
return null;//返回空,根节点添加结束
}
int cmp;//表示比较结果
Entry<K, V> parent;
// cpr临时表示比较器
Comparator<? super K> cpr = comparator;
if (cpr != null) {//比较器不为空,就使用比较器比较元素
do {
parent = t;//父节点为t
cmp = cpr.compare(key, t.key);//通过比较器对key和树节点比较得到比较结果
if (cmp < 0)//比较结果小于0,表示插入的元素比树节点小
t = t.left;//t往左走
else if (cmp > 0)//比较结果大于0,表示插入的元素比树节点大
t = t.right;//t往右走
else//cmp比较结果为0,覆盖节点中的value
return t.setValue(value);
} while (t != null);//直到t为空停下来,保证插入的是节点
} else {//比较器为空就使用元素中的比较方法
if (key == null)//插入的元素key为空,没办法和树结构中的元素比较,抛出空指针异常
throw new NullPointerException();
/*
* key进行强转,看一下key是否实现了Comparable接口,是否存在compareTo方法,
* 如果没有实现接口,也就不确定有没有compareTo方法了,没办法进行比较了
*/
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;//父节点为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)//如果比较结果小于0插入左边
parent.left = e;
else
parent.right = e;//否则插入右边
fixAfterInsertion(e);//对树进行自平衡
size++;
modCount++;
return null;
}
1.4 元素插入后对树进行自平衡
红黑树的自平衡规则:(目标就是黑色节点平衡)
- 每个节点都只能是红色或者黑色
- 根节点是黑色
- 每个叶节点（空节点）是黑色的。
- 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
private void fixAfterInsertion(Entry<K, V> x) {//x表示插入的节点,
x.color = RED;//设置插入的节点为红色
//当x不为空,x不为根节点,x的父节点为红色就需要进行平衡
while (x != null && x != root && x.parent.color == RED) {
//x的父节点等于x的爷爷节点的左边,其实就是说x的父节点是否属于左节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//获取x的爷爷节点的右节点
Entry<K, V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {//爷爷节点的右节点为红色
setColor(parentOf(x), BLACK);//将x的父节点设置为黑色
setColor(y, BLACK);//x父节点的兄弟节点设置为黑色
setColor(parentOf(parentOf(x)), RED);//爷爷节点设置为红色
x = parentOf(parentOf(x));//x指向原来的爷爷节点,目的是为了继续往上修改颜色
} else {//不为红色,也就是子节点和父节点的颜色出现冲突
//如果x等于父节点的右节点
if (x == rightOf(parentOf(x))) {
//操作的x为x的父节点
x = parentOf(x);
//左自旋,旋转后x为原来x的子节点
rotateLeft(x);
}
//x的父节点设置为黑色
setColor(parentOf(x), BLACK);
//x的爷爷节点设置为红色
setColor(parentOf(parentOf(x)), RED);
//右自旋
rotateRight(parentOf(parentOf(x)));
}
} else {
//y为爷爷节点的左节点(父节点的兄弟节点)
Entry<K, V> y = leftOf(parentOf(parentOf(x)));
//如果y的颜色为红色
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);//父节点设置为黑色
setColor(y, BLACK);//y设置为黑色
setColor(parentOf(parentOf(x)), RED);//爷爷节点设置为红色
x = parentOf(parentOf(x));//x指向原来的爷爷节点,目的是为了继续往上修改颜色
} else {
//如果父节点的左节点为x
if (x == leftOf(parentOf(x))) {
//x为父节点
x = parentOf(x);
//右自旋,旋转后x为原来x的子节点
rotateRight(x);
}
setColor(parentOf(x), BLACK);//父节点设置为黑色
setColor(parentOf(parentOf(x)), RED);//爷爷节点设置为红色
rotateLeft(parentOf(parentOf(x)));//左自旋
}
}
}
root.color = BLACK;//保证根节点必须为黑色
}
1.5左自旋
private void rotateLeft(Entry<K, V> p) {
//p不为空
if (p != null) {
//r表示p的右节点
Entry<K, V> r = p.right;
//将r的左节点 赋值给 p的有右节点
p.right = r.left;
//如果r的左节点不为空
if (r.left != null)
//r的左节点的父节点为p
r.left.parent = p;
//r的父节点为p的父节点
r.parent = p.parent;
//如果p的父节点为空
if (p.parent == null)
//r作为根节点
root = r;
//如果p的父节点的左节点等于p,说明p为父节点的左节点
else if (p.parent.left == p)
//p的父节点的左节点为r
p.parent.left = r;
else
//p的父节点的左节点为r
p.parent.right = r;
//r的左节点为p
r.left = p;
//p的父节点为r
p.parent = r;
}
}
1.6右自旋
private void rotateRight(Entry<K, V> p) {
//p不为空
if (p != null) {
//l表示p的左节点
Entry<K, V> l = p.left;
//p的左节点指向l的右节点
p.left = l.right;
//如果l的右节点不为空
if (l.right != null)
//l的右节点的父节点为p
l.right.parent = p;
//l的父节点指向p的父节点
l.parent = p.parent;
//如果p的父节点为空
if (p.parent == null)
//l为根节点
root = l;
//如果p的父节点的右节点为p
else if (p.parent.right == p)
//p的父节点的右节点为l
p.parent.right = l;
else
//p的父节点的左节点为l
p.parent.left = l;
//l的右节点指向p
l.right = p;
//p的父节点指向l
p.parent = l;
}
}
1.7案例演示:
演示代码如下:
叩丁狼.png
代码执行步骤如下:
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
[图片上传中...(image.png-249558-1571390630593-0)]
.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
36.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
叩丁狼.png
