ConcurrentHashMap：链表与红黑树

一、链表解决 hash 冲突

同一个桶的元素用链表串起来：

桶 i → Node(hash=1, k=v1, next=Node(hash=5, k=v2, next=null))

查找时遍历链表，O(n)。

二、为什么转红黑树

链表太长时（默认 ≥ 8），查找 O(n) 太慢。转成红黑树，O(log n)。

阈值

static final int TREEIFY_THRESHOLD = 8;   // 链表转树
static final int UNTREEIFY_THRESHOLD = 6; // 树退化链表
static final int MIN_TREEIFY_CAPACITY = 64; // 数组至少 64 才转树

三、TreeBin

ConcurrentHashMap 里红黑树不是直接 TreeNode，而是包了一层 TreeBin：

treeBin = new TreeBin<K,V>(k, v, null, null);

TreeBin 包装了： - 根节点 - 读写锁（读锁共享，写锁独占） - 链表头（兼容遍历）

为什么用 TreeBin 而不是直接 TreeNode？因为红黑树操作复杂，需要更细的锁。TreeBin 维护读写状态。

四、插入流程

synchronized (f) {
    if (tabAt(tab, i) == f) {
        if (fh >= 0) {   // 普通链表节点
            for (binCount = 1;; ++binCount) {
                // 尾插
                if (++k >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);   // 转树
            }
        } else if (fh == TREEBIN) {
            // 已经是树，按树插入
        }
    }
}

五、为什么不直接用 TreeNode

TreeNode 需要额外的 parent/left/right/prev 指针，内存开销大。树化是兜底，不是常态。大多数桶保持链表。

六、树退化

扩容时如果桶元素少了（< 6），红黑树转回链表：

if (count <= UNTREEIFY_THRESHOLD)
    untreeify(...);

对比 HashMap

• HashMap 也是链表转红黑树（≥8）。
• ConcurrentHashMap 多了 TreeBin 包装，处理读写并发。