併發multimap放入和刪除

這是一個由併發列表multimap實現。較低層次的實施會更好，但更復雜。併發multimap放入和刪除

忽略子列表中的O（n）刪除，這是將ConcurrentMap和CopyOnWriteArrayList組合成功能ConcurrentMultimap的正確方法嗎？有沒有未解決的數據競賽？

private final ConcurrentMap<K, Collection<V>> map = ...; // inconsequential 

public boolean put(K key, V value) { 
Collection<V> list = map.get(key); 
if(list != null) { 
    list.add(value); 
    return true; 
} 

// put if absent double check to avoid extra list creation 
list = new CopyOnWriteArrayList<V>(); 
list.add(value); 
Collection<V> old = map.putIfAbsent(key,value); 
if(old != null) old.add(value); 
return true; 
} 

public boolean remove(Object key, Object value) { 
Collection<V> list = map.get(key); 
if(list == null) return false; 

// O(n) remove is the least of my worries 
if(! list.remove(value)) return false; 

if(! list.isEmpty()) return true; 

// double-check remove 
if(! map.remove(key,list)) return true; // already removed! (yikes) 

if(list.isEmpty()) return true; 

// another entry was added! 
Collection<V> old = map.putIfAbsent(key,list); 

if(old == null) return true; 

// new list added! 
old.addAll(list); 
return true; 
}

來源

2009-06-12 Karl the Pagan

當然我沒有檢查list.remove（value）的布爾結果！總是最簡單的東西... – 2009-06-12 05:19:31

我想我正在制定發生規則可以保證正確行爲的原則。 – 2009-06-12 18:03:08

我想你有一場比賽。我看到的問題是，'put'中的線程無法確定插入的列表是否未被刪除，和/或被替換爲另一個列表。

觀察：

線程1調用put（）方法，並檢索（或產生）與鑰匙相關聯的列表。同時，線程2從地圖中刪除該列表。數據丟失。

我想你需要添加一個重試循環來驗證添加到地圖中的右列表是否在地圖中。

來源

2009-06-12 04:55:22 joshng

併發multimap放入和刪除

回答

相關問題