速讀原著-深入分析 ConcurrentHashMap

• 2020 年 2 月 14 日
• 筆記

深入分析 ConcurrentHashMap

術語定義

執行緒不安全的HashMap

因為多執行緒環境下，使用 HashMap 進行 put 操作會引起死循環，導致 CPU 利用率接近 100%， 所以在並發情況下不能使用 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();                }            }          t.start();            t.join();

效率低下的HashTable 容器

HashTable 容器使用 synchronized 來保證執行緒安全，但在執行緒競爭激烈的情況下 HashTable 的效率非常低下。因為當一個執行緒訪問HashTable 的同步方法時，其他執行緒訪問HashTable 的同步方法時，可能會進入阻塞或輪詢狀態。如執行緒 1 使用 put 進行添加元素，執行緒 2 不但不能使用 put 方法添加元素，並且也不能使用 get 方法來獲取元素，所以競爭越激烈效率越低。

鎖分段技術

HashTable 容器在競爭激烈的並發環境下表現出效率低下的原因是所有訪問 HashTable 的執行緒都必須競爭同一把鎖，那假如容器里有多把鎖，每一把鎖用於鎖容器其中一部分數據，那麼當多執行緒訪問容器里不同數據段的數據時，執行緒間就不會存在鎖競爭，從而可以有效的提高並發訪問效率，這就是 ConcurrentHashMap 所使用的鎖分段技術，首先將數據分成一段一段的存儲， 然後給每一段數據配一把鎖，當一個執行緒佔用鎖訪問其中一個段數據的時候，其他段的數據也能被其他執行緒訪問。

ConcurrentHashMap 的結構

我們通過ConcurrentHashMap 的類圖來分析ConcurrentHashMap 的結構。

ConcurrentHashMap 是由 Segment 數組結構和 HashEntry 數組結構組成。Segment 是一種可重入鎖ReentrantLock，在ConcurrentHashMap 里扮演鎖的角色，HashEntry 則用於存儲鍵值對數據。一個 ConcurrentHashMap 里包含一個 Segment 數組，Segment 的結構和 HashMap 類似，是一種數組和鏈表結構， 一個Segment 里包含一個HashEntry 數組，每個HashEntry 是一個鏈表結構的元素， 每個 Segment 守護者一個 HashEntry 數組裡的元素,當對 HashEntry 數組的數據進行修改時，必須首先獲得它對應的 Segment 鎖。

ConcurrentHashMap 的初始化

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

初始化segments 數組。讓我們來看一下初始化segmentShift，segmentMask 和segments 數組的源程式碼。

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

初始化 segmentShift 和 segmentMask。這兩個全局變數在定位 segment 時的哈希演算法里需要使用， sshift 等於 ssize 從 1 向左移位的次數，在默認情況下 concurrencyLevel 等於 16，1 需要向左移位 移動 4 次，所以sshift 等於 4。segmentShift 用於定位參與hash 運算的位數，segmentShift 等於 32 減sshift，所以等於 28，這裡之所以用 32 是因為ConcurrentHashMap 里的 hash()方法輸出的最大數是 32 位的，後面的測試中我們可以看到這點。segmentMask 是哈希運算的掩碼，等於ssize 減1，即 15，掩碼的二進位各個位的值都是 1。因為 ssize 的最大長度是 65536，所以 segmentShift 最大值是 16，segmentMask 最大值是 65535，對應的二進位是 16 位，每個位都是 1。

初始化每個 Segment。輸入參數 initialCapacity 是 ConcurrentHashMap 的初始化容量，loadfactor 是每個 segment 的負載因子，在構造方法里需要通過這兩個參數來初始化數組中的每個 segment

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

定位Segment

既然 ConcurrentHashMap 使用分段鎖 Segment 來保護不同段的數據，那麼在插入和獲取元素的時候， 必須先通過哈希演算法定位到 Segment。可以看到 ConcurrentHashMap 會首先使用Wang/Jenkins hash 的變種演算法對元素的 hashCode 進行一次再哈希

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

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

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

計算後輸出的哈希值全是 15，通過這個例子可以發現如果不進行再哈希，哈希衝突會非常嚴重， 因為只要低位一樣，無論高位是什麼數，其哈希值總是一樣。我們再把上面的二進位數據進行 再哈希後結果如下，為了方便閱讀，不足 32 位的高位補了 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

可以發現每一位的數據都散列開了，通過這種再哈希能讓數字的每一位都能參加到哈希運算當中，從而減少哈希衝突。ConcurrentHashMap 通過以下哈希演算法定位 segment。

