深入併發包 ConcurrentHashMap 源碼解析

来源:https://www.cnblogs.com/java-chen-hao/archive/2019/01/25/10320783.html
-Advertisement-
Play Games

以前寫過介紹HashMap的文章，文中提到過HashMap在put的時候，插入的元素超過了容量（由負載因數決定）的範圍就會觸發擴容操作，就是rehash，這個會重新將原數組的內容重新hash到新的擴容數組中，在多線程的環境下，存在同時其他的元素也在進行put操作，如果hash值相同，可能出現同時在同 ...


以前寫過介紹HashMap的文章，文中提到過HashMap在put的時候，插入的元素超過了容量（由負載因數決定）的範圍就會觸發擴容操作，就是rehash，這個會重新將原數組的內容重新hash到新的擴容數組中，在多線程的環境下，存在同時其他的元素也在進行put操作，如果hash值相同，可能出現同時在同一數組下用鏈表表示，造成閉環，導致在get時會出現死迴圈，所以HashMap是線程不安全的。

JDK1.7的實現

整個 ConcurrentHashMap 由一個個 Segment 組成，Segment 代表”部分“或”一段“的意思，所以很多地方都會將其描述為分段鎖。註意，行文中，我很多地方用了“槽”來代表一個 segment。

簡單理解就是，ConcurrentHashMap 是一個 Segment 數組，Segment 通過繼承 ReentrantLock 來進行加鎖，所以每次需要加鎖的操作鎖住的是一個 segment，這樣只要保證每個 Segment 是線程安全的，也就實現了全局的線程安全。

 

concurrencyLevel：並行級別、併發數、Segment 數。預設是 16，也就是說 ConcurrentHashMap 有 16 個 Segments，所以理論上，這個時候，最多可以同時支持 16 個線程併發寫，只要它們的操作分別分佈在不同的 Segment 上。這個值可以在初始化的時候設置為其他值，但是一旦初始化以後，它是不可以擴容的。

再具體到每個 Segment 內部，其實每個 Segment 很像之前介紹的 HashMap，不過它要保證線程安全，所以處理起來要麻煩些。

初始化

initialCapacity：初始容量，這個值指的是整個 ConcurrentHashMap 的初始容量，實際操作的時候需要平均分給每個 Segment。

loadFactor：負載因數，之前我們說了，Segment 數組不可以擴容，所以這個負載因數是給每個 Segment 內部使用的。

 1 public ConcurrentHashMap(int initialCapacity,
 2                          float loadFactor, int concurrencyLevel) {
 3     if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
 4         throw new IllegalArgumentException();
 5     if (concurrencyLevel > MAX_SEGMENTS)
 6         concurrencyLevel = MAX_SEGMENTS;
 7     // Find power-of-two sizes best matching arguments
 8     int sshift = 0;
 9     int ssize = 1;
10     // 計算並行級別 ssize，因為要保持並行級別是 2 的 n 次方
11     while (ssize < concurrencyLevel) {
12         ++sshift;
13         ssize <<= 1;
14     }
15     // 我們這裡先不要那麼燒腦，用預設值，concurrencyLevel 為 16，sshift 為 4
16     // 那麼計算出 segmentShift 為 28，segmentMask 為 15，後面會用到這兩個值
17     this.segmentShift = 32 - sshift;
18     this.segmentMask = ssize - 1;
19 
20     if (initialCapacity > MAXIMUM_CAPACITY)
21         initialCapacity = MAXIMUM_CAPACITY;
22 
23     // initialCapacity 是設置整個 map 初始的大小，
24     // 這裡根據 initialCapacity 計算 Segment 數組中每個位置可以分到的大小
25     // 如 initialCapacity 為 64，那麼每個 Segment 或稱之為"槽"可以分到 4 個
26     int c = initialCapacity / ssize;
27     if (c * ssize < initialCapacity)
28         ++c;
29     // 預設 MIN_SEGMENT_TABLE_CAPACITY 是 2，這個值也是有講究的，因為這樣的話，對於具體的槽上，
30     // 插入一個元素不至於擴容，插入第二個的時候才會擴容
31     int cap = MIN_SEGMENT_TABLE_CAPACITY; 
32     while (cap < c)
33         cap <<= 1;
34 
35     // 創建 Segment 數組，
36     // 並創建數組的第一個元素 segment[0]
37     Segment<K,V> s0 =
38         new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
39                          (HashEntry<K,V>[])new HashEntry[cap]);
40     Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
41     // 往數組寫入 segment[0]
42     UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
43     this.segments = ss;
44 }

