術(shù)語定義

術(shù)語英文解釋

哈希算法hash algorithm是一種將任意內(nèi)容的輸入轉(zhuǎn)換成相同長度輸出的加密方式，其輸出被稱為哈希值。

哈希表hash table根據(jù)設(shè)定的哈希函數(shù) H(key) 和處理沖突方法將一組關(guān)鍵字映象到一個(gè)有限的地址區(qū)間上，并以關(guān)鍵字在地址區(qū)間中的象作為記錄在表中的存儲(chǔ)位置，這種表稱為哈希表或散列，所得存儲(chǔ)位置稱為哈希地址或散列地址。

線程不安全的 HashMap

因?yàn)槎嗑€程環(huán)境下，使用 HashMap 進(jìn)行 put 操作會(huì)引起死循環(huán)，導(dǎo)致 CPU 利用率接近 100%，所以在并發(fā)情況下不能使用 HashMap，如以下代碼

final HashMap<String, String> map = new HashMap<String, String>(2);

Thread t = new Thread(new Runnable() {

? ? @Override

? ? public void run() {

? ? ? ? for (int i = 0; i < 10000; i++) {

? ? ? ? ? ? new Thread(new Runnable() {

? ? ? ? ? ? ? ? @Override

? ? ? ? ? ? ? ? public void run() {

? ? ? ? ? ? ? ? ? ? map.put(UUID.randomUUID().toString(), "");

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }, "ftf" + i).start();

? ? ? ? }

? ? }

}, "ftf");

t.start();

t.join();

效率低下的 HashTable 容器

HashTable 容器使用 synchronized 來保證線程安全，但在線程競(jìng)爭(zhēng)激烈的情況下 HashTable 的效率非常低下。因?yàn)楫?dāng)一個(gè)線程訪問 HashTable 的同步方法時(shí)，其他線程訪問 HashTable 的同步方法時(shí)，可能會(huì)進(jìn)入阻塞或輪詢狀態(tài)。如線程 1 使用 put 進(jìn)行添加元素，線程 2 不但不能使用 put 方法添加元素，并且也不能使用 get 方法來獲取元素，所以競(jìng)爭(zhēng)越激烈效率越低。

鎖分段技術(shù)

HashTable 容器在競(jìng)爭(zhēng)激烈的并發(fā)環(huán)境下表現(xiàn)出效率低下的原因是所有訪問 HashTable 的線程都必須競(jìng)爭(zhēng)同一把鎖，那假如容器里有多把鎖，每一把鎖用于鎖容器其中一部分?jǐn)?shù)據(jù)，那么當(dāng)多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)時(shí)，線程間就不會(huì)存在鎖競(jìng)爭(zhēng)，從而可以有效的提高并發(fā)訪問效率，這就是 ConcurrentHashMap 所使用的鎖分段技術(shù)，首先將數(shù)據(jù)分成一段一段的存儲(chǔ)，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問其中一個(gè)段數(shù)據(jù)的時(shí)候，其他段的數(shù)據(jù)也能被其他線程訪問。

ConcurrentHashMap 的結(jié)構(gòu)

我們通過 ConcurrentHashMap 的類圖來分析 ConcurrentHashMap 的結(jié)構(gòu)。

ConcurrentHashMap 是由 Segment 數(shù)組結(jié)構(gòu)和 HashEntry 數(shù)組結(jié)構(gòu)組成。Segment 是一種可重入鎖 ReentrantLock，在 ConcurrentHashMap 里扮演鎖的角色，HashEntry 則用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)。一個(gè) ConcurrentHashMap 里包含一個(gè) Segment 數(shù)組，Segment 的結(jié)構(gòu)和 HashMap 類似，是一種數(shù)組和鏈表結(jié)構(gòu)， 一個(gè) Segment 里包含一個(gè) HashEntry 數(shù)組，每個(gè) HashEntry 是一個(gè)鏈表結(jié)構(gòu)的元素， 每個(gè) Segment 守護(hù)者一個(gè) HashEntry 數(shù)組里的元素, 當(dāng)對(duì) HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須首先獲得它對(duì)應(yīng)的 Segment 鎖。

ConcurrentHashMap 的初始化

ConcurrentHashMap 初始化方法是通過 initialCapacity，loadFactor, concurrencyLevel 幾個(gè)參數(shù)來初始化 segments 數(shù)組，段偏移量 segmentShift，段掩碼 segmentMask 和每個(gè) segment 里的 HashEntry 數(shù)組 。

