这是AI翻译的帖子。
选择语言
durumis AI 总结的文章
- Vector、Hashtable、Collections.synchronizedXXX 等同步集合在内部使用 synchronized 关键字来保证同步， 但在执行多个操作或出现性能下降时可能会存在问题。
- java.util.concurrent 包提供了并发集合，如 CopyOnWriteArrayList、ConcurrentMap、 ConcurrentHashMap 等，其性能优于同步集合。
- CopyOnWriteArrayList、ConcurrentHashMap 等并发集合在读取性能方面优于同步集合， 适用于写入操作相对较少的情况。
同步集合
同步集合最具代表性的類別如下：
- Vector
- Hashtable
- Collections.synchronizedXXX
這些類別都使用 synchronized 關鍵字在公開宣告的方法中，以確保一次只允許一個執行緒存取內部的值， 從而保證了同步性。
Vector
public class Vector extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable {
...
public synchronized boolean add(E e) {
modCount++;
add(e, elementData, elementCount);
return true;
}
... 在 Vector 類別中，觀察添加元素的 add() 方法，可以發現 synchronized 關鍵字。也就是說，在 Vector 内部執行元素插入操作時，會確保同步性。
Hashtable
public class Hashtable extends Dictionary
implements Map, Cloneable, java.io.Serializable {
...
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
... 在 Hashtable 類別中，觀察檢查是否存在相同值的 contains() 方法，可以發現它與 Vector 類別一樣，使用了 synchronized 關鍵字。
Collections.synchronizedXXX
讓我們觀察使用 Collections.synchronizedList() 方法建立的 SynchronizedList 類別。
static class SynchronizedList extends SynchronizedCollection
implements List {
final Object mutex;
...
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
... 觀察 SynchronizedList 類別的方法，可以發現它們都使用了 synchronized 關鍵字。然而，它們使用 synchronized 區塊和互斥鎖來實現同步。所有方法都共用 mutex 物件，因此當一個執行緒進入 synchronized 區塊時，其他方法的 synchronized 區塊都會被鎖定。
同步集合的缺點
在多執行緒環境中，可能需要使用同步集合，但盡可能避免使用其他同步方式。主要原因有兩個。
將多個操作組合在一起使用，如同單一操作
同步集合類別在多執行緒環境中確保同步性。然而，如果需要將多個操作組合在一起使用，如同一個單一操作，就會出現問題。即使使用這些同步集合，也可能無法正常運作。
final List list = Collections.synchronizedList(new ArrayList());
final int nThreads = 2;
ExecutorService es = Executors.newFixedThreadPool(nThreads);
for (int i = 0; i < nThreads; i++) {
es.execute(new Runnable() {
public void run() {
while(true) {
try {
list.clear();
list.add("888");
list.remove(0);
} catch(IndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}
}); 執行上述程式碼時，如果執行緒 A 執行 remove(0) 操作，而執行緒 B 執行 clear() 操作，就會發生錯誤。因此，需要像以下這樣用 synchronized 區塊將它們括起來。
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 更高。
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
...
public E get(int index) {
return elementAt(getArray(), index);
}
... 以上是 get() 方法，由于没有 synchronized，因此不会被锁定。
寫入操作
CopyOnWriteArrayList 在執行寫入操作時，會使用顯式鎖定。最終，兩種集合都會在此操作中被鎖定。這時， CopyOnWriteArrayList 會執行複製陣列的昂貴操作，因此如果執行大量寫入操作，可能會出現效能問題。
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
public void add(int index, E element) {
synchronized (lock) {
...
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(es, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index, newElements, index + 1,
numMoved);
}
...
}
} 以上是 add() 方法，它使用 synchronized 區塊來鎖定並執行複製陣列的操作。
Iterator
CopyOnWriteArrayList 在提取迭代器時，會基於集合資料在提取時點的資料進行迭代，在迭代過程中， 即使集合中新增或刪除資料，也會在迭代器無關的複製本上反映變化，因此不會影響同步使用。
CopyOnWriteArraySet
建立同步 Set 的方法有以下兩種：
- Collections.synchronizedSet()
- CopyOnWriteArraySet
正如方法名稱所示，CopyOnWriteArraySet 的工作方式與 CopyOnWriteArrayList 幾乎相同， 除了資料結構特性。
讀取操作
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean contains(Object o) {
return al.contains(o);
} 以上是 contains() 方法，可以發現 CopyOnWriteArraySet 在内部定義了 CopyOnWriteArrayList， 並使用 CopyOnWriteArrayList 的方法。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
Object[] es = getArray();
return indexOfRange(o, es, 0, es.length);
}
private static int indexOfRange(Object o, Object[] es, int from, int to) {
if (o == null) {
for (int i = from; i < to; i++)
if (es[i] == null)
return i;
} else {
for (int i = from; i < to; i++)
if (o.equals(es[i]))
return i;
}
return -1;觀察 CopyOnWriteArrayList 的 contains() 方法，可以發現它沒有被鎖定。
寫入操作
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean add(E e) {
return al.addIfAbsent(e);
} add() 方法也借用了 CopyOnWriteArrayList 的方法。
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() 方法主要分為以下兩種情況（分支共有四部分）：
- 在空的雜湊桶中插入節點
- 雜湊桶中已存在節點
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[] tab = table;;) {
Node 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(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 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 pred = e;
// (5)
if ((e = e.next) == null) {
pred.next = new Node(hash, key, value);
break;
}
}
}
// (6)
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if ((p = ((TreeBin)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()），並檢查它是否為空。
static final Node tabAt(Node[] tab, int i) {
return (Node)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); (2) 存取節點中包含的 volatile 變數，並將其與原始值（null）進行比較。如果相同，則存儲新的節點。 如果不相同，則返回 for 迴圈。這種方式就是 CAS 演算法。
static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); 使用 CAS 演算法解決原子性和可見性問題，以確保同步性。
雜湊桶中已存在節點
(3) 如果已存在節點，則使用 synchronized 區塊，以確保一次只允許一個執行緒訪問。這時，由於對非空 Node
(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 區塊），以最大限度地減少執行緒競爭並確保同步性。