初始化完成，我們得到了一個 Segment 數組。

我們就當是用 new ConcurrentHashMap() 無參構造函數進行初始化的，那麼初始化完成後：

  • Segment 數組長度為 16，不可以擴容
  • Segment[i] 的預設大小為 2，負載因數是 0.75，得出初始閾值為 1.5，也就是以後插入第一個元素不會觸發擴容，插入第二個會進行第一次擴容
  • 這裡初始化了 segment[0]，其他位置還是 null，至於為什麼要初始化 segment[0]，後面的代碼會介紹
  • 當前 segmentShift 的值為 32 - 4 = 28，segmentMask 為 16 - 1 = 15，姑且把它們簡單翻譯為移位數和掩碼，這兩個值馬上就會用到

Segment 

1 static class Segment<K,V> extends ReentrantLock implements Serializable {
2 
3     transient volatile HashEntry<K,V>[] table;
4     
5     transient int count;
6     
7     transient int modCount;
8     
9 }

從上Segment的繼承體系可以看出，Segment實現了ReentrantLock,也就帶有鎖的功能,table使用volatile修飾，保證了記憶體可見性。

put 過程分析

我們先看 put 的主流程，對於其中的一些關鍵細節操作，後面會進行詳細介紹。

 1 public V put(K key, V value) {
 2     Segment<K,V> s;
 3     if (value == null)
 4         throw new NullPointerException();
 5     // 1. 計算 key 的 hash 值
 6     int hash = hash(key);
 7     // 2. 根據 hash 值找到 Segment 數組中的位置 j
 8     //    hash 是 32 位，無符號右移 segmentShift(28) 位，剩下高 4 位，
 9     //    然後和 segmentMask(15) 做一次與操作，也就是說 j 是 hash 值的高 4 位，也就是槽的數組下標
10     int j = (hash >>> segmentShift) & segmentMask;
11     // 剛剛說了，初始化的時候初始化了 segment[0]，但是其他位置還是 null，
12     // ensureSegment(j) 對 segment[j] 進行初始化
13     if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
14          (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
15         s = ensureSegment(j);
16     // 3. 插入新值到 槽 s 中
17     return s.put(key, hash, value, false);
18 }

初始化槽: ensureSegment

ConcurrentHashMap 初始化的時候會初始化第一個槽 segment[0]，對於其他槽來說，在插入第一個值的時候進行初始化。

這裡需要考慮併發，因為很可能會有多個線程同時進來初始化同一個槽 segment[k]，不過只要有一個成功了就可以。

 1 private Segment<K,V> ensureSegment(int k) {
 2     final Segment<K,V>[] ss = this.segments;
 3     long u = (k << SSHIFT) + SBASE; // raw offset
 4     Segment<K,V> seg;
 5     if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
 6         // 這裡看到為什麼之前要初始化 segment[0] 了，
 7         // 使用當前 segment[0] 處的數組長度和負載因數來初始化 segment[k]
 8         // 為什麼要用“當前”，因為 segment[0] 可能早就擴容過了
 9         Segment<K,V> proto = ss[0];
10         int cap = proto.table.length;
11         float lf = proto.loadFactor;
12         int threshold = (int)(cap * lf);
13 
14         // 初始化 segment[k] 內部的數組
15         HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
16         if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
17             == null) { // 再次檢查一遍該槽是否被其他線程初始化了。
18 
19             Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
20             // 使用 while 迴圈，內部用 CAS，當前線程成功設值或其他線程成功設值後，退出,如果其他線程成功設置後，這裡獲取到直接返回
21             while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
22                    == null) {
23                 if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
24                     break;
25             }
26         }
27     }
28     return seg;
29 }