初始化 segments 數(shù)組。讓我們來看一下初始化 segmentShift，segmentMask 和 segments 數(shù)組的源代碼。

if (concurrencyLevel > MAX_SEGMENTS)

? ? concurrencyLevel = MAX_SEGMENTS;

// Find power-of-two sizes best matching arguments

int sshift = 0;

int ssize = 1;

while (ssize < concurrencyLevel) {

? ? ++sshift;

? ? ssize <<= 1;

}

segmentShift = 32 - sshift;

segmentMask = ssize - 1;

this.segments = Segment.newArray(ssize);

由上面的代碼可知 segments 數(shù)組的長度 ssize 通過 concurrencyLevel 計(jì)算得出。為了能通過按位與的哈希算法來定位 segments 數(shù)組的索引，必須保證 segments 數(shù)組的長度是 2 的 N 次方（power-of-two size），所以必須計(jì)算出一個(gè)是大于或等于 concurrencyLevel 的最小的 2 的 N 次方值來作為 segments 數(shù)組的長度。假如 concurrencyLevel 等于 14，15 或 16，ssize 都會(huì)等于 16，即容器里鎖的個(gè)數(shù)也是 16。注意 concurrencyLevel 的最大大小是 65535，意味著 segments 數(shù)組的長度最大為 65536，對(duì)應(yīng)的二進(jìn)制是 16 位。

初始化 segmentShift 和 segmentMask。這兩個(gè)全局變量在定位 segment 時(shí)的哈希算法里需要使用，sshift 等于 ssize 從 1 向左移位的次數(shù)，在默認(rèn)情況下 concurrencyLevel 等于 16，1 需要向左移位移動(dòng) 4 次，所以 sshift 等于 4。segmentShift 用于定位參與 hash 運(yùn)算的位數(shù)，segmentShift 等于 32 減 sshift，所以等于 28，這里之所以用 32 是因?yàn)?ConcurrentHashMap 里的 hash() 方法輸出的最大數(shù)是 32 位的，后面的測(cè)試中我們可以看到這點(diǎn)。segmentMask 是哈希運(yùn)算的掩碼，等于 ssize 減 1，即 15，掩碼的二進(jìn)制各個(gè)位的值都是 1。因?yàn)?ssize 的最大長度是 65536，所以 segmentShift 最大值是 16，segmentMask 最大值是 65535，對(duì)應(yīng)的二進(jìn)制是 16 位，每個(gè)位都是 1。

初始化每個(gè) Segment。輸入?yún)?shù) initialCapacity 是 ConcurrentHashMap 的初始化容量，loadfactor 是每個(gè) segment 的負(fù)載因子，在構(gòu)造方法里需要通過這兩個(gè)參數(shù)來初始化數(shù)組中的每個(gè) segment。

if (initialCapacity > MAXIMUM_CAPACITY)

? ? initialCapacity = MAXIMUM_CAPACITY;

int c = initialCapacity / ssize;

if (c * ssize < initialCapacity)

? ? ++c;

int cap = 1;

while (cap < c)

? ? cap <<= 1;

for (int i = 0; i < this.segments.length; ++i)

? ? this.segments[i] = new Segment<K,V>(cap, loadFactor);

上面代碼中的變量 cap 就是 segment 里 HashEntry 數(shù)組的長度，它等于 initialCapacity 除以 ssize 的倍數(shù) c，如果 c 大于 1，就會(huì)取大于等于 c 的 2 的 N 次方值，所以 cap 不是 1，就是 2 的 N 次方。segment 的容量 threshold＝(int)cap*loadFactor，默認(rèn)情況下 initialCapacity 等于 16，loadfactor 等于 0.75，通過運(yùn)算 cap 等于 1，threshold 等于零。

定位 Segment

既然 ConcurrentHashMap 使用分段鎖 Segment 來保護(hù)不同段的數(shù)據(jù)，那么在插入和獲取元素的時(shí)候，必須先通過哈希算法定位到 Segment?？梢钥吹?ConcurrentHashMap 會(huì)首先使用 Wang/Jenkins hash 的變種算法對(duì)元素的 hashCode 進(jìn)行一次再哈希。

