concurrenthashmap的size方法原理

同上，這也是同一個(gè)面試的時(shí)候別人問(wèn)的，我只是記得看過(guò)，在concurrenthashmap中會(huì)統(tǒng)計(jì)多次，當(dāng)時(shí)就說(shuō)會(huì)統(tǒng)計(jì)兩次進(jìn)行比較，人家接著問(wèn)為啥。。。我傻了一下，這不是明擺著兩次統(tǒng)計(jì)的中間有新的變化了，會(huì)導(dǎo)致統(tǒng)計(jì)不準(zhǔn)確嗎？當(dāng)時(shí)也不知道說(shuō)啥好，以為他有新的點(diǎn)，就說(shuō)不知道。面試時(shí)很多問(wèn)題其實(shí)冷靜下來(lái)想一下，可以更進(jìn)一步的，有時(shí)候其實(shí)也是怕他更進(jìn)一步后下面的挖坑挖大了。

下面具體說(shuō)一下這個(gè)size方法

代碼就不貼了。只說(shuō)原理。

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

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

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

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

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

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

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

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

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

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

concurrenthashmap的size的思考

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

我們首先會(huì)想到以下兩種方法

1.獲取所有的Segment鎖。

這個(gè)方法是可行的，但是這會(huì)導(dǎo)致并發(fā)性能變差，因?yàn)槟惬@取了所有的鎖，那么別的線程將無(wú)法對(duì)該HashMap執(zhí)行任何操作。

2.逐個(gè)地獲取Segment。

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

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

java1.7以前的源碼：

由于在累加count的操作的過(guò)程中之前累加過(guò)的count發(fā)生變化的幾率非常小，所以ConcurrentHashMap先嘗試2次不鎖住Segment的方式來(lái)統(tǒng)計(jì)每個(gè)Segment的大小，如果在統(tǒng)計(jì)的過(guò)程中Segment的count發(fā)生了變化，這時(shí)候再加鎖統(tǒng)計(jì)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;
? ? }

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

查看兩個(gè)屬性：baseCount 和 counterCells。

先看 baseCount

private transient volatile long baseCount;

baseCount是一個(gè) volatile 的變量，在 addCount 方法中會(huì)使用它，而 addCount 方法在 put 結(jié)束后會(huì)調(diào)用。在 addCount 方法中，會(huì)對(duì)這個(gè)變量做 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ā)導(dǎo)致 CAS 失敗了，怎么辦呢？使用 counterCells。

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

最后，再來(lái)看一下counterCells這個(gè)類(lèi)。

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

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

先引用個(gè)偽共享的解釋?zhuān)?緩存系統(tǒng)中是以緩存行（cache line）為單位存儲(chǔ)的。

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

當(dāng)多線程修改互相獨(dú)立的變量時(shí)， 如果這些變量共享同一個(gè)緩存行，就會(huì)無(wú)意中影響彼此的性能，這就是偽共享。

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

最新評(píng)論