【67期】談談ConcurrentHashMap是如何保證線程安全的？

程序員的成長之路

互聯(lián)網/程序員/技術/資料共享?

閱讀本文大概需要 5 分鐘。

來自：www.cnblogs.com/keeya/p/9632958.html

我們知道，ConcurrentHashmap(1.8)這個并發(fā)集合框架是線程安全的，當你看到源碼的get操作時，會發(fā)現(xiàn)get操作全程是沒有加任何鎖的，這也是這篇博文討論的問題——為什么它不需要加鎖呢？

ConcurrentHashMap的簡介

我想有基礎的同學知道在jdk1.7中是采用Segment + HashEntry + ReentrantLock的方式進行實現(xiàn)的，而1.8中放棄了Segment臃腫的設計，取而代之的是采用Node + CAS + Synchronized來保證并發(fā)安全進行實現(xiàn)。

• JDK1.8的實現(xiàn)降低鎖的粒度，JDK1.7版本鎖的粒度是基于Segment的，包含多個HashEntry，而JDK1.8鎖的粒度就是HashEntry（首節(jié)點）

• JDK1.8版本的數(shù)據結構變得更加簡單，使得操作也更加清晰流暢，因為已經使用synchronized來進行同步，所以不需要分段鎖的概念，也就不需要Segment這種數(shù)據結構了，由于粒度的降低，實現(xiàn)的復雜度也增加了

• JDK1.8使用紅黑樹來優(yōu)化鏈表，基于長度很長的鏈表的遍歷是一個很漫長的過程，而紅黑樹的遍歷效率是很快的，代替一定閾值的鏈表，這樣形成一個最佳拍檔

get操作源碼

• 首先計算hash值，定位到該table索引位置，如果是首節(jié)點符合就返回

• 如果遇到擴容的時候，會調用標志正在擴容節(jié)點ForwardingNode的find方法，查找該節(jié)點，匹配就返回

• 以上都不符合的話，就往下遍歷節(jié)點，匹配就返回，否則最后就返回null

  
  

//會發(fā)現(xiàn)源碼中沒有一處加了鎖
public?V?get(Object?key)?{
????Node[]?tab;?Node?e,?p;?int?n,?eh;?K?ek;
????int?h?=?spread(key.hashCode());?//計算hash
????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&
??????(e?=?tabAt(tab,?(n?-?1)?&?h))?!=?null)?{//讀取首節(jié)點的Node元素
????????if?((eh?=?e.hash)?==?h)?{?//如果該節(jié)點就是首節(jié)點就返回
????????????if?((ek?=?e.key)?==?key?||?(ek?!=?null?&&?key.equals(ek)))
????????????????return?e.val;
????????}
????????//hash值為負值表示正在擴容，這個時候查的是ForwardingNode的find方法來定位到nextTable來
????????//eh=-1，說明該節(jié)點是一個ForwardingNode，正在遷移，此時調用ForwardingNode的find方法去nextTable里找。
????????//eh=-2，說明該節(jié)點是一個TreeBin，此時調用TreeBin的find方法遍歷紅黑樹，由于紅黑樹有可能正在旋轉變色，所以find里會有讀寫鎖。
????????//eh>=0，說明該節(jié)點下掛的是一個鏈表，直接遍歷該鏈表即可。
????????else?if?(eh?0)
????????????return?(p?=?e.find(h,?key))?!=?null???p.val?:?null;
????????while?((e?=?e.next)?!=?null)?{//既不是首節(jié)點也不是ForwardingNode，那就往下遍歷
????????????if?(e.hash?==?h?&&
?????????????((ek?=?e.key)?==?key?||?(ek?!=?null?&&?key.equals(ek))))
?????????????????return?e.val;
????????}
????}
????return?null;
}

get沒有加鎖的話，ConcurrentHashMap是如何保證讀到的數(shù)據不是臟數(shù)據的呢？

volatile登場

對于可見性，Java提供了volatile關鍵字來保證可見性、有序性。但不保證原子性。

普通的共享變量不能保證可見性，因為普通共享變量被修改之后，什么時候被寫入主存是不確定的，當其他線程去讀取時，此時內存中可能還是原來的舊值，因此無法保證可見性。

• volatile關鍵字對于基本類型的修改可以在隨后對多個線程的讀保持一致，但是對于引用類型如數(shù)組，實體bean，僅僅保證引用的可見性，但并不保證引用內容的可見性。。

• 禁止進行指令重排序。

背景：為了提高處理速度，處理器不直接和內存進行通信，而是先將系統(tǒng)內存的數(shù)據讀到內部緩存（L1，L2或其他）后再進行操作，但操作完不知道何時會寫到內存。