private static int hash(int h) {

? ? ? ? h += (h << 15) ^ 0xffffcd7d;

? ? ? ? h ^= (h >>> 10);

? ? ? ? h += (h << 3);

? ? ? ? h ^= (h >>> 6);

? ? ? ? h += (h << 2) + (h << 14);

? ? ? ? return h ^ (h >>> 16);

? ? }

之所以進(jìn)行再哈希，其目的是為了減少哈希沖突，使元素能夠均勻的分布在不同的 Segment 上，從而提高容器的存取效率。假如哈希的質(zhì)量差到極點(diǎn)，那么所有的元素都在一個(gè) Segment 中，不僅存取元素緩慢，分段鎖也會(huì)失去意義。我做了一個(gè)測(cè)試，不通過再哈希而直接執(zhí)行哈希計(jì)算。

System.out.println(Integer.parseInt("0001111", 2) & 15);

System.out.println(Integer.parseInt("0011111", 2) & 15);

System.out.println(Integer.parseInt("0111111", 2) & 15);

System.out.println(Integer.parseInt("1111111", 2) & 15);

計(jì)算后輸出的哈希值全是 15，通過這個(gè)例子可以發(fā)現(xiàn)如果不進(jìn)行再哈希，哈希沖突會(huì)非常嚴(yán)重，因?yàn)橹灰臀灰粯?，無論高位是什么數(shù)，其哈希值總是一樣。我們?cè)侔焉厦娴亩M(jìn)制數(shù)據(jù)進(jìn)行再哈希后結(jié)果如下，為了方便閱讀，不足 32 位的高位補(bǔ)了 0，每隔四位用豎線分割下。

0100｜0111｜0110｜0111｜1101｜1010｜0100｜1110

1111｜0111｜0100｜0011｜0000｜0001｜1011｜1000

0111｜0111｜0110｜1001｜0100｜0110｜0011｜1110

1000｜0011｜0000｜0000｜1100｜1000｜0001｜1010

可以發(fā)現(xiàn)每一位的數(shù)據(jù)都散列開了，通過這種再哈希能讓數(shù)字的每一位都能參加到哈希運(yùn)算當(dāng)中，從而減少哈希沖突。ConcurrentHashMap 通過以下哈希算法定位 segment。

final Segment<K,V> segmentFor(int hash) {

? ? ? ? return segments[(hash >>> segmentShift) & segmentMask];

? ? }

默認(rèn)情況下 segmentShift 為 28，segmentMask 為 15，再哈希后的數(shù)最大是 32 位二進(jìn)制數(shù)據(jù)，向右無符號(hào)移動(dòng) 28 位，意思是讓高 4 位參與到 hash 運(yùn)算中， (hash >>> segmentShift) & segmentMask 的運(yùn)算結(jié)果分別是 4，15，7 和 8，可以看到 hash 值沒有發(fā)生沖突。

ConcurrentHashMap 的 get 操作

Segment 的 get 操作實(shí)現(xiàn)非常簡單和高效。先經(jīng)過一次再哈希，然后使用這個(gè)哈希值通過哈希運(yùn)算定位到 segment，再通過哈希算法定位到元素，代碼如下：

public V get(Object key) {

? ? int hash = hash(key.hashCode());

? ? return segmentFor(hash).get(key, hash);

}

get 操作的高效之處在于整個(gè) get 過程不需要加鎖，除非讀到的值是空的才會(huì)加鎖重讀，我們知道 HashTable 容器的 get 方法是需要加鎖的，那么 ConcurrentHashMap 的 get 操作是如何做到不加鎖的呢？原因是它的 get 方法里將要使用的共享變量都定義成 volatile，如用于統(tǒng)計(jì)當(dāng)前 Segement 大小的 count 字段和用于存儲(chǔ)值的 HashEntry 的 value。定義成 volatile 的變量，能夠在線程之間保持可見性，能夠被多線程同時(shí)讀，并且保證不會(huì)讀到過期的值，但是只能被單線程寫（有一種情況可以被多線程寫，就是寫入的值不依賴于原值），在 get 操作里只需要讀不需要寫共享變量 count 和 value，所以可以不用加鎖。之所以不會(huì)讀到過期的值，是根據(jù) java 內(nèi)存模型的 happen before 原則，對(duì) volatile 字段的寫入操作先于讀操作，即使兩個(gè)線程同時(shí)修改和獲取 volatile 變量，get 操作也能拿到最新的值，這是用 volatile 替換鎖的經(jīng)典應(yīng)用場(chǎng)景。

