正文
HashMap源码分析（Java8）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
1. HashMap
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量：16
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量：2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子：0.75
static final int TREEIFY_THRESHOLD = 8; // 链表转红黑树的阈值：8
static final int UNTREEIFY_THRESHOLD = 6; // 红黑树转链表的阈值：6
static final int MIN_TREEIFY_CAPACITY = 64; // 链表转红黑树的最小容量：64
// 若容量小于64，则binCount大于8时，不将链表转为红黑树（treeify），而是扩容（resize）
transient Node<K,V>[] table; // 哈希表（HashMap.Node implements Map.Entry）
transient Set<Map.Entry<K,V>> entrySet; // Entry集合（HashMap.EntrySet）
transient int size; // table中Node元素个数
transient int modCount; // HashMap修改计数，调用put、remove、clear...：modCount++（与HashIterator相关）
int threshold; // table已分配空间时，threshold为table下次扩容阈值
// table未分配空间时，threshold可用于保存指定的初始容量
final float loadFactor; // 加载因子
public HashMap(int initialCapacity, float loadFactor) {
... ...
this.loadFactor = loadFactor;
// table容量必须为2^n（建议看下tableSizeFor方法）
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false); // 用putVal方法将m中的元素添加到table中
}
... ...
}
1）get
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量：16
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量：2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子：0.75
static final int TREEIFY_THRESHOLD = 8; // 链表转红黑树的阈值：8
static final int UNTREEIFY_THRESHOLD = 6; // 红黑树转链表的阈值：6
static final int MIN_TREEIFY_CAPACITY = 64; // 链表转红黑树的最小容量：64
// 若容量小于64，则binCount大于8时，不将链表转为红黑树（treeify），而是扩容（resize）
transient Node<K,V>[] table; // 哈希表（HashMap.Node implements Map.Entry）
transient Set<Map.Entry<K,V>> entrySet; // Entry集合（HashMap.EntrySet）
transient int size; // table中Node元素个数
transient int modCount; // HashMap修改计数，调用put、remove、clear...：modCount++（与HashIterator相关）
int threshold; // table已分配空间时，threshold为table下次扩容阈值
// table未分配空间时，threshold可用于保存指定的初始容量
final float loadFactor; // 加载因子
public HashMap(int initialCapacity, float loadFactor) {
... ...
this.loadFactor = loadFactor;
// table容量必须为2^n（建议看下tableSizeFor方法）
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false); // 用putVal方法将m中的元素添加到table中
}
... ...
}
1‘ 根据key找到映射的bin
2’ 若bin的首个节点是否为待查找节点，则直接返回
3' 若bin为红黑树则在红黑树中查找，若bin为链表则遍历链表
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 已经为table分配空间 && key映射的bin存在
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 判断bin中首个节点是否为待查找节点
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode) // bin为红黑树根节点，则在红黑树中查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do { // bin为链表，则遍历链表
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
2）put
1‘ 根据key找到映射的bin
2’ 若bin是否为空，则直接添加节点
3' 若bin为红黑树则在红黑树中添加节点，若bin为链表则在链表尾部添加节点
4' 若bin中已存在具有相同key的节点，则覆盖（或不覆盖）原value
5' 若bin中不存在具有相同key的节点，则size++并根据size判断是否扩容
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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尚未分配空间
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 当前bin为空
tab[i] = newNode(hash, key, value, null);
else { // 当前bin不为空
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 判断首个节点中存在相同的key
e = p;
else if (p instanceof TreeNode) // bin为红黑树，则在红黑数中添加节点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // bin为链表，则在链表中插入节点
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); // 在链表尾部添加节点
if (binCount >= TREEIFY_THRESHOLD - 1) // 链表长度 >= 8，链表转为红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // bin中存在具有相同key的节点
break;
p = e;
}
}
if (e != null) { // bin中存在具有相同key的节点
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) // 判断是否覆盖旧值
e.value = value;
afterNodeAccess(e); // noop
return oldValue;
}
}
++modCount;
if (++size > threshold) // 添加元素后，超过扩容阈值
resize(); // 扩容
afterNodeInsertion(evict); // noop
return null;
}
3）remove
1‘ 根据key找到映射的bin
2’ 判断bin的首个节点是否为待删除节点
3' 若bin为红黑树则在红黑树中查找，若bin为链表则遍历链表
4' 若找到相应的节点，则在红黑树或链表中删除之
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
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;
// 已经为table分配空间 && key映射的bin存在
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 判断首个节点是否为待删除节点
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode) // bin为空黑树，则在红黑树中查找
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else { // bin为链表，则遍历链表
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 在bin中找到被删除节点node && （删除node时不比较value || 删除node时比较value，而value相等）
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
if (node instanceof TreeNode) // 在红黑树中删除节点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // 待删除节点为链表首个节点
tab[index] = node.next;
else // 待删除节点非链表首个节点
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node); // noop
return node;
}
}
return null;
}
4）resize
调用putVal方法往table中添加元素时：
1' 若table尚未分配空间，则调用此方法进行初始化
2' 在table中添加元素后，若size大于扩容阈值，则调用此方法进行扩容
3‘ 迁移旧table中的节点到新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容量 >= 2^30，扩容阈值设为最大整数，不扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 1. 新table容量 = 旧table容量 * 2
// 2. 若新table容量 < 2^30，且旧table容量 >= 16，则新table阈值 = 旧table阈值 << 1
// 3. 否则，新table阈值另行计算（新table阈值 = 最大整数 / 新table容量 * 加载因子）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 新的阈值 = 旧的阈值 << 1
}
else if (oldThr > 0) // table尚未分配空间，指定初始容量（保存在thredshold中）
newCap = oldThr;
else { // table尚未分配空间，默认初始容量（16）
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { // 另行计算新table阈值，最大整数 / 新容量 * 加载因子
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) { // 当前正在扩容（非初始化）
for (int j = 0; j < oldCap; ++j) { // 遍历旧table，迁移节点到新table中
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 当前bin为红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 分割红黑树到新table中
else { // 当前bin为链表
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) { // e进入低位链表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // e进入高位链表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead; // 低位链表挂至新table
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead; // 高位链表挂至新table
}
}
}
}
}
return newTab;
}
5）treeifyBin
调用putVal方法往table中添加元素时，新元素所在bin中元素数量 > 8时，调用此方法将bin由单向链表转化为双向链表 + 红黑树。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// table未初始化 || table容量 < 64，则进行resize（table初始化 || table扩容）
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) { // 在当前bin上建立双向链表，并在双向链表上建立红黑树
TreeNode<K,V> hd = null, tl = null; // 双向链表头、尾节点
do {
TreeNode<K,V> p = replacementTreeNode(e, null); // Node -> TreeNode
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab); // 在双向链表上继续建立红黑树
}
}
6）containsKey和containsValue
containsKey：getNode返回非空
containsValue：依次遍历bin，并依次遍历bin中链表
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) { // 在bin中遍历链表
if ((v = e.value) == value || (value != null && value.equals(v)))
return true;
}
}
}
return false;
}
7）entrySet、keySet和values
依次返回EntrySet、KeySet、Values
1' EntrySet、KeySet继承自AbstractSet，而Values继承自AbstractCollection
2' EntrySet、KeySet、Values对应的迭代器分别为：EntryIterator、KeyIterator、ValueIterator
3' EntryIterator、KeyIterator、ValueIterator均继承自HashIterator，依赖HashIterator.nextNode分别对Node（Entry）、K、V进行迭代
4' 对EntrySet、KeySet、Values，及各自迭代器，调用remove方法，都将最终调用HashMap的removeNode方法删除节点
5' 对EntrySet、KeySet、Values，不能调用add方法添加元素，否则将抛出UnsupportedOperationException
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
public Set<K> keySet() {
Set<K> ks;
return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
}
public Collection<V> values() {
Collection<V> vs;
return (vs = values) == null ? (values = new Values()) : vs;
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; } // return HashMap.this.size
public final void clear() { HashMap.this.clear(); } // HashMap.this.clear
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator(); // HashMap.EntryIterator
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key); // HashMap.this.getNode
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null; // HashMap.this.removeNode
}
return false;
}
// add方法继承自AbstractCollection：throw UnsupportedOperationException
... ...
}
final class KeySet extends AbstractSet<K> {
public final int size() { return size; } // return HashMap.this.size
public final void clear() { HashMap.this.clear(); } // HashMap.this.clear
public final Iterator<K> iterator() { return new KeyIterator(); } // HashMap.KeyIterator
public final boolean contains(Object o) { return containsKey(o); } // HashMap.this.containsKey
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null; // HashMap.this.removeNode，matchValue为true
}
// add方法继承自AbstractCollection：throw UnsupportedOperationException
... ...
}
final class Values extends AbstractCollection<V> {
public final int size() { return size; } // return HashMap.this.size
public final void clear() { HashMap.this.clear(); } // HashMap.this.clear
public final Iterator<V> iterator() { return new ValueIterator(); } // HashMap.ValueIterator
public final boolean contains(Object o) { return containsValue(o); } // HashMap.this.containsValue
// remove方法继承自AbstractCollection（用ValueIterator查找和删除首个匹配的节点）
// add方法继承自AbstractCollection：throw UnsupportedOperationException
... ...
}
abstract class HashIterator {
Node<K,V> next; // 下一节点
Node<K,V> current; // 当前节点
int expectedModCount;
int index; // 下一bin位置
HashIterator() {
expectedModCount = modCount; // 纪录当前HashMap的修改计数
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) {
// 在table中找到第一处非空bin，next指向该bin首个节点，index指向下个bin
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
// 若当前bin中，next后置位还有节点，则next指向后置节点
// 若当前bin中，next后置位没有节点，则next指向后置bin中首个节点（如果存在）
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false); // HashMap.this.removeNode
expectedModCount = modCount;
}
}
final class KeyIterator extends HashIterator implements Iterator<K> {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
2. HashMap.TreeNode（红黑树）
// 红黑树更详细实现，请大家参考java.util.TreeMap，本文只针对HashMap中引入的红黑树作简要的描述
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; // 左孩子
TreeNode<K,V> right; // 右孩子
TreeNode<K,V> prev; // 前置节点（next继承自HashMap.Node）
boolean red; // 红黑标记
TreeNode(int hash, K key, V val, Node<K,V> next);
// 红黑树根节点
final TreeNode<K,V> root();
// 当前红黑树也是一个双向链表，该方法将红黑树root移至双向链表头部
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;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null) // root存在后置节点
((TreeNode<K,V>)rn).prev = rp;
if (rp != null) // root存在前置节点
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
// 从当前节点开始查找
final TreeNode<K,V> find(int h, Object k, Class<?> kc);
// 从root开始查找
final TreeNode<K,V> getTreeNode(int h, Object k);
// key所属类未实现Comparable接口，且可能覆盖Object.hashCode方法
// 用System.identityHashCode(key)比较TreeNode大小
static int tieBreakOrder(Object a, Object b);
// 在双向链表上建立红黑树
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 = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) { // 红黑树为空
x.parent = null;
x.red = false;
root = x;
}
else { // 红黑树不为空
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) || // K未实现Comparable接口
(dir = compareComparables(kc, k, pk)) == 0) // compareTo return 0
dir = tieBreakOrder(k, pk);// 用System.identityHashCode(key)比较TreeNode大小
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) { // 往左走，左子树为空 || 往右走，右子树为空
x.parent = xp; // x父节点置为xp
if (dir <= 0)
xp.left = x; // x插入xp左子树
else
xp.right = x; // x插入xp右子树
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
// 红黑树转单向链表
final Node<K,V> untreeify(HashMap<K,V> map) {
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); // TreeNode -> Node
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
// 在红黑树中插入节点（balanceInsertion）
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v);
// 在红黑树中删除当前节点（balanceDeletion）
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable);
// 分割红黑树（table扩容）
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
TreeNode<K,V> loHead = null, loTail = null; // 低位双向链表
TreeNode<K,V> hiHead = null, hiTail = null; // 高位双向链表
int lc = 0, hc = 0;
// 当前节点为双向链表头结点
for (TreeNode<K,V> e = b, next; e != null; e = next) { // 遍历双向链表，e为当前节点
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) { // e进入低位双向链表
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc; // 低位节点计数++
}
else { // e进入高位双向链表
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc; // 高位节点计数++
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD) // 低位链表大小 <= 6
tab[index] = loHead.untreeify(map); // 用低位双向链表建立单向链表
else {
tab[index] = loHead;
if (hiHead != null) // 节点没有全部进入低位双向链表
loHead.treeify(tab); // 在低位双向链表上建立红黑树
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD) // 高位节点数 <= 6
tab[index + bit] = hiHead.untreeify(map); // 用高位双向链表建立单向链表
else {
tab[index + bit] = hiHead;
if (loHead != null) // 节点没有全部进入高位双向链表
hiHead.treeify(tab); // 在高位双向链表上建立红黑树
}
}
}
// 以p为支点左旋
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<KeNode<K,V> p);
// 以p为支点右旋
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<KeNode<K,V> p);
// 插入节点后平衡调整
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x);
// 删除节点后平衡调整
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x);
... ...
}
// 红黑树更详细实现，请大家参考java.util.TreeMap，本文只针对HashMap中引入的红黑树作简要的描述
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; // 左孩子
TreeNode<K,V> right; // 右孩子
TreeNode<K,V> prev; // 前置节点（next继承自HashMap.Node）
boolean red; // 红黑标记 TreeNode(int hash, K key, V val, Node<K,V> next);
// 红黑树根节点
final TreeNode<K,V> root();
// 当前红黑树也是一个双向链表，该方法将红黑树root移至双向链表头部
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;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null) // root存在后置节点
((TreeNode<K,V>)rn).prev = rp;
if (rp != null) // root存在前置节点
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
} // 从当前节点开始查找
final TreeNode<K,V> find(int h, Object k, Class<?> kc);
// 从root开始查找
final TreeNode<K,V> getTreeNode(int h, Object k); // key所属类未实现Comparable接口，且可能覆盖Object.hashCode方法
// 用System.identityHashCode(key)比较TreeNode大小
static int tieBreakOrder(Object a, Object b); // 在双向链表上建立红黑树
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 = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) { // 红黑树为空
x.parent = null;
x.red = false;
root = x;
}
else { // 红黑树不为空
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) || // K未实现Comparable接口
(dir = compareComparables(kc, k, pk)) == 0) // compareTo return 0
dir = tieBreakOrder(k, pk);// 用System.identityHashCode(key)比较TreeNode大小
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) { // 往左走，左子树为空 || 往右走，右子树为空
x.parent = xp; // x父节点置为xp
if (dir <= 0)
xp.left = x; // x插入xp左子树
else
xp.right = x; // x插入xp右子树
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
} // 红黑树转单向链表
final Node<K,V> untreeify(HashMap<K,V> map) {
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); // TreeNode -> Node
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
} // 在红黑树中插入节点（balanceInsertion）
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v); // 在红黑树中删除当前节点（balanceDeletion）
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable); // 分割红黑树（table扩容）
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
TreeNode<K,V> loHead = null, loTail = null; // 低位双向链表
TreeNode<K,V> hiHead = null, hiTail = null; // 高位双向链表
int lc = 0, hc = 0;
// 当前节点为双向链表头结点
for (TreeNode<K,V> e = b, next; e != null; e = next) { // 遍历双向链表，e为当前节点
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) { // e进入低位双向链表
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc; // 低位节点计数++
}
else { // e进入高位双向链表
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc; // 高位节点计数++
}
} if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD) // 低位链表大小 <= 6
tab[index] = loHead.untreeify(map); // 用低位双向链表建立单向链表
else {
tab[index] = loHead;
if (hiHead != null) // 节点没有全部进入低位双向链表
loHead.treeify(tab); // 在低位双向链表上建立红黑树
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD) // 高位节点数 <= 6
tab[index + bit] = hiHead.untreeify(map); // 用高位双向链表建立单向链表
else {
tab[index + bit] = hiHead;
if (loHead != null) // 节点没有全部进入高位双向链表
hiHead.treeify(tab); // 在高位双向链表上建立红黑树
}
}
} // 以p为支点左旋
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<KeNode<K,V> p); // 以p为支点右旋
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<KeNode<K,V> p); // 插入节点后平衡调整
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x); // 删除节点后平衡调整
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x); ... ...
}
