前言
concurrenthashmap是java 5中支持高并發、高吞吐量的線程安全hashmap實現。
我們知道，concurrenthashmap(1.8)這個并發集合框架是線程安全的，當你看到源碼的get操作時，會發現get操作全程是沒有加任何鎖的，這也是這篇博文討論的問題——為什么它不需要加鎖呢？
下面話不多說了，來一起看看詳細的介紹吧
concurrenthashmap的簡介
我想有基礎的同學知道在jdk1.7中是采用segment + hashentry + reentrantlock的方式進行實現的，而1.8中放棄了segment臃腫的設計，取而代之的是采用node + cas + synchronized來保證并發安全進行實現。
- jdk1.8的實現降低鎖的粒度，jdk1.7版本鎖的粒度是基于segment的，包含多個hashentry，而jdk1.8鎖的粒度就是hashentry（首節點）
- jdk1.8版本的數據結構變得更加簡單，使得操作也更加清晰流暢，因為已經使用synchronized來進行同步，所以不需要分段鎖的概念，也就不需要segment這種數據結構了，由于粒度的降低，實現的復雜度也增加了
- jdk1.8使用紅黑樹來優化鏈表，基于長度很長的鏈表的遍歷是一個很漫長的過程，而紅黑樹的遍歷效率是很快的，代替一定閾值的鏈表，這樣形成一個最佳拍檔
get操作源碼
- 首先計算hash值，定位到該table索引位置，如果是首節點符合就返回
- 如果遇到擴容的時候，會調用標志正在擴容節點forwardingnode的find方法，查找該節點，匹配就返回
- 以上都不符合的話，就往下遍歷節點，匹配就返回，否則最后就返回null
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
//會發現源碼中沒有一處加了鎖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) {//讀取首節點的node元素 if ((eh = e.hash) == h) { //如果該節點就是首節點就返回 if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } //hash值為負值表示正在擴容，這個時候查的是forwardingnode的find方法來定位到nexttable來 //eh=-1，說明該節點是一個forwardingnode，正在遷移，此時調用forwardingnode的find方法去nexttable里找。 //eh=-2，說明該節點是一個treebin，此時調用treebin的find方法遍歷紅黑樹，由于紅黑樹有可能正在旋轉變色，所以find里會有讀寫鎖。 //eh>=0，說明該節點下掛的是一個鏈表，直接遍歷該鏈表即可。 else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; while ((e = e.next) != null) {//既不是首節點也不是forwardingnode，那就往下遍歷 if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null;} |
get沒有加鎖的話，concurrenthashmap是如何保證讀到的數據不是臟數據的呢？
volatile登場
對于可見性，java提供了volatile關鍵字來保證可見性、有序性。但不保證原子性。
普通的共享變量不能保證可見性，因為普通共享變量被修改之后，什么時候被寫入主存是不確定的，當其他線程去讀取時，此時內存中可能還是原來的舊值，因此無法保證可見性。
- volatile關鍵字對于基本類型的修改可以在隨后對多個線程的讀保持一致，但是對于引用類型如數組，實體bean，僅僅保證引用的可見性，但并不保證引用內容的可見性。。
- 禁止進行指令重排序。
背景：為了提高處理速度，處理器不直接和內存進行通信，而是先將系統內存的數據讀到內部緩存（l1，l2或其他）后再進行操作，但操作完不知道何時會寫到內存。
- 如果對聲明了volatile的變量進行寫操作，jvm就會向處理器發送一條指令，將這個變量所在緩存行的數據寫回到系統內存。但是，就算寫回到內存，如果其他處理器緩存的值還是舊的，再執行計算操作就會有問題。
- 在多處理器下，為了保證各個處理器的緩存是一致的，就會實現緩存一致性協議，當某個cpu在寫數據時，如果發現操作的變量是共享變量，則會通知其他cpu告知該變量的緩存行是無效的，因此其他cpu在讀取該變量時，發現其無效會重新從主存中加載數據。
總結下來：
- 第一：使用volatile關鍵字會強制將修改的值立即寫入主存；
- 第二：使用volatile關鍵字的話，當線程2進行修改時，會導致線程1的工作內存中緩存變量的緩存行無效（反映到硬件層的話，就是cpu的l1或者l2緩存中對應的緩存行無效）；
- 第三：由于線程1的工作內存中緩存變量的緩存行無效，所以線程1再次讀取變量的值時會去主存讀取。
是加在數組上的volatile嗎?
|
1
2
3
4
5
|
/** * 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可以修飾數組的，只是意思和它表面上看起來的樣子不同。舉個栗子，volatile int array[10]是指array的地址是volatile的而不是數組元素的值是volatile的.
用volatile修飾的node
get操作可以無鎖是由于node的元素val和指針next是用volatile修飾的，在多線程環境下線程a修改因為hash沖突修改結點的val或者新增節點的時候是對線程b可見的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
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修飾數組對get操作沒有效果那加在數組上的volatile的目的是什么呢？
其實就是為了使得node數組在擴容的時候對其他線程具有可見性而加的volatile
總結
在1.8中concurrenthashmap的get操作全程不需要加鎖，這也是它比其他并發集合比如hashtable、用collections.synchronizedmap()包裝的hashmap;安全效率高的原因之一。
get操作全程不需要加鎖是因為node的成員val是用volatile修飾的和數組用volatile修飾沒有關系。
數組用volatile修飾主要是保證在數組擴容的時候保證可見性。
好了，以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對服務器之家的支持。
原文鏈接：https://www.cnblogs.com/keeya/p/9632958.html
