本文整理自漫画：什么是ConcurrentHashMap？ - 小灰的文章 - 知乎 。已获得作者授权。
HashMap 在高并发下会出现链表环，从而导致程序出现死循环。高并发下避免HashMap 出问题的方法有两种。一是使用HashTable，二是使用Collections.syncronizedMap
但是这两种方法的性能都能差。因为这两个在执行读写操作时都是将整个集合加锁，导致多个线程无法同时读写集合。高并发下的HashMap出现的问题就需要ConcurrentHashMap 来解决了。
什么是ConcurrentHashMap？
ConcurrentHashMap 中有一个Segment 的概念。
Segment是什么呢？Segment本身就相当于一个HashMap对象。
同HashMap一样，Segment包含一个HashEntry数组，数组中的每一个HashEntry既是一个键值对，也是一个链表的头节点。
单一的Segment结构如下：
像这样的Segment对象，在ConcurrentHashMap集合中有多少个呢？有2的N次方个，共同保存在一个名为segments的数组当中。
因此整个ConcurrentHashMap的结构如下：
可以说，ConcurrentHashMap 是一个二级哈希表。在一个总的哈希表下面，有若干个子哈希表。
这样的二级结构，和数据库的水平拆分有些相似。
ConcurrentHashMap 的优势
ConcurrentHashMap 的优势就是采取了锁分段技术，每一个Segment 的读写操作高度自治，Segment 之间互不影响。
Case1：不同Segment 的并发写入
image.png
不同Segment的写入是可以并发执行的。
Case2：同一Segment的一写一读
同一Segment的写和读是可以并发执行的。
Case3：同一Segment的并发写入
Segment的写入是需要上锁的，因此对同一Segment的并发写入会被阻塞。
由此可见，ConcurrentHashMap当中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。
Concurrent 的读写过程
Get方法：
- 为输入的Key做Hash运算，得到hash值。
- 通过hash值，定位到对应的Segment对象
- 再次通过hash值，定位到Segment当中数组的具体位置。
Put方法：
- 为输入的Key做Hash运算，得到hash值。
- 通过hash值，定位到对应的Segment对象
- 获取可重入锁
- 再次通过hash值，定位到Segment当中数组的具体位置。
- 插入或覆盖HashEntry对象。
- 释放锁。
读写操作均需要二次定位到Segment。
ConcurrentHashMap 在调用Size 方法时如何解决一致性问题？
Size方法的目的是统计ConcurrentHashMap的总元素数量， 自然需要把各个Segment内部的元素数量汇总起来。
但是，如果在统计Segment元素数量的过程中，已统计过的Segment瞬间插入新的元素，这时候该怎么办呢？
ConcurrentHashMap的Size方法是一个嵌套循环，大体逻辑如下：
- 遍历所有的Segment。
- 把Segment的元素数量累加起来。
- 把Segment的修改次数累加起来。
- 判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束。
- 如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计。
- 再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等。
- 释放锁，统计结束。
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 = this.segments;
int size;
boolean overflow; // true if size overflows 32 bits
long sum; // sum of modCounts
long last = 0L; // previous sum
int retries = -1; // first iteration isn't retry
try {
for (;;) {
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
if (sum == last)
break;
last = sum;
}
} finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
return overflow ? Integer.MAX_VALUE : size;
}
为什么这样设计呢？这种思想和乐观锁悲观锁的思想如出一辙。
为了尽量不锁住所有Segment，首先乐观地假设Size过程中不会有修改。当尝试一定次数，才无奈转为悲观锁，锁住所有Segment保证强一致性。
想看原作者的文章可以看看这个公众号。
image.png
网友评论