總的來說，ensureSegment(int k) 比較簡單，對於併發操作使用 CAS 進行控制。

第一層很簡單，根據 hash 值很快就能找到相應的 Segment，之後就是 Segment 內部的 put 操作了。

Segment 內部是由 數組+鏈表 組成的。

 1 final V put(K key, int hash, V value, boolean onlyIfAbsent) {
 2     // 在往該 segment 寫入前，需要先獲取該 segment 的獨占鎖
 3     //    先看主流程，後面還會具體介紹這部分內容
 4     HashEntry<K,V> node = tryLock() ? null :
 5         scanAndLockForPut(key, hash, value);
 6     V oldValue;
 7     try {
 8         // 這個是 segment 內部的數組
 9         HashEntry<K,V>[] tab = table;
10         // 再利用 hash 值，求應該放置的數組下標
11         int index = (tab.length - 1) & hash;
12         // first 是數組該位置處的鏈表的表頭
13         HashEntry<K,V> first = entryAt(tab, index);
14 
15         // 下麵這串 for 迴圈雖然很長，不過也很好理解，想想該位置沒有任何元素和已經存在一個鏈表這兩種情況
16         for (HashEntry<K,V> e = first;;) {
17             if (e != null) {
18                 K k;
19                 if ((k = e.key) == key ||
20                     (e.hash == hash && key.equals(k))) {
21                     oldValue = e.value;
22                     if (!onlyIfAbsent) {
23                         // 覆蓋舊值
24                         e.value = value;
25                         ++modCount;
26                     }
27                     break;
28                 }
29                 // 繼續順著鏈表走
30                 e = e.next;
31             }
32             else {
33                 // node 到底是不是 null，這個要看獲取鎖的過程，不過和這裡都沒有關係。
34                 // 如果不為 null，那就直接將它設置為鏈表表頭；如果是null，初始化並設置為鏈表表頭。
35                 if (node != null)
36                     node.setNext(first);
37                 else
38                     node = new HashEntry<K,V>(hash, key, value, first);
39 
40                 int c = count + 1;
41                 // 如果超過了該 segment 的閾值，這個 segment 需要擴容
42                 if (c > threshold && tab.length < MAXIMUM_CAPACITY)
43                     rehash(node); // 擴容後面也會具體分析
44                 else
45                     // 沒有達到閾值，將 node 放到數組 tab 的 index 位置，
46                     // 其實就是將新的節點設置成原鏈表的表頭
47                     setEntryAt(tab, index, node);
48                 ++modCount;
49                 count = c;
50                 oldValue = null;
51                 break;
52             }
53         }
54     } finally {
55         // 解鎖
56         unlock();
57     }
58     return oldValue;
59 }

整體流程還是比較簡單的，由於有獨占鎖的保護，所以 segment 內部的操作並不複雜。至於這裡面的併發問題，我們稍後再進行介紹。

到這裡 put 操作就結束了，接下來，我們說一說其中幾步關鍵的操作。

獲取寫入鎖: scanAndLockForPut

前面我們看到，在往某個 segment 中 put 的時候，首先會調用 node = tryLock() ? null : scanAndLockForPut(key, hash, value)，也就是說先進行一次 tryLock() 快速獲取該 segment 的獨占鎖，如果失敗，那麼進入到 scanAndLockForPut 這個方法來獲取鎖。

