为什么ConcurrentHashMap是弱一致的

ゝ一世哀愁。 2022-09-23 15:54 90阅读 0赞

转自http://ifeve.com/concurrenthashmap-weakly-consistent/

### 为什么ConcurrentHashMap是弱一致的 ###

本文将用到Java内存模型的happens-before偏序关系（下文将简称为hb）以及ConcurrentHashMap的底层模型相关的知识。happens-before相关内容参见：[JLS §17.4.5. Happens-before Order][JLS _17.4.5. Happens-before Order]、[深入理解Java内存模型][Java]以及[Happens before][]；ConcurrentHashMap的详细介绍以及底层原理见[深入分析ConcurrentHashMap][ConcurrentHashMap]。本文将从ConcurrentHashMap的get，clear，iterator（entrySet、keySet、values方法）三个方法来分析它们的弱一致问题。

#### ConcurrentHashMap\#get ####

get方法是弱一致的，是什么含义？可能你期望往ConcurrentHashMap底层数据结构中加入一个元素后，立马能对get可见，但ConcurrentHashMap并不能如你所愿。换句话说，put操作将一个元素加入到底层数据结构后，get可能在某段时间内还看不到这个元素，若不考虑内存模型，单从代码逻辑上来看，却是应该可以看得到的。

下面将结合代码和java内存模型相关内容来分析下put/get方法（*本文中所有ConcurrentHashMap相关的代码均来自hotspot1.6.0\_18*）。put方法我们只需关注Segment\#put，get方法只需关注Segment\#get，在继续之前，先要说明一下Segment里有两个volatile变量：**count**和**table**；HashEntry里有一个volatile变量：**value**。

Segment\#put

V put(K key, int hash, V value, boolean onlyIfAbsent) {
    	lock();
    	try {
    		int c = count;
    		if (c++ > threshold) // ensure capacity
    			rehash();
    		HashEntry<K,V>[] tab = table;
    		int index = hash & (tab.length - 1);
    		HashEntry<K,V> first = tab[index];
    		HashEntry<K,V> e = first;
    		while (e != null && (e.hash != hash || !key.equals(e.key)))
    			e = e.next;
    
    		V oldValue;
    		if (e != null) {
    			oldValue = e.value;
    			if (!onlyIfAbsent)
    				e.value = value;
    		}
    		else {
    			oldValue = null;
    			++modCount;
    			tab[index] = new HashEntry<K,V>(key, hash, first, value);
    			count = c; // write-volatile
    		}
    		return oldValue;
    	} finally {
    		unlock();
    	}
    }

Segment\#get

V get(Object key, int hash) {
    	if (count != 0) { // read-volatile
    		HashEntry<K,V> e = getFirst(hash);
    		while (e != null) {
    			if (e.hash == hash && key.equals(e.key)) {
    				V v = e.value;
    				if (v != null)
    					return v;
    				return readValueUnderLock(e); // recheck
    			}
    			e = e.next;
    		}
    	}
    	return null;
    }

我们如何确定线程1放入某个变量的值是否对线程2可见？文章开头提到的JLS链接中有说到，当a hb c时，a对c可见，那么我们接下来我们只要寻找put和get之间所有可能的执行轨迹上的hb关系。要找出hb关系，我们需要先找出与hb相关的Action。为方便，这里将两段代码放到了一张图片上。

[![concurrentHashMap_put_get-1024x512.png][]][concurrentHashMap_put_get-1024x512.png 1]

可以注意到，同一个Segment实例中的put操作是加了锁的，而对应的get却没有。根据hb关系中的线程间Action类别，可以从上图中找出这些Action，主要是volatile读写和加解锁，也就是图中画了横线的那些。

put操作可以分为两种情况，一是key已经存在，修改对应的value；二是key不存在，将一个新的Entry加入底层数据结构。

key已经存在的情况比较简单，即if (e != null)部分，前面已经说过HashEntry的value是个volatile变量，当线程1给value赋值后，会立马对执行get的线程2可见，而不用等到put方法结束。

key不存在的情况稍微复杂一些，新加一个Entry的逻辑在else中。那么将new HashEntry赋值给tab\[index\]是否能立刻对执行get的线程可见呢？我们只需分析写tab\[index\]与读取tab\[index\]之间是否有hb关系即可。

假设执行put的线程与执行get的线程的轨迹是这样的

