術(shù)語(yǔ)定義

術(shù)語(yǔ)英文解釋

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

哈希表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 來(lái)保證線程安全茸俭，但在線程競(jìng)爭(zhēng)激烈的情況下 HashTable 的效率非常低下吊履。因?yàn)楫?dāng)一個(gè)線程訪問(wèn) HashTable 的同步方法時(shí)，其他線程訪問(wèn) HashTable 的同步方法時(shí)调鬓，可能會(huì)進(jìn)入阻塞或輪詢狀態(tài)艇炎。如線程 1 使用 put 進(jìn)行添加元素，線程 2 不但不能使用 put 方法添加元素腾窝，并且也不能使用 get 方法來(lái)獲取元素缀踪，所以競(jìng)爭(zhēng)越激烈效率越低居砖。

鎖分段技術(shù)

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

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

我們通過(guò) ConcurrentHashMap 的類圖來(lái)分析 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 初始化方法是通過(guò) initialCapacity灭返，loadFactor, concurrencyLevel 幾個(gè)參數(shù)來(lái)初始化 segments 數(shù)組，段偏移量 segmentShift坤邪，段掩碼 segmentMask 和每個(gè) segment 里的 HashEntry 數(shù)組 熙含。

初始化 segments 數(shù)組。讓我們來(lái)看一下初始化 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ù)組的長(zhǎng)度 ssize 通過(guò) concurrencyLevel 計(jì)算得出。為了能通過(guò)按位與的哈希算法來(lái)定位 segments 數(shù)組的索引黔衡，必須保證 segments 數(shù)組的長(zhǎng)度是 2 的 N 次方（power-of-two size）蚓聘，所以必須計(jì)算出一個(gè)是大于或等于 concurrencyLevel 的最小的 2 的 N 次方值來(lái)作為 segments 數(shù)組的長(zhǎng)度。假如 concurrencyLevel 等于 14盟劫，15 或 16夜牡，ssize 都會(huì)等于 16，即容器里鎖的個(gè)數(shù)也是 16捞高。注意 concurrencyLevel 的最大大小是 65535氯材，意味著 segments 數(shù)組的長(zhǎng)度最大為 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 的最大長(zhǎng)度是 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)造方法里需要通過(guò)這兩個(gè)參數(shù)來(lái)初始化數(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ù)組的長(zhǎng)度剩胁，它等于 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壁查，通過(guò)運(yùn)算 cap 等于 1觉至，threshold 等于零。

定位 Segment

既然 ConcurrentHashMap 使用分段鎖 Segment 來(lái)保護(hù)不同段的數(shù)據(jù)睡腿，那么在插入和獲取元素的時(shí)候语御，必須先通過(guò)哈希算法定位到 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è)試态贤，不通過(guò)再哈希而直接執(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，通過(guò)這個(gè)例子可以發(fā)現(xiàn)如果不進(jìn)行再哈希悠汽，哈希沖突會(huì)非常嚴(yán)重箱吕，因?yàn)橹灰臀灰粯樱瑹o(wú)論高位是什么數(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ù)都散列開(kāi)了慨亲，通過(guò)這種再哈希能讓數(shù)字的每一位都能參加到哈希運(yùn)算當(dāng)中婚瓜，從而減少哈希沖突。ConcurrentHashMap 通過(guò)以下哈希算法定位 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ù)蛉签，向右無(wú)符號(hào)移動(dòng) 28 位胡陪，意思是讓高 4 位參與到 hash 運(yùn)算中， (hash >>> segmentShift) & segmentMask 的運(yùn)算結(jié)果分別是 4碍舍，15柠座，7 和 8，可以看到 hash 值沒(méi)有發(fā)生沖突片橡。

ConcurrentHashMap 的 get 操作

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

public V get(Object key) {

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

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

}

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

transient volatile int count;

volatile V value;

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

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

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

ConcurrentHashMap 的 Put 操作

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

是否需要擴(kuò)容。在插入元素前會(huì)先判斷 Segment 里的 HashEntry 數(shù)組是否超過(guò)容量（threshold），如果超過(guò)閥值俏蛮，數(shù)組進(jìn)行擴(kuò)容撑蚌。值得一提的是，Segment 的擴(kuò)容判斷比 HashMap 更恰當(dāng)搏屑，因?yàn)?HashMap 是在插入元素后判斷元素是否已經(jīng)到達(dá)容量的争涌，如果到達(dá)了就進(jìn)行擴(kuò)容，但是很有可能擴(kuò)容之后沒(méi)有新元素插入辣恋，這時(shí) HashMap 就進(jìn)行了一次無(wú)效的擴(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 操作過(guò)程中，之前累加過(guò)的 count 發(fā)生變化的幾率非常小汽摹，所以 ConcurrentHashMap 的做法是先嘗試 2 次通過(guò)不鎖住 Segment 的方式來(lái)統(tǒng)計(jì)各個(gè) Segment 大小李丰，如果統(tǒng)計(jì)的過(guò)程中，容器的 count 發(fā)生了變化逼泣，則再采用加鎖的方式來(lái)統(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í)踐》。