下麵我們來具體分析這個方法中是怎麼控制加鎖的。

 1 private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
 2     HashEntry<K,V> first = entryForHash(this, hash);
 3     HashEntry<K,V> e = first;
 4     HashEntry<K,V> node = null;
 5     int retries = -1; // negative while locating node
 6 
 7     // 迴圈獲取鎖
 8     while (!tryLock()) {
 9         HashEntry<K,V> f; // to recheck first below
10         if (retries < 0) {
11             if (e == null) {
12                 if (node == null) // speculatively create node
13                     // 進到這裡說明數組該位置的鏈表是空的，沒有任何元素
14                     // 當然，進到這裡的另一個原因是 tryLock() 失敗，所以該槽存在併發，不一定是該位置
15                     node = new HashEntry<K,V>(hash, key, value, null);
16                 retries = 0;
17             }
18             else if (key.equals(e.key))
19                 retries = 0;
20             else
21                 // 順著鏈表往下走
22                 e = e.next;
23         }
24         // 重試次數如果超過 MAX_SCAN_RETRIES（單核1多核64），那麼不搶了，進入到阻塞隊列等待鎖
25         //    lock() 是阻塞方法，直到獲取鎖後返回
26         else if (++retries > MAX_SCAN_RETRIES) {
27             lock();
28             break;
29         }
30         else if ((retries & 1) == 0 &&
31                  // 這個時候是有大問題了，那就是有新的元素進到了鏈表，成為了新的表頭
32                  //     所以這邊的策略是，相當於重新走一遍這個 scanAndLockForPut 方法
33                  (f = entryForHash(this, hash)) != first) {
34             e = first = f; // re-traverse if entry changed
35             retries = -1;
36         }
37     }
38     return node;
39 }

這個方法有兩個出口，一個是 tryLock() 成功了，迴圈終止，另一個就是重試次數超過了 MAX_SCAN_RETRIES，進到 lock() 方法，此方法會阻塞等待，直到成功拿到獨占鎖。

這個方法就是看似複雜，但是其實就是做了一件事，那就是獲取該 segment 的獨占鎖，如果需要的話順便實例化了一下 node。

獲取鎖時，並不直接使用lock來獲取，因為該方法獲取鎖失敗時會掛起。事實上，它使用了自旋鎖，如果tryLock獲取鎖失敗，說明鎖被其它線程占用，此時通過迴圈再次以tryLock的方式申請鎖。如果在迴圈過程中該Key所對應的鏈表頭被修改，則重置retry次數。如果retry次數超過一定值，則使用lock方法申請鎖。

這裡使用自旋鎖是因為自旋鎖的效率比較高，但是它消耗CPU資源比較多，因此在自旋次數超過閾值時切換為互斥鎖。

擴容: rehash

重覆一下，segment 數組不能擴容，擴容是 segment 數組某個位置內部的數組 HashEntry\<k,v>[] 進行擴容，擴容後，容量為原來的 2 倍。

首先，我們要回顧一下觸發擴容的地方，put 的時候，如果判斷該值的插入會導致該 segment 的元素個數超過閾值，那麼先進行擴容，再插值，讀者這個時候可以回去 put 方法看一眼。