<table style="margin:0px 0px 1em; padding:0px; border-collapse:collapse; width:916px; border:0px"> 
 <tbody> 
  <tr> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">执行put的线程</td> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">执行get的线程</td> 
  </tr> 
  <tr> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">⑧tab[index] = new HashEntry&lt;K,V&gt;(key, hash, first, value)</td> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">②count = c</td> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">&nbsp;</td> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">③if (count != 0)</td> 
  </tr> 
  <tr> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">&nbsp;</td> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">⑨HashEntry e = getFirst(hash);</td> 
  </tr> 
 </tbody> 
</table>

tab变量是一个普通的变量，虽然给它赋值的是volatile的table。另外，虽然引用类型（数组类型）的变量table是volatile的，但table中的元素不是volatile的，因此⑧只是一个普通的写操作；count变量是volatile的，因此②是一个volatile写；③很显然是一个volatile读；⑨中getFirst方法中读取了table，因此包含一个volatile读。

根据Synchronization Order，对同一个volatile变量，有volatile写 hb volatile读。在这个执行轨迹中，时间上②在③之前发生，且②是写count，③是读count，都是针对同一个volatile变量count，因此有② hb ③；又因为⑧和②是同一个线程中的，③和⑨是同一个线程中的，根据Program Order，有⑧ hb ②，③ hb ⑨。目前我们有了三组关系了⑧ hb ②，② hb ③，③ hb ⑨，再根据hb关系是可传递的（即若有x hb y且y hb z，可得出x hb z），可以得出⑧ hb ⑨。因此，如果按照上述执行轨迹，⑧中写入的数组元素对⑨中的读取操作是可见的。

再考虑这样一个执行轨迹：

<table style="margin:0px 0px 1em; padding:0px; border-collapse:collapse; width:916px; border:0px"> 
 <tbody> 
  <tr> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">执行put的线程</td> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">执行get的线程</td> 
  </tr> 
  <tr> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">⑧tab[index] = new HashEntry&lt;K,V&gt;(key, hash, first, value)</td> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">&nbsp;</td> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">③if (count != 0)</td> 
  </tr> 
  <tr> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">②count = c</td> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">&nbsp;</td> 
   <td style="border:1px solid rgb(204,204,204); padding:15px">⑨HashEntry e = getFirst(hash);</td> 
  </tr> 
 </tbody> 
</table>

这里只是变换了下执行顺序。每条语句的volatile读写含义同上，但它们之间的hb关系却改变了。Program Order是我们一直拥有的，即我们有⑧ hb ②，③ hb ⑨。但这次对volatile的count的读时间上发生在对count的写之前，我们无法得出② hb ⑨这层关系了。因此，通过count变量，在这个轨迹上是无法得出⑧ hb ⑨的。那么，存不存在其它可替换关系，让我们仍能得出⑧ hb ⑨呢？

我们要找的是，在⑧之后有一条语句或指令x，在⑨之前有一条语句或指令y，存在x hb y。这样我们可以有⑧ hb x，x hb y， y hb ⑨。就让我们来找一下是否存在这样的x和y。图中的⑤、⑥、⑦、①存在volatile读写，但是它们在⑧之前，因此对确立⑧ hb ⑨这个关系没有用处；同理，④在⑨之后，我们要找的是⑨之前的，因此也对这个问题无益。前面已经分析过了②，③之间没法确立hb关系。

在⑧之后，我们发现一个unlock操作，如果能在⑨之前找到一个lock操作，那么我们要找的x就是unlock，要找的y就是lock，因为Synchronization Order中有unlock hb lock的关系。但是，很不幸运，⑨之前没有lock操作。因此，对于这样的轨迹，是没有⑧ hb ⑨关系的，也就是说，如果某个Segment实例中的put将一个Entry加入到了table中，在未执行count赋值操作之前有另一个线程执行了同一个Segment实例中的get，来获取这个刚加入的Entry中的value，那么是有可能取不到的！

此外，如果getFirst(hash)先执行，tab\[index\] = new HashEntry<K,V>(key, hash, first, value)后执行，那么，这个get操作也是看不到put的结果的。

……

正是因为get操作几乎所有时候都是一个无锁操作（get中有一个readValueUnderLock调用，不过这句执行到的几率极小），使得同一个Segment实例上的put和get可以同时进行，这就是get操作是弱一致的根本原因。Java API中对此有一句简单的描述:

> Retrievals reflect the results of the most recently ***completed*** update operations holding upon their onset.

