我們知道哈希表是一種非常高效的數據結構，設計優良的哈希函數可以使其上的增刪改查操作達到O(1)級別。 Java為我們提供了一個現成的哈希結構，那就是HashMap類，在前面的文章中我曾經介紹過HashMap類，知道它的所有方法都未進行同步，因此在多線程環境中是不安全的。為此，Java為我們提供了另外一個HashTable類，它對於多線程同步的處理非常簡單粗暴，那就是在HashMap的基礎上對其所有方法都使用synchronized關鍵字進行加鎖。這種方法雖然簡單，但導致了一個問題，那就是在同一時間內只能由一個線程去操作哈希表。即使這些線程都只是進行讀操作也必須要排隊，這在競爭激烈的多線程環境中極為影響性能。本篇介紹的ConcurrentHashMap就是為了解決這個問題的，它的內部使用分段鎖將鎖進行細粒度化，從而使得多個線程能夠同時操作哈希表，這樣極大的提高了性能。下圖是其內部結構的示意圖。
1. ConcurrentHashMap有哪些成員變量？
//默認初始化容量static final int DEFAULT_INITIAL_CAPACITY = 16;//默認加載因子static final float DEFAULT_LOAD_FACTOR = 0.75f;//默認並發級別static final int DEFAULT_CONCURRENCY_LEVEL = 16;//集合最大容量static final int MAXIMUM_CAPACITY = 1 << 30;//分段鎖的最小數量static final int MIN_SEGMENT_TABLE_CAPACITY = 2;//分段鎖的最大數量static final int MAX_SEGMENTS = 1 << 16;//加鎖前的重試次數static final int RETRIES_BEFORE_LOCK = 2;//分段鎖的掩碼值final int segmentMask;//分段鎖的移位值final int segmentShift;//分段鎖數組final Segment<K,V>[] segments;
在閱讀完本篇文章之前，相信讀者不能理解這些成員變量的具體含義和作用，不過請讀者們耐心看下去，後面將會在具體場景中一一介紹到這些成員變量的作用。在這裡讀者只需對這些成員變量留個眼熟即可。但是仍有個別變量是我們現在需要了解的，例如Segment數組代表分段鎖集合，並發級別則代表分段鎖的數量(也意味有多少線程可以同時操作)，初始化容量代表整個容器的容量，加載因子代表容器元素可以達到多滿的一種程度。
2. 分段鎖的內部結構是怎樣的？
//分段鎖static final class Segment<K,V> extends ReentrantLock implements Serializable { //自旋最大次數static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1; //哈希表transient volatile HashEntry<K,V>[] table; //元素總數transient int count; //修改次數transient int modCount; //元素閥值transient int threshold; //加載因子final float loadFactor; //省略以下內容...}Segment是ConcurrentHashMap的靜態內部類，可以看到它繼承自ReentrantLock，因此它在本質上是一個鎖。它在內部持有一個HashEntry數組(哈希表)，並且保證所有對該數組的增刪改查方法都是線程安全的，具體是怎樣實現的後面會講到。所有對ConcurrentHashMap的增刪改查操作都可以委託Segment來進行，因此ConcurrentHashMap能夠保證在多線程環境下是安全的。又因為不同的Segment是不同的鎖，所以多線程可以同時操作不同的Segment，也就意味著多線程可以同時操作ConcurrentHashMap，這樣就能避免HashTable的缺陷，從而極大的提高性能。
3. ConcurrentHashMap初始化時做了些什麼？
//核心構造器@SuppressWarnings("unchecked")public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) { throw new IllegalArgumentException(); } //確保並發級別不大於限定值if (concurrencyLevel > MAX_SEGMENTS) { concurrencyLevel = MAX_SEGMENTS; } int sshift = 0; int ssize = 1; //保證ssize為2的冪, 且是最接近的大於等於並發級別的數while (ssize < concurrencyLevel) { ++sshift; ssize <<= 1; } //計算分段鎖的移位值this.segmentShift = 32 - sshift; //計算分段鎖的掩碼值this.segmentMask = ssize - 1; //總的初始容量不能大於限定值if (initialCapacity > MAXIMUM_CAPACITY) { initialCapacity = MAXIMUM_CAPACITY; } //獲取每個分段鎖的初始容量int c = initialCapacity / ssize; //分段鎖容量總和不小於初始總容量if (c * ssize < initialCapacity) { ++c; } int cap = MIN_SEGMENT_TABLE_CAPACITY; //保證cap為2的冪, 且是最接近的大於等於c的數while (cap < c) { cap <<= 1; } //新建一個Segment對像模版Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor), (HashEntry<K,V>[])new HashEntry[cap]); //新建指定大小的分段鎖數組Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize]; //使用UnSafe給數組第0個元素賦值UNSAFE.putOrderedObject(ss, SBASE, s0); this.segments = ss;}ConcurrentHashMap有多個構造器，但是上面貼出的是它的核心構造器，其他構造器都通過調用它來完成初始化。核心構造器需要傳入三個參數，分別是初始容量，加載因子和並發級別。在前面介紹成員變量時我們可以知道默認的初始容量為16，加載因子為0.75f，並發級別為16。現在我們看到核心構造器的代碼，首先是通過傳入的concurrencyLevel來計算出ssize，ssize是Segment數組的長度，它必須保證是2的冪，這樣就可以通過hash&ssize-1來計算分段鎖在數組中的下標。由於傳入的concurrencyLevel不能保證是2的冪，所以不能直接用它來當作Segment數組的長度，因此我們要找到一個最接近concurrencyLevel的2的冪，用它來作為數組的長度。假如現在傳入的concurrencyLevel=15，通過上面代碼可以計算出ssize=16，sshift=4。接下來立馬可以算出segmentShift=16，segmentMask=15。注意這裡的segmentShift是分段鎖的移位值，segmentMask是分段鎖的掩碼值，這兩個值是用來計算分段鎖在數組中的下標，在下面我們會講到。在算出分段鎖的個數ssize之後，就可以根據傳入的總容量來計算每個分段鎖的容量，它的值c = initialCapacity / ssize。分段鎖的容量也就是HashEntry數組的長度，同樣也必須保證是2的冪，而上面算出的c的值不能保證這一點，所以不能直接用c作為HashEntry數組的長度，需要另外找到一個最接近c的2的冪，將這個值賦給cap，然後用cap來作為HashEntry數組的長度。現在我們有了ssize和cap，就可以新建分段鎖數組Segment[]和元素數組HashEntry[]了。注意，與JDK1.6不同是的，在JDK1.7中只新建了Segment數組，並沒有對它初始化，初始化Segment的操作留到了插入操作時進行。
4. 通過怎樣的方式來定位鎖和定位元素？
//根據哈希碼獲取分段鎖@SuppressWarnings("unchecked")private Segment<K,V> segmentForHash(int h) { long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);}//根據哈希碼獲取元素@SuppressWarnings("unchecked")static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) { HashEntry<K,V>[] tab; return (seg == null || (tab = seg.table) == null) ? null : (HashEntry<K,V>) UNSAFE.getObjectVolatile(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);}在JDK1.7中是通過UnSafe來獲取數組元素的，因此這裡比JDK1.6多了些計算數組元素偏移量的代碼，這些代碼我們暫時不關注，現在我們只需知道下面這兩點：
a. 通過哈希碼計算分段鎖在數組中的下標：(h >>> segmentShift) & segmentMask。
b. 通過哈希碼計算元素在數組中的下標：(tab.length - 1) & h。
現在我們假設傳給構造器的兩個參數為initialCapacity=128, concurrencyLevel=16。根據計算可以得到ssize=16, sshift=4，segmentShift=28，segmentMask=15。同樣，算得每個分段鎖內的HashEntry數組的長度為8，所以tab.length-1=7。根據這些值，我們通過下圖來解釋如何根據同一個哈希碼來定位分段鎖和元素。
可以看到分段鎖和元素的定位都是通過元素的哈希碼來決定的。定位分段鎖是取哈希碼的高位值(從32位處取起)，定位元素是取的哈希碼的低位值。現在有個問題，它們一個從32位的左端取起，一個從32位的右端取起，那麼會在某個時刻產生衝突嗎？我們在成員變量裡可以找到MAXIMUM_CAPACITY = 1 << 30，MAX_SEGMENTS = 1 << 16，這說明定位分段鎖和定位元素使用的總的位數不超過30，並且定位分段鎖使用的位數不超過16，所以至少還隔著2位的空餘，因此是不會產生衝突的。
5. 查找元素具體是怎樣實現的？
//根據key獲取valuepublic V get(Object key) { Segment<K,V> s; HashEntry<K,V>[] tab; //使用哈希函數計算哈希碼int h = hash(key); //根據哈希碼計算分段鎖的索引long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; //獲取分段鎖和對應的哈希表if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) { //根據哈希碼獲取鍊錶頭結點, 再對鍊錶進行遍歷for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); e != null; e = e.next) { K k; //根據key和hash找到對應元素後返回value值if ((k = e.key) == key || (e.hash == h && key.equals(k))) { return e.value; } } } return null;}在JDK1.6中分段鎖的get方法是通過下標來訪問數組元素的，而在JDK1.7中是通過UnSafe的getObjectVolatile方法來讀取數組中的元素。為啥要這樣做？我們知道雖然Segment對象持有的HashEntry數組引用是volatile類型的，但是數組內的元素引用不是volatile類型的，因此多線程對數組元素的修改是不安全的，可能會在數組中讀取到尚未構造完成的對象。在JDK1.6中是通過第二次加鎖讀取來保證安全的，而JDK1.7中通過UnSafe的getObjectVolatile方法來讀取同樣也是為了保證這一點。使用getObjectVolatile方法讀取數組元素需要先獲得元素在數組中的偏移量，在這裡根據哈希碼計算得到分段鎖在數組中的偏移量為u，然後通過偏移量u來嘗試讀取分段鎖。由於分段鎖數組在構造時沒進行初始化，因此可能讀出來一個空值，所以需要先進行判斷。在確定分段鎖和它內部的哈希表都不為空之後，再通過哈希碼讀取HashEntry數組的元素，根據上面的結構圖可以看到，這時獲得的是鍊錶的頭結點。之後再從頭到尾的對鍊錶進行遍歷查找，如果找到對應的值就將其返回，否則就返回null。以上就是整個查找元素的過程。
6. 插入元素具體是怎樣實現的？
//向集合添加鍵值對(若存在則替換)@SuppressWarnings("unchecked")public V put(K key, V value) { Segment<K,V> s; //傳入的value不能為空if (value == null) throw new NullPointerException(); //使用哈希函數計算哈希碼int hash = hash(key); //根據哈希碼計算分段鎖的下標int j = (hash >>> segmentShift) & segmentMask; //根據下標去嘗試獲取分段鎖if ((s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) { //獲得的分段鎖為空就去構造一個s = ensureSegment(j); } //調用分段鎖的put方法return s.put(key, hash, value, false);}//向集合添加鍵值對(不存在才添加)@SuppressWarnings("unchecked")public V putIfAbsent(K key, V value) { Segment<K,V> s; //傳入的value不能為空if (value == null) throw new NullPointerException(); //使用哈希函數計算哈希碼int hash = hash(key); //根據哈希碼計算分段鎖的下標int j = (hash >>> segmentShift) & segmentMask; //根據下標去嘗試獲取分段鎖if ((s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) { //獲得的分段鎖為空就去構造一個s = ensureSegment(j); } //調用分段鎖的put方法return s.put(key, hash, value, true);}ConcurrentHashMap中有兩個添加鍵值對的方法，通過put方法添加時如果存在則會進行覆蓋，通過putIfAbsent方法添加時如果存在則不進行覆蓋，這兩個方法都是調用分段鎖的put方法來完成操作，只是傳入的最後一個參數不同而已。在上面代碼中我們可以看到首先是根據key的哈希碼來計算出分段鎖在數組中的下標，然後根據下標使用UnSafe類getObject方法來讀取分段鎖。由於在構造ConcurrentHashMap時沒有對Segment數組中的元素初始化，所以可能讀到一個空值，這時會先通過ensureSegment方法新建一個分段鎖。獲取到分段鎖之後再調用它的put方法完成添加操作，下面我們來看看具體是怎樣操作的。
//添加鍵值對final V put(K key, int hash, V value, boolean onlyIfAbsent) { //嘗試獲取鎖, 若失敗則進行自旋HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); V oldValue; try { HashEntry<K,V>[] tab = table; //計算元素在數組中的下標int index = (tab.length - 1) & hash; //根據下標獲取鍊錶頭結點HashEntry<K,V> first = entryAt(tab, index); for (HashEntry<K,V> e = first;;) { //遍歷鍊錶尋找該元素, 找到則進行替換if (e != null) { K k; if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { oldValue = e.value; //根據參數決定是否替換舊值if (!onlyIfAbsent) { e.value = value; ++modCount; } break; } e = e.next; //沒找到則在鍊錶添加一個結點} else { //將node結點插入鍊錶頭部if (node != null) { node.setNext(first); } else { node = new HashEntry<K,V>(hash, key, value, first); } //插入結點後將元素總是加1 int c = count + 1; //元素超過閥值則進行擴容if (c > threshold && tab.length < MAXIMUM_CAPACITY) { rehash(node); //否則就將哈希表指定下標替換為node結點} else { setEntryAt(tab, index, node); } ++modCount; count = c; oldValue = null; break; } } } finally { unlock(); } return oldValue;}為保證線程安全，分段鎖中的put操作是需要進行加鎖的，所以線程一開始就會去獲取鎖，如果獲取成功就繼續執行，若獲取失敗則調用scanAndLockForPut方法進行自旋，在自旋過程中會先去掃描哈希表去查找指定的key，如果key不存在就會新建一個HashEntry返回，這樣在獲取到鎖之後就不必再去新建了，為的是在等待鎖的過程中順便做些事情，不至於白白浪費時間，可見作者的良苦用心。具體自旋方法我們後面再細講，現在先把關注點拉回來，線程在成功獲取到鎖之後會根據計算到的下標，獲取指定下標的元素。此時獲取到的是鍊錶的頭結點，如果頭結點不為空就對鍊錶進行遍歷查找，找到之後再根據onlyIfAbsent參數的值決定是否進行替換。如果遍歷沒找到就會新建一個HashEntry指向頭結點，此時如果自旋時創建了HashEntry，則直接將它的next指向當前頭結點，如果自旋時沒有創建就在這里新建一個HashEntry並指向頭結點。在向鍊錶添加元素之後檢查元素總數是否超過閥值，如果超過就調用rehash進行擴容，沒超過的話就直接將數組對應下標的元素引用指向新添加的node。 setEntryAt方法內部是通過調用UnSafe的putOrderedObject方法來更改數組元素引用的，這樣就保證了其他線程在讀取時可以讀到最新的值。
7. 刪除元素具體是怎樣實現的？
//刪除指定元素(找到對應元素後直接刪除)public V remove(Object key) { //使用哈希函數計算哈希碼int hash = hash(key); //根據哈希碼獲取分段鎖的索引Segment<K,V> s = segmentForHash(hash); //調用分段鎖的remove方法return s == null ? null : s.remove(key, hash, null);}//刪除指定元素(查找值等於給定值才刪除)public boolean remove(Object key, Object value) { //使用哈希函數計算哈希碼int hash = hash(key); Segment<K,V> s; //確保分段鎖不為空才調用remove方法return value != null && (s = segmentForHash(hash)) != null && s.remove(key, hash, value) != null;}ConcurrentHashMap提供了兩種刪除操作，一種是找到後直接刪除，一種是找到後先比較再刪除。這兩種刪除方法都是先根據key的哈希碼找到對應的分段鎖後，再通過調用分段鎖的remove方法完成刪除操作。下面我們來看看分段鎖的remove方法。
//刪除指定元素final V remove(Object key, int hash, Object value) { //嘗試獲取鎖, 若失敗則進行自旋if (!tryLock()) { scanAndLock(key, hash); } V oldValue = null; try { HashEntry<K,V>[] tab = table; //計算元素在數組中的下標int index = (tab.length - 1) & hash; //根據下標取得數組元素(鍊錶頭結點) HashEntry<K,V> e = entryAt(tab, index); HashEntry<K,V> pred = null; //遍歷鍊錶尋找要刪除的元素while (e != null) { K k; //next指向當前結點的後繼結點HashEntry<K,V> next = e.next; //根據key和hash尋找對應結點if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { V v = e.value; //傳入的value不等於v就跳過, 其他情況就進行刪除操作if (value == null || value == v || value.equals(v)) { //如果pred為空則代表要刪除的結點為頭結點if (pred == null) { //重新設置鍊錶頭結點setEntryAt(tab, index, next); } else { //設置pred結點的後繼為next結點pred.setNext(next); } ++modCount; --count; //記錄元素刪除之前的值oldValue = v; } break; } //若e不是要找的結點就將pred引用指向它pred = e; //檢查下一個結點e = next; } } finally { unlock(); } return oldValue;}在刪除分段鎖中的元素時需要先獲取鎖，如果獲取失敗就調用scanAndLock方法進行自旋，如果獲取成功就執行下一步，首先計算數組下標然後通過下標獲取HashEntry數組的元素，這裡獲得了鍊錶的頭結點，接下來就是對鍊錶進行遍歷查找，在此之前先用next指針記錄當前結點的後繼結點，然後對比key和hash看看是否是要找的結點，如果是的話就執行下一個if判斷。滿足value為空或者value的值等於結點當前值這兩個條件就會進入到if語句中進行刪除操作，否則直接跳過。在if語句中執行刪除操作時會有兩種情況，如果當前結點為頭結點則直接將next結點設置為頭結點，如果當前結點不是頭結點則將pred結點的後繼設置為next結點。這裡的pred結點表示當前結點的前繼結點，每次在要檢查下一個結點之前就將pred指向當前結點，這就保證了pred結點總是當前結點的前繼結點。注意，與JDK1.6不同，在JDK1.7中HashEntry對象的next變量不是final的，因此這裡可以通過直接修改next引用的值來刪除元素，由於next變量是volatile類型的，所以讀線程可以馬上讀到最新的值。
8. 替換元素具體是怎樣實現的？
//替換指定元素(CAS操作)public boolean replace(K key, V oldValue, V newValue) { //使用哈希函數計算哈希碼int hash = hash(key); //保證oldValue和newValue不為空if (oldValue == null || newValue == null) throw new NullPointerException(); //根據哈希碼獲取分段鎖的索引Segment<K,V> s = segmentForHash(hash); //調用分段鎖的replace方法return s != null && s.replace(key, hash, oldValue, newValue);}//替換元素操作(CAS操作)final boolean replace(K key, int hash, V oldValue, V newValue) { //嘗試獲取鎖, 若失敗則進行自旋if (!tryLock()) { scanAndLock(key, hash); } boolean replaced = false; try { HashEntry<K,V> e; //通過hash直接找到頭結點然後對鍊錶遍歷for (e = entryForHash(this, hash); e != null; e = e.next) { K k; //根據key和hash找到要替換的結點if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { //如果指定的當前值正確則進行替換if (oldValue.equals(e.value)) { e.value = newValue; ++modCount; replaced = true; } //否則不進行任何操作直接返回break; } } } finally { unlock(); } return replaced;}ConcurrentHashMap同樣提供了兩種替換操作，一種是找到後直接替換，另一種是找到後先比較再替換(CAS操作)。這兩種操作的實現大致是相同的，只是CAS操作在替換前多了一層比較操作，因此我們只需簡單了解其中一種操作即可。這裡拿CAS操作進行分析，還是老套路，首先根據key的哈希碼找到對應的分段鎖，然後調用它的replace方法。進入分段鎖中的replace方法後需要先去獲取鎖，如果獲取失敗則進行自旋，如果獲取成功則進行下一步。首先根據hash碼獲取鍊錶頭結點，然後根據key和hash進行遍歷查找，找到了對應的元素之後，比較給定的oldValue是否是當前值，如果不是則放棄修改，如果是則用新值進行替換。由於HashEntry對象的value域是volatile類型的，因此可以直接替換。
9. 自旋時具體做了些什麼？
//自旋等待獲取鎖(put操作)private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) { //根據哈希碼獲取頭結點HashEntry<K,V> first = entryForHash(this, hash); HashEntry<K,V> e = first; HashEntry<K,V> node = null; int retries = -1; //在while循環內自旋while (!tryLock()) { HashEntry<K,V> f; if (retries < 0) { //如果頭結點為空就新建一個node if (e == null) { if (node == null) { node = new HashEntry<K,V>(hash, key, value, null); } retries = 0; //否則就遍歷鍊錶定位該結點} else if (key.equals(e.key)) { retries = 0; } else { e = e.next; } //retries每次在這加1, 並判斷是否超過最大值} else if (++retries > MAX_SCAN_RETRIES) { lock(); break; //retries為偶數時去判斷first有沒有改變} else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) { e = first = f; retries = -1; } } return node;}//自旋等待獲取鎖(remove和replace操作)private void scanAndLock(Object key, int hash) { //根據哈希碼獲取鍊錶頭結點HashEntry<K,V> first = entryForHash(this, hash); HashEntry<K,V> e = first; int retries = -1; //在while循環裡自旋while (!tryLock()) { HashEntry<K,V> f; if (retries < 0) { //遍歷鍊錶定位到該結點if (e == null || key.equals(e.key)) { retries = 0; } else { e = e.next; } //retries每次在這加1, 並判斷是否超過最大值} else if (++retries > MAX_SCAN_RETRIES) { lock(); break; //retries為偶數時去判斷first有沒有改變} else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) { e = first = f; retries = -1; } }}在前面我們講到過，分段鎖中的put，remove，replace這些操作都會要求先去獲取鎖，只有成功獲得鎖之後才能進行下一步操作，如果獲取失敗就會進行自旋。自旋操作也是在JDK1.7中添加的，為了避免線程頻繁的掛起和喚醒，以此提高並發操作時的性能。在put方法中調用的是scanAndLockForPut，在remove和replace方法中調用的是scanAndLock。這兩種自旋方法大致是相同的，這裡我們只分析scanAndLockForPut方法。首先還是先根據hash碼獲得鍊錶頭結點，之後線程會進入while循環中執行，退出該循環的唯一方式是成功獲取鎖，而在這期間線程不會被掛起。剛進入循環時retries的值為-1，這時線程不會馬上再去嘗試獲取鎖，而是先去尋找到key對應的結點(沒找到會新建一個)，然後再將retries設為0，接下來就會一次次的嘗試獲取鎖，對應retries的值也會每次加1，直到超過最大嘗試次數如果還沒獲取到鎖，就會調用lock方法進行阻塞獲取。在嘗試獲取鎖的期間，還會每隔一次(retries為偶數)去檢查頭結點是否被改變，如果被改變則將retries重置回-1，然後再重走一遍剛才的流程。這就是線程自旋時所做的操作，需注意的是如果在自旋時檢測到頭結點已被改變，則會延長線程的自旋時間。
10. 哈希表擴容時都做了哪些操作？
//再哈希@SuppressWarnings("unchecked")private void rehash(HashEntry<K,V> node) { //獲取舊哈希表的引用HashEntry<K,V>[] oldTable = table; //獲取舊哈希表的容量int oldCapacity = oldTable.length; //計算新哈希表的容量(為舊哈希表的2倍) int newCapacity = oldCapacity << 1; //計算新的元素閥值threshold = (int)(newCapacity * loadFactor); //新建一個HashEntry數組HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity]; //生成新的掩碼值int sizeMask = newCapacity - 1; //遍歷舊表的所有元素for (int i = 0; i < oldCapacity ; i++) { //取得鍊錶頭結點HashEntry<K,V> e = oldTable[i]; if (e != null) { HashEntry<K,V> next = e.next; //計算元素在新表中的索引int idx = e.hash & sizeMask; //next為空表明鍊錶只有一個結點if (next == null) { //直接把該結點放到新表中newTable[idx] = e; }else { HashEntry<K,V> lastRun = e; int lastIdx = idx; //定位lastRun結點, 將lastRun之後的結點直接放到新表中for (HashEntry<K,V> last = next; last != null; last = last.next) { int k = last.hash & sizeMask; if (k != lastIdx) { lastIdx = k; lastRun = last; } } newTable[lastIdx] = lastRun; //遍歷在鍊錶lastRun結點之前的元素, 將它們依次復製到新表中for (HashEntry<K,V> p = e; p != lastRun; p = p.next) { V v = p.value; int h = p.hash; int k = h & sizeMask; HashEntry<K,V> n = newTable[k]; newTable[k] = new HashEntry<K,V>(h, p.key, v, n); } } } } //計算傳入結點在新表中的下標int nodeIndex = node.hash & sizeMask; //將傳入結點添加到鍊錶頭結點node.setNext(newTable[nodeIndex]); //將新表指定下標元素換成傳入結點newTable[nodeIndex] = node; //將哈希表引用指向新表table = newTable;}rehash方法在put方法中被調用，我們知道在put方法時會新建元素並添加到哈希數組中，隨著元素的增多發生哈希衝突的可能性越大，哈希表的性能也會隨之下降。因此每次put操作時都會檢查元素總數是否超過閥值，如果超過則調用rehash方法進行擴容。因為數組長度一旦確定則不能再被改變，因此需要新建一個數組來替換原先的數組。從代碼中可以知道新創建的數組長度為原數組的2倍(oldCapacity << 1)。創建好新數組後需要將舊數組中的所有元素移到新數組中，因此需要計算每個元素在新數組中的下標。計算新下標的過程如下圖所示。
我們知道下標直接取的是哈希碼的後幾位，由於新數組的容量是直接用舊數組容量右移1位得來的，因此掩碼位數向右增加1位，取到的哈希碼位數也向右增加1位。如上圖，若舊的掩碼值為111，則元素下標為101，擴容後新的掩碼值為1111，則計算出元素的新下標為0101。由於同一條鍊錶上的元素下標是相同的，現在假設鍊錶所有元素的下標為101，在擴容後該鍊錶元素的新下標只有0101或1101這兩種情況，因此數組擴容會打亂原先的鍊錶並將鍊錶元素分成兩批。在計算出新下標後需要將元素移動到新數組中，在HashMap中通過直接修改next引用導致了多線程的死鎖。雖然在ConcurrentHashMap中通過加鎖避免了這種情況，但是我們知道next域是volatile類型的，它的改動能立馬被讀線程讀取到，因此為保證線程安全採用複制元素來遷移數組。但是對鍊錶中每個元素都進行複制有點影響性能，作者發現鍊錶尾部有許多元素的next是不變的，它們在新數組中的下標是相同的，因此可以考慮整體移動這部分元素。具統計實際操作中只有1/6的元素是必須複製的，所以整體移動鍊錶尾部元素(lastRun後面的元素)是可以提升一定性能的。
注：本篇文章基於JDK1.7版本。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。