transient volatile int count;

volatile V value;

在定位元素的代碼里我們可以發(fā)現(xiàn)定位 HashEntry 和定位 Segment 的哈希算法雖然一樣，都與數(shù)組的長度減去一相與，但是相與的值不一樣，定位 Segment 使用的是元素的 hashcode 通過再哈希后得到的值的高位，而定位 HashEntry 直接使用的是再哈希后的值。其目的是避免兩次哈希后的值一樣，導(dǎo)致元素雖然在 Segment 里散列開了，但是卻沒有在 HashEntry 里散列開。

hash >>> segmentShift) & segmentMask// 定位 Segment 所使用的 hash 算法

int index = hash & (tab.length - 1);// 定位 HashEntry 所使用的 hash 算法

ConcurrentHashMap 的 Put 操作

由于 put 方法里需要對(duì)共享變量進(jìn)行寫入操作，所以為了線程安全，在操作共享變量時(shí)必須得加鎖。Put 方法首先定位到 Segment，然后在 Segment 里進(jìn)行插入操作。插入操作需要經(jīng)歷兩個(gè)步驟，第一步判斷是否需要對(duì) Segment 里的 HashEntry 數(shù)組進(jìn)行擴(kuò)容，第二步定位添加元素的位置然后放在 HashEntry 數(shù)組里。

是否需要擴(kuò)容。在插入元素前會(huì)先判斷 Segment 里的 HashEntry 數(shù)組是否超過容量（threshold），如果超過閥值，數(shù)組進(jìn)行擴(kuò)容。值得一提的是，Segment 的擴(kuò)容判斷比 HashMap 更恰當(dāng)，因?yàn)?HashMap 是在插入元素后判斷元素是否已經(jīng)到達(dá)容量的，如果到達(dá)了就進(jìn)行擴(kuò)容，但是很有可能擴(kuò)容之后沒有新元素插入，這時(shí) HashMap 就進(jìn)行了一次無效的擴(kuò)容。

如何擴(kuò)容。擴(kuò)容的時(shí)候首先會(huì)創(chuàng)建一個(gè)兩倍于原容量的數(shù)組，然后將原數(shù)組里的元素進(jìn)行再 hash 后插入到新的數(shù)組里。為了高效 ConcurrentHashMap 不會(huì)對(duì)整個(gè)容器進(jìn)行擴(kuò)容，而只對(duì)某個(gè) segment 進(jìn)行擴(kuò)容。

ConcurrentHashMap 的 size 操作

如果我們要統(tǒng)計(jì)整個(gè) ConcurrentHashMap 里元素的大小，就必須統(tǒng)計(jì)所有 Segment 里元素的大小后求和。Segment 里的全局變量 count 是一個(gè) volatile 變量，那么在多線程場(chǎng)景下，我們是不是直接把所有 Segment 的 count 相加就可以得到整個(gè) ConcurrentHashMap 大小了呢？不是的，雖然相加時(shí)可以獲取每個(gè) Segment 的 count 的最新值，但是拿到之后可能累加前使用的 count 發(fā)生了變化，那么統(tǒng)計(jì)結(jié)果就不準(zhǔn)了。所以最安全的做法，是在統(tǒng)計(jì) size 的時(shí)候把所有 Segment 的 put，remove 和 clean 方法全部鎖住，但是這種做法顯然非常低效。 因?yàn)樵诶奂?count 操作過程中，之前累加過的 count 發(fā)生變化的幾率非常小，所以 ConcurrentHashMap 的做法是先嘗試 2 次通過不鎖住 Segment 的方式來統(tǒng)計(jì)各個(gè) Segment 大小，如果統(tǒng)計(jì)的過程中，容器的 count 發(fā)生了變化，則再采用加鎖的方式來統(tǒng)計(jì)所有 Segment 的大小。

那么 ConcurrentHashMap 是如何判斷在統(tǒng)計(jì)的時(shí)候容器是否發(fā)生了變化呢？使用 modCount 變量，在 put , remove 和 clean 方法里操作元素前都會(huì)將變量 modCount 進(jìn)行加 1，那么在統(tǒng)計(jì) size 前后比較 modCount 是否發(fā)生變化，從而得知容器的大小是否發(fā)生變化。

參考資料

JDK1.6 源代碼。

《Java 并發(fā)編程實(shí)踐》。