HashMap特点
HashMap是Java中非常高效的key-value对数据存储结构。
它有如下特点：
- 插入数据和获取数据非常高效。
- 允许使用null key和null value。
- key value对没有顺序概念，遍历时顺序不是元素插入的顺序（保证顺序使用LinkedHashMap）。
- 非线程安全（需要线程安全使用ConcurrentHashMap）。
HashMap的内部结构
HashMap的最外层数据结构为数组。这个数组的size（叫做HashMap的capacity）为初始大小或者是人工指定。这个数组叫做node table，数组的每一个元素可以视为一个篮子，称之为bin。数组的长度必须是2的n次方。放入每个格子的元素是key value对。决定元素放入哪个bin的逻辑为计算key的hashCode（暂时理解为采用hashCode计算，后面代码分析中会发现为了更好的散布将hashCode再次加工了），然后和数组的size - 1按位与（size是2的n次方，减去1在二进制上相当于一个全是1的数，1的位数正好是size，这样可以将任意hashCode尽可能均匀的映射在node table有限的空间中），得到的结果就是bin在数组中的index。
如果元素的key的hashCode相同怎么处理？HashMap引入了二级数据结构：单向链表。hashCode相同的key对应的key value，组成单向链表，存放于同一个bin中。这样就解决了hashCode冲突的问题。
那么问题又来了，如果hashCode冲突的太多怎么处理？这时候链表会非常长，查找或者删除的时候需要遍历很长的链表，效率较低。如果链表过长（大于TREEIFY_THRESHOLD），这时候HashMap将链表自动转换为红黑树结构。红黑树结构对于大量数据的查找非常的高效。
似乎所有的疑问都解决了。但是还有一个：为什么还用单向链表，只要hashCode冲突全用红黑树不就行了？明显是忽略的红黑树的存储代价。HashMap中的红黑树存储占用空间是链表节点的2倍。同一个bin中元素较少的情况，使用红黑树存储并不能比单向链表有更突出的性能。为了平衡性能和空间消耗，HashMap在链表元素数大于TREEIFY_THRESHOLD并且HashMap的capacity大于MIN_TREEIFY_CAPACITY的时候转换为红黑树，在红黑树元素数量小于UNTREEIFY_THRESHOLD的时候退化为单向链表。
Load factor负载因子
通过上面内部结构的讲解可以看到，HashMap的node table存储的越满，hashCode冲突的情况就可能越多，链表和红黑树再优秀，也不可能和按照hashCode直接找bin 的速度相提并论。所以说要有一个机制，node table满到一定程度（多“满”使用HashMap的size / capacity衡量），HashMap需要自动扩容。这个满到什么程度用术语表示即load factor负载因子。默认的负载因子为0.75，平衡了查找元素耗时和存储空间消耗。无特殊需求建议不要更改。
Treeify树型化
HashMap中有个很重要的树形化概念。前面HashMap的内部结构已分析过红黑树，这里仅简要复述。
通常来说HashMap的bin不会存放太多数量的hashCode碰撞的元素。采用链表形式存放已经可以满足性能要求。
但是在一个bin下的节点过多这种情况，链表的查找性能会明显下降。需要将bin的数据结构变换为红黑树。可能有人会问，既然红黑树性能这么好为什么不单纯使用红黑树？问题在于tree node大小是普通链表node的2倍，为了平衡空间和时间的消耗，HashMap规定了TREEIFY_THRESHOLD，值为8。意思是只有一个bin中的节点数量超过8个的时候才可能转换为红黑树。除此之外，如果HashMap在resize的时候发现bin的节点数量小于UNTREEIFY_THRESHOLD(值为6)，数据结构会退化为普通链表。
性能分析
尽管HashMap为了高性能而设计，但是不恰当的使用会使性能大打折扣。
HashMap性能的影响因素如下：
初始容量和resize
HashMap的初始capacity是16。在使用过程中随着元素的扩容逐渐增大，16 -> 32 -> 64 -> ...。每一次扩充都伴随有resize。resize过程伴随着所有元素重新分配bin，然后移动元素。显然resize是非常耗时的操作。一种优化方式是元素数量可以提前预估的场景，在创建HashMap的时候明确指定初始容量。这样可以避免很多次resize操作。
Load factor
前面讲过，load factor是时间和空间消耗的平衡。load factor设置过低，HashMap会频繁扩容，会浪费空间。load factor设置过高，HashMap延迟扩容，更容易造成hashCode冲突（node table存在更多的链表和红黑树），影响性能。
Key的hashCode散布情况
理想情况均匀散布的key的hashCode能够最小化hashCode冲突造成的性能问题。如果key的hashCode散布不均匀，会造成node table大量空闲但是某些bin存在很长的链表/红黑树这种情况。相当于HashMap最外层数据结构几乎没有发挥作用，严重影响HashMap性能。这一点一定要格外注意。
到这里为止HashMap的文字介绍基本完成，接下来开始HashMap的源代码分析。
HashMap的主要成员变量
// 默认初始化容量大小，默认值为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 支持的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
// 如果node table入口数量超过了负载因子和当前容量的乘积，node table会扩容并重新计算各个入口的hash，放入对应的桶中
// 相当于重建内部数据结构
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 若一个bin的元素数量超过8，则链表结构才有可能变为树结构
static final int TREEIFY_THRESHOLD = 8;
// 若一个bin的元素数量少于6，则树结构会退化为链表结构
static final int UNTREEIFY_THRESHOLD = 6;
// 只有hashMap容量大小到达这个值的时候，bin链表才有可能树形化
static final int MIN_TREEIFY_CAPACITY = 64;
// 就是前面说的node table
transient Node<K,V>[] table;
// 目前保存的key value对数量
transient int size;
// 修改次数，用于检测并发修改情况，后面会专门分析
transient int modCount;
// 每次HashMap元素增加都去计算该不该扩容效率太低了
// 不如扩容的时候计算好，下次达到什么size的时候再次扩容，这个size就是threshold
// 即下一次该触发resize的阈值
int threshold;
重要操作源代码
插入数据
插入数据对应的put方法。代码如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
首先在hash方法中计算key的hash，如果key为null返回0。否则，取key对象的hashCode的高16位和hashCode的低16位异或作为hashCode的低16位，高16位保持不变。
这种算法将hashCode高16位的变化散布到低16位。因为后面计算key对应bin的时候，需要将hash值和HashMap的capacity（即Node<K,V>[] table的大小，不是HashMap实际存储对象数量的size） - 1做按位与运算（意思是只保留hash值的低capacity位）。所以说如果一组key的hashCode正好只在高位发生变化，这组key的hash值进行按位与之后是一定会发生冲突的。因此hash方法将hashCode的高位和低位变化通过异或运算，散布在一起，进一步减少hash碰撞的概率。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
然后调用putVal方法。将数据存入。
// onlyIfAbsent: 如果为true，key对应的值存在的时候不替换
// evict: true的话表示table在creation mode，在afterNodeInsertion回调中使用
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// n为table的length
// 如果node table为null或者length为0，返回初始化默认容量(16)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 找出元素对应的bin
// 算法为取hash值的后capacity位作为tab的下标，找到对应的node
// 如果node不存在，将值放入新的node中
if ((p = tab[i = (n - 1) & hash]) == null)
// 这里node是链表Node
// bin中只有一个数据的话，也用的是链表节点
tab[i] = newNode(hash, key, value, null);
else {
// 到这里说明存在key的hash碰撞
// 但不意味着key相同的元素已找到
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 节点内容的hash值相同，key为同一个object或者key语义等价
// 说明找到key相同的节点，接下来走替换值的流程
e = p;
else if (p instanceof TreeNode)
// 如果p是TreeNode，说明bin数据结构已经树形化，走添加树节点逻辑，后面分析
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 到这里是添加链表节点的过程
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 遍历链表，找到最后一个节点
// 在这个节点之后追加新节点
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 如果链表节点数量到达树形化阈值，切换为红黑树结构，后面分析
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 节点内容的hash值相同，key为同一个object或者key等价
// 说明key已存在，接下来走替换值的流程
break;
p = e;
}
}
if (e != null) { // existing mapping for key
// 这里是key相同的节点已找到，替换值的逻辑
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// 如果允许替换值，或者旧值为null
// 替换为新值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 自增修改计数
// 用来检测遍历的同时是否修改了hashMap
++modCount;
if (++size > threshold)
// size自增后如果大于threshold(Node table数组大小，2的n次方)
// 需要扩容2倍
resize();
afterNodeInsertion(evict);
return null;
}
删除数据
删除数据对应的是remove方法。代码如下：
public V remove(Object key) {
Node<K,V> e;
// 返回remove掉节点的值
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
hash计算逻辑和前面相同。这里只分析removeNode方法，如下：
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// 如果找到了hash对应的node，key存在于HashMap
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果hash相同，并且key是同一个object或者key语义相等（equals）
// 说明这个bin中只有一个node，没有链表或者树节点
// 或者该node恰好是bin中的第一个节点
// 记录下这个node，走后面删除节点逻辑
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
// 如果这个bin中是树形结构，调用getTreeNode找到这个node
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
// 遍历链表，查找node
node = e;
break;
}
// 当找到链表中符合条件的node之后，p为该node的上一个node
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 判断是否需要值相同的时候才移除node
if (node instanceof TreeNode)
// 如果是树节点，调用removeTreeNode
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 如果是bin中第一个节点（链表），tab[index]指向该节点下一个
// 如果bin中只有这一个节点也没关系，node.next为null，相当于将tab[index]设置为null
tab[index] = node.next;
else
// 如果node不是bin中链表第一个节点
// p的下一个节点指向node的下一个节点，跳过node，相当于把node删除
p.next = node.next;
// 自增修改计数
++modCount;
// 大小减一
--size;
afterNodeRemoval(node);
return node;
}
}
// key在hashMap中不存在，什么都没有remove，返回null
return null;
}
获取key对应的value
对应的为get方法。代码如下：
public V get(Object key) {
Node<K,V> e;
// 调用了getNode方法
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
接着分析getNode方法。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 找到bin中的第一个节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
// 如果hash和key都相同，返回这个节点
return first;
if ((e = first.next) != null) {
// 如果第一个节点的next节点不为空
// 说明这个bin中不止一个节点，需要分类为链表和树两种情况处理
if (first instanceof TreeNode)
// 如果是树节点，调用getTreeNode方法
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 如果是链表结构，遍历节点，直到找到hash和key都相同的节点返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 没有找到符合要求的节点，返回null
return null;
}
扩容
扩容对应resize方法。它不仅用于扩容，还可以在特定情况下恢复HashMap初始容量。
final Node<K,V>[] resize() {
// 保存resize之前的node table为oldTable
Node<K,V>[] oldTab = table;
// 获取resize之前的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 获取resize之前的threshold
int oldThr = threshold;
// 定义新容量，新threshold
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// 超过最大容量，不扩容返回
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// resize之前容量大于初始容量，并且容量扩大2倍之后小于最大容量
// 符合这个条件可进行扩容操作
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 新容量赋值为oldThreshold，为初始容量
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// oldCap和oldThr都为0
// 初始化容量
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 计算thredshold，乘以loadFActor，如果超过MAXIMUM_CAPACITY则newThr为Integer.MAX_VALUE
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的node table，容量为新的容量
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 逐个遍历旧node table
if ((e = oldTab[j]) != null) {
// 如果bin中存在node
// 清空旧table中bin对应的node
oldTab[j] = null;
if (e.next == null)
// e的next为null说明这个bin中只有一个节点
// 重新计算在新table中的位置后存入新table
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 如果节点是treeNode类型
// 需要将红黑树分裂，分裂的方法见后面分析
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 到这里，说明bin下存放着链表
// 需要将链表分裂
// 容量扩大2倍之后，由于hash值计算bin位置的时候需要和(容量-1)做按位与运算
// 因此他们在新table中的位置可能会改变
// 这里将链表按照在新table中的bin位置是否改变分为拆分为两个
// low为不需要移动的node，high为需要移动的node
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
// 遍历链表
next = e.next;
if ((e.hash & oldCap) == 0) {
// hash值没有变化，不需要移动到新的bin
// 这里组装low链表，loHead为链表开头，loTail为链表末尾
// 如果loTail为null说明为low链表开头，赋值loHead
if (loTail == null)
loHead = e;
else
// 否则将节点串到loTail之后
loTail.next = e;
// loTail指向当前节点，准备下一次循环操作
loTail = e;
}
else {
// 组装high链表
// hiHead为链表开头，loTail为链表末尾
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
// 这里说明low链表存在
loTail.next = null;
// low链表放入原先的bin中
newTab[j] = loHead;
}
if (hiTail != null) {
// 这里说明high链表存在
hiTail.next = null;
// high链表的bin位置为原来的bin位置+旧的容量值
// 将high链表存入新的bin中
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回处理过的node table
return newTab;
}
需要注意的是，扩容遇到链表或者红黑树的时候，需要将它分裂。
链表分裂的原理描述如下：
链表中所有节点的hash值扩容前后是不会改变的。但是hash值和新的容量-1按位与运算之后（确定元素在扩容后的HashMap中的bin位置），可能会出现两种结果（因为新capacity是老capacity的两倍，二进制多了一位）：
- 值仍然不变：这些节点仍保留在原先的bin中。
- 值发生了变化：新的值 = 旧的值 + 旧的capacity。这些节点需要移动到新的bin中。
TreeNode的split和链表分裂基本相同，区别在于分裂后需要检查红黑树的元素数量，如果数量过少，需要退化为链表结构。
这里将TreeNode的split方法提前讲解。它的代码如下所示：
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 和前面分拆链表的逻辑基本相同
// 多出来了low和high链表长度的统计，用于决定是否将分拆后的链表转换为树形结构
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
// 如果树中的元素小于阈值，退化为链表结构
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
// 前面构建的low树是个倾斜的树，这里需要重新树形化
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
遍历和并发修改限制
HashMap可以遍历EntrySet，keySet或者是values遍历时执行的逻辑分别是EntrySet， keySet和Values的forEach方法。这三个方法的内容基本上是完全一样的，除了消费遍历内容的consumer不一样。我们以EntrySet的forEach方法为例分析。
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
// 遍历node table
// 遍历前暂存modCount
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
// 如果一个bin中存储了链表或者是树结构，逐个遍历他们
action.accept(e);
}
// 遍历完成后检查modCount是否发生变化
// 如果变化抛出异常
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
需要注意的是modCount这个变量。HashMap只支持单线程操作，因此每次遍历的前后都会检查HashMap是否发生变化（put或remove的时候会修改modCount）。如果发生变化，抛出ConcurrentModificationException。可以阻止一个线程使用iterator遍历的同时，另一个线程使用HashMap的put或remove方法操作HashMap这种场景。
当然。上面的分析不代表HashMap不支持遍历的时候移除元素。我们可以在使用iterator遍历的时候，在同一个线程使用iterator的remove方法移除元素。该remove方法的代码位于HashIterator的remove方法。如下所示：
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
// remove前发生并发修改，报错
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
// remove节点
removeNode(hash(key), key, null, false, false);
// 然后重设expectedModCount
// 这是为什么iterator可以遍历的同时remove元素的原因
expectedModCount = modCount;
}
红黑树
到这里我们开始分析HashMap中最难理解的部分：红黑树的实现。
红黑树相对于其他树的好处是不需要维护各个节点的高度（距离根节点的距离）信息就可以保证基本平衡（比平衡二叉树宽松），处理效率相对较高。
HashMap中的红黑树和传统数据结构算法中的红黑树基本相同。熟悉数据结构的读者可以略过此节。不熟悉的读者可参考https://www.jianshu.com/p/e136ec79235c/。
本节侧重于代码层面分析红黑树操作。
树节点定义
TreeNode继承自LinkedHashMap.Entry，LinkedHashMap.Entry又继承自HashMap.Node。所以说TreeNode除了树节点自身的特性之外，还可以当作单向链表或者双向链表的节点使用。
// 父节点
TreeNode<K,V> parent; // red-black tree links
// 左节点
TreeNode<K,V> left;
// 右节点
TreeNode<K,V> right;
// 前一个节点。即便是树结构，仍然保留着链表时候的顺序，通过prev和next指针维护顺序
TreeNode<K,V> prev; // needed to unlink next upon deletion
// 表示是否是红黑树的红节点
boolean red;
TreeNode中的树节点相关概念：
- parent: 父节点
- left: 左子节点
- right: 右子节点
- red: 颜色。是否是红色
TreeNode中的双向链表节点相关概念：
- prev: 前一个节点
- next: 下一个节点
TreeNode中的单向链表节点相关概念：
- next: 下一个节点
重要方法
重要工具方法
在分析增删和查找节点之前，我们先分析几个比较重要的工具方法。
root方法返回包含当前节点的树的根节点。
final TreeNode<K,V> root() {
// 一直向上查找当前节点的父节点
// 直到父节点为null为止
// 这个节点就是当前树的root节点
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
moveRootToFront方法将指定的root节点作为bin的第一个节点存入node table中。
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
// 计算root节点应位于哪个bin下
int index = (n - 1) & root.hash;
// 取出来这个bin位置的第一个节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
// 如果这个节点不是root
Node<K,V> rn;
// 将root节点作为这个bin的第一个节点
tab[index] = root;
// rp是root的前一个节点
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
// 如果root下一个节点存在
// rn的前一个设为rp
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
// 如果rp存在
// rp的下一个设置为rn
rp.next = rn;
// 前面两个if相当于rn和rp直接关联，跳过root节点本身
if (first != null)
// 如果first存在，first前一个设置为root
first.prev = root;
// 关联root下一个节点为first
root.next = first;
root.prev = null;
}
// 检查红黑树的合法性
assert checkInvariants(root);
}
}
moveRootToFront没有改变树结构，仅仅是将TreeNode视为双向链表调整了顺序。将指定的root节点作为第一个节点存入bin。
checkInvariants方法检查红黑树的合法性。逻辑如下：
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
if (tb != null && tb.next != t)
// 前一个节点存在，且前一个节点的下一个节点不是本节点
// 说明树有问题，返回false
return false;
if (tn != null && tn.prev != t)
// 下一个节点存在，且下一个节点的前一个节点不是本节点
return false;
if (tp != null && t != tp.left && t != tp.right)
// 父节点存在，当前节点既不是父节点的左节点也不是右节点
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
// 左节点存在，左节点的父节点不是当前节点或者是左节点的hash值大于当前节点的hash值（顺序不对）
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
// 右节点同理
return false;
if (t.red && tl != null && tl.red && tr != null && tr.red)
// 当前节点是红节点，且左右节点都为红色
return false;
if (tl != null && !checkInvariants(tl))
// 左节点需要递归检查
return false;
if (tr != null && !checkInvariants(tr))
// 右节点同理
return false;
return true;
}
链表转换为树结构
我们从HashMap把bin中的链表转换为树结构的方法treeifyBin开始分析。代码如下：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 如果不符合树形化条件，调用resize方法
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 找到bin中第一个节点
TreeNode<K,V> hd = null, tl = null;
do {
// 遍历整个链表
// 替换e为TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
// 设置头节点
hd = p;
else {
// 将链表上所有节点转换为TreeNode，使用prev和next指针，保持原来的顺序串起来
// 这里只是将节点类型转换而已，真正的树结构还没有形成
// 最后的treeify方法才生成树结构
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
// 生成树形结构
hd.treeify(tab);
}
}
treeify树形化方法，生成树结构。
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
// x为当前节点，next为下一个节点
next = (TreeNode<K,V>)x.next;
// 左右都设为null
x.left = x.right = null;
if (root == null) {
// 如果没有root
// 设置当前节点为root
x.parent = null;
// 红黑树root节点为黑节点
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
// 这个for的逻辑为寻找x节点插入树的位置，将x节点插入
// 从root节点开始，寻找插入节点的位置
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
// p的hash大于x的hash
dir = -1;
else if (ph < h)
// p的hash小于x的hash
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// 如果hash相同，compareTo方法比较也相同，两者class名称仍相同
// 调用tieBreakOrder方法比较，使用System.identityHashCode比较
dir = tieBreakOrder(k, pk);
// xp意思是x的父节点
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 根据dir，找到p的左节点或右节点，如果为null的话
// x的父节点设置为p
x.parent = xp;
// 根据dir，设置xp的左节点或右节点为x
// 将x节点插入树中
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 插入x节点后红黑树可能会被破坏，需要重新平衡
// 平衡后root节点可能会有变化
root = balanceInsertion(root, x);
break;
}
}
}
}
// 最后，将root节点作为bin的第一个节点，存入node table
moveRootToFront(tab, root);
}
tieBreakOrder方法从className和内存地址产生的hashCode来比较两个对象。归根结底也要比较出两个对象的大小。
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
// System.identityHashCode忽略对象是否重写了hashCode方法，永远返回根据对象物理内存地址产生的hash值
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
查找节点
从当前节点的子树中查找符合条件的子节点。
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
// h比ph小，查找左子树
p = pl;
else if (ph < h)
// 否则，查找右子树
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
// 如果hash相同，key是同一个object或者是key语义上相同，p就是要找的节点，返回它
return p;
else if (pl == null)
// 如果hash相同，key为null或语义不同
// 向下遍历存在的子树
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
// 如果左右子树都存在，使用key类型自定义的比较方法比较结果
// 确定是查找左子树还是右子树
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
// 如果key的自定义比较结果相同，或者kc是null（没实现Comparable接口）
// 递归查找右子树
return q;
else
// 上面没找到结果，下一次遍历处理左子树
p = pl;
} while (p != null);
// 没有找到返回null
return null;
}
插入数据
putTreeVal方法，将键值加入到树结构中。
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
// 获取根节点，通常来说this为bin的第一个节点，也是树的根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
// 从p(root)节点开始循环
// ph是p节点的hash
// pk是p节点的key
int dir, ph; K pk;
if ((ph = p.hash) > h)
// 如果p的hash比要插入节点的hash大
// 说明需要找p左节点，dir(方向)设置为-1
dir = -1;
else if (ph < h)
// 否则找p的右节点
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
// hash值相同的情况下
// 如果pk和k是同一个object或者语义相等
// 这个节点已找到，返回它
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
// hash值相同，k为null或者语义不相等
// k的class没有实现Comparable接口
// 或者k的class实现了Comparable接口，使用k自定义的比较逻辑比较大小仍相等
if (!searched) {
TreeNode<K,V> q, ch;
// 标记已搜索
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
// 依次从p的左节点和右节点找值相同的节点，如果找到就返回
return q;
}
// 如果找不到，就比较class name甚至是k对象本身的hashCode（忽略重写的hashCode方法逻辑）
dir = tieBreakOrder(k, pk);
}
// 赋值p到xp
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 根据dir找p的左节点或右节点，如果是null的话
// 获取xp的下一个节点
// 这里需要注意prev和next是链表中的概念
// HashMap在树节点中还同时维护着链表的前后关系
Node<K,V> xpn = xp.next;
// 新建一个TreeNode，这个TreeNode下一个节点是xp的next节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
// 关联新创建的x节点到树中
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 关联链表结构
xp.next = x;
// x的前一个节点设为xp
// x的父节点设置为xp
x.parent = x.prev = xp;
// 如果xp下一个节点存在，设置它的前一个节点为新插入的x节点
// 到这里链表结构的节点新增和树结构的节点新增都已完成
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 插入节点后进行平衡树操作，然后找出平衡后的根节点，作为在bin中的first节点
moveRootToFront(tab, balanceInsertion(root, x));
// 新插入节点的情况返回null
return null;
}
// 如果上面p的左节点或右节点存在，需要再递归处理它的左节点或右节点
}
}
balanceInsertion方法用于插入节点之后平衡红黑树。每次插入数据前树都是平衡过的，只需考虑新加入节点造成的影响。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// x为新插入的节点
// 新插入的节点永远是红色的。如果插入后不符合红黑树规则，再做变换
// 如果新插入的节点是黑色的，那么一定会出现这条路径上黑色节点多于其他路径这种情况
// 即每次插入节点都必须要平衡，效率很低
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
// 一直循环，直到手动退出
if ((xp = x.parent) == null) {
// 新插入的节点没有父节点，意思是新插入的节点为树的根节点
// 根据红黑树规则，根节点一定是黑色节点
x.red = false;
// 返回根节点
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
// x节点为黑色，或者没有祖父节点，无需操作返回root节点
// 这个if分支只会在递归向上变换的时候才会进入
return root;
if (xp == (xppl = xpp.left)) {
// 父节点为红色
// 父节点是祖父节点的左节点
if ((xppr = xpp.right) != null && xppr.red) {
// xppr是祖父节点的右节点，即叔叔节点
// 如果叔叔节点也是红色，只需做变色处理
// 父节点和叔节点本来是红色的，将他们变为黑色
xppr.red = false;
xp.red = false;
// 将祖父节点变为红色
xpp.red = true;
// 当前节点设置为祖父节点，递归变色或旋转过程
x = xpp;
}
else {
// 如果叔叔节点不存在或者是黑色
// 需要将树旋转
if (x == xp.right) {
// 如果当前节点是父节点的右节点，需要将父节点左旋
// 将xp作为当前节点
root = rotateLeft(root, x = xp);
// 重新赋值旋转后的xpp（祖父节点）
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
// 如果父节点存在，设置父节点为黑色
xp.red = false;
if (xpp != null) {
// 祖父节点设为红色
xpp.red = true;
// 祖父节点右旋
root = rotateRight(root, xpp);
}
}
}
}
else {
// 父节点为红色
// 父节点是祖父节点的右节点
// 和上面if分支的处理方式相同，只是逻辑反过来而已
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
// 如果当前节点是父节点的左节点，需要将父节点右旋
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
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) {
// p为需要左旋的节点
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
// r赋值为p的右节点
// 如果p和p的右节点存在
// 这段用来调整子树
if ((rl = p.right = r.left) != null)
// r的左节点变为p的右节点
// rl节点为从右子树移动到左子树的节点
// rl的父节点不再为r，需要设置为p
rl.parent = p;
// 这段用来调整父节点和旋转后的r节点的关系
if ((pp = r.parent = p.parent) == null)
// 右节点的父节点不再为p，需要调整为p的父节点
// pp设为r的父节点
// 如果pp不存在，说明旋转过后的r为目前树的根节点
// 重新设置root节点，将root节点标记为黑色
(root = r).red = false;
else if (pp.left == p)
// 如果旋转之前当前节点是pp的左节点
// 那么旋转后pp的左节点为r
pp.left = r;
else
// 同理，旋转之前当前节点是pp的右节点
// 那么旋转后pp的右节点为r
pp.right = r;
// 这段用来调整r和p的关系
// p变为r的左节点
r.left = p;
// p的父节点为r
p.parent = r;
}
return root;
}
右旋的逻辑和左旋基本相同，唯一区别就是代码中左右节点反过来。不再赘述。
插入节点平衡逻辑整理如下：
- 插入的节点永远为红色
- 如果插入节点的父节点为黑色，不需要平衡
- 如果插入节点的父节点为红色。分为下面两种情形。
下面只讨论插入节点的父节点是祖父节点的左节点(xp == xppl)。
- 情形1：x是xp的左节点(x == xpl)，左旋pp，pp变红，p变黑。
- 情形2：x是xp的右节点(x == xpr)，右旋p节点，再左旋pp节点。pp变红，x变黑。
如果xp == xppr，和上面的情形逻辑相同，操作方向对称过来即可，不再赘述。
删除数据
removeTreeNode方法在树中删除当前节点（谁调用removeTreeNode就删除谁）。
红黑树节点删除分为如下步骤：
- 找出需要删除的节点。
- 如果删除节点没有任何子节点，直接删除。
- 如果删除节点只有一个子节点，使用子节点代替删除节点。
- 如果删除节点具有两个子节点。使用后继节点替代被删除的节点。
- 重新将树平衡。
这里的后继节点是比删除节点大的最小节点。
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
// movable是删除节点的时候可否移动其他节点
int n;
if (tab == null || (n = tab.length) == 0)
return;
// 计算节点hash
int index = (n - 1) & hash;
// 找到树的root节点（对应bin中的第一个节点）
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
// 从链表的范畴，将本节点（要删除的节点）剔除
// succ为当前节点的后继节点，pred为前置节点
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
// 如果没有前置节点，把bin的第一个节点设置为后继节点
tab[index] = first = succ;
else
// 否则把前置节点和后继节点连起来，跳过要删除的当前节点
pred.next = succ;
if (succ != null)
// 如果有后继节点，把它和前置节点连起来
succ.prev = pred;
if (first == null)
return;
if (root.parent != null)
// 如果root节点不是tree真正的root节点，找到它
root = root.root();
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
// 树中元素太少，退化为链表结构
tab[index] = first.untreeify(map); // too small
return;
}
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
// p为要删除的节点，pl是要删除节点的左节点，right是要删除节点的右节点，replacement是替换掉要删除节点的节点
// 删除一个节点后，为了仍保持树结构，需要找到比删除节点大的最小节点来替换它，这个替换的节点就是replacement
if (pl != null && pr != null) {
// 最复杂的情况，pl和pr都存在
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // find successor
// 一直向下查找pr的各级左节点，找到比删除节点大的最小节点
s = sl;
// s节点和p节点交换颜色
// 后面会交换s和p节点，意思就是s节点和p节点所在位置的颜色不变
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
// 如果正好p的右节点是s，即s的父节点是p
// s p交换位置
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
// p的父节点指向s的父节点
// p取代原来s的位置
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
// s右节点设为p的右节点
// p右节点的父节点设置为s
// 即p的右子树关联到s上
pr.parent = s;
}
// p左节点清空
p.left = null;
if ((p.right = sr) != null)
// p右节点设为s的右节点
// sr父节点设置为p
sr.parent = p;
if ((s.left = pl) != null)
// s不可能存在左子树，因为s是刚好比p大的最小元素，是从pr节点开始一直查找左节点，直到它是叶子节点的结果（一直查找直到左节点是null为止）
// s的左节点和p原本的左节点树建立联系
pl.parent = s;
// 这段if用来关联s和pp节点
if ((s.parent = pp) == null)
// 设置s的父节点为p的父节点
// 如果为null，说明现在s为根节点
root = s;
else if (p == pp.left)
// pp关联到s节点
// s取代p节点
pp.left = s;
else
// 同上
pp.right = s;
// 到这里为止s和p节点已完成位置交换
// 如果s有右节点，replacement为右节点
// 否则为p，接下来会移除p节点
// sl肯定为null，所以这里不用考虑
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
// 如果p的子节点只有左或右，replacement取这个唯一的子节点
replacement = pl;
else if (pr != null)
// 同上
replacement = pr;
else
// 如果没有任何子节点(1)
replacement = p;
if (replacement != p) {
// replacement为sr
// 设置sr的父节点为交换过位置之后的p节点的parent
// p节点被孤立
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
// 如果pp为null，说明root节点就是replacement节点
root = replacement;
// 下面将pp直接和replacement关联起来，p节点彻底和树断开联系
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
// p和其他所有节点解除关系
p.left = p.right = p.parent = null;
}
// 如果删除的节点(现在的p节点，颜色为原来s节点的颜色，因为前面s和p互换过颜色)是红节点，不需额外操作树仍然是平衡的
// 否则需要做删除后平衡
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
// (1)中的情况，p没有任何子节点
TreeNode<K,V> pp = p.parent;
// 将p和p的父节点解除关系
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
// 将root节点作为bin中存放的第一个节点
moveRootToFront(tab, r);
}
上面的逻辑总结为：
- 找出后继节点s（比p大的最小节点，即pr递归查找left节点，直到left节点为null为止）。
- s和p节点交换位置，s原本的右子树关联到p节点上，p原本的左右子树关联到s节点上。
- 如果p节点有子节点，将pp节点和p的子节点（只可能有右节点）直接连接。p节点被孤立，将被移除。替换p节点的节点为原s的右节点。
- 如果p节点为红色节点，直接移除不违反红黑树规则。否则需要做删除后平衡。
- 如果p没有子节点，直接移除p。替换p的节点是p本身。
balanceDeletion方法删除后平衡。删除节点之前的树是平衡过的，仅需要考虑本次删除节点造成的影响。
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// x为替换节点，即removeTreeNode中的replacement
// 如果s,p交换前s没有右节点，replacement为交换后的p节点，否则为交换后的p节点的右节点（即交换前的s节点的右节点）
// 方法返回值为平衡后树的根节点
for (TreeNode<K,V> xp, xpl, xpr;;) {
if (x == null || x == root)
// x不存在或者x就是root，返回root
return root;
else if ((xp = x.parent) == null) {
// 如果x是root节点，s,p交换后root节点可能发生变化
// 根据红黑树规则，设置x节点为黑色
x.red = false;
// 返回x节点
return x;
}
else if (x.red) {
// 如果x是红节点，变为黑色
// 如果x是叶子节点，移除了不影响平衡下
// 如果x不是叶子节点，p节点的右节点是replacement节点，被移除的p节点一定是黑色的（两个红色节点不可能相邻）
// 移除p后少一个黑色节点，把x变为黑色后刚好弥补，树结构仍然正确，无需进一步处理
x.red = false;
return root;
}
else if ((xpl = xp.left) == x) {
// x是黑色节点，x是其父节点的左节点
// (1)
if ((xpr = xp.right) != null && xpr.red) {
// x的右兄弟节点为红色，将其变为黑色
xpr.red = false;
// 父节点变为红色
xp.red = true;
// 左旋父节点，为左子树补充一个黑色节点，右子树黑节点不变
root = rotateLeft(root, xp);
// 赋值旋转后的兄弟节点，为原兄弟节点的左节点（如果有的话），黑色
xpr = (xp = x.parent) == null ? null : xp.right;
}
// 如果没有兄弟节点，此时子树已经平衡，需要向上递归执行
if (xpr == null)
x = xp;
else {
// 如果有兄弟节点
// 到这里xpr一定是黑色
// 如果xpr存在且为黑色，不走上面的(1)处的if分支
// 如果xpr是上面(1)处if分支左旋之后的新xpr，这个新xpr是原来x兄弟节点的左节点
// 原来兄弟节点是红色（进if分支的条件），由红黑树规则可知，红色节点不可能直接连接
// 所以原来x兄弟节点的左节点一定是黑色的
// 因此这里xpr一定是黑色
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
// sl为兄弟节点左节点，sr为兄弟节点右节点
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
// 兄弟节点的左右节点都不是红色节点
// 设置兄弟节点为红色
// 此时兄弟节点所在子树的黑色节点数减少1，和x节点子树相同，xp以下已平衡
xpr.red = true;
// 向上递归
x = xp;
}
else {
// 兄弟节点的左右节点存在红节点
if (sr == null || !sr.red) {
// 兄弟节点右节点不存在或者是黑色
// 兄弟节点左节点不存在或者是红色
if (sl != null)
// 兄弟节点左节点存在，变为黑色
// 左子树黑色+1
sl.red = false;
// 兄弟节点变为红色
// 从兄弟节点开始，左子树黑色数量复原，右子树黑色-1
xpr.red = true;
// 兄弟节点右旋
// sl为黑色，s为红色，sr为黑色
// 右旋后左子树黑色节点不变，右子树黑色复原
// 恢复平衡
root = rotateRight(root, xpr);
// 获取右旋后的兄弟节点
// 这段if变换后，兄弟节点是原兄弟节点的左节点，为黑色
// 兄弟节点的右节点为红色
xpr = (xp = x.parent) == null ?
null : xp.right;
}
// 下面统一处理兄弟节点的右节点为红色这种情况
// 这里思路就是从兄弟节点右子树中借一个红色节点过来(sr)
// 旋转前后保持原来x，xp和s位置的节点颜色不变
// 这样x节点所在子树就比原来多了一个黑色节点，x兄弟节点所在子树黑色不变
// x节点替换后可保持平衡
// 如果兄弟节点存在
if (xpr != null) {
// 兄弟节点设置为父节点的颜色
// 如果父节点不存在，兄弟节点设置为黑色
xpr.red = (xp == null) ? false : xp.red;
// 如果兄弟节点右节点存在，设置为黑色
if ((sr = xpr.right) != null)
sr.red = false;
}
if (xp != null) {
// x有父节点，则父节点设置为黑色，xp左右树黑色都+1
xp.red = false;
// 左旋父节点
root = rotateLeft(root, xp);
}
// 将x设为root，递归
x = root;
}
}
}
else { // symmetric
// 如果x是黑色节点，x是父节点的右节点
// 和上面的逻辑相同，只有操作方向是反过来的，完全对称
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
下面总结最复杂的情况：删除节点(x)是黑色，并且存在兄弟节点。
如果替换节点是父节点(xp)的左节点（x == xpl）且xpr（兄弟节点）为红色。xp变为红色，xpr变为黑色，左旋xp。之后x的兄弟节点为原来的xprl，一定是黑色。变换为下面的场景。
如果替换节点是父节点(xp)的左节点（x == xpl）且xpr（兄弟节点）为黑色。
- 情况1：替换节点的兄弟节点的右节点（sr）为红色。借用sr，左旋xp节点，保持原树位置的节点颜色不变。从而实现xp左子树（替换节点所在子树）黑色节点+1，右子树黑色节点数目不变。可保持平衡。
- 情况2：替换节点的兄弟节点的右节点（sr）为黑色，sl为红色。sl变为黑色，s变为红色。左旋s，变为情况1。
- 情况3：sr和sl都是黑色。将s直接变红，然后xp作为替换节点递归向上。
同理，如果替换节点是父节点(xp)的右节点(x == xpr)，逻辑和前面的相同，区别仅是操作方向对称过来，不再赘述。
树结构退化为链表
untreeify方法将树结构退化为链表。
// 调用这个方法的节点应为头节点（树中最小的节点）
final Node<K,V> untreeify(HashMap<K,V> map) {
// 创建head(hd)和tail(tl)
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
// 从当前节点逐个向后遍历
// 替换树节点为普通链表节点
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
// 开始遍历的时候tl为null，需要指定hd
hd = p;
else
// 链表向后组装
tl.next = p;
// 移动链表尾部指针
tl = p;
}
// 返回链表头节点
return hd;
}
网友评论