該方法不需要考慮併發，因為到這裡的時候，是持有該 segment 的獨占鎖的。

 1 // 方法參數上的 node 是這次擴容後，需要添加到新的數組中的數據。
 2 private void rehash(HashEntry<K,V> node) {
 3     HashEntry<K,V>[] oldTable = table;
 4     int oldCapacity = oldTable.length;
 5     // 2 倍
 6     int newCapacity = oldCapacity << 1;
 7     threshold = (int)(newCapacity * loadFactor);
 8     // 創建新數組
 9     HashEntry<K,V>[] newTable =
10         (HashEntry<K,V>[]) new HashEntry[newCapacity];
11     // 新的掩碼，如從 16 擴容到 32，那麼 sizeMask 為 31，對應二進位 ‘000...00011111’
12     int sizeMask = newCapacity - 1;
13 
14     // 遍歷原數組，老套路，將原數組位置 i 處的鏈表拆分到 新數組位置 i 和 i+oldCap 兩個位置
15     for (int i = 0; i < oldCapacity ; i++) {
16         // e 是鏈表的第一個元素
17         HashEntry<K,V> e = oldTable[i];
18         if (e != null) {
19             HashEntry<K,V> next = e.next;
20             // 計算應該放置在新數組中的位置，
21             // 假設原數組長度為 16，e 在 oldTable[3] 處，那麼 idx 只可能是 3 或者是 3 + 16 = 19
22             int idx = e.hash & sizeMask;
23             if (next == null)   // 該位置處只有一個元素，那比較好辦
24                 newTable[idx] = e;
25             else { // Reuse consecutive sequence at same slot
26                 // e 是鏈表表頭
27                 HashEntry<K,V> lastRun = e;
28                 // idx 是當前鏈表的頭結點 e 的新位置
29                 int lastIdx = idx;
30 
31                 // 下麵這個 for 迴圈會找到一個 lastRun 節點，這個節點之後的所有元素是將要放到一起的
32                 for (HashEntry<K,V> last = next;
33                      last != null;
34                      last = last.next) {
35                     int k = last.hash & sizeMask;
36                     if (k != lastIdx) {
37                         lastIdx = k;
38                         lastRun = last;
39                     }
40                 }
41                 // 將 lastRun 及其之後的所有節點組成的這個鏈表放到 lastIdx 這個位置
42                 newTable[lastIdx] = lastRun;
43                 // 下麵的操作是處理 lastRun 之前的節點，
44                 //    這些節點可能分配在另一個鏈表中，也可能分配到上面的那個鏈表中
45                 for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
46                     V v = p.value;
47                     int h = p.hash;
48                     int k = h & sizeMask;
49                     HashEntry<K,V> n = newTable[k];
50                     newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
51                 }
52             }
53         }
54     }
55     // 將新來的 node 放到新數組中剛剛的 兩個鏈表之一 的 頭部
56     int nodeIndex = node.hash & sizeMask; // add the new node
57     node.setNext(newTable[nodeIndex]);
58     newTable[nodeIndex] = node;
59     table = newTable;
60 }

總結一下put的流程：

當執行put操作時，會進行第一次key的hash來定位Segment的位置，如果該Segment還沒有初始化，即通過CAS操作進行賦值，然後進行第二次hash操作，找到相應的HashEntry的位置，這裡會利用繼承過來的鎖的特性，在將數據插入指定的HashEntry位置時（鏈表的尾端），會通過繼承ReentrantLock的tryLock（）方法嘗試去獲取鎖，如果獲取成功就直接插入相應的位置，如果已經有線程獲取該Segment的鎖，那當前線程會以自旋的方式去繼續的調用tryLock（）方法去獲取鎖，超過指定次數就掛起，等待喚醒。

get 過程分析

相對於 put 來說，get 真的不要太簡單。

  1. 計算 hash 值，找到 segment 數組中的具體位置，或我們前面用的“槽”
  2. 槽中也是一個數組，根據 hash 找到數組中具體的位置
  3. 到這裡是鏈表了，順著鏈表進行查找即可
 1 public V get(Object key) {
 2     Segment<K,V> s; // manually integrate access methods to reduce overhead
 3     HashEntry<K,V>[] tab;
 4     // 1. hash 值
 5     int h = hash(key);
 6     long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
 7     // 2. 根據 hash 找到對應的 segment
 8     if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
 9         (tab = s.table) != null) {
10         // 3. 找到segment 內部數組相應位置的鏈表，遍歷
11         for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
12                  (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
13              e != null; e = e.next) {
14             K k;
15             if ((k = e.key) == key || (e.hash == h && key.equals(k)))
16                 return e.value;
17         }
18     }
19     return null;
20 }

size操作

put、remove和get操作只需要關心一個Segment，而size操作需要遍歷所有的Segment才能算出整個Map的大小。一個簡單的方案是，先鎖住所有Sgment，計算完後再解鎖。但這樣做，在做size操作時，不僅無法對Map進行寫操作，同時也無法進行讀操作，不利於對Map的並行操作。

