一、概念

哈希算法（hash algorithm）：是一種將任意內容的輸入轉換成相同長度輸出的加密方式，其輸出被稱為哈希值。

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

二、HashMap與HashTable1，線程不安全的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() {@Overridepublic void run() { map.put(UUID.randomUUID().toString(), '');} }, 'ftf' + i).start();} }}, 'ftf');t.start();t.join();2，效率低下的HashTable容器

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

三、ConcurrentHashMap1，鎖分段技術

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

2，ConcurrentHashMap的結構

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

3，ConcurrentHashMap的初始化

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

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

if (concurrencyLevel > MAX_SEGMENTS) concurrencyLevel = MAX_SEGMENTS;// Find power-of-two sizes best matching argumentsint sshift = 0;int ssize = 1;while (ssize < concurrencyLevel) { ++sshift; ssize <<= 1;}segmentShift = 32 - sshift;segmentMask = ssize - 1;this.segments = Segment.newArray(ssize);

由上面的代碼可知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。

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數組的長度，它等于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等于零。

4，定位Segment

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

rivate 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中，不僅存取元素緩慢，分段鎖也會失去意義。我做了一個測試，不通過再哈希而直接執行哈希計算。

1 System.out.println(Integer.parseInt('0001111', 2) & 15);2 System.out.println(Integer.parseInt('0011111', 2) & 15);3 System.out.println(Integer.parseInt('0111111', 2) & 15);4 System.out.println(Integer.parseInt('1111111', 2) & 15);

計算后輸出的哈希值全是15，通過這個例子可以發現如果不進行再哈希，哈希沖突會非常嚴重，因為只要低位一樣，無論高位是什么數，其哈希值總是一樣。我們再把上面的二進制數據進行再哈希后結果如下，為了方便閱讀，不足32位的高位補了0，每隔四位用豎線分割下。

1 0100｜0111｜0110｜0111｜1101｜1010｜0100｜11102 1111｜0111｜0100｜0011｜0000｜0001｜1011｜10003 0111｜0111｜0110｜1001｜0100｜0110｜0011｜11104 1000｜0011｜0000｜0000｜1100｜1000｜0001｜1010

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

1 final Segment<K,V> segmentFor(int hash) {2 return segments[(hash >>> segmentShift) & segmentMask];3 }

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

5，ConcurrentHashMap的get操作

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

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

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

1 transient volatile int count;2 volatile V value;

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

1 hash >>> segmentShift) & segmentMask//定位Segment所使用的hash算法2 int index = hash & (tab.length - 1);// 定位HashEntry所使用的hash算法6，ConcurrentHashMap的Put操作

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

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

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

7，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是否發生變化，從而得知容器的大小是否發生變化。

到此這篇關于Java ConcurrentHashMap用法案例詳解的文章就介紹到這了,更多相關Java ConcurrentHashMap講解內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！