清晨的一缕阳光
返回

ConcurrentHashMap 原理详解

ConcurrentHashMap 原理详解

ConcurrentHashMap 是线程安全的 HashMap，JDK 1.8 从分段锁演进为 CAS+synchronized，性能大幅提升。

一、版本对比

1.1 核心差异

特性JDK 1.7JDK 1.8
底层结构Segment + HashEntryNode + 链表 + 红黑树
锁机制分段锁（ReentrantLock）synchronized + CAS
锁粒度Segment 级别桶（Bucket）级别
并发度16（Segment 数）数组长度（默认 16）
读操作无锁（volatile）无锁（volatile）

1.2 演进原因

JDK 1.7 问题
├── 内存占用高（Segment 数组）
├── 并发度受限（固定 16）
└── 结构复杂

JDK 1.8 优化
├── 简化结构（移除 Segment）
├── 细粒度锁（桶级别）
└── 红黑树优化查询

二、JDK 1.7 实现

2.1 数据结构

ConcurrentHashMap
└── Segment[] segments (默认 16)
    └── HashEntry[] table
        └── HashEntry → HashEntry (链表)
// Segment 继承 ReentrantLock
static final class Segment<K,V> extends ReentrantLock {
    transient volatile HashEntry<K,V>[] table;
}

2.2 初始化

// 初始化 Segment 数组
int sshift = 4; // 2^4 = 16
int segmentShift = 32 - sshift;

segments = new Segment[16];

// 每个 Segment 初始化 HashEntry 数组
for (int i = 0; i < segments.length; ++i)
    segments[i] = new Segment<K,V>();

2.3 put 操作

public V put(K key, V value) {
    // 1. 计算 hash
    int hash = hash(key);
    
    // 2. 定位 Segment
    int j = (hash >>> segmentShift) & segmentMask;
    Segment<K,V> segment = segments[j];
    
    // 3. 锁定 Segment
    segment.lock();
    try {
        // 4. 在 Segment 内执行 put
        HashEntry<K,V>[] tab = segment.table;
        // ... 插入逻辑
    } finally {
        segment.unlock();
    }
}

2.4 优缺点

优点：

缺点：

三、JDK 1.8 实现

3.1 数据结构

ConcurrentHashMap
└── Node[] table (数组)
    ├── Node → Node (链表)
    └── TreeNode → TreeNode (红黑树)
// Node 结构
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;  // volatile 保证可见性
    volatile Node<K,V> next;
}

3.2 关键参数

// 默认容量
static final int DEFAULT_CAPACITY = 16;

// 树化阈值
static final int TREEIFY_THRESHOLD = 8;

// 非树化阈值
static final int UNTREEIFY_THRESHOLD = 6;

// 最小树化容量
static final int MIN_TREEIFY_CAPACITY = 64;

// 扩容阈值（负载因子 0.75）
static final int MAXIMUM_CAPACITY = 1 << 30;

3.3 put 操作

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null)
        throw new NullPointerException();
    
    int hash = spread(key.hashCode());
    int binCount = 0;
    
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        
        // 1. 初始化数组
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        
        // 2. 桶为空，CAS 插入
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;
        }
        
        // 3. 扩容协助
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        
        // 4. 桶非空，synchronized 锁头节点
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        // 链表插入
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek = e.key;
                            if (ek.equals(key)) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value, null);
                                break;
                            }
                        }
                    }
                    // 红黑树插入
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                // 检查树化
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

3.4 锁优化

// synchronized 锁头节点（桶级别）
synchronized (f) {
    // 插入/更新操作
}

// JDK 1.7 锁 Segment（段级别）
segment.lock();

优势：

四、扩容机制

4.1 扩容触发

// 元素数量超过阈值
if (sizeCtl >= 0) {
    if (tab == null || n >= sizeCtl)
        transfer(tab, null);
}

4.2 多线程协助扩容

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    
    // 计算每个线程处理的桶数
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE;
    
    if (nextTab == null) {
        // 创建新数组（容量翻倍）
        nextTab = new Node<K,V>[n << 1];
    }
    
    // 多线程协助迁移
    while (true) {
        Node<K,V> f; int fh;
        // CAS 获取迁移任务
        while (nextIndex >= 0 || i + stride >= advanceIndex) {
            // 迁移桶
            if (f != null) {
                // 链表/红黑树拆分
                // 高位 → 新位置
                // 低位 → 原位置
            }
        }
    }
}

4.3 扩容优化

JDK 1.7：单线程扩容（Segment 内部）
JDK 1.8：多线程协助扩容（全局）
    ↓
多个线程同时参与迁移
CAS 标记迁移状态
避免重复迁移

五、读操作

5.1 get 方法

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    
    int h = spread(key.hashCode());
    
    // 1. 定位桶
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        
        // 2. 头节点匹配
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        
        // 3. 遍历链表/红黑树
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

5.2 volatile 保证可见性

volatile V val;           // 值可见
volatile Node<K,V> next;  // 链表可见

无需加锁：读操作通过 volatile 保证可见性

六、使用注意

6.1 原子操作

ConcurrentHashMap<String, AtomicInteger> map = new ConcurrentHashMap<>();

// ❌ 非原子操作
map.get("count").incrementAndGet();

// ✅ 原子操作
map.computeIfAbsent("count", k -> new AtomicInteger()).incrementAndGet();

// ✅ 或使用 putIfAbsent
AtomicInteger count = new AtomicInteger();
map.putIfAbsent("count", count);
map.get("count").incrementAndGet();

6.2 批量操作

// 并行度阈值（默认 1）
long count = map.mappingCount();

// 批量遍历
map.forEach(10, (k, v) -> System.out.println(k + "=" + v));

// 批量搜索
Map.Entry<String, Integer> result = map.search(10, (k, v) -> {
    if ("key".equals(k)) return new AbstractMap.SimpleEntry<>(k, v);
    return null;
});

// 批量归约
String reduced = map.reduce(10, Map.Entry::getKey, (s1, s2) -> s1 + "," + s2);

6.3 与 Hashtable 对比

特性ConcurrentHashMapHashtable
锁机制CAS + synchronizedsynchronized（全表锁）
并发度高低
null 值不支持不支持
性能高低
推荐✅ 是❌ 否

七、总结

ConcurrentHashMap 核心要点：

版本锁机制并发度性能
JDK 1.7分段锁16中
JDK 1.8CAS + synchronized数组长度高

演进优势：

  1. 简化结构（移除 Segment）
  2. 细粒度锁（桶级别）
  3. 红黑树优化（O(log n)）
  4. 多线程协助扩容

JDK 1.8 的 ConcurrentHashMap 在几乎所有场景下都优于 1.7，是高并发首选。

分享这篇文章到:
分享到QQ 分享到微博 分享文章到Email
上一篇文章
ReentrantLock 原理与实战
下一篇文章
Java 类加载机制详解