您好,登錄后才能下訂單哦!
前言
我們知道,ConcurrentHashmap(1.8)這個并發(fā)集合框架是線程安全的,當(dāng)你看到源碼的get操作時,會發(fā)現(xiàn)get操作全程是沒有加任何鎖的,這也是這篇博文討論的問題——為什么它不需要加鎖呢?
ConcurrentHashMap的簡介
我想有基礎(chǔ)的朋友知道在jdk1.7中是采用Segment + HashEntry + ReentrantLock的方式進行實現(xiàn)的,而1.8中放棄了Segment臃腫的設(shè)計,取而代之的是采用Node + CAS + Synchronized來保證并發(fā)安全進行實現(xiàn)。
JDK1.8的實現(xiàn)降低鎖的粒度,JDK1.7版本鎖的粒度是基于Segment的,包含多個HashEntry,而JDK1.8鎖的粒度就是HashEntry(首節(jié)點)
JDK1.8版本的數(shù)據(jù)結(jié)構(gòu)變得更加簡單,使得操作也更加清晰流暢,因為已經(jīng)使用synchronized來進行同步,所以不需要分段鎖的概念,也就不需要Segment這種數(shù)據(jù)結(jié)構(gòu)了,由于粒度的降低,實現(xiàn)的復(fù)雜度也增加了
JDK1.8使用紅黑樹來優(yōu)化鏈表,基于長度很長的鏈表的遍歷是一個很漫長的過程,而紅黑樹的遍歷效率是很快的,代替一定閾值的鏈表,這樣形成一個最佳拍檔
get操作源碼
首先計算hash值,定位到該table索引位置,如果是首節(jié)點符合就返回
如果遇到擴容的時候,會調(diào)用標(biāo)志正在擴容節(jié)點ForwardingNode的find方法,查找該節(jié)點,匹配就返回
以上都不符合的話,就往下遍歷節(jié)點,匹配就返回,否則最后就返回null
//會發(fā)現(xiàn)源碼中沒有一處加了鎖 public?V?get(Object?key)?{ ??Node<K,V>[]?tab;?Node<K,V>?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,正在遷移,此時調(diào)用ForwardingNode的find方法去nextTable里找。 ????//eh=-2,說明該節(jié)點是一個TreeBin,此時調(diào)用TreeBin的find方法遍歷紅黑樹,由于紅黑樹有可能正在旋轉(zhuǎn)變色,所以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ù)據(jù)不是臟數(shù)據(jù)的呢?
volatile登場
對于可見性,Java提供了volatile關(guān)鍵字來保證可見性、有序性。但不保證原子性。
普通的共享變量不能保證可見性,因為普通共享變量被修改之后,什么時候被寫入主存是不確定的,當(dāng)其他線程去讀取時,此時內(nèi)存中可能還是原來的舊值,因此無法保證可見性。
volatile關(guān)鍵字對于基本類型的修改可以在隨后對多個線程的讀保持一致,但是對于引用類型如數(shù)組,實體bean,僅僅保證引用的可見性,但并不保證引用內(nèi)容的可見性。。
禁止進行指令重排序。
背景:為了提高處理速度,處理器不直接和內(nèi)存進行通信,而是先將系統(tǒng)內(nèi)存的數(shù)據(jù)讀到內(nèi)部緩存(L1,L2或其他)后再進行操作,但操作完不知道何時會寫到內(nèi)存。
如果對聲明了volatile的變量進行寫操作,JVM就會向處理器發(fā)送一條指令,將這個變量所在緩存行的數(shù)據(jù)寫回到系統(tǒng)內(nèi)存。但是,就算寫回到內(nèi)存,如果其他處理器緩存的值還是舊的,再執(zhí)行計算操作就會有問題。
在多處理器下,為了保證各個處理器的緩存是一致的,就會實現(xiàn)緩存一致性協(xié)議,當(dāng)某個CPU在寫數(shù)據(jù)時,如果發(fā)現(xiàn)操作的變量是共享變量,則會通知其他CPU告知該變量的緩存行是無效的,因此其他CPU在讀取該變量時,發(fā)現(xiàn)其無效會重新從主存中加載數(shù)據(jù)。
總結(jié)下來:
第一:使用volatile關(guān)鍵字會強制將修改的值立即寫入主存;
第二:使用volatile關(guān)鍵字的話,當(dāng)線程2進行修改時,會導(dǎo)致線程1的工作內(nèi)存中緩存變量的緩存行無效(反映到硬件層的話,就是CPU的L1或者L2緩存中對應(yīng)的緩存行無效);
第三:由于線程1的工作內(nèi)存中緩存變量的緩存行無效,所以線程1再次讀取變量的值時會去主存讀取。
歡迎大家關(guān)注我的公種浩【程序員追風(fēng)】,文章都會在里面更新,整理的資料也會放在里面。
是加在數(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<K,V>[]?table;
我們知道volatile可以修飾數(shù)組的,只是意思和它表面上看起來的樣子不同。舉個栗子,volatile int array[10]是指array的地址是volatile的而不是數(shù)組元素的值是volatile的.
用volatile修飾的Node
get操作可以無鎖是由于Node的元素val和指針next是用volatile修飾的,在多線程環(huán)境下線程A修改結(jié)點的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<K,V>?next; ??Node(int?hash,?K?key,?V?val,?Node<K,V>?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<K,V>?find(int?h,?Object?k)?{ ????Node<K,V>?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ù)組在擴容的時候?qū)ζ渌€程具有可見性而加的volatile
總結(jié)
在1.8中ConcurrentHashMap的get操作全程不需要加鎖,這也是它比其他并發(fā)集合比如hashtable、用Collections.synchronizedMap()包裝的hashmap;安全效率高的原因之一。
get操作全程不需要加鎖是因為Node的成員val是用volatile修飾的和數(shù)組用volatile修飾沒有關(guān)系。
數(shù)組用volatile修飾主要是保證在數(shù)組擴容的時候保證可見性。
最后?
歡迎大家一起交流,喜歡文章記得關(guān)注我點個贊喲,感謝支持!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。