概述
JDK 8对HashMap进行了比较大的优化，底层实现由之前的数组+链表改为数组+链表+红黑树，本文就HashMap的几个主要方法和Jdk 1.8之前的死循环问题展开学习讨论。JDK 8的HashMap的数据结构如下图所示，当链表节点较少时仍然是以链表存在，当链表节点较多时（大于8）会转为红黑树。
本文地址：http://blog.csdn.net/v123411739/article/details/78996181
几个点：
先了解以下几个点，有利于更好的理解HashMap的源码和阅读本文。
- 头节点指的是table表上索引位置的节点，也就是链表的头节点。
- 根结点（root节点）指的是红黑树最上面的那个节点，也就是没有父节点的节点。
- 红黑树的根结点不一定是索引位置的头结点。
- 转为红黑树节点后，链表的结构还存在，通过next属性维持，红黑树节点在进行操作时都会维护链表的结构，并不是转为红黑树节点，链表结构就不存在了。
- 在红黑树上，叶子节点也可能有next节点，因为红黑树的结构跟链表的结构是互不影响的，不会因为是叶子节点就说该节点已经没有next节点。
- 源码中一些变量定义：如果定义了一个节点p，则pl为p的左节点，pr为p的右节点，pp为p的父节点，ph为p的hash值，pk为p的key值，kc为key的类等等。源码中很喜欢在if/for等语句中进行赋值并判断，请注意。
-
链表中移除一个节点只需如下图操作，其他操作同理。
-
红黑树在维护链表结构时，移除一个节点只需如下图操作（红黑树中增加了一个prev属性），其他操作同理。注：此处只是红黑树维护链表结构的操作，红黑树还需要单独进行红黑树的移除或者其他操作。
基本属性
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载因子0.75
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8; // 链表节点转换红黑树节点的阈值, 9个节点转
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6; // 红黑树节点转换链表节点的阈值, 6个节点转
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64; // 转红黑树时, table的最小长度
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> { // 基本hash节点, 继承自Entry
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;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
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);
}
// ...
}
get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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) { // table不为空 && table长度大于0 && table对应位置(根据hash值计算出的索引位置)不为空
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k)))) // first节点的key和hash值等于传入的则返回first节点
return first;
if ((e = first.next) != null) { // 否则向下遍历
if (first instanceof TreeNode) // 判断是否为TreeNode
return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 调用红黑树的方法查找目标节点
do { // 向下遍历链表, 直至找到一个节点的key和传入的key相等时, 返回该节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null; // 找不到符合的返回空
}
- 先对table进行校验，校验是否为空，length是否大于0
- 使用table.length - 1和hash值进行位与运算，得出在table上的索引位置，将该索引位置的节点赋值给first节点，校验该索引位置是否为空
- 检查first节点的hash值和key是否和入参的一样，如果一样则first即为目标节点，直接返回first节点
- 如果first的next节点不为空则继续遍历
- 如果first节点为TreeNode，则调用getTreeNode方法（见下文代码块1）查找目标节点
- 如果first节点不为TreeNode，则调用普通的遍历链表方法查找目标节点
- 如果查找不到目标节点则返回空
代码块1：getTreeNode方法
/**
* Calls find for root node.
*/
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null); // 父节点为空则代表该节点为根节点, 直接返回根结点, 否则调用find方法
}
- 找到调用此方法的节点的树的根节点
- 使用该树的根节点调用find方法（见下文代码块2）
代码块2：find方法
/**
* Finds the node starting at root p with the given hash and key.
* The kc argument caches comparableClassFor(key) upon first use
* comparing keys.
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) { // 从first节点(根结点)开始查找, 通过hash值和key找到对应的节点(此处是红黑树的遍历, 红黑树是特殊的自平衡二叉查找树)
TreeNode<K,V> p = this; // this为上文的first节点
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h) // 传入的hash值小于p节点的hash值, 则往p节点的左边遍历
p = pl; // p赋值为p节点的左节点
else if (ph < h) // 传入的hash值大于p节点的hash值, 则往p节点的右边遍历
p = pr; // p赋值为p节点的右节点
else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 传入的hash值等于p节点的hash值并且传入的key值跟p节点的key值相等, 则该p节点即为目标节点, 返回p节点
return p;
else if (pl == null) // p节点的左节点为空则将向右遍历
p = pr;
else if (pr == null) // p节点的右节点为空则向左遍历
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) && // 如果传入的key(k)所属的类实现了Comparable接口, 则将传入的key跟p节点的key进行比较
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr; // k < pk则向左遍历(p赋值为p的左节点), 否则向右遍历
else if ((q = pr.find(h, k, kc)) != null) // 代码走到此处, 代表key所属类没有实现Comparable, 因此直接指定向p的右节点递归
return q;
else
p = pl; // 以上都不符合则将p赋值为p的左节点, 与上一个判断进行对应, 上一个判断向右递归没有结果, 则向左进行查找
} while (p != null);
return null;
}
- 将p节点赋值为调用此方法的节点
- 如果传入的hash值小于p节点的hash值, 则往p节点的左边遍历
- 如果传入的hash值大于p节点的hash值, 则往p节点的右边遍历
- 如果传入的hash值等于p节点的hash值，并且传入的key值跟p节点的key值相等, 则该p节点即为目标节点, 返回p节点
- 如果p的左右节点有为空的，则直接向另一个方向遍历
- 如果传入的key（即代码中的变量k）所属的类实现了Comparable接口（kc不为空，comparableClassFor方法见下文代码块3）, 并且传入的key跟p节点的key进行比较结果不想等，k < pk则向左遍历（p赋值为p的左节点）, 否则向右遍历
- 代码走到此处，代表key所属类没有实现Comparable，因此直接指定向p的右节点递归，如果能查找目标节点则返回
- 以上都不符合则将p赋值为p的左节点，与7）对应, 上一个判断向右递归没有结果，则向左进行查找
- 以上都找不到目标节点则返回空
代码块3：comparableClassFor方法
/**如果x实现了Comparable接口，则返回实现该接口的类。
* Returns x's Class if it is of the form "class C implements
* Comparable<C>", else null.
*/
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
put方法
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) // table是否为空或者length等于0, 如果是则调用扩容方法
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 通过hash值计算索引位置, 如果table表该索引位置节点为空则新增一个
tab[i] = newNode(hash, key, value, null);
else { // table表的该位置不为空
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 判断p节点(传入hash值对应索引位置的头节点)的key是否跟传入的key相等
e = p; // 如果相等, 则p节点即为要查找的目标节点
else if (p instanceof TreeNode) // 判断p节点是否为TreeNode, 如果是则调用红黑树的putTreeVal方法查找目标节点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) { // 遍历此链表, binCount用于统计节点数
if ((e = p.next) == null) { // 查找不到key相同的值则新增一个节点并插入链表尾部
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 校验节点是否超过8个, 减一是因为此处是从p节点的下一个节点开始的
treeifyBin(tab, hash); // 将该链表节点转换为红黑树节点(即根据传入的hash值计算的索引位置的链表)
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) // e节点的hash值和key值都与传入的相等, 则e即为目标节点, 跳出循环
break;
p = e; // 遍历下一个节点
}
}
if (e != null) { // e不为空则代表根据传入的hash值和key值查找到了节点, 将该节点的value覆盖, 返回oldValue
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 用于LinkedHashMap
return oldValue;
}
}
++modCount;
if (++size > threshold) // 插入节点后超过阈值则进行扩容
resize();
afterNodeInsertion(evict); // 用于LinkedHashMap
return null;
}
- 校验table是否为空或者length等于0，如果是则调用resize方法（见下文resize方法）进行扩容
- 通过hash值计算索引位置，将该索引位置的节点赋值给p节点，如果该索引位置节点为空则使用传入的参数新增一个节点
- 判断p节点的key和hash值是否跟传入的相等，如果相等, 则p节点即为要查找的目标节点，将p节点赋值给e节点
- 如果p节点不是目标节点，则判断p节点是否为TreeNode，如果是则调用红黑树的putTreeVal方法（见下文代码块4）查找目标节点
- 如果p节点也不是TreeNode，则调用普通的链表方法进行查找，并定义变量binCount来统计该链表的节点数
- 如果p的next节点为空时，则代表找不到目标节点，则新建一个节点并插入链表尾部，并校验节点数是否超过8个，如果超过则调用treeifyBin方法（见下文代码块6）将链表节点转为红黑树节点
- 如果遍历的节点存在hash值和key值都与传入的相同，则该节点即为目标节点，赋值给e节点，并跳出循环
- 如果e节点不为空，则代表目标节点存在，使用传入的value覆盖该节点的value，并返回oldValue
- 如果时新增节点则判断新增后的节点大小是否超过阈值，如果超过则调用resize方法（见下文resize方法）进行扩容
代码块4：putTreeVal方法
/**
* Tree version of putVal.
* 红黑树插入会同时维护原来的链表属性, 即原来的next属性
*/
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;
TreeNode<K,V> root = (parent != null) ? root() : this; // 查找根节点, 索引位置的头节点并不一定为红黑树的根结点
for (TreeNode<K,V> p = root;;) { // 将根节点赋值给p, 开始遍历
int dir, ph; K pk;
if ((ph = p.hash) > h) // 如果传入的hash值小于p节点的hash值, 将dir赋值为-1, 代表向左查找树
dir = -1;
else if (ph < h) // 如果传入的hash值大于p节点的hash值, 将dir赋值为1, 代表向右查找树
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 传入的hash值等于p节点的hash值并且传入的key值跟p节点的key值相等, 则该p节点即为目标节点, 返回p节点
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) { // 如果传入的hash值跟p节点的hash值相同, 并且k的类没有实现Comparable接口(不可比较), 或者k和p节点的key相等
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节点的左节点和右节点分别调用find方法进行查找, 如果查找到目标节点则返回
return q;
}
dir = tieBreakOrder(k, pk); // 否则使用定义的一套规则来比较k和p节点的key的大小, 用来决定向左还是向右查找
}
TreeNode<K,V> xp = p; // x的父节点变量, 中间变量, 用于下面给x的父节点赋值
if ((p = (dir <= 0) ? p.left : p.right) == null) { // dir <= 0则向左节点查找, 否则向右节点查找, 如果已经无法继续查找, 则代表该位置即为x的目标位置
Node<K,V> xpn = xp.next; // x的父节点的next节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); // 创建新的节点, 其中x的next节点为原来x的父节点的next节点, 即将x节点插入x的父节点与原x的父节点的next节点之间
if (dir <= 0) // 如果时dir <= 0, 则代表x节点为父节点的左节点
xp.left = x;
else // 如果时dir> 0, 则代表x节点为父节点的右节点
xp.right = x;
xp.next = x; // 将x的父节点的next节点设置为x
x.parent = x.prev = xp; // 将x的parent和prev节点设置为xp
if (xpn != null) // 如果原x的父节点的next节点不为空, 则将该节点的prev节点设置为x节点, 与上文的x节点的next节点对应
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x)); // 进行红黑树的插入平衡调整
return null;
}
}
}
- 查找当前红黑树的根结点，将根结点赋值给p节点，开始进行查找
- 如果传入的hash值小于p节点的hash值，将dir赋值为-1， 代表向左查找树
- 如果传入的hash值大于p节点的hash值， 将dir赋值为1，代表向右查找树
- 如果传入的hash值等于p节点的hash值，并且传入的key值跟p节点的key值相等, 则该p节点即为目标节点，返回p节点
- 如果传入的hash值等于p节点的hash值，并且k的类没有实现Comparable接口（不可比较），或者k和p节点的key使用compare方法比较相等：第一次会从p节点的左节点和右节点分别调用find方法（见上文代码块2）进行查找，如果查找到目标节点则返回；如果不是第一次或者调用find方法（见上文代码块2）没有结果，则调用tieBreakOrder方法（见下文代码块5）比较k和p节点的key值的大小，以决定向树的左节点还是右节点查找。
- 如果dir <= 0则向左节点查找（p赋值为p.left，并进行下一次循环），否则向右节点查找，如果已经无法继续查找（p赋值后为null），则代表该位置即为x的目标位置，另外变量xp用来记录最后一个节点，即为下文新增的x节点的父节点。
- 以传入的hash、key、value参数和xp节点的next节点为参数，构建x节点（注意：xp节点在此处可能是叶子节点、没有左节点的节点、没有右节点的节点三种情况，即使它是叶子节点，它也可能有next节点，红黑树的结构跟链表的结构是互不影响的，不会因为某个节点是叶子节点就说它没有next节点，红黑树在进行操作时会同时维护红黑树结构和链表结构），根据dir的值决定x决定放在xp节点的左节点还是右节点，将xp的next节点设为x，将x的父节点和prev节点设为xp，如果原xp的next节点（xpn）不为空, 则将该节点的prev节点设置为x节点, 与上面的将x节点的next节点设置为xpn对应。
- 进行红黑树的插入平衡调整，见文末的解释2。
代码块5：tieBreakOrder方法
/**定义一套规则用于极端情况下比较两个参数的大小。
* Tie-breaking utility for ordering insertions when equal
* hashCodes and non-comparable. We don't require a total
* order, just a consistent insertion rule to maintain
* equivalence across rebalancings. Tie-breaking further than
* necessary simplifies testing a bit.
*/
static int tieBreakOrder(Object a, Object b) { // 用于不可比较或者hashCode相同时进行比较的方法, 只是一个一致的插入规则来维护重定位的等价性。
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
代码块6：treeifyBin方法
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
* 将所有链表节点转为红黑树节点, 如果table太小则进行扩容
*/
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) // table为空或者table的长度小于64, 进行扩容
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) { // 根据hash值计算索引值, 遍历该索引位置的链表
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null); // 链表节点转红黑树节点
if (tl == null)
hd = p; // 头结点
else {
p.prev = tl; // 当前节点的prev属性设为上一个节点
tl.next = p; // 上一个节点的next属性设置为当前节点
}
tl = p; // tl赋值为p, 在下一次循环中作为上一个节点
} while ((e = e.next) != null);
if ((tab[index] = hd) != null) // 将table该索引的位置赋值为新转的TreeNode的头节点, 如果不为空
hd.treeify(tab); // 以头结点为根结点, 转红黑树
}
}
- 校验table是否为空，如果长度小于64，则调用resize方法（见下文resize方法）进行扩容。
- 根据hash值计算索引值，将该索引位置的节点赋值给e节点，从e节点开始遍历该索引位置的链表。
- 调用replacementTreeNode方法（该方法就一行代码，直接返回一个新建的TreeNode）将链表节点转为红黑树节点，将头结点赋值给hd节点，每次遍历结束将p节点赋值给tl，用于在下一次循环中作为上一个节点进行一些链表的关联操作（p.prev = tl 和 tl.next = p）。
- 将table该索引的位置赋值为新转的TreeNode的头节点hd，如果该节点不为空，则以hd为根结点，调用treeify方法（见下文代码块7）转红黑树。
代码块7：treeify方法
/**
* Forms tree of the nodes linked from this node.
* @return root of tree
*/
final void treeify(Node<K,V>[] tab) { // 构建红黑树
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) { // this即为调用此方法的TreeNode
next = (TreeNode<K,V>)x.next; // next赋值为x的下个节点
x.left = x.right = null; // 将x的左右节点设置为空
if (root == null) { // 如果还没有根结点, 则将x设置为根结点
x.parent = null; // 根结点没有父节点
x.red = false; // 根结点必须为黑色
root = x; // 将x设置为根结点
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) { // 如果当前节点不是根结点, 则从根节点开始查找属于x节点的位置
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) // 如果x节点(将要插入红黑树的节点)的hash值小于p节点(当前遍历到的红黑树节点)的hash值, 则向p节点的左边查找
dir = -1; // 设置-1, 用于下文向左查找
else if (ph < h) // 与上面相反, 如果x节点的hash值大于p节点的hash值, 则向p节点的右边查找
dir = 1; // 设置1, 用于下文向右查找
else if ((kc == null && // 如果x节点的hash值跟p节点的hash值相同, 并且x的key没有实现Comparable接口(不可比较), 或者x节点的key和p节点的key相等
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk); // 使用定义的一套规则来比较x节点和p节点的大小
TreeNode<K,V> xp = p; // x的父节点变量, 中间变量用于下面给x的父节点赋值
if ((p = (dir <= 0) ? p.left : p.right) == null) { // dir <= 0则向左查找, 否则向右查找, 如果已经无法继续查找, 则代表该位置即为x的目标位置
x.parent = xp; // x的父节点即为最后一次遍历的p节点
if (dir <= 0) // 如果时dir <= 0, 则代表x节点为父节点的左节点
xp.left = x;
else // 如果时dir > 0, 则代表x节点为父节点的右节点
xp.right = x;
root = balanceInsertion(root, x); // 进行红黑树的插入平衡(通过左旋、右旋和改变节点颜色来保证当前树符合红黑树的要求)
break;
}
}
}
}
moveRootToFront(tab, root); // 如果root节点不在table索引位置的头结点, 则将其调整为头结点
}
- 从调用此方法的节点作为起点，开始进行遍历，并将此节点设为root节点，标记为黑色（x.red = false）。
- 如果当前节点不是根结点，则从根节点开始查找属于该节点的位置（该段代码跟之前的代码块2和代码块4的查找代码类似）。
- 如果x节点(将要插入红黑树的节点)的hash值小于p节点(当前遍历到的红黑树节点)的hash值，则向p节点的左边查找。
- 与3相反，如果x节点的hash值大于p节点的hash值，则向p节点的右边查找。
- 如果x节点的hash值跟p节点的hash值相同, 并且x的key没有实现Comparable接口（不可比较），或者x节点的key和p节点的key相等，使用tieBreakOrder方法（见上文代码块5）来比较x节点和p节点的大小，以决定向左还是向右查找（dir <= 0向左，否则向右）。
- 如果dir <= 0则向左节点查找（p赋值为p.left，并进行下一次循环），否则向右节点查找，如果已经无法继续查找（p赋值后为null），则代表该位置即为x的目标位置，另外变量xp用来记录最后一个节点，即为下文新增的x节点的父节点。
- 将x的父节点设置为xp，根据dir的值决定x决定放在xp节点的左节点还是右节点，最后进行红黑树的插入平衡调整。
- 调用moveRootToFront方法（见下文代码块8）将root节点调整到索引位置的头结点。
代码块8：moveRootToFront方法
/**
* Ensures that the given root is the first node of its bin.
* 如果当前索引位置的头节点不是root节点, 则将root的上一个节点和下一个节点进行关联, 将root放到头节点的位置,
* 原头节点放在root的next节点上
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) { // 如果root节点不是该索引位置的头节点
Node<K,V> rn;
tab[index] = root; // 将该索引位置的头节点赋值为root节点
TreeNode<K,V> rp = root.prev; // root节点的上一个节点
if ((rn = root.next) != null) // 如果root节点的下一个节点不为空, 则将root节点的下一个节点的prev属性设置为root节点的上一个节点
((TreeNode<K,V>)rn).prev = rp;
if (rp != null) // 如果root节点的上一个节点不为空, 则将root节点的上一个节点的next属性设置为root节点的下一个节点
rp.next = rn;
if (first != null) // 如果原头节点不为空, 则将原头节点的prev属性设置为root节点,
first.prev = root;
root.next = first; // 将root节点的next属性设置为原头节点
root.prev = null;
}
assert checkInvariants(root); // 检查树是否正常
}
}
- 校验root是否为空、table是否为空、table的length是否大于0。
- 根据root节点的hash值计算出索引位置，判断该索引位置的头节点是否为root节点，如果不是则进行以下操作将该索引位置的头结点替换为root节点。
- 将该索引位置的头结点赋值为root节点，如果root节点的next节点不为空，则将root节点的next节点的prev节点设置为root节点的prev节点。
- 如果root节点的prev节点不为空，则将root节点的prev节点的next节点设置为root节点的next节点（3和4两个操作是一个完整的链表移除某个节点过程）。
- 如果原头节点不为空，则将原头节点的prev节点设置为root节点
- 将root节点的next节点设置为原头节点（5和6两个操作将first节点接到root节点后面）
- root此时已经被放到该位置的头结点位置，因此将prev节点设为空。
- 调用checkInvariants方法（见下文代码块9）检查树是否正常。
代码块9：checkInvariants方法
/**将传入的节点作为根结点，遍历所有节点，校验节点的合法性，主要是保证该树符合红黑树的规则。
* Recursive invariant check
*/
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)
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))
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;
}
resize方法
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 老table不为空
if (oldCap >= MAXIMUM_CAPACITY) { // 老table的容量超过最大容量值
threshold = Integer.MAX_VALUE; // 设置阈值为Integer.MAX_VALUE
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) // 如果容量*2小于最大容量并且不小于16, 则将阈值设置为原来的两倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr; // 老表的容量为0，阈值大于0, 则将新表的容量设置为老表的阈值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; // 老表的容量为0, 老表的阈值为0, 则为空表, 进行初始化
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { // 如果新表的阈值为空, 则通过新的容量*负载因子获得阈值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 将当前阈值设置为刚计算出来的新的阈值
@SuppressWarnings({"rawtypes","unchecked"})
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;
if ((e = oldTab[j]) != null) { // 将索引值为j的老表头节点赋值给e
oldTab[j] = null; // 将老表的节点设置为空, 等扩容结束老表所有数据会被清空, 以便垃圾收集器回收其空间
if (e.next == null) // 如果e.next为空, 则代表老表的该位置只有1个节点, 通过hash值计算新表的索引位置, 直接将该节点放在新表的该位置上
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 调用treeNode的hash分布(跟下面最后一个else的内容几乎相同)
else { // preserve order
Node<K,V> loHead = null, loTail = null; // 存储跟原索引位置相同的节点
Node<K,V> hiHead = null, hiTail = null; // 存储索引位置为:原索引+oldCap的节点
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 如果e的hash值与老表的容量(为一串只有1个为1的二进制数, 例如16为0000 0000 0001 0000)进行与运算为0, 即扩容后的索引位置跟老表的索引位置一样
if (loTail == null) // 如果loTail为空, 代表该节点为第一个节点
loHead = e; // 则将loHead赋值为该节点
else
loTail.next = e; // 否则将节点添加在loTail后面
loTail = e; // 并将loTail赋值为新增的节点
}
else { // 如果e的hash值与老表的容量(为一串只有1个为1的二进制数, 例如16为0000 0000 0001 0000)进行与运算为1,即扩容后的索引位置为:老表的索引位置＋oldCap
if (hiTail == null)// 如果hiTail为空, 代表该节点为第一个节点
hiHead = e; // 则将hiHead赋值为该节点
else
hiTail.next = e; // 否则将节点添加在hiTail后面
hiTail = e; // 并将hiTail赋值为新增的节点
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null; // 最后一个节点的next设为空
newTab[j] = loHead; // 将原索引位置的节点设置为对应的头结点
}
if (hiTail != null) {
hiTail.next = null; // 最后一个节点的next设为空
newTab[j + oldCap] = hiHead; // 将索引位置为原索引+oldCap的节点设置为对应的头结点
}
}
}
}
}
return newTab;
}
- 如果老表的容量大于0，判断老表的容量是否超过最大容量值：如果超过则将阈值设置为Integer.MAX_VALUE，并直接返回老表（此时oldCap * 2比Integer.MAX_VALUE大，因此无法进行重新分布，只是单纯的将阈值扩容到最大）；如果容量 * 2小于最大容量并且不小于16，则将阈值设置为原来的两倍。
- 如果老表的容量为0，老表的阈值大于0，则将新表的容量设置为老表的阈值。
- 如果老表的容量为0，老表的阈值为0，则为空表, 进行初始化。
- 如果新表的阈值为空，则通过新的容量*负载因子获得阈值。
- 将当前阈值设置为刚计算出来的新的阈值， 定义新表，容量为刚计算出来的新容量，将当前的表设置为新定义的表。
- 如果老表不为空，则需遍历所有节点，将节点赋值给新表。
- 将老表上索引为j的头结点赋值给e节点，并将老表上索引为j的节点设置为空。
- 如果e的next节点为空，则代表老表的该位置只有1个节点，通过hash值计算新表的索引位置，直接将该节点放在新表的该位置上。
- 如果e的next节点不为空，并且e为TreeNode，则调用split方法（见下文代码块10）进行hash分布。
- 如果e的next节点不为空，并且e为普通的链表节点，则进行普通的hash分布。
- 如果e的hash值与老表的容量（为一串只有1个为2的二进制数，例如16为0000 0000 0001 0000）进行位与运算为0，则说明e节点扩容后的索引位置跟老表的索引位置一样（见例子1），进行链表拼接操作：如果loTail为空，代表该节点为第一个节点，则将loHead赋值为该节点；否则将节点添加在loTail后面，并将loTail赋值为新增的节点。
- 如果e的hash值与老表的容量（为一串只有1个为2的二进制数，例如16为0000 0000 0001 0000）进行位与运算为1，则说明e节点扩容后的索引位置为：老表的索引位置＋oldCap（见例子1），进行链表拼接操作：如果hiTail为空，代表该节点为第一个节点，则将hiHead赋值为该节点；否则将节点添加在hiTail后面，并将hiTail赋值为新增的节点。
- 老表节点重新hash分布在新表结束后，如果loTail不为空（说明老表的数据有分布到新表上原索引位置的节点），则将最后一个节点的next设为空，并将新表上原索引位置的节点设置为对应的头结点；如果hiTail不为空（说明老表的数据有分布到新表上原索引+oldCap位置的节点），则将最后一个节点的next设为空，并将新表上索引位置为原索引+oldCap的节点设置为对应的头结点。
- 返回新表。
代码块10：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; // 存储索引位置为:原索引+oldCap的节点
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next; // next赋值为e的下个节点
e.next = null; // 同事将老表的节点设置为空
if ((e.hash & bit) == 0) { // 如果e的hash值与老表的容量(为一串只有1个为2的二进制数, 例如16为0000 0000 0001 0000)进行与运算为0, 即扩容后的索引位置跟老表的索引位置一样
if ((e.prev = loTail) == null) // 如果loTail为空, 代表该节点为第一个节点
loHead = e; // 则将loHead赋值为该节点
else
loTail.next = e; // 否则将节点添加在loTail后面
loTail = e; // 并将loTail赋值为新增的节点
++lc; // 统计原索引位置的节点个数
}
else { // 如果e的hash值与老表的容量(为一串只有1个为2的二进制数, 例如16为0000 0000 0001 0000)进行与运算为1, 即扩容后的索引位置为:老表的索引位置＋oldCap
if ((e.prev = hiTail) == null) // 如果hiHead为空, 代表该节点为第一个节点
hiHead = e; // 则将hiHead赋值为该节点
else
hiTail.next = e; // 否则将节点添加在hiTail后面
hiTail = e; // 并将hiTail赋值为新增的节点
++hc; // 统计索引位置为原索引+oldCap的节点个数
}
}
if (loHead != null) { // 原索引位置的节点不为空
if (lc <= UNTREEIFY_THRESHOLD) // 节点个数<=6个则将红黑树转为链表结构
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead; // 将原索引位置的节点设置为对应的头结点
if (hiHead != null) // hiHead不为空则代表原来的红黑树(老表的红黑树由于节点被分到两个位置)已经被改变, 需要重新构建新的红黑树
loHead.treeify(tab); // 以loHead为根结点, 构建新的红黑树
}
}
if (hiHead != null) { // 索引位置为原索引+oldCap的节点不为空
if (hc <= UNTREEIFY_THRESHOLD) // 节点个数<=6个则将红黑树转为链表结构
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead; // 将索引位置为原索引+oldCap的节点设置为对应的头结点
if (loHead != null) // loHead不为空则代表原来的红黑树(老表的红黑树由于节点被分到两个位置)已经被改变, 需要重新构建新的红黑树
hiHead.treeify(tab); // 以hiHead为根结点, 构建新的红黑树
}
}
}
- 以调用此方法的节点开始，遍历整个红黑树节点（此处实际是遍历的链表节点，上文提过，红黑树节点也会同事维护链表结构）。
- 如果e的hash值与老表的容量（为一串只有1个为2的二进制数，例如16为0000 0000 0001 0000）进行位与运算为0，则说明e节点扩容后的索引位置跟老表的索引位置一样（见下文例子1），进行链表拼接操作：如果loTail为空，代表该节点为第一个节点，则将loHead赋值为该节点；否则将节点添加在loTail后面，并将loTail赋值为新增的节点，并统计原索引位置的节点个数。
- 如果e的hash值与老表的容量（为一串只有1个为2的二进制数，例如16为0000 0000 0001 0000）进行位与运算为1，则说明e节点扩容后的索引位置为：老表的索引位置＋oldCap（见例子1），进行链表拼接操作：如果hiTail为空，代表该节点为第一个节点，则将hiHead赋值为该节点；否则将节点添加在hiTail后面，并将hiTail赋值为新增的节点，并统计索引位置为原索引+oldCap的节点个数。
- 如果原索引位置的节点不为空：如果当该索引位置节点数<=6个，调用untreeify方法（见下文代码块11）将红黑树节点转为链表节点；否则将原索引位置的节点设置为对应的头结点（即loHead结点），如果判断hiHead不为空则代表原来的红黑树（老表的红黑树由于节点被分到两个位置）已经被改变，需要重新构建新的红黑树，以loHead为根结点，调用treeify方法（见上文代码块7）构建新的红黑树。
- 如果索引位置为原索引+oldCap的节点不为空：如果当该索引位置节点数<=6个，调用untreeify方法（见下文代码块11）将红黑树节点转为链表节点；否则将索引位置为原索引+oldCap的节点设置为对应的头结点（即hiHead结点），如果判断loHead不为空则代表原来的红黑树（老表的红黑树由于节点被分到两个位置）已经被改变，需要重新构建新的红黑树，以hiHead为根结点，调用treeify方法（见上文代码块7）构建新的红黑树。
代码块11：untreeify方法
final Node<K,V> untreeify(HashMap<K,V> map) { // 将红黑树节点转为链表节点, 当节点<=6个时会被触发
Node<K,V> hd = null, tl = null; // hd指向头结点, tl指向尾节点
for (Node<K,V> q = this; q != null; q = q.next) { // 从调用该方法的节点, 即链表的头结点开始遍历, 将所有节点全转为链表节点
Node<K,V> p = map.replacementNode(q, null); // 调用replacementNode方法构建链表节点
if (tl == null) // 如果tl为null, 则代表当前节点为第一个节点, 将hd赋值为该节点
hd = p;
else // 否则, 将尾节点的next属性设置为当前节点p
tl.next = p;
tl = p; // 每次都将tl节点指向当前节点, 即尾节点
}
return hd; // 返回转换后的链表的头结点
}
- 从调用该方法的节点，即链表的头结点开始遍历, 将所有节点全转为链表节点
- 调用replacementNode方法构建链表节点
- 如果tl为null, 则代表当前节点为第一个节点，将hd赋值为该节点，否则, 将尾节点的next属性设置为当前节点p
- 每次都将tl节点指向当前节点, 即尾节点
- 返回转换后的链表的头结点
例子1：扩容后，节点重hash为什么只可能分布在原索引位置与原索引+olcCap位置？
扩容代码中，使用e节点的hash值跟oldCap进行位与运算，以此决定将节点分布到原索引位置或者原索引+oldCap位置上，这是为什么了？
假设老表的容量为16，即oldCap=16，则新表容量为16*2=32，假设节点1的hash值为0000 0000 0000 0000 0000 1111 0000 1010，节点2的hash值为0000 0000 0000 0000 0000 1111 0001 1010，则节点1和节点2在老表的索引位置计算如下图计算1，由于老表的长度限制，节点1和节点2的索引位置只取决于节点hash值的最后4位。再看计算2，计算2为新表的索引计算，可以知道如果两个节点在老表的索引位置相同，则新表的索引位置只取决于节点hash值倒数第5位的值，而此位置的值刚好为老表的容量值16，此时节点在新表的索引位置只有两种情况：原索引位置和原索引+oldCap位置（在此例中即为10和10+16=26）。由于结果只取决于节点hash值的倒数第5位，而此位置的值刚好为老表的容量值16，因此此时新表的索引位置的计算可以替换为计算3，直接使用节点的hash值与老表的容量16进行位于运算，如果结果为0则该节点在新表的索引位置为原索引位置，否则该节点在新表的索引位置为原索引+oldCap位置。
remove方法
/**
* Removes the mapping for the specified key from this map if present.
*
* @param key key whose mapping is to be removed from the map
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
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) { // 如果table不为空并且根据hash值计算出来的索引位置不为空, 将该位置的节点赋值给p
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 如果p的hash值和key都与传入的相同, 则p即为目标节点, 赋值给node
node = p;
else if ((e = p.next) != null) { // 否则向下遍历节点
if (p instanceof TreeNode) // 如果p是TreeNode则调用红黑树的方法查找节点
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do { // 遍历链表查找符合条件的节点
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) { // 当节点的hash值和key与传入的值相同, 则该节点即为目标节点, 赋值给node, 并跳出循环
node = e;
break;
}
p = e; // p节点赋值为本次结束的e
} while ((e = e.next) != null); // 下一次循环的节点为e的next节点, 即为p的next节点
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) { // 如果node不为空(即根据传入key和hash值查找到目标节点),
if (node instanceof TreeNode) // 如果是TreeNode则调用红黑树的移除方法
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // 如果node是该索引位置的头结点则直接将该索引位置的值赋值为node的next节点
tab[index] = node.next;
else // 否则将node的上一个节点的next节点设置为node的next节点, 即将node节点移除, 将node的上下节点进行关联(链表的移除)
p.next = node.next;
++modCount; // 修改次数加1
--size; // table的总节点减1
afterNodeRemoval(node); // 供LinkedHashMap使用
return node;
}
}
return null;
}
- 如果table不为空并且根据hash值计算出来的索引位置的值不为空，将该位置的节点赋值给p。
- 如果p节点的hash值和key都与传入的相同，则p即为目标节点，赋值给node。
- 向下遍历节点，如果p是TreeNode则调用getTreeNode方法（见上文代码块1）查找节点，并赋值给node。
- 遍历链表查找符合条件的节点，当节点的hash值和key与传入的值相同，则该节点即为目标节点, 赋值给node，并跳出循环。
- 如果node不为空，即根据传入key和hash值查找到目标节点，判断node是否为TreeNode，如果是则调用红黑树的移除方法removeTreeNode方法（见下文代码块12）。
- 如果node是该索引位置的头结点则直接将该索引位置的值赋值为node节点的next节点。
- 否则将node的上一个节点（p节点）的next节点设置为node的next节点，即将node节点移除，将node的上下节点进行关联（链表的移除，可以看开头的第7点）。
代码块12：removeTreeNode方法
/**
* Removes the given node, that must be present before this call.
* This is messier than typical red-black deletion code because we
* cannot swap the contents of an interior node with a leaf
* successor that is pinned by "next" pointers that are accessible
* independently during traversal. So instead we swap the tree
* linkages. If the current tree appears to have too few nodes,
* the bin is converted back to a plain bin. (The test triggers
* somewhere between 2 and 6 nodes, depending on tree structure).
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0) // table为空或者length为0直接返回
return;
int index = (n - 1) & hash; // 根据hash计算出索引的位置
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; // 索引位置的头结点赋值给first和root
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev; // 该方法被将要被移除的对象node(TreeNode)调用, 因此此方法的this为node节点, 则此处next即为node的next节点, prev即为node的prev节点
if (pred == null) // 如果node节点的prev节点为空
tab[index] = first = succ; // 则将table索引位置的值和first节点的值赋值为succ节点(node的next节点)即可
else
pred.next = succ; // 否则将node的prev节点的next节点设置为succ节点(node的next节点)(链表的移除)
if (succ != null) // 如果succ节点不为空
succ.prev = pred; // 则将succ的prev节点设置为pred, 与上面对应
if (first == null) // 如果此处first为空, 则代表该索引位置已经没有节点则直接返回
return;
if (root.parent != null) // 如果root的父节点不为空, 则将root赋值为根结点 (root在上面被赋值为索引位置的头结点, 索引位置的头节点并不一定为红黑树的根结点)
root = root.root();
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) { // 通过root节点来判断此红黑树是否太小, 如果是则转为链表节点并返回(转链表后就无需再进行下面的红黑树处理)
tab[index] = first.untreeify(map); // too small
return;
}
// 以下代码为红黑树的处理, 上面的代码已经将链表的部分处理完成
TreeNode<K,V> p = this, pl = left, pr = right, replacement; // 上面已经说了this为将要被移除的node节点, 将p赋值为node节点, pl赋值为node的左节点, pr赋值为node的右节点
if (pl != null && pr != null) { // p的左节点和右节点都不为空时
TreeNode<K,V> s = pr, sl; // s节点赋值为p的右节点
while ((sl = s.left) != null) // 向左一直查找, 直到叶子节点, 跳出循环时, s为叶子节点
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // 交换p节点和s节点(叶子节点)的颜色
TreeNode<K,V> sr = s.right; // s的右节点
TreeNode<K,V> pp = p.parent; // p的父节点
// 第一次调整
if (s == pr) { // 如果p节点的右节点即为叶子节点
p.parent = s; // 将p的父节点赋值为s
s.right = p; // 将s的右节点赋值为p
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) { // 将p的父节点赋值为s的父节点sp, 如果sp不为空
if (s == sp.left) // 如果s节点为左节点
sp.left = p; // 则将s的父节点的左节点赋值为p节点
else // 如果s节点为右节点
sp.right = p; // 则将s的父节点的右节点赋值为p节点
}
if ((s.right = pr) != null) // s的右节点赋值为p节点的右节点
pr.parent = s; // p节点的右节点的父节点赋值为s
}
// 第二次调整
p.left = null;
if ((p.right = sr) != null) // 将p节点的右节点赋值为s的右节点sr, 如果sr不为空
sr.parent = p; // 则将s右节点的父节点赋值为p节点
if ((s.left = pl) != null) // 将s节点的左节点赋值为p的左节点pl, 如果pl不为空
pl.parent = s; // 则将p左节点的父节点赋值为s节点
if ((s.parent = pp) == null) // 将s的父节点赋值为p的父节点pp, 如果pp为空
root = s; // 则p节点为root节点, 此时交换后s成为新的root节点
else if (p == pp.left) // 如果p不为root节点, 并且p是父节点的左节点
pp.left = s; // 将p父节点的左节点赋值为s节点
else // 如果p不为root节点, 并且p是父节点的右节点
pp.right = s; // 将p父节点的右节点赋值为s节点
if (sr != null)
replacement = sr; // 如果sr不为空，则replacement为sr节点(用来替换掉p节点)
else
replacement = p; // 否则replacement为p节点
}
else if (pl != null) // 如果p的左节点不为空, 右节点为空, replacement节点为p的左节点
replacement = pl;
else if (pr != null) // 如果p的右节点不为空, 左节点为空, replacement节点为p的右节点
replacement = pr;
else // 如果p的左右节点都为空, 即p为叶子节点, replacement节点为p节点本身
replacement = p;
// 第三次调整
if (replacement != p) { // 如果p节点不是叶子节点
TreeNode<K,V> pp = replacement.parent = p.parent; //将replacement节点的父节点赋值为p节点的父节点, 同事赋值给pp节点
if (pp == null) // 如果p节点没有父节点, 即p为root节点
root = replacement; // 则将root节点赋值为replacement节点即可
else if (p == pp.left) // 如果p节点不是root节点, 并且p节点为父节点的左节点
pp.left = replacement; // 则将p父节点的左节点赋值为replacement节点
else // 如果p节点不是root节点, 并且p节点为父节点的右节点
pp.right = replacement; // 则将p父节点的右节点赋值为replacement节点
p.left = p.right = p.parent = null; // p节点的位置已经被完整的替换为replacement节点, 将p节点清空
}
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement); // 如果p节点不为红色则进行红黑树删除平衡调整(如果删除的节点是红色则不会破坏红黑树的平衡无需调整)
if (replacement == p) { // 如果p节点为叶子节点, 则简单的将p节点去除即可
TreeNode<K,V> pp = p.parent; // pp赋值为p节点的父节点
p.parent = null; // 将p的parent节点设置为空
if (pp != null) { // 如果p的父节点存在
if (p == pp.left) // 如果p节点为父节点的左节点
pp.left = null; // 则将父节点的左节点赋值为空
else if (p == pp.right) // 如果p节点为父节点的右节点
pp.right = null; // 则将父节点的右节点赋值为空
}
}
if (movable)
moveRootToFront(tab, r); // 将root节点移到索引位置的头结点
}
- 如果table为空或者length为0直接返回。
- 根据hash值和length-1位于运算计算出索引的位置。
- 将索引位置的头结点赋值给first和root，removeTreeNode方法是被将要移除的节点node调用，因此removeTreeNode方法里的this即为将要被移除的节点node，将node的next节点赋值给succ节点，prev节点赋值给pred节点。
- 如果node节点的prev节点为空，则代表要被移除的node节点为头结点，则将table索引位置的值和first节点的值赋值为node的next节点（succ节点）即可。
- 否则将node的prev节点（pred节点）的next节点设置为node的next节点（succ节点），如果succ节点不为空，则将succ的prev节点设置为pred，与前面对应（TreeNode链表的移除，见开头第8点）。
- 如果进行到此first节点为空，则代表该索引位置已经没有节点则直接返回。
- 如果root的父节点不为空，则将root赋值为根结点（root在上面被赋值为索引位置的头结点，索引位置的头节点并不一定为红黑树的根结点）。
- 通过root节点来判断此红黑树是否太小，如果太小则转为链表节点并返回（转链表后就无需再进行下面的红黑树处理），链表维护部分到此结束，此前的代码说明了，红黑树在进行移除的同时也会维护链表结构，之后的代码为红黑树的移除节点处理。
- 上面已经说了this为将要被移除的node节点，将p节点赋值为将要被移除的node节点（则此时p节点就是我们要移除的节点），pl赋值为node的左节点, pr赋值为node的右节点（方法的命令见开头第6点），replacement变量用来存储将要替换掉被移除的node节点。
- 如果p的左节点和右节点都不为空时，s节点赋值为p的右节点；向s的左节点一直向左查找, 直到叶子节点，跳出循环时，s为叶子节点；交换p节点和s节点（叶子节点）的颜色（此文下面的所有操作都是为了实现将p节点和s节点进行位置调换，因此此处先将颜色替换）；sr赋值为s节点的右节点，pp节点赋值为p节点的父节点（命令规律见文章开头第6点）。
- PS：下面的第一次调整和第二次调整是将p节点和s节点进行了位置调换，然后找出要替换掉p节点的replacement；第三次调整是将replacement节点覆盖掉p节点；这部分的代码逻辑比较不容易理解透，建议自己动手画图模拟。（下文图解1即为这三次调整的例子）
- 进行第一次调整：如果p节点的右节点即为叶子节点，将p的父节点赋值为s，将s的右节点赋值为p即可；否则，将p的父节点赋值为s的父节点sp，并判断sp是否为空，如果不为空，并判断s是sp的左节点还是右节点，将s节点替换为p节点；将s的右节点赋值为p节点的右节点pr，如果pr不为空则将pr的父节赋值为s节点。
- 进行第二次调整：将p节点的左节点清空（上文pl已经保存了该节点）；将p节点的右节点赋值为s的右节点sr，如果sr不为空，则将sr的父节点赋值为p节点；将s节点的左节点赋值为p的左节点pl，如果pl不为空，则将p左节点的父节点赋值为s节点；将s的父节点赋值为p的父节点pp，如果pp为空，则p节点为root节点，此时交换后s成为新的root节点，将root赋值为s节点；如果p不为root节点，并且p是父节点的左节点，将p父节点的左节点赋值为s节点；如果p不为root节点，并且p是父节点的右节点，将p父节点的右节点赋值为s节点；如果sr不为空，将replacement赋值为sr节点，否则赋值为p节点（为什么sr是replacement的首选，p为备选？见解释1）。
- 承接第10点的判断，第10点~第12点为p的左右节点都不为空的情况需要进行的处理；如果p的左节点不为空，右节点为空，将replacement赋值为p的左节点即可；如果p的右节点不为空，左节点为空，将replacement赋值为p的右节点即可；如果p的左右节点都为空，即p为叶子节点, 将replacement赋值为p节点本身。
- 进行第三次调整：如果p节点不是replacement（即p不是叶子节点），将replacement的父节点赋值为p的父节点，同事赋值给pp节点；如果pp为空（p节点没有父节点），即p为root节点，则将root节点赋值为replacement节点即可；如果p节点不是root节点，并且p节点为父节点的左节点，则将p父节点的左节点赋值为replacement节点；如果p节点不是root节点，并且p节点为父节点的右节点，则将p父节点的右节点赋值为replacement节点；p节点的位置已经被完整的替换为replacement节点, 将p节点清空。
- 如果p节点不为红色则进行红黑树删除平衡调整（如果删除的节点是红色则不会破坏红黑树的平衡无需调整，见文末的解释2）。
- 如果p节点为叶子节点，则简单的将p节点移除：将pp赋值为p节点的父节点，将p的parent节点设置为空，如果p的父节点pp存在，如果p节点为父节点的左节点，则将父节点的左节点赋值为空，如果p节点为父节点的右节点，则将父节点的右节点赋值为空。
- 如果movable为true，则调用moveRootToFront方法（见上文代码块8）将root节点移到索引位置的头结点。
解释1：为什么sr是replacement的首选，p为备选？
解析：首先我们看sr是什么？从代码中可以看到sr第一次被赋值时，是在s节点进行了向左穷遍历结束后，因此此时s节点是没有左节点的，sr即为s节点的右节点。而从上面的三次调整我们知道，p节点已经跟s节点进行了位置调换，所以此时sr其实是p节点的右节点，并且p节点没有左节点，因此要移除p节点，只需要将p节点的右节点sr覆盖掉p节点即可，因此sr是replacement的首选，如果sr为空，则代表p节点为叶子节点，此时将p节点清空即可。
图解1：removeTreeNode图解
本图解忽略红黑树的颜色，请注意。
下面的图解是代码中的最复杂的情况，即流程最长的那个，p节点不为根结点，p节点有左右节点，s节点不为pr节点，s节点有右节点。
解释2：关于红黑树的平衡调整？
答：红黑树的操作涉及的操作比较复杂，三言两语无法说清。有兴趣的可以去单独学习，本文由于篇幅关系暂不详细介绍红黑树的具体操作，在这简单的介绍：红黑树是一种自平衡二叉树，拥有优秀的查询和插入/删除性能，广泛应用于关联数组。
对比AVL树，AVL要求每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1，而红黑树通过适当的放低该条件（红黑树限制从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，结果是这个树大致上是平衡的），以此来减少插入/删除时的平衡调整耗时，从而获取更好的性能，而这虽然会导致红黑树的查询会比AVL稍慢，但相比插入/删除时获取的时间，这个付出在大多数情况下显然是值得的。
在HashMap中的应用：HashMap在进行插入和删除时有可能会触发红黑树的插入平衡调整（balanceInsertion方法）或删除平衡调整（balanceDeletion ）方法，调整的方式主要有以下手段：左旋转（rotateLeft方法）、右旋转（rotateRight方法）、改变节点颜色（x.red = false、x.red = true），进行调整的原因是为了维持红黑树的数据结构。
死循环问题
在Jdk 1.8以前，Java语言在并发情况下使用HashMap造成Race Condition，从而导致死循环。程序经常占了100%的CPU，查看堆栈，你会发现程序都Hang在了HashMap.get()这个方法上了，重启程序后问题消失。具体分析可以查看这篇文章：疫苗：JAVA HASHMAP的死循环，有人将这个问题当成一个bug提给了Sun，但是Sun认为这并不是个bug，因为HashMap本来就不保证并发的线程安全性，在并发下，要用ConcurrentHashMap来代替。
那么，在Jdk 1.8的时候，这个问题解决了吗？
我们知道，Jdk 1.8以前，导致死循环的主要原因是扩容后，节点的顺序会反掉，如下图：扩容前节点A在节点C前面，而扩容后节点C在节点A前面。
JDK 8扩容过程
JDK1.8 普通链表的扩容代码，如下图所示，在上文已经分析过了：主要是在一个do/while中处理同一个位置的所有节点。
前提：我们假设有3个节点，节点A，节点B，节点C，并且假设他们的hash值等于key值，则按上图扩容的过程模拟如下。
先看下老表和新表计算索引位置的过程：（hash计算省略前面28位0，只看最后4位）
具体扩容过程：
结果：可以看出，扩容后，节点A和节点C的先后顺序跟扩容前是一样的。因此，即使此时有多个线程并发扩容，也不会出现死循环的情况。当然，这仍然改变不了HashMap仍是非并发安全，在并发下，还是要使用ConcurrentHashMap来代替。
参考
HashMap源码（JDK 8）