同步集合
同步集合最具代表性的類別如下：
- Vector
- Hashtable
- Collections.synchronizedXXX
這些類別都使用 synchronized 關鍵字在公開宣告的方法中，以確保一次只允許一個執行緒存取內部的值， 從而保證了同步性。
Vector
```javascript
public class Vector
在 Vector 類別中，觀察添加元素的 add() 方法，可以發現 synchronized 關鍵字。也就是說，在 Vector 内部執行元素插入操作時，會確保同步性。
Hashtable
```javascript public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { ... public synchronized boolean contains(Object value) { if (value == null) { throw new NullPointerException(); }
}
在 Hashtable 類別中，觀察檢查是否存在相同值的 contains() 方法，可以發現它與 Vector 類別一樣，使用了 synchronized 關鍵字。
Collections.synchronizedXXX
讓我們觀察使用 Collections.synchronizedList() 方法建立的 SynchronizedList 類別。
```javascript
static class SynchronizedList
}
觀察 SynchronizedList 類別的方法，可以發現它們都使用了 synchronized 關鍵字。然而，它們使用 synchronized 區塊和互斥鎖來實現同步。所有方法都共用 mutex 物件，因此當一個執行緒進入 synchronized 區塊時，其他方法的 synchronized 區塊都會被鎖定。
同步集合的缺點
在多執行緒環境中，可能需要使用同步集合，但盡可能避免使用其他同步方式。主要原因有兩個。
將多個操作組合在一起使用，如同單一操作
同步集合類別在多執行緒環境中確保同步性。然而，如果需要將多個操作組合在一起使用，如同一個單一操作，就會出現問題。即使使用這些同步集合，也可能無法正常運作。
```javascript
final List
for (int i = 0; i < nThreads; i++) { es.execute(new Runnable() {
}
執行上述程式碼時，如果執行緒 A 執行 remove(0) 操作，而執行緒 B 執行 clear() 操作，就會發生錯誤。因此，需要像以下這樣用 synchronized 區塊將它們括起來。
```javascript synchronized (list) { list.clear(); list.add("888"); list.remove(0); }
效能下降
如果將所有想要使用共用物件的方法都變成 synchronized 方法，或者在方法内部定義相同的 synchronized 區塊，當一個執行緒取得鎖定時，其他執行緒就無法使用所有同步方法，只能處於阻塞狀態。這種重複的現象會導致效能下降。
併發集合
java.util.concurrent 包提供以下併發集合類型，本文僅會討論其中一部分。
- CopyOnWriteArrayList
- 它是 List 類別的子類別，是一種以迭代訪問物件清單的效能為優先的併發集合。
- ConcurrentMap
- 一種併發集合，介面定義了 put-if-absent、replace 和條件移除操作，這些操作在新增項目時， 只有在項目不存在的情況下才會新增。
- ConcurrentHashMap
- 它是 ConcurrentMap 的子類別，一種用於取代 HashMap 並確保併發性的併發集合。
- ConcurrentLinkedQueue
- 一種 FIFO 方式的 Queue，是一種確保併發性的併發集合。如果 Queue 中沒有元素，它會立即返回， 並執行其他操作。
- LinkedBlockingQueue
- 與 ConcurrentLinkedQueue 類似，但如果 Queue 為空，則從 Queue 中取出項目的操作會等待 直到有新的項目新增，反之，如果 Queue 設定了大小，且 Queue 已滿，則新增項目的操作會等待 直到 Queue 有空位。
- ConcurrentSkipListMap, ConcurrentSkipListSet
- 分別是 SortedMap 和 SortedSet 類別的改進版本，它們增強了併發性。
只需將現有的同步集合類別替換為併發集合，就能在不引入其他風險因素的情況下，顯著提升整體效能。
讓我們仔細觀察併發集合與同步集合的對比。
CopyOnWriteArrayList
建立同步 ArrayList 的方法有以下兩種：
- Collections.synchronizedList()
- CopyOnWriteArrayList
Collections.synchronizedList() 是在 JDK 1.2 版本中新增的。此集合對所有讀取和寫入操作都進行了同步， 因此可以認為它是一種缺乏彈性的設計。因此，出現了 CopyOnWriteArrayList 來彌補它的不足。
讀取操作
SynchronizedList 在讀取和寫入操作時，會對自身實例加鎖。然而，CopyOnWriteArrayList 在執行所有寫入操作時， 都會複製原始陣列中的元素，建立一個新的臨時陣列，在臨時陣列上執行寫入操作，最後更新原始陣列。由於這個設計， 讀取操作不會被鎖定，因此效能比 SynchronizedList 更高。
```javascript
public class CopyOnWriteArrayList
}
以上是 get() 方法，由于没有 synchronized，因此不会被锁定。
寫入操作
CopyOnWriteArrayList 在執行寫入操作時，會使用顯式鎖定。最終，兩種集合都會在此操作中被鎖定。這時， CopyOnWriteArrayList 會執行複製陣列的昂貴操作，因此如果執行大量寫入操作，可能會出現效能問題。
```javascript
public class CopyOnWriteArrayList
}
以上是 add() 方法，它使用 synchronized 區塊來鎖定並執行複製陣列的操作。
Iterator
CopyOnWriteArrayList 在提取迭代器時，會基於集合資料在提取時點的資料進行迭代，在迭代過程中， 即使集合中新增或刪除資料，也會在迭代器無關的複製本上反映變化，因此不會影響同步使用。
CopyOnWriteArraySet
建立同步 Set 的方法有以下兩種：
- Collections.synchronizedSet()
- CopyOnWriteArraySet
正如方法名稱所示，CopyOnWriteArraySet 的工作方式與 CopyOnWriteArrayList 幾乎相同， 除了資料結構特性。
讀取操作
```javascript
public class CopyOnWriteArraySet
}
以上是 contains() 方法，可以發現 CopyOnWriteArraySet 在内部定義了 CopyOnWriteArrayList， 並使用 CopyOnWriteArrayList 的方法。
```javascript public boolean contains(Object o) { return indexOf(o) >= 0; }
public int indexOf(Object o) { Object[] es = getArray(); return indexOfRange(o, es, 0, es.length); }
}
觀察 CopyOnWriteArrayList 的 contains() 方法，可以發現它沒有被鎖定。
寫入操作
```javascript
public class CopyOnWriteArraySet
}
add() 方法也借用了 CopyOnWriteArrayList 的方法。
```javascript public boolean addIfAbsent(E e) { Object[] snapshot = getArray(); return indexOfRange(e, snapshot, 0, snapshot.length) < 0 && addIfAbsent(e, snapshot); }
private boolean addIfAbsent(E e, Object[] snapshot) { synchronized (lock) { Object[] current = getArray(); int len = current.length; if (snapshot != current) { // Optimize for lost race to another addXXX operation int common = Math.min(snapshot.length, len); for (int i = 0; i < common; i++) if (current[i] != snapshot[i] && Objects.equals(e, current[i])) return false; if (indexOfRange(e, current, common, len) >= 0) return false; } Object[] newElements = Arrays.copyOf(current, len + 1); newElements[len] = e; setArray(newElements); return true; } }
觀察 addIfAbsent() 方法，可以發現寫入操作時會鎖定並執行複製陣列的操作。因此，CopyOnWriteArraySet 與 CopyOnWriteArrayList 一樣，最好不要執行太多寫入操作。
ConcurrentHashMap
建立同步 HashMap 的方法有以下兩種：
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMap 是一種基於雜湊的 Map，與 HashMap 相同。與 synchronizedMap 相比，它 以更有效的方式確保同步性。
在 Java 8 之前，它使用繼承自 ReentrantLock 的 Segment 來區分區域，並通過鎖定每個區域來確保同步性。
從 Java 8 開始，它採用對每個表格桶進行獨立鎖定的方式。如果要插入一個空的桶，則使用 CAS 演算法 而不是鎖定。其他更改會在每個桶的第一個節點上獲得部分鎖定（synchronized 區塊），以最大限度地 減少執行緒競爭並確保同步性。
讓我們觀察 ConcurrentHashMap 插入新節點的 putVal() 方法的程式碼，以了解它是如何確保同步性的。 請注意，以下示例程式碼是基於 Java 11。
putVal() 方法主要分為以下兩種情況（分支共有四部分）：
- 在空的雜湊桶中插入節點
- 雜湊桶中已存在節點
```javascript final V putVal(K key, V value, boolean onlyIfAbsent) { if (key null || value null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; K fk; V fv; if (tab null || (n = tab.length) 0) tab = initTable(); // (1) else if ((f = tabAt(tab, i = (n - 1) & hash)) null) { // (2) if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value))) break; } else if ((fh = f.hash) MOVED) tab = helpTransfer(tab, f); else if (onlyIfAbsent // check first node without acquiring lock && fh hash && ((fk = f.key) key || (fk != null && key.equals(fk))) && (fv = f.val) != null) return fv; // (3) else { V oldVal = null; synchronized (f) { if (tabAt(tab, i) f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; // (4) if (e.hash hash && ((ek = e.key) key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; // (5) if ((e = e.next) null) { pred.next = new Node<K,V>(hash, key, value); break; } } } // (6) else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } else if (f instanceof ReservationNode) throw new IllegalStateException("Recursive update"); } } ... } } ... }
在空的雜湊桶中插入節點
(1) 要插入一個新節點，會取得對應桶的值（tabAt()），並檢查它是否為空。
```javascript static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); }
(2) 存取節點中包含的 volatile 變數，並將其與原始值（null）進行比較。如果相同，則存儲新的節點。 如果不相同，則返回 for 迴圈。這種方式就是 CAS 演算法。
```javascript static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) { return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); }
使用 CAS 演算法解決原子性和可見性問題，以確保同步性。
雜湊桶中已存在節點
(3) 如果已存在節點，則使用 synchronized 區塊，以確保一次只允許一個執行緒訪問。這時，由於對非空 Node<K, V> 類型的雜湊桶加鎖，因此訪問相同桶的執行緒會處於阻塞狀態。
(4) 用新的節點替換。
(5) 如果發生雜湊衝突，則添加到 Separate Chaing 中。
(6) 如果發生雜湊衝突，則添加到樹中。
參考
預期面試問題和答案
Vector、HashTable 和 Collections.SynchronziedXXX 的缺點是什麼？
Vector、HashTable 和 SynchronziedXxx 類別使用 synchronized 方法或區塊，並共用一個鎖定物件。因此， 當一個執行緒取得鎖定時，其他執行緒將無法使用所有方法，只能處於阻塞狀態。這會導致應用程式效能下降。
SynchronizedList 和 CopyOnArrayList 之間的差異是什麼？
SynchronizedList 在讀取和寫入操作時，會對自身實例加鎖。然而，CopyOnArrayList 在執行寫入操作時， 會對相應的區塊加鎖，並複製原始陣列中的元素，建立一個新的臨時陣列，在臨時陣列上執行寫入操作，最後更新原始 陣列。由於這個設計，讀取操作不會被鎖定，因此效能比 SynchronizedList 更高。但寫入操作會執行複製陣列的 昂貴操作，因此效能比 SynchronizedList 更低。
因此，如果寫入操作比讀取操作少，則使用 CopyOnArrayList 會更有效。
SynchronizedMap 和 ConcurrentHashMap 之間的差異是什麼？
SynchronziedMap 在讀取和寫入操作時，會對自身實例加鎖。然而，ConcurrentHashMap 使用對每個表格桶進行 獨立鎖定的方式。如果要插入一個空的桶，則使用 CAS 演算法而不是鎖定。其他更改會在訪問的桶上獲得部分鎖定 （synchronized 區塊），以最大限度地減少執行緒競爭並確保同步性。
评论0