為更好支持併發操作，ConcurrentHashMap會在不上鎖的前提逐個Segment計算3次size，如果某相鄰兩次計算獲取的所有Segment的更新次數（每個Segment都與HashMap一樣通過modCount跟蹤自己的修改次數，Segment每修改一次其modCount加一）相等，說明這兩次計算過程中無更新操作，則這兩次計算出的總size相等，可直接作為最終結果返回。如果這三次計算過程中Map有更新，則對所有Segment加鎖重新計算Size。該計算方法代碼如下

 1 public int size() {
 2   final Segment<K,V>[] segments = this.segments;
 3   int size;
 4   boolean overflow; // true if size overflows 32 bits
 5   long sum;         // sum of modCounts
 6   long last = 0L;   // previous sum
 7   int retries = -1; // first iteration isn't retry
 8   try {
 9     for (;;) {
10       if (retries++ == RETRIES_BEFORE_LOCK) {
11         for (int j = 0; j < segments.length; ++j)
12           ensureSegment(j).lock(); // force creation
13       }
14       sum = 0L;
15       size = 0;
16       overflow = false;
17       for (int j = 0; j < segments.length; ++j) {
18         Segment<K,V> seg = segmentAt(segments, j);
19         if (seg != null) {
20           sum += seg.modCount;
21           int c = seg.count;
22           if (c < 0 || (size += c) < 0)
23             overflow = true;
24         }
25       }
26       if (sum == last)
27         break;
28       last = sum;
29     }
30   } finally {
31     if (retries > RETRIES_BEFORE_LOCK) {
32       for (int j = 0; j < segments.length; ++j)
33         segmentAt(segments, j).unlock();
34     }
35   }
36   return overflow ? Integer.MAX_VALUE : size;
37 }

ConcurrentHashMap的Size方法是一個嵌套迴圈，大體邏輯如下：

1.遍歷所有的Segment。

2.把Segment的元素數量累加起來。

3.把Segment的修改次數累加起來。

4.判斷所有Segment的總修改次數是否大於上一次的總修改次數。如果大於，說明統計過程中有修改，重新統計，嘗試次數+1；如果不是。說明沒有修改，統計結束。

5.如果嘗試次數超過閾值，則對每一個Segment加鎖，再重新統計。

6.再次判斷所有Segment的總修改次數是否大於上一次的總修改次數。由於已經加鎖，次數一定和上次相等。

7.釋放鎖，統計結束。

併發問題分析

現在我們已經說完了 put 過程和 get 過程，我們可以看到 get 過程中是沒有加鎖的，那自然我們就需要去考慮併發問題。

添加節點的操作 put 和刪除節點的操作 remove 都是要加 segment 上的獨占鎖的，所以它們之間自然不會有問題，我們需要考慮的問題就是 get 的時候在同一個 segment 中發生了 put 或 remove 操作。

  1. put 操作的線程安全性。

    1. 初始化槽，這個我們之前就說過了，使用了 CAS 來初始化 Segment 中的數組。
    2. 添加節點到鏈表的操作是插入到表頭的，所以，如果這個時候 get 操作在鏈表遍歷的過程已經到了中間，是不會影響的。當然，另一個併發問題就是 get 操作在 put 之後，需要保證剛剛插入表頭的節點被讀取，這個依賴於 setEntryAt 方法中使用的 UNSAFE.putOrderedObject。
    3. 擴容。擴容是新創建了數組，然後進行遷移數據，最後面將 newTable 設置給屬性 table。所以，如果 get 操作此時也在進行，那麼也沒關係，如果 get 先行，那麼就是在舊的 table 上做查詢操作；而 put 先行，那麼 put 操作的可見性保證就是 table 使用了 volatile 關鍵字。

  2. remove 操作的線程安全性。

    remove 操作我們沒有分析源碼，所以這裡說的讀者感興趣的話還是需要到源碼中去求實一下的。

    get 操作需要遍歷鏈表，但是 remove 操作會"破壞"鏈表。

    如果 remove 破壞的節點 get 操作已經過去了，那麼這裡不存在任何問題。

    如果 remove 先破壞了一個節點，分兩種情況考慮。 1、如果此節點是頭結點，那麼需要將頭結點的 next 設置為數組該位置的元素，table 雖然使用了 volatile 修飾，但是 volatile 並不能提供數組內部操作的可見性保證，所以源碼中使用了 UNSAFE 來操作數組，請看方法 setEntryAt。2、如果要刪除的節點不是頭結點，它會將要刪除節點的後繼節點接到前驅節點中，這裡的併發保證就是 next 屬性是 volatile 的。

