红黑树(red black tree)
特点
- 一个节点是红色或黑色
- 根节点是黑色
- 如果一个节点是红色，那么它的子节点必须是黑色
- 一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点(红色节点不影响)
两种旋转方式和一种颜色变换
- 单旋转方式
- 双旋转方式(需要两次反方向的单旋转)
- 当两个子节点均为红色的时候，执行颜色变换，因为插入的是红色节点，会产生冲突。例如根节点的子节点是红色，两个叶子节点变成黑色，根节点变成红色，再变成黑色。
问题
- 为什么插入的总是红色节点?
因为插入前，树都是构建好的，如果插入的是黑色节点，就破坏了每一条路径必须包含相同数目的黑色节点这一特性 - 为什么进行旋转？
因为插入时总是红色节点，如果不旋转的话，违背了一个节点是红色，那么它的子节点必须是黑色这一特性 - 为什么进行颜色变换？
图示的第一种旋转，红色节点 X 的插入破坏了红黑树结构，所以进行旋转，旋转后的结构如图所示，旋转后，P 和 G 点如果维持本来的颜色，就会违背第三、四条特性，所以，进行颜色变换。 - 与 AVL(Adelson-Velsky and Landis Tree) 树（平衡二叉查找树）比较?
红黑树不是通过递归方式，而是通过循环的方式来实现，不需要保存节点高度字段，节省内存
两者最坏操作时间复杂度都是O(logN)
HashMap特性
- 允许 key 、 value 任一值或同时为 null
- HashMap 的元素时无序，不稳定
- HashMap 写操作线程不安全，读操作线程安全
- 支持已任何形式创建的迭代器
- 不支持除迭代本身方法(remove())改变集合元素，否则会抛出 ConcurrentModificationException 异常
HashMap与HashTable区别
- HashTable 读写操作是线程安全
- HashTable 不允许 key 、 value 任一值或同时为 null
HashMap内部类
内部类简介
- Node (static class):基于 hash 的链表节点，由 LinkedHashMap.Entry 、 TreeNode 继承实现
- TreeNode (static final class)
- Values (final Class)：HashMap中的 value 集合
- KeySet (final Class)：HashMap中的 key 集合
- EntrySet (final Class)：HashMap中的 Entry 集合
- HashIterator (abstract class)：抽象迭代器
- KeyIterator (final Class): HashMap中的 Key 集合的迭代器
- ValueIterator (final class)：HashMap中的 Value 集合的迭代器
- EntryIterator (final class)：HashMap中的 Entry 集合的迭代器
- HashMapSpliterator (static class):抽象的并行迭代器
- KeySpliterator (static final class):HashMap中的 Key 集合的并行迭代器
- ValueSpliterator (static final class):HashMap中的 Value 集合的并行迭代器
- EntrySpliterator (static final class)：HashMap中的 Entry 集合的并行迭代器
Node 内部类
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
return o instanceof Map.Entry e
&& Objects.equals(key, e.getKey())
&& Objects.equals(value, e.getValue());
}
}
TreeNode 内部类
static final class TreeNode extends LinkedHashMap.Entry
{
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next)
{
super(hash, key, val, next);
}
final void treeify(Node[] tab)
{
// ......
}
static TreeNode balanceInsertion(TreeNode root, TreeNode x)
{
// ......
}
static TreeNode rotateLeft(TreeNode root, TreeNode p)
{
// ......
}
static TreeNode rotateRight(TreeNode root, TreeNode p)
{
// ......
}
// ......其余方法省略
}
HashMap中内部变量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
HashMap插入
put()方法
使用内部 putval()方法
putval()方法
* @param hash hash for key (key 的 Hash 值)
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value (如果键存在，是否需要更新 value值，true 更新 false 不更新)
* @param evict if false, the table is in creation mode.(如果为false，表示该表处于创建模式，jdk1.8版本里面使用该参数的方法是空实现，故暂没有作用)
* @return previous value, or null if none(返回之前的值，如果没有直接返回 null)
-
表是否为null或表长度是否为零，决定了是否先进行初始化。
- 1.1 初始化表，调用方法resize()
- 1.2 Hash计算后，如果对应桶内为null，往桶内添加数据，此时桶内使用数据结构为链表
- 1.3 Hash计算后，如果对应桶内不为null，判断key的 Hash 值以及 key 值是否相等，
- 1.3.1 相等，直接覆盖
- 1.3.2 不相等，判断节点结构是否为红黑树结构(TreeNode)实例，是则直接使用 putTreeVal() 方法
- 1.3.3 判断节点结构是否为红黑树节点结构(TreeNode)实例，不是则直接将数据插入链表末端，并判断链表长度是否大于等于 8 ，是则开始进行将链表进化为红黑树的操作(treeifyBin)
-
treeifyBin()
- 2.1 如果表为null或者表长度小于 64 ，则进行表长度扩容
- 2.2 如果表长度大于 64 且表最后一个桶内数据不为null，则将桶内链表的节点结构转换为TreeNode，并连成一个链表
- 2.3 进化红黑树(treeify)
-
转换红黑树代码解析
final void treeify(Node[] tab) {
TreeNode root = null;
for (TreeNode x = this, next; x != null; x = next) {
next = (TreeNode)x.next;
x.left = x.right = null;
if (root == null) {
// 配置红黑树根节点
x.parent = null;
x.red = false;
root = x;
}
else {
// 存在根节点后，根据外层的for循环，知晓当前节点 x 的信息
// 开始从上往下进行红黑树节点添加，以下的 for 循环是核心循环，进行节点添加
K k = x.key;
int h = x.hash;
Class kc = null;
// for 循环是为了寻找一个空的节点位置，将元素放入
for (TreeNode p = root;;) {
// for 循环中没有控制条件，需循环内部跳出
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
// 节点的 Hash 值 大于 当前元素 Hash 值，放左节点
dir = -1;
else if (ph < h)
// 节点的 Hash 值 小于 当前元素 Hash 值，放右节点
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// 先尝试通过Comparable比较两个对象(当前pk的key对象和x的key对象)
// 1. 先通过 comparableClassFor 方法判断两者是否可以进行 Comparable
// 2. 如果可以，通过 compareComparables 方法进行比较
// 判断条件中的方法没有分出胜负则使用此方法分出胜负
dir = tieBreakOrder(k, pk);
TreeNode xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 维护红黑树添加节点后的结构
root = balanceInsertion(root, x);
break;
}
}
}
}
//Ensures that the given root is the first node of its bin
// 确保根节点在链表的第一个
moveRootToFront(tab, root);
}
- 需要被插入的元素的key对象是否实现了 Comparable 接口
static Class comparableClassFor(Object x) {
// 当前元素key 是否实现了 Comparable 接口
if (x instanceof Comparable) {
Class c; Type[] ts, as; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
// 如果 x 是字符串对象，直接返回，因为 String 实现了Comparable接口
return c;
if ((ts = c.getGenericInterfaces()) != null) {
// 获取 x 实现了哪些接口，包含泛型接口(泛型信息)
for (Type t : ts) {
if ((t instanceof ParameterizedType) &&
((p = (ParameterizedType) t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
// 如果当前接口t是个泛型接口
// 如果该泛型接口t的原始类型p 是 Comparable 接口
// 如果该Comparable接口p只定义了一个泛型参数
// 如果这一个泛型参数的类型就是c，那么返回c
return c;
}
}
}
return null;
}
- 通过 Comparable 比较大小，确定节点位置
static int compareComparables(Class kc, Object k, Object x) {
// 如果 x == null 或者 x 的实现类不是 comparableClassFor 获取的类，直接返回 0
// 如果 x != null 或者 x 的实现类是 comparableClassFor 获取的类
// 通过 Comparable 比较大小，返回比较结果
return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x));
}
static TreeNode balanceInsertion(TreeNode root,
TreeNode x) {
// 印证了之前说的新加入节点都是红色的
x.red = true;
// xp x 的父节点
// xpp x 的祖父节点
// xppl x 的祖父的左节点
// xppr x 的祖父的右节点
for (TreeNode xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
// 如果 x 的父节点是 null 说明 x 节点为 根节点
// 红黑树特性 根节点必须黑色
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
// 进入 else 说明 x 不是根节点，
// x 的父节点为黑色，可以在下面直接添加红色节点，直接返回根，
// x 的祖父节点为空，表示 x 的父节点是根节点，且调用该方法前，节点已经添加完成，所以直接返回根节点
return root;
// 进入下面的执行逻辑表示
// 1. x 的父节点xp是红色的，
// 2. x 的祖父节点xpp不为空
// 这样就遇到两个红色节点相连的问题，所以必须经过颜色变换和双旋转
if (xp == (xppl = xpp.left)) {
// x 的父节点是 x 祖父节点的左节点
if ((xppr = xpp.right) != null && xppr.red) {
// x 的祖父节点的右节点不是 null 且右节点是红色，则证明祖父节点的左节点也是红色
// 因为红色节点下面不能再挂红色节点，所以需要将祖父节点的左右节点全部变成黑色，祖父节点变成红色(就是前面说的颜色变换)
xppr.red = false;
xp.red = false;
xpp.red = true;
// 为什么让 x = xpp ？因为 xpp 变成红色节点后可能与 xpp 的父节点发生冲突(两个红色节点相连)，
// 就此形成了图示的第二种旋转，所以需要从下往上旋转
x = xpp;
}
else {
// x 的祖父节点的右节点是 null 且右节点是黑色
// 那么此时的结构位置就有两种情况
// 1. xpp->xp(xxp的左节点)->x(xp的右节点)
if (x == xp.right) {
// 向左旋（图示的单旋转方式）注意进行左旋的节点是 x 的父节点
root = rotateLeft(root, x = xp);
// 将xp 的父节点执向 x 的祖父节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 2. xpp->xp(xxp的左节点)->x(xp的左节点) 或者上面旋转后，也会形成这种结构
if (xp != null) {
// x 的父节点变为黑色
xp.red = false;
if (xpp != null) {
// x 的祖父节点变为红色
xpp.red = true;
// 向右旋 （图示的单旋转方式）
root = rotateRight(root, xpp);
}
}
}
}
else {
// x 的父节点是祖父节点的右节点
if (xppl != null && xppl.red) {
// x 的祖父节点的左节点不是 null 且是红色节点
// 那么 x 的父节点 肯定也是红色节点，这样就符合图示的第三种旋转
// x 的祖父节点的左节点变成黑色节点，x 的父节点也变成黑色节点 ，x 的祖父节点变成红色节点
xppl.red = false;
xp.red = false;
xpp.red = true;
// 为什么 x = xpp ? 因为 x 的祖父节点变成红色节点后，可能产生两个红色节点相连的冲突，即图示的第二种旋转
// 所以将x = xpp ，进行从下而上的旋转
x = xpp;
}
else {
// x 的祖父节点的左节点是 null 且是黑色节点，那么 x 的父节点肯定是黑色
// 此时结构肯定有两种
// 1. xpp右->xp左->x
if (x == xp.left) {
// 向右旋
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 2. xpp右->xp右->x 或上述旋转后形成的该结构
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
// 向左旋
root = rotateLeft(root, xpp);
}
}
}
}
}
}
static TreeNode rotateLeft(TreeNode root,
TreeNode p) {
// root 表示根节点
// p 表示 x 的父节点 xp
// pp 表示 父节点的父节点 祖父节点
// rl 表示 右节点的左节点
// r 表示 右节点
// 左旋就是将某个节点旋转为其右节点的左节点
TreeNode r, pp, rl;
if (p != null && (r = p.right) != null) {
// 如果符合的话，p 的右节点指向 rl 否则指向 null
if ((rl = p.right = r.left) != null)
rl.parent = p;
// 如果pp 为空，实际剩下三个节点
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
// 如果pp 不为为空
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
// 执行完该代码，形成图示结构
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
```java // (图示 PP != null) 执行完该代码，形成图示结构 if ((pp = r.parent = p.parent) == null) (root = r).red = false; ```
```java // (图示 PP != null) 执行完该代码，形成图示结构(图示 pp.left == p 成立) else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; ```
```java // (图示 PP == null) 执行完该代码，形成图示结构 if ((pp = r.parent = p.parent) == null) (root = r).red = false; ```
```java // (图示 PP == null) 执行完该代码，形成图示结构 r.left = p; p.parent = r; ```
static TreeNode rotateRight(TreeNode root,
TreeNode p) {
// l 左节点
// pp 祖父节点
// lr 左节点的右节点
// 右旋就是将某个节点旋转为其左节点(孩子)的右节点(孩子)
TreeNode l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
// 执行完图示代码，形成右旋开始前的红黑树结构
// x 的父节点变为黑色
xp.red = false;
if (xpp != null) {
// x 的祖父节点变为红色
xpp.red = true;
// 向右旋 （图示的单旋转方式）
}
- 图示右旋过程 ```java // 执行完图示代码，形成图示结构 if (p != null && (l = p.left) != null) { if ((lr = p.left = l.right) != null) lr.parent = p; ```
```java // ( 图示 pp != null )执行完图示代码，形成图示结构 if ((pp = l.parent = p.parent) == null) (root = l).red = false; ```
```java // ( 图示 pp != null )执行完图示代码，形成图示结构 else pp.left = l; l.right = p; p.parent = l; ```
```java // ( 图示 pp == null )执行完图示代码，形成图示结构 if ((pp = l.parent = p.parent) == null) (root = l).red = false; ```
```java // ( 图示 pp == null )执行完图示代码，形成图示结构 l.right = p; p.parent = l; ```
问题：
- 为什么右旋前，需要将 x 节点变成黑色？
因为这样就可以不考虑 xppp 节点的颜色，即使 xppp 节点颜色是红色，可以进行再次平衡旋转
以上都是拿 x 的父节点是祖父节点的左节点的情况，x 的父节点是祖父节点的右节点的情况，与之相反。
