ConcurrentHashMap的实现原理

1. 基本概念和设计目标

ConcurrentHashMap是Java并发包(java.util.concurrent)中的一个线程安全的HashMap实现。它的设计目标是在保证线程安全的同时，提供比Hashtable和Collections.synchronizedMap更高的并发性能。

设计目标

• 高并发性：允许多个线程同时读和一定程度的写操作
• 线程安全：保证多线程环境下数据的一致性
• 高性能：尽可能减少锁竞争，提高并发访问效率

2. JDK 1.7及之前的实现（分段锁）

在JDK 1.7及之前的版本中，ConcurrentHashMap采用**分段锁(Segment)**的设计来实现并发控制。

内部结构

ConcurrentHashMap内部由一个Segment数组组成，每个Segment又包含一个HashEntry数组。Segment是一种可重入锁(ReentrantLock)，每个Segment守护着它所包含的HashEntry数组中的元素。

工作原理

1. 数据定位：

   • 首先通过key的hash值确定在哪个Segment中
   • 然后在该Segment中通过再次hash确定具体的HashEntry位置

2. 并发控制：

   • 写操作需要获取对应Segment的锁
   • 读操作不需要加锁（通过volatile保证可见性）
   • 不同Segment的写操作可以并发进行

3. 容量计算：

   • 整个ConcurrentHashMap的容量是所有Segment容量的总和
   • 每个Segment的容量默认为16，负载因子为0.75

代码示例

// JDK 1.7 ConcurrentHashMap的put方法简化版
public V put(K key, V value) {
    Segment<K,V> s;
    // 计算key的hash值，并找到对应的Segment
    int hash = hash(key.hashCode());
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
        s = ensureSegment(j);
    // 调用Segment的put方法
    return s.put(key, hash, value, false);
}

// Segment的put方法简化版
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    // 尝试获取锁，如果失败则自旋获取
    HashEntry<K,V> node = tryLock() ? null :
        scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                K k;
                if ((k = e.key) == key ||
                    (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                e = e.next;
            }
            else {
                if (node != null)
                    node.setNext(first);
                else
                    node = new HashEntry<K,V>(hash, key, value, first);
                int c = count + 1;
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);
                else
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        unlock();
    }
    return oldValue;
}

优缺点

优点：

• 锁粒度细，并发度高
• 在多线程环境下读写性能较好

缺点：

• 内存占用较高（每个Segment都维护自己的HashEntry数组）
• 在某些场景下，并发度可能不够高（Segment数量固定）

3. JDK 1.8及之后的实现（CAS + synchronized）

从JDK 1.8开始，ConcurrentHashMap的实现发生了重大变化，放弃了分段锁的设计，转而采用CAS(Compare And Swap)操作和synchronized关键字来实现并发控制。

内部结构

JDK 1.8的ConcurrentHashMap内部结构与HashMap类似，由一个Node数组组成，每个Node可能是一个链表或红黑树的头节点。

工作原理

1. CAS操作：

   • 在无竞争的情况下，使用CAS操作来更新节点的值
   • CAS是一种无锁算法，通过比较并交换来保证原子性

2. synchronized锁：

   • 在有竞争的情况下，使用synchronized锁住对应的桶（Node数组中的某个位置）
   • 锁的粒度更细，只锁住需要修改的桶，而不是整个Segment

3. 关键优化：

   • 扩容优化：支持多线程并发扩容
   • 树化优化：当链表长度超过8时，转换为红黑树，提高查询效率
   • 计数优化：使用CounterCell来记录元素数量，减少竞争

代码示例

// JDK 1.8 ConcurrentHashMap的putVal方法简化版
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;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 如果桶为空，使用CAS操作添加新节点
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 使用synchronized锁住桶的头节点
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                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;
}

优缺点

优点：

• 内存占用更少（不需要维护多个Segment）
• 锁粒度更细，并发度更高
• 在高并发场景下性能更好

缺点：

• 实现更复杂，理解难度更高
• 在某些低并发场景下，性能可能不如JDK 1.7的实现

4. 关键操作的实现原理

get操作

1. JDK 1.7：

   • 不加锁，通过volatile保证可见性
   • 首先定位到Segment，然后在Segment中查找对应的HashEntry

2. JDK 1.8：

   • 不加锁，通过volatile保证可见性
   • 直接通过hash值定位到对应的桶，然后遍历链表或红黑树

put操作

1. JDK 1.7：

   • 首先定位到Segment，然后获取Segment的锁
   • 在Segment中执行put操作，可能触发rehash
   • 释放锁

2. JDK 1.8：

   • 首先定位到桶
   • 如果桶为空，使用CAS操作添加新节点
   • 如果桶不为空，使用synchronized锁住桶的头节点
   • 执行put操作，可能触发树化或扩容
   • 释放锁

size操作

1. JDK 1.7：

   • 遍历所有Segment，累加它们的count值
   • 在累加过程中，可能尝试获取Segment的锁（如果连续两次获取的值不一致）

2. JDK 1.8：

   • 使用CounterCell数组来记录元素数量
   • 在多线程环境下，不同线程可能更新不同的CounterCell
   • 计算size时，累加所有CounterCell的值

扩容操作

1. JDK 1.7：

   • 每个Segment独立扩容，不影响其他Segment
   • 扩容时获取Segment的锁，阻塞其他线程对该Segment的操作

2. JDK 1.8：

   • 支持多线程并发扩容
   • 扩容时，将数组分成多个部分，不同线程可以负责迁移不同的部分
   • 迁移过程中，读操作可以并发进行，写操作可能会协助扩容

5. 与其他线程安全Map的对比

Hashtable

• 锁机制：使用synchronized关键字锁住整个表
• 性能特点：
  • 任何写操作都会阻塞整个表
  • 读操作也需要加锁
  • 并发度低，性能较差

Collections.synchronizedMap

• 锁机制：使用synchronized关键字锁住整个Map对象
• 性能特点：
  • 任何写操作都会阻塞整个Map
  • 读操作也需要加锁
  • 并发度低，性能较差
  • 迭代时需要手动加锁

ConcurrentHashMap

• 锁机制：
  • JDK 1.7：分段锁（Segment）
  • JDK 1.8：CAS + synchronized
• 性能特点：
  • 锁粒度细，只锁住需要修改的部分
  • 读操作不需要加锁（通过volatile保证可见性）
  • 并发度高，性能较好
  • 支持复合操作的原子性（如putIfAbsent）

6. 总结

ConcurrentHashMap是Java并发包中一个重要的线程安全Map实现，它的设计目标是提供高并发性和高性能。

• JDK 1.7及之前：采用分段锁（Segment）的设计，每个Segment是一个独立的哈希表，拥有自己的锁。这种设计允许多个线程同时访问不同的Segment，提高了并发性。

• JDK 1.8及之后：放弃了分段锁的设计，转而采用CAS操作和synchronized关键字。锁的粒度更细，只锁住需要修改的桶，进一步提高了并发性。

ConcurrentHashMap的实现原理体现了Java并发编程的一些重要思想，如无锁算法、细粒度锁、并发扩容等。理解ConcurrentHashMap的实现原理，对于编写高性能的并发程序非常有帮助。

参考资料

1. Java ConcurrentHashMap官方文档
2. Java并发编程实战
3. The Java® Virtual Machine Specification
4. Java并发源码分析：ConcurrentHashMap