最後我們來看看併發操作示意圖

Case1：不同Segment的併發寫入

不同Segment的寫入是可以併發執行的。

Case2：同一Segment的一寫一讀

同一Segment的寫和讀是可以併發執行的。

Case3：同一Segment的併發寫入

Segment的寫入是需要上鎖的，因此對同一Segment的併發寫入會被阻塞。

由此可見，ConcurrentHashMap當中每個Segment各自持有一把鎖。在保證線程安全的同時降低了鎖的粒度，讓併發操作效率更高。

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • c語言----<項目>_小游戲<2048>
    2048 小游戲 主要是針對邏輯思維的一個訓練. 主要學習方面:1.隨機數產生的概率.2.行與列在進行移動的時候幾種情況.3.MessageBox的使用 include include include include using namespace std; int board[4][4] = {0 ...
  • 零基礎如何開始學習 Python？看完這篇小白變小牛！
    最近開始整理python的資料，博主建立了一個qq群，希望給大家提供一個交流的同平臺: 78486745 ,歡迎大家加入共同交流學習。 1、選擇Python版本 對於Python工程師來說，Python的版本則是你們的工作環境。所以在學習之前一定要考慮選擇一個合適自己的版本，Python3對零基礎的 ...
  • BZOJ1802: [Ahoi2009]checker(性質分析 dp)
    題意 "題目鏈接" Sol 一個不太容易發現但是又很顯然的性質： 如果有兩個相鄰的紅格子，那麼第一問答案為0, 第二問可以推 否則第一問答案為偶數格子上的白格子數，第二問答案為偶數格子上的紅格子數 cpp include define Pair pair define MP(x, y) make_p ...
  • Ubuntu 16.04 下簡單安裝使用golang之備忘
      剛開始學習Go語言，這裡記錄下我在Ubuntu 16.04下安裝使用golang的過程，方便以後查詢。   一、安裝   1、添加源   如果使用預設的源安裝golang的話，版本太低，只到1.6，所以要添加一個新的源並更新，執行以下命 ...
  • Python就業都有哪些崗位？
    現在互聯網巨頭，都已經轉投到人工智慧領域，而人工智慧的首選編程語言就是python，未來前景顯而易見。那麼問題來了，想學Python，Python工程師工資一般多少?值得去學嗎? 最近開始整理python的資料，會陸續放到博客中存檔。找了幾個qq群，其中有一個群78486745。後面就沒怎麼加群了， ...
  • python pynput監聽鍵盤
    """小白隨筆，大佬勿噴"""#鍵盤輸入from pynput.keyboard import Key,Controller,Listenerkeyboard = Controller()keyboard.press("a") #按下akeyboard.release("a") #鬆開akeyboa ...
  • 服務端如何獲取客戶端請求IP地址
    服務端獲取客戶端請求IP地址，常見的包括：x forwarded for、client ip等請求頭，以及remote_addr參數。 一、remote_addr、x forwarded for、client ip remote\_addr：指的是當前直接請求的客戶端IP地址，它存在於tcp請求體中 ...
  • 【題解】 LGP2730 【魔板 Magic Squares】
    【題目背景】 在成功地發明瞭魔方之後，魯比克先生髮明瞭它的二維版本，稱作魔板。這是一張有8個大小相同的格子的魔板： 【題目描述】 我們知道魔板的每一個方格都有一種顏色。這8種顏色用前8個正整數來表示。可以用顏色的序列來表示一種魔板狀態，規定從魔板的左上角開始，沿順時針方向依次取出整數，構成一個顏色序 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類