也就是说API上保证get操作一定能看到**已完成**的put操作。已完成的put操作肯定在get读取count之前对count做了写入操作。因此，也就是我们第一个轨迹分析的情况。

#### ConcurrentHashMap\#clear ####

clear方法很简单，看下代码即知。

public void clear() {
    	for (int i = 0; i < segments.length; ++i)
    		segments[i].clear();
    }

因为没有全局的锁，在清除完一个segments之后，正在清理下一个segments的时候，已经清理segments可能又被加入了数据，因此clear返回的时候，ConcurrentHashMap中是可能存在数据的。因此，clear方法是弱一致的。

#### ConcurrentHashMap中的迭代器 ####

ConcurrentHashMap中的迭代器主要包括entrySet、keySet、values方法。它们大同小异，这里选择entrySet解释。当我们调用entrySet返回值的iterator方法时，返回的是EntryIterator，在EntryIterator上调用next方法时，最终实际调用到了HashIterator.advance()方法，看下这个方法：

final void advance() {
    	if (nextEntry != null && (nextEntry = nextEntry.next) != null)
    		return;
    
    	while (nextTableIndex >= 0) {
    		if ( (nextEntry = currentTable[nextTableIndex--]) != null)
    			return;
    	}
    
    	while (nextSegmentIndex >= 0) {
    		Segment<K,V> seg = segments[nextSegmentIndex--];
    		if (seg.count != 0) {
    			currentTable = seg.table;
    			for (int j = currentTable.length - 1; j >= 0; --j) {
    				if ( (nextEntry = currentTable[j]) != null) {
    					nextTableIndex = j - 1;
    					return;
    				}
    			}
    		}
    	}
    }

这个方法在遍历底层数组。在遍历过程中，如果已经遍历的数组上的内容变化了，迭代器不会抛出ConcurrentModificationException异常。如果未遍历的数组上的内容发生了变化，则有可能反映到迭代过程中。这就是ConcurrentHashMap迭代器弱一致的表现。

#### 总结 ####

ConcurrentHashMap的弱一致性主要是为了提升效率，是一致性与效率之间的一种权衡。要成为强一致性，就得到处使用锁，甚至是全局锁，这就与Hashtable和同步的HashMap一样了。

曾经研究过jkd1.5新特性，其中**ConcurrentHashMap就是其中之一，其特点：效率比Hashtable高，并发性比hashmap好。结合了两者的特点。**  
   集合是编程中最常用的数据结构。而谈到并发，几乎总是离不开集合这类高级数据结构的支持。比如两个线程需要同时访问一个中间临界区（Queue），比如常会用缓存作为外部文件的副本（HashMap）。这篇文章主要分析jdk1.5的3种并发集合类型（concurrent，copyonright，queue）中的ConcurrentHashMap，让我们从原理上细致的了解它们，能够让我们在深度项目开发中获益非浅。

在tiger之前，我们使用得最多的数据结构之一就是HashMap和Hashtable。大家都知道， **HashMap中未进行同步考虑，而Hashtable则使用了synchronized，带来的直接影响就是可选择，我们可以在单线程时使用HashMap提高效率，而多线程时用Hashtable来保证安全。**

当我们享受着jdk带来的便利时同样承受它带来的不幸恶果。通过分析Hashtable就知道， synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，安全的背后是巨大的浪费，慧眼独具的DougLee立马拿出了解决方案----ConcurrentHashMap。

** ConcurrentHashMap和Hashtable主要区别就是围绕着锁的粒度以及如何锁。如图**

![0_1328159341AvdF.gif][]

左边便是Hashtable的实现方式---锁整个hash表；而右边则是**ConcurrentHashMap的实现方式---锁桶（或段）。** ConcurrentHashMap将hash表分为16个桶（默认值），诸如get,put,remove等常用操作只锁当前需要用到的桶。试想，原来 只能一个线程进入，现在却能同时16个写线程进入（写线程才需要锁定，而读线程几乎不受限制，之后会提到），并发性的提升是显而易见的。