默認情況下 segmentShift 為 28，segmentMask 為 15，再哈希後的數最大是 32 位二進位數據，向右無符號移動 28 位， 意思是讓高 4 位參與到 hash 運算中， (hash >>> segmentShift) & segmentMask 的運算結果分別是 4，15，7 和 8，可以看到 hash 值沒有發生衝突。

ConcurrentHashMap 的get 操作

Segment 的 get 操作實現非常簡單和高效。先經過一次再哈希，然後使用這個哈希值通過哈希運算定位到 segment，再通過哈希演算法定位到元素，程式碼如下：

public V get(Object key) {          int hash = hash(key.hashCode());          return segmentFor(hash).get(key, hash);      }

get 操作的高效之處在於整個 get 過程不需要加鎖，除非讀到的值是空的才會加鎖重讀，我們知道 HashTable 容器的 get 方法是需要加鎖的，那麼 ConcurrentHashMap 的 get 操作是如何做到不加鎖的呢？原因是它的 get 方法里將要使用的共享變數都定義成 volatile，如用於統計當前Segement 大小的 count 欄位和用於存儲值的HashEntry 的 value。定義成 volatile 的變數，能夠在執行緒之間保持可見性，能夠被多執行緒同時讀，並且保證不會讀到過期的值，但是只能被單執行緒寫（有一種情況可以被多執行緒寫，就是寫入的值不依賴於原值），在 get 操作里只需要讀不需要寫共享變數 count 和 value，所以可以不用加鎖。之所以不會讀到過期的值，是根據 java 記憶體模型的happen before 原則，對volatile 欄位的寫入操作先於讀操作，即使兩個執行緒同時修改和獲取 volatile 變數，get 操作也能拿到最新的值，這是用 volatile 替換鎖的經典應用場景。

transient volatile int count;    volatile V value;

在定位元素的程式碼里我們可以發現定位HashEntry 和定位Segment 的哈希演算法雖然一樣，都與數組的長度減去一相與，但是相與的值不一樣，定位 Segment 使用的是元素的 hashcode 通過再哈希後得到的值的高位，而定位 HashEntry 直接使用的是再哈希後的值。其目的是避免兩次哈希後的值一樣，導致元素雖然在 Segment 里散列開了，但是卻沒有在 HashEntry 里散列開。

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

ConcurrentHashMap 的Put 操作

由於 put 方法里需要對共享變數進行寫入操作，所以為了執行緒安全，在操作共享變數時必須得加鎖。Put 方法首先定位到 Segment，然後在 Segment 里進行插入操作。插入操作需要經歷兩個步驟，第一步判斷是否需要對Segment 里的HashEntry 數組進行擴容，第二步定位添加元素的位置然後放在HashEntry 數組裡。

是否需要擴容。在插入元素前會先判斷 Segment 里的 HashEntry 數組是否超過容量（threshold）， 如果超過閥值，數組進行擴容。值得一提的是，Segment 的擴容判斷比 HashMap 更恰當，因為HashMap 是在插入元素後判斷元素是否已經到達容量的，如果到達了就進行擴容，但是很有可 能擴容之後沒有新元素插入，這時HashMap 就進行了一次無效的擴容。

如何擴容。擴容的時候首先會創建一個兩倍於原容量的數組，然後將原數組裡的元素進行再hash 後插入到新的數組裡。為了高效 ConcurrentHashMap 不會對整個容器進行擴容，而只對某個 segment 進行擴容。

ConcurrentHashMap 的size 操作

如果我們要統計整個 ConcurrentHashMap 里元素的大小，就必須統計所有 Segment 里元素的大小後求和。Segment 里的全局變數 count 是一個 volatile 變數，那麼在多執行緒場景下，我們是不是直接把所有Segment 的 count 相加就可以得到整個ConcurrentHashMap 大小了呢？不是的，雖然相加時可以獲取每個 Segment 的 count 的最新值，但是拿到之後可能累加前使用的 count 發生了變化，那麼統計結果就不準了。所以最安全的做法，是在統計 size 的時候把所有 Segment 的put，remove 和 clean 方法全部鎖住，但是這種做法顯然非常低效。 因為在累加 count 操作過程中，之前累加過的count 發生變化的幾率非常小，所以 ConcurrentHashMap 的做法是先嘗試 2 次通過不鎖住Segment 的方式來統計各個Segment 大小，如果統計的過程中，容器的count 發生了變化，則再採用加鎖的方式來統計所有 Segment 的大小。

那麼ConcurrentHashMap 是如何判斷在統計的時候容器是否發生了變化呢？使用modCount 變數， 在 put , remove 和 clean 方法里操作元素前都會將變數 modCount 進行加 1，那麼在統計 size 前後比較 modCount 是否發生變化，從而得知容器的大小是否發生變化。