Java Collection-Within-Collection併發性

Question

我正在試圖製作一個使用set-in-a-map線程安全的類。我不確定what特別需要同步。

該地圖被定義爲類似於Map<Class<K>, Set<V>> map;的東西。以下是地圖被在實現內部使用的方式減少：

與地圖

public void addObject(K key, V object) { 
    getSet(key).add(object); 
} 

public void removeObject(K key, V object) { 
    getSet(key).remove(object); 
} 

public void iterateObjectsInternally(K key, Object... params) 
{ 
    for (V o : getSet(key)) { 
     o.doSomething(params); 
    } 
} 

private Set<V> getSet(K key) { 
    if (!map.containsKey(key)) { 
     map.put(key, new Set<V>()); 
    } 

    return map.get(key); 
} 

問題

至於使用map本身去，唯一的併發問題，我看是在getSet(K)，其中線程上下文可以在containsKey和put之間切換。在這種情況下，可能出現以下情況：

[Thread A] map.containsKey(key)  => returns false 
[Thread B] map.containsKey(key)  => returns false 
[Thread B] map.put(key, new Set<V>()) 
[Thread B] map.get(key).add(object) 
[Thread A] map.put(key, new Set<V>()) => Thread A ovewrites Thread B's object [!] 
[Thread B] map.get(key).add(object) 

現在，我目前使用此實現定期HashMap。而且，如果我正確的話，使用Collection.synchronizedMap()或ConcurrentHashMap只會解決方法級別的併發問題。也就是說，方法將以原子方式執行。這些都沒有提到方法之間相互作用的方式，所以即使使用並行解決方案，以下情況仍然會發生。

ConcurrentHashMap確實有，但是，有方法putIfAbsent。這個缺點是map.putIfAbsent(key, new Set<V>())陳述會在每次請求時創建一個新的集合。這似乎是一個很大的開銷。

另一方面，僅僅將這兩個語句包裝在同步塊中就足夠了嗎？

synchronized(map) { 
    if (!map.containsKey(key)) { 
     map.put(key, new Set<V>()); 
    } 
} 

有沒有比鎖定整個地圖更好的方法？有沒有辦法只鎖定鍵，以便地圖上的其他值的讀取不會被鎖定？

synchronized(key) { 
    if (!map.containsKey(key)) { 
     map.put(key, new Set<V>()); 
    } 
} 

請注意，密鑰不一定是相同的對象（它們是特別Class<?>類型），但是通過哈希碼相等。如果同步要求對象地址相等，則同步key可能無法正常工作。

與套裝

更大的問題問題，我想，如果是一組被正確使用自知。有幾個問題：添加對象，刪除對象和迭代對象。

包裝Collections.synchronizedList列表是否足以避免addObject和removeObject中的併發問題？我假設沒問題，因爲同步封裝將使它們成爲原子操作。

但是，迭代可能是一個不同的故事。對於iterateObjectsInternally，即使設定是同步的，但它仍然必須保持外部同步：

Set<V> set = getSet(key); 
synchronized(set) { 
    for (V value : set) { 
     // thread-safe iteration 
    } 
} 

然而，這似乎是一個可怕的浪費。如果相反，我們更換簡單地使用CopyOnWriteArrayList或CopyOnWriteArraySet作爲定義。由於迭代只會使用數組內容的快照，因此無法從其他線程修改它。另外，CopyOnWriteArrayList對add和remove方法使用重入鎖，這意味着add和remove同樣也是安全的（因爲它們是同步方法）。 CopyOnWriteArrayList似乎很有吸引力，因爲內部結構的迭代次數遠遠超過列表中修改的次數。此外，使用複製的迭代器，無需擔心addObject或removeObject在另一個線程中搞亂了從iterateObjectInternally（ConcurrentModificationExceptions）開始的迭代。

這些並行檢查是否在正確的軌道上和/或足夠嚴格？我是一名有併發編程問題的新手，我可能會錯過某些明顯或過度思考的東西。我知道有幾個類似的問題，但是我的實施看起來不同，不能像我那樣專門提問。

Answer 1

你肯定是在推翻這一點。根據您的併發特性使用簡單的ConcurrentHashMap和ConcurrentSkipListSet/CopyOnWriteArraySet（主要是在迭代需要考慮數據的即時修改時）。使用類似下面的代碼片段作爲GETSET方法：

private Set<V> getSet(K key) { 
    Set<V> rv = map.get(key); 
    if (rv != null) { 
     return rv; 
    } 
    map.putIfAbsent(key, new Set<V>()); 
    return map.get(key); 
} 

當添加/刪除對象，您將需要確定缺少的更新是否是在你的問題域的問題迭代這將確保適當的無鎖併發。如果在迭代過程中添加新對象時不會出現問題，請使用CopyOnWriteArraySet。

第三方面，你想深入瞭解你可以使用什麼樣的粒度w.r.t.併發性，你的要求是什麼，在邊緣情況下什麼是正確的行爲，最重要的是你的代碼必須覆蓋哪些性能和併發特性 - 如果是在啓動時發生兩次，我只是讓所有的方法同步併成爲用它完成。

Answer 2

如果您要經常添加到'set'，CopyOnWriteArrayList和CopyOnWriteArraySet不會變得可行 - 他們使用太多的資源來添加操作。但是，如果你很少添加，並且經常迭代'set'，那麼它們就是你最好的選擇。

Java ConcurrentHashMap將每個映射放入一個存儲桶本身 - 如果缺少操作會在搜索鍵時鎖定列表，然後釋放鎖並放入鍵，則放置該存儲區。絕對使用ConcurrentHashMap而不是地圖。

你的getSet方法本來會很慢，特別是在同步時 - 也許你可以預先加載所有的鍵和集合。

我建議你按照Louis Wasserman的說法行事，看看你的表現是否符合Guava標準。