更令人惊讶的是ConcurrentHashMap的读取并发，因为在读取的大多数时候都没有用到锁定，所以读取操作几乎是完全的并发操作，而写操作锁定的粒度又非常细，比起之前又更加快速（这一点在桶更多时表现得更明显些）。 **只有在求size等操作时才需要锁定整个表**。而在迭代时， **ConcurrentHashMap使用了不同于传统集合的快速失败迭代器（见之前的文章《JAVA API备忘---集合》）的另一种迭代方式，我们称为弱一致迭代器。**在这种迭代方式中，当iterator被创建后集合再发生改变就不再是抛出 ConcurrentModificationEx ception，取而代之的是在改变时new新的数据从而不影响原有的数 据，iterator完成后再将头指针替换为新的数据，这样iterator线程可以使用原来老的数据，而写线程也可以并发的完成改变，更重要的，这保证 了多个线程并发执行的连续性和扩展性，是性能提升的关键。

接下来，让我们看看ConcurrentHashMap中的几个重要方法，心里知道了实现机制后，使用起来就更加有底气。

ConcurrentHashMap中主要实体类就是三个： **ConcurrentHashMap（整个Hash表）,Segment（桶），HashEntry（节点）**，对应上面的图可以看出之间的关系。

get 方法（请注意，这里分析的方法都是针对桶的，因为ConcurrentHashMap的最大改进就是将粒度细化到了桶上），首先判断了当前桶的数据个数是 否为0，为0自然不可能get到什么，只有返回null，这样做避免了不必要的搜索，也用最小的代价避免出错。然后得到头节点（方法将在下面涉及）之后就 是根据hash和key逐个判断是否是指定的值，如果是并且值非空就说明找到了，直接返回；程序非常简单，但有一个令人困惑的地方，这句 **return readValueUnderLock(e)**到底是用来干什么的呢？研究它的代码，在锁定之后返回一个值。但这里已经有一句V v = e.value得到了节点的值，这句return readValueUnderLock(e)是否多此一举？事实上，这里完全是 **为了并发考虑的，这里当v为空时，可能是一个线程正在改变节点，而之前的 get操作都未进行锁定，根据bernstein条件，读后写或写后读都会引起数据的不一致，所以这里要对这个e重新上锁再读一遍，以保证得到的是正确值，**这里不得不佩服Doug Lee思维的严密性。整个get操作只有很少的情况会锁定，相对于之前的Hashtable，并发是不可避免的啊！

**\[java\]**  [view plain][]   [copy][view plain]

1.  V get(Object key, **int** hash) \{  
2.      **if** (count != 0) \{ // read-volatile  
3.          HashEntry<K,V> e = getFirst(hash);  
4.          **while** (e != **null**) \{  
5.              **if** (e.hash == hash && key.equals(e.key)) \{  
6.                  V v = e.value;  
7.                  **if** (v != **null**)  
8.                      **return** v;  
9.                  **return** readValueUnderLock(e); // recheck  
10.             \}  
11.             e = e.next;  
12.         \}  
13.     \}  
14.     **return** **null**;  
15. \}  
16.   
17. V readValueUnderLock(HashEntry<K,V> e) \{  
18.     lock();  
19.     **try** \{  
20.         **return** e.value;  
21.     \} **finally** \{  
22.         unlock();  
23.     \}  
24. \}

**put 操作一上来就锁定了整个segment，这当然是为了并发的安全，修改数据是不能并发进行的**，必须得有个判断是否超限的语句以确保容量不足时能够 rehash，而比较难懂的是这句int index = hash & (tab.length - 1)，原来 **segment里面才是真正的hashtable，即每个segment是一个传统意义上的hashtable**,如上图，从两者的结构就可以看出区别，这里就是找出需要的entry在table的哪一个位置，之后得到的entry就是这个链的第一个节点，如果e!=null，说明找到了，这是就要替换节点的值（onlyIfAbsent == false），否则，我们需要new一个entry，它的后继是first，而让tab\[index\]指向它，什么意思呢？实际上就是将这个新entry 插入到链头，剩下的就非常容易理解了。

**\[java\]**  [view plain][]   [copy][view plain]

1.  V put(K key, **int** hash, V value, **boolean** onlyIfAbsent) \{  
2.              lock();  
3.              **try** \{  
4.                  **int** c = count;  
5.                  **if** (c++ > threshold) // ensure capacity  
6.                      rehash();  
7.                  HashEntry<K,V>\[\] tab = table;  
8.                  **int** index = hash & (tab.length - 1);  
9.                  HashEntry<K,V> first = tab\[index\];  
10.                 HashEntry<K,V> e = first;  
11.                 **while** (e != **null** && (e.hash != hash || !key.equals(e.key)))  
12.                     e = e.next;  
13.   
14.                 V oldValue;  
15.                 **if** (e != **null**) \{  
16.                     oldValue = e.value;  
17.                     **if** (!onlyIfAbsent)  
18.                         e.value = value;  
19.                 \}  
20.                 **else** \{  
21.                     oldValue = **null**;  
22.                     ++modCount;  
23.                     tab\[index\] = **new** HashEntry<K,V>(key, hash, first, value);  
24.                     count = c; // write-volatile  
25.                 \}  
26.                 **return** oldValue;  
27.             \} **finally** \{  
28.                 unlock();  
29.             \}  
30.         \}

