作者:上帝愛吃蘋果
目錄
1.ConcurrentHashMap的簡介
2.get操作源碼
3.volatile登場
4.是加在數組上的volatile嗎?
5.用volatile修飾的Node
6.總結
我們知道,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使用紅黑樹來優化連結清單,基于長度很長的連結清單的周遊是一個很漫長的過程,而紅黑樹的周遊效率是很快的,代替一定門檻值的連結清單,這樣形成一個最佳拍檔
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnLiZjN0QTZyUGOwQWYiFjYmZDZxYDO2QDNkFmNykTN1czYzEWY0gzN08CXt92Yu4GZjlGbh5SZslmZxl3Lc9CX6MHc0RHaiojIsJye.png)
get操作源碼
首先計算hash值,定位到該table索引位置,如果是首節點符合就傳回
如果遇到擴容的時候,會調用标志正在擴容節點ForwardingNode的find方法,查找該節點,比對就傳回
以上都不符合的話,就往下周遊節點,比對就傳回,否則最後就傳回null
//會發現源碼中沒有一處加了鎖
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嗎?
/**
* 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修改結點的val或者新增節點的時候是對線程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修飾數組對get操作沒有效果那加在數組上的volatile的目的是什麼呢?
其實就是為了使得Node數組在擴容的時候對其他線程具有可見性而加的volatile
總結
在1.8中ConcurrentHashMap的get操作全程不需要加鎖,這也是它比其他并發集合比如hashtable、用Collections.synchronizedMap()包裝的hashmap;安全效率高的原因之一。
get操作全程不需要加鎖是因為Node的成員val是用volatile修飾的和數組用volatile修飾沒有關系。
數組用volatile修飾主要是保證在數組擴容的時候保證可見性。
歡迎大家一起交流,喜歡文章記得點個贊喲,感謝支援!