• 如果對聲明了volatile的變量進行寫操作，JVM就會向處理器發(fā)送一條指令，將這個變量所在緩存行的數(shù)據寫回到系統(tǒng)內存。但是，就算寫回到內存，如果其他處理器緩存的值還是舊的，再執(zhí)行計算操作就會有問題。

• 在多處理器下，為了保證各個處理器的緩存是一致的，就會實現(xiàn)緩存一致性協(xié)議，當某個CPU在寫數(shù)據時，如果發(fā)現(xiàn)操作的變量是共享變量，則會通知其他CPU告知該變量的緩存行是無效的，因此其他CPU在讀取該變量時，發(fā)現(xiàn)其無效會重新從主存中加載數(shù)據。

總結下來：

第一：使用volatile關鍵字會強制將修改的值立即寫入主存；

第二：使用volatile關鍵字的話，當線程2進行修改時，會導致線程1的工作內存中緩存變量的緩存行無效（反映到硬件層的話，就是CPU的L1或者L2緩存中對應的緩存行無效）；

第三：由于線程1的工作內存中緩存變量的緩存行無效，所以線程1再次讀取變量的值時會去主存讀取。

是加在數(shù)組上的volatile嗎?

????/**
?????*?The?array?of?bins.?Lazily?initialized?upon?first?insertion.
?????*?Size?is?always?a?power?of?two.?Accessed?directly?by?iterators.
?????*/
????transient?volatile?Node[]?table;

我們知道volatile可以修飾數(shù)組的，只是意思和它表面上看起來的樣子不同。舉個栗子，volatile int array[10]是指array的地址是volatile的而不是數(shù)組元素的值是volatile的.

用volatile修飾的Node

get操作可以無鎖是由于Node的元素val和指針next是用volatile修飾的，在多線程環(huán)境下線程A修改結點的val或者新增節(jié)點的時候是對線程B可見的。

static?class?Node<K,V>?implements?Map.Entry<K,V>?{
????final?int?hash;
????final?K?key;
????//可以看到這些都用了volatile修飾
????volatile?V?val;
????volatile?Node?next;

????Node(int?hash,?K?key,?V?val,?Node?next)?{
????????this.hash?=?hash;
????????this.key?=?key;
????????this.val?=?val;
????????this.next?=?next;
????}

????public?final?K?getKey()?{?return?key;?}
????public?final?V?getValue()?{?return?val;?}
????public?final?int?hashCode()?{?return?key.hashCode()?^?val.hashCode();?}
????public?final?String?toString(){?return?key?+?"="?+?val;?}
????public?final?V?setValue(V?value)?{
????????throw?new?UnsupportedOperationException();
????}

????public?final?boolean?equals(Object?o)?{
????????Object?k,?v,?u;?Map.Entry?e;
????????return?((o?instanceof?Map.Entry)?&&
??????????(k?=?(e?=?(Map.Entry)o).getKey())?!=?null?&&
??????????(v?=?e.getValue())?!=?null?&&
??????????(k?==?key?||?k.equals(key))?&&
??????????(v?==?(u?=?val)?||?v.equals(u)));?
????}

????/**
????*?Virtualized?support?for?map.get();?overridden?in?subclasses.
????*/
????Node?find(int?h,?Object?k)?{
????????Node?e?=?this;
????????if?(k?!=?null)?{
????????????do?{
????????????????K?ek;
????????????????if?(e.hash?==?h?&&
?????????????????((ek?=?e.key)?==?k?||?(ek?!=?null?&&?k.equals(ek))))
???????????????????return?e;
????????????}?while?((e?=?e.next)?!=?null);
????????}
????????return?null;
????}
}

既然volatile修飾數(shù)組對get操作沒有效果那加在數(shù)組上的volatile的目的是什么呢？

其實就是為了使得Node數(shù)組在擴容的時候對其他線程具有可見性而加的volatile

總結

• 在1.8中ConcurrentHashMap的get操作全程不需要加鎖，這也是它比其他并發(fā)集合比如hashtable、用Collections.synchronizedMap()包裝的hashmap;安全效率高的原因之一。

• get操作全程不需要加鎖是因為Node的成員val是用volatile修飾的和數(shù)組用volatile修飾沒有關系。

• 數(shù)組用volatile修飾主要是保證在數(shù)組擴容的時候保證可見性。

推薦閱讀：

【66期】Java容器面試題：談談你對 HashMap 的理解

【65期】Spring的IOC是啥？有什么好處?

【64期】MySQL 服務占用cpu 100%，如何排查問題? （MySQL面試第七彈）

5T技術資源大放送！包括但不限于：C/C++，Linux，Python，Java，PHP，人工智能，單片機，樹莓派，等等。在公眾號內回復「2048」，即可免費獲?。?！

微信掃描二維碼，關注我的公眾號

朕已閱?