聊一聊concurrenthashmap的size方法原理

Posted on by

concurrenthashmap的size方法原理

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

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

代碼就不貼瞭。隻說原理。

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

1.進行第一遍遍歷segments數組

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

這裡需要提一下modCount，這個是當segment有任何操作都會進行一次增量操作，代表的是對Segment中元素的數量造成影響的操作的次數，這個值隻增不減！！！！隻增不減很重要，這樣就不會出現一個segment+1，導致modcount+1,而另一個segment-1，即modcount-1 ,從而在統計所有的時候modcount沒有變化。

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

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

3.如果經判斷發現兩次統計出的modCount並不一致

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

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

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

concurrenthashmap的size的思考

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

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

1.獲取所有的Segment鎖。

這個方法是可行的，但是這會導致並發性能變差，因為你獲取瞭所有的鎖，那麼別的線程將無法對該HashMap執行任何操作。

2.逐個地獲取Segment。

這種方法也有問題，有可能在後面獲取下一個Segment裡面的元素的個數的時候，上面一個Segment裡面元素的個數已經很可能改變瞭，因此最後累加到最後，有可能數據是錯誤的。

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

java1.7以前的源碼：

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

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

取size的核心是sumCount函數。

    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();
        }

但是如果並發導致 CAS 失敗瞭，怎麼辦呢？使用 counterCells。

如果上面 CAS 失敗瞭，在 fullAddCount 方法中，會繼續死循環操作，直到成功。

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

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

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

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

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

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

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。

推薦閱讀：