remove 操作非常类似put，但要注意一点区别，中间那个for循环是做什么用的呢？（\*号标记）从代码来看，就是将定位之后的所有entry克隆并拼回前面去， 但有必要吗？每次删除一个元素就要将那之前的元素克隆一遍？这点其实是由entry的不变性来决定的，仔细观察entry定义，发现除了value，其他 所有属性都是用final来修饰的，这意味着在第一次设置了next域之后便不能再改变它，取而代之的是将它之前的节点全都克隆一次。至于entry为什么要设置为不变性，这跟不变性的访问不需要同步从而节省时间有关，关于不变性的更多内容，请参阅之前的文章《线程高级---线程的一些编程技巧》

**\[java\]**  [view plain][]   [copy][view plain]

1.      V remove(Object key, **int** hash, Object value) \{  
2.          lock();  
3.          **try** \{  
4.              **int** c = count - 1;  
5.              HashEntry<K,V>\[\] tab = table;  
6.              **int** index = hash & (tab.length - 1);  
7.              HashEntry<K,V> first = tab\[index\];  
8.              HashEntry<K,V> e = first;  
9.              **while** (e != **null** && (e.hash != hash || !key.equals(e.key)))  
10.                 e = e.next;  
11.   
12.             V oldValue = **null**;  
13.             **if** (e != **null**) \{  
14.                 V v = e.value;  
15.                 **if** (value == **null** || value.equals(v)) \{  
16.                     oldValue = v;  
17.                     // All entries following removed node can stay  
18.                     // in list, but all preceding ones need to be  
19.                     // cloned.  
20.                     ++modCount;  
21.                     HashEntry<K,V> newFirst = e.next;  
22.                     **for** (HashEntry<K,V> p = first; p != e; p = p.next)  
23.                         newFirst = **new** HashEntry<K,V>(p.key, p.hash,  
24.                                                       newFirst, p.value);  
25.                     tab\[index\] = newFirst;  
26.                     count = c; // write-volatile  
27.                 \}  
28.             \}  
29.             **return** oldValue;  
30.         \} **finally** \{  
31.             unlock();  
32.         \}  
33.     \}  
34.   
35. **static** **final** **class** HashEntry<K,V> \{  
36.     **final** K key;  
37.     **final** **int** hash;  
38.     **volatile** V value;  
39.     **final** HashEntry<K,V> next;  
40.   
41.     HashEntry(K key, **int** hash, HashEntry<K,V> next, V value) \{  
42.         **this**.key = key;  
43.         **this**.hash = hash;  
44.         **this**.next = next;  
45.         **this**.value = value;  
46.     \}  
47.   
48. 　　@SuppressWarnings("unchecked")  
49. 　　**static** **final** <K,V> HashEntry<K,V>\[\] newArray(**int** i) \{  
50.     　　**return** **new** HashEntry\[i\];  
51. 　　\}  
52. \}

转自：  [http://www.cnblogs.com/samuelin/articles/2208194.html][http_www.cnblogs.com_samuelin_articles_2208194.html]

[JLS _17.4.5. Happens-before Order]: http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.5
[Java]: http://ifeve.com/java-memory-model-7/
[Happens before]: http://ifeve.com/happens-before/
[ConcurrentHashMap]: http://ifeve.com/concurrenthashmap/
[concurrentHashMap_put_get-1024x512.png]: /images/20220720/741f7ead9db54ac6b14e9220b23558fe.png
[concurrentHashMap_put_get-1024x512.png 1]: http://ifeve.com/concurrenthashmap-weakly-consistent/concurrenthashmap_put_get/
[0_1328159341AvdF.gif]: /images/20220720/8dbbf491e85843c48f7efc6081d94f17.png
[view plain]: http://blog.csdn.net/wl_ldy/article/details/7228127#
[http_www.cnblogs.com_samuelin_articles_2208194.html]: http://www.cnblogs.com/samuelin/articles/2208194.html