并发多图放置和删除 [英] Concurrent multimap put and remove
问题描述
这是由组成的并发列表多图实现。较低级别的实现会更好,但是更复杂。
This is a composed concurrent list multimap implementation. A lower-level implementation would be better, but more complex.
忽略子列表中的O(n)删除,这是否是构成ConcurrentMap和CopyOnWriteArrayList的正确方法进入功能性的ConcurrentMultimap?是否有任何未解决的数据争用?
Ignoring the O(n) removal in the sublist, is this the correct way to compose a ConcurrentMap and CopyOnWriteArrayList into a functional ConcurrentMultimap? Are there any unresolved data races?
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;
}
推荐答案
我认为您参加了比赛。我看到的问题是,处于放置状态的线程无法确定插入的列表没有被删除,和/或未被其他列表替换。
I think you have a race. The problem I see is that a thread that is in 'put' CANNOT be sure that the list being inserted into hasn't been removed, and/or replaced with another list.
观察:
线程1调用put(),并检索(或创建)与键关联的列表。同时,线程2从地图中删除了该列表。数据丢失。
Thread 1 calls put(), and retrieves (or creates) the list associated with the key. Meanwhile, Thread 2 removes that list from the map. Data lost.
我认为您需要添加一个重试循环,以在添加正确的列表后验证其是否在地图中。
I think you'll need to add a retry loop to verify that the right list is in the map after adding to it.
这篇关于并发多图放置和删除的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!