2

这是一个组合并发列表多图实现。较低级别的实现会更好，但更复杂。

忽略子列表中的 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;
}
4

1 回答 1

3

我认为你有比赛。我看到的问题是“放置”中的线程无法确定插入的列表没有被删除和/或替换为另一个列表。

观察：

线程 1 调用 put()，并检索（或创建）与键关联的列表。同时，线程 2 从地图中删除了该列表。数据丢失。

我认为您需要添加一个重试循环来验证正确的列表在添加后是否在地图中。

于 2009-06-12T04:55:22.723 回答