我們知道哈希表是一種非常高效的數據結構,設計優良的哈希函數可以使其上的增刪改查操作達到O(1)級別。Java為我們提供了一個現成的哈希結構,那就是HashMap類,在前面的文章中我曾經介紹過HashMap類,知道它的所有方法都未進行同步,因此在多線程環境中是不安全的。為此,Java為我們提供了另外一 ...
我們知道哈希表是一種非常高效的數據結構,設計優良的哈希函數可以使其上的增刪改查操作達到O(1)級別。Java為我們提供了一個現成的哈希結構,那就是HashMap類,在前面的文章中我曾經介紹過HashMap類,知道它的所有方法都未進行同步,因此在多線程環境中是不安全的。為此,Java為我們提供了另外一個HashTable類,它對於多線程同步的處理非常簡單粗暴,那就是在HashMap的基礎上對其所有方法都使用synchronized關鍵字進行加鎖。這種方法雖然簡單,但導致了一個問題,那就是在同一時間內只能由一個線程去操作哈希表。即使這些線程都只是進行讀操作也必須要排隊,這在競爭激烈的多線程環境中極為影響性能。本篇介紹的ConcurrentHashMap就是為瞭解決這個問題的,它的內部使用分段鎖將鎖進行細粒度化,從而使得多個線程能夠同時操作哈希表,這樣極大的提高了性能。下圖是其內部結構的示意圖。
1. ConcurrentHashMap有哪些成員變數?
1 //預設初始化容量 2 static final int DEFAULT_INITIAL_CAPACITY = 16; 3 4 //預設載入因數 5 static final float DEFAULT_LOAD_FACTOR = 0.75f; 6 7 //預設併發級別 8 static final int DEFAULT_CONCURRENCY_LEVEL = 16; 9 10 //集合最大容量 11 static final int MAXIMUM_CAPACITY = 1 << 30; 12 13 //分段鎖的最小數量 14 static final int MIN_SEGMENT_TABLE_CAPACITY = 2; 15 16 //分段鎖的最大數量 17 static final int MAX_SEGMENTS = 1 << 16; 18 19 //加鎖前的重試次數 20 static final int RETRIES_BEFORE_LOCK = 2; 21 22 //分段鎖的掩碼值 23 final int segmentMask; 24 25 //分段鎖的移位值 26 final int segmentShift; 27 28 //分段鎖數組 29 final Segment<K,V>[] segments;
在閱讀完本篇文章之前,相信讀者不能理解這些成員變數的具體含義和作用,不過請讀者們耐心看下去,後面將會在具體場景中一一介紹到這些成員變數的作用。在這裡讀者只需對這些成員變數留個眼熟即可。但是仍有個別變數是我們現在需要瞭解的,例如Segment數組代表分段鎖集合,併發級別則代表分段鎖的數量(也意味有多少線程可以同時操作),初始化容量代表整個容器的容量,載入因數代表容器元素可以達到多滿的一種程度。
2. 分段鎖的內部結構是怎樣的?
1 //分段鎖 2 static final class Segment<K,V> extends ReentrantLock implements Serializable { 3 //自旋最大次數 4 static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1; 5 //哈希表 6 transient volatile HashEntry<K,V>[] table; 7 //元素總數 8 transient int count; 9 //修改次數 10 transient int modCount; 11 //元素閥值 12 transient int threshold; 13 //載入因數 14 final float loadFactor; 15 //省略以下內容 16 ... 17 }
Segment是ConcurrentHashMap的靜態內部類,可以看到它繼承自ReentrantLock,因此它在本質上是一個鎖。它在內部持有一個HashEntry數組(哈希表),並且保證所有對該數組的增刪改查方法都是線程安全的,具體是怎樣實現的後面會講到。所有對ConcurrentHashMap的增刪改查操作都可以委托Segment來進行,因此ConcurrentHashMap能夠保證在多線程環境下是安全的。又因為不同的Segment是不同的鎖,所以多線程可以同時操作不同的Segment,也就意味著多線程可以同時操作ConcurrentHashMap,這樣就能避免HashTable的缺陷,從而極大的提高性能。
3. ConcurrentHashMap初始化時做了些什麼?
1 //核心構造器 2 @SuppressWarnings("unchecked") 3 public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { 4 if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) { 5 throw new IllegalArgumentException(); 6 } 7 //確保併發級別不大於限定值 8 if (concurrencyLevel > MAX_SEGMENTS) { 9 concurrencyLevel = MAX_SEGMENTS; 10 } 11 int sshift = 0; 12 int ssize = 1; 13 //保證ssize為2的冪, 且是最接近的大於等於併發級別的數 14 while (ssize < concurrencyLevel) { 15 ++sshift; 16 ssize <<= 1; 17 } 18 //計算分段鎖的移位值 19 this.segmentShift = 32 - sshift; 20 //計算分段鎖的掩碼值 21 this.segmentMask = ssize - 1; 22 //總的初始容量不能大於限定值 23 if (initialCapacity > MAXIMUM_CAPACITY) { 24 initialCapacity = MAXIMUM_CAPACITY; 25 } 26 //獲取每個分段鎖的初始容量 27 int c = initialCapacity / ssize; 28 //分段鎖容量總和不小於初始總容量 29 if (c * ssize < initialCapacity) { 30 ++c; 31 } 32 int cap = MIN_SEGMENT_TABLE_CAPACITY; 33 //保證cap為2的冪, 且是最接近的大於等於c的數 34 while (cap < c) { 35 cap <<= 1; 36 } 37 //新建一個Segment對象模版 38 Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor), (HashEntry<K,V>[])new HashEntry[cap]); 39 //新建指定大小的分段鎖數組 40 Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize]; 41 //使用UnSafe給數組第0個元素賦值 42 UNSAFE.putOrderedObject(ss, SBASE, s0); 43 this.segments = ss; 44 }
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. 通過怎樣的方式來定位鎖和定位元素?
1 //根據哈希碼獲取分段鎖 2 @SuppressWarnings("unchecked") 3 private Segment<K,V> segmentForHash(int h) { 4 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; 5 return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u); 6 } 7 8 //根據哈希碼獲取元素 9 @SuppressWarnings("unchecked") 10 static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) { 11 HashEntry<K,V>[] tab; 12 return (seg == null || (tab = seg.table) == null) ? null : 13 (HashEntry<K,V>) UNSAFE.getObjectVolatile(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); 14 }
在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. 查找元素具體是怎樣實現的?
1 //根據key獲取value 2 public V get(Object key) { 3 Segment<K,V> s; 4 HashEntry<K,V>[] tab; 5 //使用哈希函數計算哈希碼 6 int h = hash(key); 7 //根據哈希碼計算分段鎖的索引 8 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; 9 //獲取分段鎖和對應的哈希表 10 if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) { 11 //根據哈希碼獲取鏈表頭結點, 再對鏈表進行遍歷 12 for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile 13 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); 14 e != null; e = e.next) { 15 K k; 16 //根據key和hash找到對應元素後返回value值 17 if ((k = e.key) == key || (e.hash == h && key.equals(k))) { 18 return e.value; 19 } 20 } 21 } 22 return null; 23 }
在JDK1.6中分段鎖的get方法是通過下標來訪問數組元素的,而在JDK1.7中是通過UnSafe的getObjectVolatile方法來讀取數組中的元素。為啥要這樣做?我們知道雖然Segment對象持有的HashEntry數組引用是volatile類型的,但是數組內的元素引用不是volatile類型的,因此多線程對數組元素的修改是不安全的,可能會在數組中讀取到尚未構造完成的對象。在JDK1.6中是通過第二次加鎖讀取來保證安全的,而JDK1.7中通過UnSafe的getObjectVolatile方法來讀取同樣也是為了保證這一點。使用getObjectVolatile方法讀取數組元素需要先獲得元素在數組中的偏移量,在這裡根據哈希碼計算得到分段鎖在數組中的偏移量為u,然後通過偏移量u來嘗試讀取分段鎖。由於分段鎖數組在構造時沒進行初始化,因此可能讀出來一個空值,所以需要先進行判斷。在確定分段鎖和它內部的哈希表都不為空之後,再通過哈希碼讀取HashEntry數組的元素,根據上面的結構圖可以看到,這時獲得的是鏈表的頭結點。之後再從頭到尾的對鏈表進行遍歷查找,如果找到對應的值就將其返回,否則就返回null。以上就是整個查找元素的過程。
6. 插入元素具體是怎樣實現的?
1 //向集合添加鍵值對(若存在則替換) 2 @SuppressWarnings("unchecked") 3 public V put(K key, V value) { 4 Segment<K,V> s; 5 //傳入的value不能為空 6 if (value == null) throw new NullPointerException(); 7 //使用哈希函數計算哈希碼 8 int hash = hash(key); 9 //根據哈希碼計算分段鎖的下標 10 int j = (hash >>> segmentShift) & segmentMask; 11 //根據下標去嘗試獲取分段鎖 12 if ((s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) { 13 //獲得的分段鎖為空就去構造一個 14 s = ensureSegment(j); 15 } 16 //調用分段鎖的put方法 17 return s.put(key, hash, value, false); 18 } 19 20 //向集合添加鍵值對(不存在才添加) 21 @SuppressWarnings("unchecked") 22 public V putIfAbsent(K key, V value) { 23 Segment<K,V> s; 24 //傳入的value不能為空 25 if (value == null) throw new NullPointerException(); 26 //使用哈希函數計算哈希碼 27 int hash = hash(key); 28 //根據哈希碼計算分段鎖的下標 29 int j = (hash >>> segmentShift) & segmentMask; 30 //根據下標去嘗試獲取分段鎖 31 if ((s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) { 32 //獲得的分段鎖為空就去構造一個 33 s = ensureSegment(j); 34 } 35 //調用分段鎖的put方法 36 return s.put(key, hash, value, true); 37 }
ConcurrentHashMap中有兩個添加鍵值對的方法,通過put方法添加時如果存在則會進行覆蓋,通過putIfAbsent方法添加時如果存在則不進行覆蓋,這兩個方法都是調用分段鎖的put方法來完成操作,只是傳入的最後一個參數不同而已。在上面代碼中我們可以看到首先是根據key的哈希碼來計算出分段鎖在數組中的下標,然後根據下標使用UnSafe類getObject方法來讀取分段鎖。由於在構造ConcurrentHashMap時沒有對Segment數組中的元素初始化,所以可能讀到一個空值,這時會先通過ensureSegment方法新建一個分段鎖。獲取到分段鎖之後再調用它的put方法完成添加操作,下麵我們來看看具體是怎樣操作的。
1 //添加鍵值對 2 final V put(K key, int hash, V value, boolean onlyIfAbsent) { 3 //嘗試獲取鎖, 若失敗則進行自旋 4 HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); 5 V oldValue; 6 try { 7 HashEntry<K,V>[] tab = table; 8 //計算元素在數組中的下標 9 int index = (tab.length - 1) & hash; 10 //根據下標獲取鏈表頭結點 11 HashEntry<K,V> first = entryAt(tab, index); 12 for (HashEntry<K,V> e = first;;) { 13 //遍歷鏈表尋找該元素, 找到則進行替換 14 if (e != null) { 15 K k; 16 if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { 17 oldValue = e.value; 18 //根據參數決定是否替換舊值 19 if (!onlyIfAbsent) { 20 e.value = value; 21 ++modCount; 22 } 23 break; 24 } 25 e = e.next; 26 //沒找到則在鏈表添加一個結點 27 } else { 28 //將node結點插入鏈表頭部 29 if (node != null) { 30 node.setNext(first); 31 } else { 32 node = new HashEntry<K,V>(hash, key, value, first); 33 } 34 //插入結點後將元素總是加1 35 int c = count + 1; 36 //元素超過閥值則進行擴容 37 if (c > threshold && tab.length < MAXIMUM_CAPACITY) { 38 rehash(node); 39 //否則就將哈希表指定下標替換為node結點 40 } else { 41 setEntryAt(tab, index, node); 42 } 43 ++modCount; 44 count = c; 45 oldValue = null; 46 break; 47 } 48 } 49 } finally { 50 unlock(); 51 } 52 return oldValue; 53 }
為保證線程安全,分段鎖中的put操作是需要進行加鎖的,所以線程一開始就會去獲取鎖,如果獲取成功就繼續執行,若獲取失敗則調用scanAndLockForPut方法進行自旋,在自旋過程中會先去掃描哈希表去查找指定的key,如果key不存在就會新建一個HashEntry返回,這樣在獲取到鎖之後就不必再去新建了,為的是在等待鎖的過程中順便做些事情,不至於白白浪費時間,可見作者的良苦用心。具體自旋方法我們後面再細講,現在先把關註點拉回來,線程在成功獲取到鎖之後會根據計算到的下標,獲取指定下標的元素。此時獲取到的是鏈表的頭結點,如果頭結點不為空就對鏈表進行遍歷查找,找到之後再根據onlyIfAbsent參數的值決定是否進行替換。如果遍歷沒找到就會新建一個HashEntry指向頭結點,此時如果自旋時創建了HashEntry,則直接將它的next指向當前頭結點,如果自旋時沒有創建就在這裡新建一個HashEntry並指向頭結點。在向鏈表添加元素之後檢查元素總數是否超過閥值,如果超過就調用rehash進行擴容,沒超過的話就直接將數組對應下標的元素引用指向新添加的node。setEntryAt方法內部是通過調用UnSafe的putOrderedObject方法來更改數組元素引用的,這樣就保證了其他線程在讀取時可以讀到最新的值。
7. 刪除元素具體是怎樣實現的?
1 //刪除指定元素(找到對應元素後直接刪除) 2 public V remove(Object key) { 3 //使用哈希函數計算哈希碼 4 int hash = hash(key); 5 //根據哈希碼獲取分段鎖的索引 6 Segment<K,V> s = segmentForHash(hash); 7 //調用分段鎖的remove方法 8 return s == null ? null : s.remove(key, hash, null); 9 } 10 11 //刪除指定元素(查找值等於給定值才刪除) 12 public boolean remove(Object key, Object value) { 13 //使用哈希函數計算哈希碼 14 int hash = hash(key); 15 Segment<K,V> s; 16 //確保分段鎖不為空才調用remove方法 17 return value != null && (s = segmentForHash(hash)) != null && s.remove(key, hash, value) != null; 18 }
ConcurrentHashMap提供了兩種刪除操作,一種是找到後直接刪除,一種是找到後先比較再刪除。這兩種刪除方法都是先根據key的哈希碼找到對應的分段鎖後,再通過調用分段鎖的remove方法完成刪除操作。下麵我們來看看分段鎖的remove方法。
1 //刪除指定元素 2 final V remove(Object key, int hash, Object value) { 3 //嘗試獲取鎖, 若失敗則進行自旋 4 if (!tryLock()) { 5 scanAndLock(key, hash); 6 } 7 V oldValue = null; 8 try { 9 HashEntry<K,V>[] tab = table; 10 //計算元素在數組中的下標 11 int index = (tab.length - 1) & hash; 12 //根據下標取得數組元素(鏈表頭結點) 13 HashEntry<K,V> e = entryAt(tab, index); 14 HashEntry<K,V> pred = null; 15 //遍歷鏈表尋找要刪除的元素 16 while (e != null) { 17 K k; 18 //next指向當前結點的後繼結點 19 HashEntry<K,V> next = e.next; 20 //根據key和hash尋找對應結點 21 if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { 22 V v = e.value; 23 //傳入的value不等於v就跳過, 其他情況就進行刪除操作 24 if (value == null || value == v || value.equals(v)) { 25 //如果pred為空則代表要刪除的結點為頭結點 26 if (pred == null) { 27 //重新設置鏈表頭結點 28 setEntryAt(tab, index, next); 29 } else { 30 //設置pred結點的後繼為next結點 31 pred.setNext(next); 32 } 33 ++modCount; 34 --count; 35 //記錄元素刪除之前的值 36 oldValue = v; 37 } 38 break; 39 } 40 //若e不是要找的結點就將pred引用指向它 41 pred = e; 42 //檢查下一個結點 43 e = next; 44 } 45 } finally { 46 unlock(); 47 } 48 return oldValue; 49 }
在刪除分段鎖中的元素時需要先獲取鎖,如果獲取失敗就調用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. 替換元素具體是怎樣實現的?
1 //替換指定元素(CAS操作) 2 public boolean replace(K key, V oldValue, V newValue) { 3 //使用哈希函數計算哈希碼 4 int hash = hash(key); 5 //保證oldValue和newValue不為空 6 if (oldValue == null || newValue == null) throw new NullPointerException(); 7 //根據哈希碼獲取分段鎖的索引 8 Segment<K,V> s = segmentForHash(hash); 9 //調用分段鎖的replace方法 10 return s != null && s.replace(key, hash, oldValue, newValue); 11 } 12 13 //替換元素操作(CAS操作) 14 final boolean replace(K key, int hash, V oldValue, V newValue) { 15 //嘗試獲取鎖, 若失敗則進行自旋 16 if (!tryLock()) { 17 scanAndLock(key, hash); 18 } 19 boolean replaced = false; 20 try { 21 HashEntry<K,V> e; 22 //通過hash直接找到頭結點然後對鏈表遍歷 23 for (e = entryForHash(this, hash); e != null; e = e.next) { 24 K k; 25 //根據key和hash找到要替換的結點 26 if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { 27 //如果指定的當前值正確則進行替換 28 if (oldValue.equals(e.value)) { 29 e.value = newValue; 30 ++modCount; 31 replaced = true; 32 } 33 //否則不進行任何操作直接返回 34 break; 35 } 36 } 37 } finally { 38 unlock(); 39 } 40 return replaced; 41 }
ConcurrentHashMap同樣提供了兩種替換操作,一種是找到後直接替換,另一種是找到後先比較再替換(CAS操作)。這兩種操作的實現大致是相同的,只是CAS操作在替換前多了一層比較操作,因此我們只需簡單瞭解其中一種操作即可。這裡拿CAS操作進行分析,還是老套路,首先根據key的哈希碼找到對應的分段鎖,然後調用它的replace方法。進入分段鎖中的replace方法後需要先去獲取鎖,如果獲取失敗則進行自旋,如果獲取成功則進行下一步。首先根據hash碼獲取鏈表頭結點,然後根據key和hash進行遍歷查找,找到了對應的元素之後,比較給定的oldValue是否是當前值,如果不是則放棄修改,如果是則用新值進行替換。由於HashEntry對象的value域是volatile類型的,因此可以直接替換。
9. 自旋時具體做了些什麼?
1 //自旋等待獲取鎖(put操作) 2 private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) { 3 //根據哈希碼獲取頭結點 4 HashEntry<K,V> first = entryForHash(this, hash); 5 HashEntry<K,V> e = first; 6 HashEntry<K,V> node = null; 7 int retries = -1; 8 //在while迴圈內自旋 9 while (!tryLock()) { 10 HashEntry<K,V> f; 11 if (retries < 0) { 12 //如果頭結點為空就新建一個node 13 if (e == null) { 14 if (node == null) { 15 node = new HashEntry<K,V>(hash, key, value, null); 16 } 17 retries = 0; 18 //否則就遍歷鏈表定位該結點 19 } else if (key.equals(e.key)) { 20 retries = 0; 21 } else { 22 e = e.next; 23 } 24 //retries每次在這加1, 並判斷是否超過最大值 25 } else if (++retries > MAX_SCAN_RETRIES) { 26 lock(); 27 break; 28 //retries為偶數時去判斷first有沒有改變 29 } else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) { 30 e = first = f; 31 retries = -1; 32 } 33 } 34 return node; 35 } 36 37 //自旋等待獲取鎖(remove和replace操作) 38 private void scanAndLock(Object key, int hash) { 39 //根據哈希碼獲取鏈表頭結點 40 HashEntry<K,V> first = entryForHash(this, hash); 41 HashEntry<K,V> e = first; 42 int retries = -1; 43 //在while迴圈里自旋 44 while (!tryLock()) { 45 HashEntry<K,V> f; 46 if (retries < 0) { 47 //遍歷鏈表定位到該結點 48 if (e == null || key.equals(e.key)) { 49