红黑树(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<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> 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<K, V> extends LinkedHashMap.Entry<K, V>
{
TreeNode<K, V> parent; // red-black tree links
TreeNode<K, V> left;
TreeNode<K, V> right;
TreeNode<K, V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K, V> next)
{
super(hash, key, val, next);
}
final void treeify(Node<K,V>[] tab)
{
// ......
}
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x)
{
// ......
}
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p)
{
// ......
}
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p)
{
// ......
}
// ......其余方法省略
}
HashMap中内部变量
/**
* 默认桶的数量 为 16 必须是 2 的幂次方
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 桶的最大数量为 2 的 30 幂次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 桶的负载因子，当存有数据的桶的数量超过 75% ，就会扩容为 2 倍桶数量，并自动进行再散列(rehashed)
* 可以查看构造函数
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 桶内数据量超过这个阈值就会将桶内数据结构从链表转为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 桶内数据量小于这个阈值就会将桶内数据结构从红黑树退化为链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 如果桶的数量小于 64 ，会先扩容，直至桶的数量超过 64
* 这样是为了减少形成很满的桶，因为桶的数量越多，越不容易造成桶满
* 借鉴了 <see>https://stackoverflow.com/questions/43911369/hashmap-java-8-implementation</see>
*/
static final int MIN_TREEIFY_CAPACITY = 64;
HashMap插入
put()方法
使用内部 putval()方法
putval()方法
- putval方法参数说明
```java
- @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)
转换红黑树代码解析
treeify()
final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; for (TreeNode<K,V> x = this, next; x != null; x = next) { next = (TreeNode<K,V>)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<K,V> 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<K,V> 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 <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { // 印证了之前说的新加入节点都是红色的 x.red = true; // xp x 的父节点 // xpp x 的祖父节点 // xppl x 的祖父的左节点 // xppr x 的祖父的右节点 for (TreeNode<K,V> 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); } } } } } }rotateLeft
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { // root 表示根节点 // p 表示 x 的父节点 xp // pp 表示 父节点的父节点 祖父节点 // rl 表示 右节点的左节点 // r 表示 右节点 // 左旋就是将某个节点旋转为其右节点的左节点 TreeNode<K,V> 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;
```
rotateRight
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { // l 左节点 // pp 祖父节点 // lr 左节点的右节点 // 右旋就是将某个节点旋转为其左节点(孩子)的右节点(孩子) TreeNode<K,V> 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; // 向右旋 （图示的单旋转方式） }图示右旋过程
// 执行完图示代码，形成图示结构 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 的父节点是祖父节点的右节点的情况，与之相反。