並行マルチマップの配置と削除

Question

これはで構成され、同時リストマルチマップの実装です。下位レベルの実装はより優れていますが、より複雑になります。

サブリストの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; 
} 

Answer 1

私はあなたにレースがあると思います。私が見る問題は、 'put'にあるスレッドは、挿入されているリストが削除されていないこと、および/または別のリストに置き換えられていることを確認できないことです。

は守ってください。

スレッド1つの置くコール（）、および取り出し（または作成）キーに関連付けられたリストを。一方、スレッド2はそのリストをマップから削除します。データが失われました。

リトライループを追加して、右側のリストがマップに追加されたことを確認する必要があると思います。