JavaConcurrentHashMap类解析

基于JDK 7 的 ConcurrentHashMap 源码

1. 存储结构

static final class HashEntry<K,V> {final int hash;final K key;volatile V value;volatile HashEntry<K,V> next;
}


• ConcurrentHashMap 和 HashMap 实现上类似&＃xff0c;最主要的差别是 ConcurrentHashMap 采用了分段锁&＃xff08;Segment&＃xff09;&＃xff0c;每个分段锁维护着几个桶&＃xff08;HashEntry&＃xff09;&＃xff0c;多个线程可以同时访问不同分段锁上的桶&＃xff0c;从而使其并发度更高&＃xff08;并发度就是 Segment 的个数&＃xff09;。
• ConcurrentHashMap的桶结构和HashMap的主要区别是后两个元素声明为了 volatile 类型。
• HashMap 支持 fail-fast 机制&＃xff0c;而ConcurrentHashMap没有modCount字段&＃xff0c;不支持fail-fast 机制。

段结构的定义(Segment)&＃xff1a;

static final class Segment<K,V> extends ReentrantLock implements Serializable {private static final long serialVersionUID &＃61; 2249069246763182397L;static final int MAX_SCAN_RETRIES &＃61;Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;transient volatile HashEntry<K,V>[] table;transient int count;transient int modCount;transient int threshold;final float loadFactor;
}


final Segment<K,V>[] segments; // 一个ConcurrentHashMap有多个Segment


默认的并发级别为 16&＃xff0c;也就是说默认创建 16 个 Segment。

static final int DEFAULT_CONCURRENCY_LEVEL &＃61; 16;


如下图&＃xff0c;第一层为Segment&＃xff0c;第二层为HashEntry。

2. size 操作

• 每个 Segment 维护了一个 count 变量来统计该 Segment 中的键值对个数。 transient int count;
• 在执行 size 操作时&＃xff0c;需要遍历所有 Segment 然后把 count 累计起来。
• ConcurrentHashMap 在执行 size 操作时先尝试不加锁&＃xff0c;如果连续两次不加锁操作得到的结果一致&＃xff0c;那么可以认为这个结果是正确的。
• 尝试次数使用 RETRIES_BEFORE_LOCK 定义&＃xff0c;该值为 2&＃xff0c;retries 初始值为 -1&＃xff0c;因此尝试次数为 3。
• 如果尝试的次数超过 3 次&＃xff0c;就需要对每个 Segment 加锁。

size() 操作源码&＃xff1a;

/*** Number of unsynchronized retries in size and containsValue* methods before resorting to locking. This is used to avoid* unbounded retries if tables undergo continuous modification* which would make it impossible to obtain an accurate result.*/
static final int RETRIES_BEFORE_LOCK &＃61; 2;public int size() {// Try a few times to get accurate count. On failure due to// continuous async changes in table, resort to locking.final Segment<K,V>[] segments &＃61; this.segments;int size;boolean overflow; // true if size overflows 32 bitslong sum; // sum of modCountslong last &＃61; 0L; // previous sumint retries &＃61; -1; // first iteration isn&＃39;t retrytry {for (;;) {// 超过尝试次数&＃xff0c;则对每个 Segment 加锁if (retries&＃43;&＃43; &＃61;&＃61; RETRIES_BEFORE_LOCK) {for (int j &＃61; 0; j < segments.length; &＃43;&＃43;j)ensureSegment(j).lock(); // force creation}sum &＃61; 0L;size &＃61; 0;overflow &＃61; false;for (int j &＃61; 0; j < segments.length; &＃43;&＃43;j) {Segment<K,V> seg &＃61; segmentAt(segments, j);if (seg !&＃61; null) {sum &＃43;&＃61; seg.modCount;int c &＃61; seg.count;if (c < 0 || (size &＃43;&＃61; c) < 0)overflow &＃61; true;}}// 连续两次得到的结果一致&＃xff0c;则认为这个结果是正确的if (sum &＃61;&＃61; last)break;last &＃61; sum;}} finally {if (retries > RETRIES_BEFORE_LOCK) {for (int j &＃61; 0; j < segments.length; &＃43;&＃43;j)segmentAt(segments, j).unlock();}}return overflow ? Integer.MAX_VALUE : size;
}


3. JDK 1.8 的改动

• JDK 1.7 使用分段锁机制来实现并发更新操作&＃xff0c;核心类为 Segment&＃xff0c;它继承自重入锁 ReentrantLock&＃xff0c;并发度与 Segment 数量相等。
• JDK 1.8 使用了 CAS 操作来支持更高的并发度&＃xff0c;在 CAS 操作失败时使用内置锁 synchronized。
• 并且 JDK 1.8 的实现也在链表过长时会转换为红黑树。

本文参考自这里