concurrenthashmap的size方法原理

同上，這也是同一個面試的時候別人問的，我只是記得看過，在concurrenthashmap中會統(tǒng)計多次，當時就說會統(tǒng)計兩次進行比較，人家接著問為啥。。。我傻了一下，這不是明擺著兩次統(tǒng)計的中間有新的變化了，會導致統(tǒng)計不準確嗎？當時也不知道說啥好，以為他有新的點，就說不知道。面試時很多問題其實冷靜下來想一下，可以更進一步的，有時候其實也是怕他更進一步后下面的挖坑挖大了。

下面具體說一下這個size方法

代碼就不貼了。只說原理。

眾所周知，concurrenthashmap有很多歌segments，首先遍歷segments將每個segment的count加起來作為整個concurrenthashMap的size。如果沒有并發(fā)的情況下這自然就可以了，但這是多線程的，如果前腳統(tǒng)計完后腳有變化了，這就不準確了，源碼中引入了，modCount和兩次比較來實現(xiàn)size的確認。具體過程是：

1.進行第一遍遍歷segments數(shù)組

將每個segemnt的count加起來作為總數(shù)，期間把每個segment的modCount加起來sum作為結果是否被修改的判斷依據(jù)。

這里需要提一下modCount，這個是當segment有任何操作都會進行一次增量操作，代表的是對Segment中元素的數(shù)量造成影響的操作的次數(shù)，這個值只增不減?。。。≈辉霾粶p很重要，這樣就不會出現(xiàn)一個segment+1，導致modcount+1,而另一個segment-1，即modcount-1 ,從而在統(tǒng)計所有的時候modcount沒有變化。

2.size操作就是遍歷了兩次所有的Segments

每次記錄Segment的modCount值，然后將兩次的modCount進行比較，如果相同，則表示期間沒有發(fā)生過寫入操作，就將原先遍歷的結果返回，如果不相同，則把這個過程再重復做一次，如果再不相同，則就需要將所有的Segment都鎖住，然后一個一個遍歷了。

3.如果經(jīng)判斷發(fā)現(xiàn)兩次統(tǒng)計出的modCount并不一致

那就如上所說，要重新啟用全部segment加鎖的方式來進行count的獲取和統(tǒng)計了，這樣在此期間每個segement都被鎖住，無法進行其他操作，統(tǒng)計出的count自然很準確。

而之所以之所以要先不加鎖進行判斷，道理很明顯，就是不希望因為size操作獲取這么多鎖，因為獲取鎖不光占用資源，也會影響其他線程對ConcurrentHash的使用，影響并發(fā)情況下程序執(zhí)行的效率。使用鎖要謹慎！

原理大概就是這樣的，具體的代碼可以去看源碼，而且源碼1.7和1.8有差別。。。有空再貼出來比較比較吧。

concurrenthashmap的size的思考

ConcurrentHashMap是通過分段鎖來控制整個Map的安全性和并發(fā)性，那么ConcurrentHashMap在求size的時候是如何兼顧到性能以及安全性的呢?

我們首先會想到以下兩種方法

1.獲取所有的Segment鎖。

這個方法是可行的，但是這會導致并發(fā)性能變差，因為你獲取了所有的鎖，那么別的線程將無法對該HashMap執(zhí)行任何操作。

2.逐個地獲取Segment。

這種方法也有問題，有可能在后面獲取下一個Segment里面的元素的個數(shù)的時候，上面一個Segment里面元素的個數(shù)已經(jīng)很可能改變了，因此最后累加到最后，有可能數(shù)據(jù)是錯誤的。

那么ConcurrentHashMap采用的是什么措施呢。源碼如下所示：

java1.7以前的源碼：

由于在累加count的操作的過程中之前累加過的count發(fā)生變化的幾率非常小，所以ConcurrentHashMap先嘗試2次不鎖住Segment的方式來統(tǒng)計每個Segment的大小，如果在統(tǒng)計的過程中Segment的count發(fā)生了變化，這時候再加鎖統(tǒng)計Segment的count。

java1.7以及1，7以后的源碼：

取size的核心是sumCount函數(shù)。

? ? final long sumCount() {
? ? ? ? CounterCell[] as = counterCells; CounterCell a;
? ? ? ? long sum = baseCount;
? ? ? ? if (as != null) {
? ? ? ? ? ? for (int i = 0; i < as.length; ++i) {
? ? ? ? ? ? ? ? if ((a = as[i]) != null)
? ? ? ? ? ? ? ? ? ? sum += a.value;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return sum;
? ? }

核心邏輯：當 counterCells 不是 null，就遍歷元素，并和 baseCount 累加。

查看兩個屬性：baseCount 和 counterCells。

先看 baseCount

private transient volatile long baseCount;

baseCount是一個 volatile 的變量，在 addCount 方法中會使用它，而 addCount 方法在 put 結束后會調用。在 addCount 方法中，會對這個變量做 CAS 加法。

? private final void addCount(long x, int check) {
? ? ? ? CounterCell[] as; long b, s;
? ? ? ? if ((as = counterCells) != null ||
? ? ? ? ? ? !U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
? ? ? ? ? ? CounterCell a; long v; int m;
? ? ? ? ? ? boolean uncontended = true;
? ? ? ? ? ? if (as == null || (m = as.length - 1) < 0 ||
? ? ? ? ? ? ? ? (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
? ? ? ? ? ? ? ? !(uncontended =
? ? ? ? ? ? ? ? ? U.compareAndSetLong(a, CELLVALUE, v = a.value, v + x))) {
? ? ? ? ? ? ? ? fullAddCount(x, uncontended);
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
? ? ? ? ? ? if (check <= 1)
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? s = sumCount();
? ? ? ? }

但是如果并發(fā)導致 CAS 失敗了，怎么辦呢？使用 counterCells。

如果上面 CAS 失敗了，在 fullAddCount 方法中，會繼續(xù)死循環(huán)操作，直到成功。

最后，再來看一下counterCells這個類。

? ? @jdk.internal.vm.annotation.Contended static final class CounterCell {
? ? ? ? volatile long value;
? ? ? ? CounterCell(long x) { value = x; }
? ? }

上述源碼中的注釋是為了避免偽共享(false sharing)。

先引用個偽共享的解釋： 緩存系統(tǒng)中是以緩存行（cache line）為單位存儲的。

緩存行是2的整數(shù)冪個連續(xù)字節(jié)， 一般為32-256個字節(jié)。最常見的緩存行大小是64個字節(jié)。

當多線程修改互相獨立的變量時， 如果這些變量共享同一個緩存行，就會無意中影響彼此的性能，這就是偽共享。

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論