JAVA HashMap 高并发下链表变红黑树？链化与树化机制解析
大家好，今天我们来聊聊Java HashMap在高并发场景下的链表树化机制。HashMap作为Java中最常用的数据结构之一，其性能在很大程度上依赖于哈希冲突的处理。当多个键映射到同一个桶（bucket）时，会形成链表。在高并发环境下，大量的哈希冲突可能导致链表过长，从而显著降低HashMap的性能。为了解决这个问题，JDK 1.8引入了红黑树，当链表长度超过一定阈值时，会将链表转换为红黑树，以提高查找效率。
1. HashMap 的基本结构
在深入讨论树化机制之前，我们先回顾一下HashMap的基本结构。HashMap本质上是一个数组，数组中的每个元素被称为桶（bucket）。每个桶可以存储一个键值对，或者是一个链表/红黑树的根节点，用于解决哈希冲突。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
transient Node<K,V>[] table; // 存储数据的数组
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; // 指向下一个节点的指针，用于形成链表
// 构造函数和其他方法省略...
}
}table 数组是HashMap的核心数据结构，用于存储键值对。Node 类代表链表中的节点，包含哈希值、键、值和指向下一个节点的指针。
2. 哈希冲突与链化
当多个键的哈希值相同（或者哈希值不同但经过 indexFor 方法计算后落在同一个桶中）时，就会发生哈希冲突。HashMap采用链地址法解决冲突，即在同一个桶中，将所有冲突的键值对以链表的形式存储。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 计算桶的位置
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) // 如果是TreeNode，说明已经是红黑树
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) // TREEIFY_THRESHOLD = 8
treeifyBin(tab, hash); // 链表长度超过阈值，尝试树化
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}putVal 方法是HashMap的核心方法，用于插入键值对。当发生哈希冲突时，新的节点会被添加到链表的末尾。TREEIFY_THRESHOLD 是一个重要的参数，用于控制链表转换为红黑树的阈值，默认值为8。
3. 树化（Treeify）机制
当链表长度超过 TREEIFY_THRESHOLD 时，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(); // 如果数组长度小于 MIN_TREEIFY_CAPACITY，则扩容
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
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); // 调用 TreeNode.treeify 方法将链表转换为红黑树
}
}treeifyBin 方法并不是直接将链表转换为红黑树，而是先检查数组的容量是否小于 MIN_TREEIFY_CAPACITY。如果小于，则会进行扩容，而不是树化。这是因为当数组容量较小时，扩容可以有效地减少哈希冲突，从而降低链表长度。MIN_TREEIFY_CAPACITY 的默认值为64。
如果数组容量大于等于 MIN_TREEIFY_CAPACITY，则会将链表转换为红黑树。转换的过程主要分为两步：
- 将链表节点转换为树节点（TreeNode）:
replacementTreeNode方法负责将链表节点Node转换为树节点TreeNode。 - 将树节点连接成双向链表: 将转换后的树节点连接成一个双向链表，方便后续的红黑树转换。
- 调用
TreeNode.treeify方法进行树化:TreeNode.treeify方法负责将双向链表转换为红黑树。
TreeNode.treeify 方法的具体实现涉及红黑树的平衡操作，比较复杂，这里不再赘述。
static <K,V> TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}4. 红黑树的优势
红黑树是一种自平衡的二叉搜索树，它具有以下特点：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶子节点（NIL）是黑色。
- 如果一个节点是红色，则它的两个子节点都是黑色。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树的自平衡特性保证了其查找、插入和删除操作的时间复杂度为 O(log n)，其中 n 是树中节点的数量。相比于链表，红黑树的查找效率大大提高。
| 操作 | 链表 | 红黑树 |
|---|---|---|
| 查找 | O(n) | O(log n) |
| 插入 | O(1) | O(log n) |
| 删除 | O(n) | O(log n) |
5. 解树化（Untreeify）机制
当红黑树中的节点数量减少到一定程度时，红黑树会退化为链表。这个过程被称为解树化。解树化的阈值由 UNTREEIFY_THRESHOLD 控制，默认值为6。
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;
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)
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);
}
}
}split 方法在扩容时被调用，用于将红黑树中的节点重新分配到新的桶中。如果某个桶中的节点数量小于等于 UNTREEIFY_THRESHOLD，则会调用 untreeify 方法将红黑树转换为链表。
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (TreeNode<K,V> q = this; q != null; q = (TreeNode<K,V>)q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}untreeify 方法将树节点 TreeNode 转换回链表节点 Node，从而完成解树化过程。
6. 为什么需要树化和解树化？
HashMap引入树化和解树化机制是为了在空间和时间之间取得平衡。当哈希冲突严重时，链表过长，查找效率降低。此时，将链表转换为红黑树可以提高查找效率，但会增加空间开销。当哈希冲突减少时，红黑树的优势不再明显，反而会增加空间开销。此时，将红黑树退化为链表可以减少空间开销。
通过动态地在链表和红黑树之间转换，HashMap可以在不同的负载情况下保持较好的性能。
7. 高并发下的考量
在高并发环境下，HashMap的树化和解树化过程可能会受到线程安全问题的影响。JDK 1.8中的HashMap并没有完全解决并发安全问题，例如，在扩容过程中可能会出现数据丢失或者死循环等问题。
因此，在高并发环境下，建议使用线程安全的ConcurrentHashMap。ConcurrentHashMap采用了分段锁等机制，保证了线程安全。
8. 总结HashMap链表树化与解树化的重要性
HashMap通过链表树化和解树化机制，在高负载和低负载情况下动态调整数据结构，从而在时间和空间之间取得平衡。在选择HashMap时，需要根据实际情况选择合适的实现方式，在高并发环境下建议使用ConcurrentHashMap。 掌握HashMap的树化和解树化机制，可以帮助我们更好地理解HashMap的性能特点，从而更好地使用HashMap。