java - Java ConcurrentSkipListMap:以原子方式添加另一个Collection对象

我有一个并发场景，其中我必须向已排序的数据结构写很多东西。

因此，我考虑过使用ConcurrentSkipListMap。我的定义是这样的：ConcurrentSkipListMap<K, List<V>>，当插入第一个元素时，这当然使得管理List<V>的插入非常困难。

即：

List<V> list = map.get(k);
if (list == null) {
    list = new LinkedList<V>();
    map.put(list);
}
list.add(v);

当然这不是原子的。使用class putIfAbsent()方法会使它很笨拙且效率低下：

List<V> newElement = new LinkedList<V>();
List<V> previous = map.putIfAbsent(k, newElement);
if (previous != null) {
    previous.add(v);
} else {
    newElement.add(v);
}

一种方法当然是创建我自己的锁并保护普通的TreeMap，但是由于我对此对象有很高的写入率，因此我希望为其专门设计一些东西。当然，像python的collections.defaultdict这样的东西是完美的。

最佳答案

几件事。

第一：处理缺席案件的最有效方法是进行伪双重检查

public void add(Object key, Object val) {
    List list = map.get(key);
    if (list == null) {
        list = new LinkedList();
        List temp = map.putIfAbsent(list);
        if (temp != null)
            list = temp;
    }
    list.add(val);
}

对于不存在的情况，这是最有效的方法。

第二：添加到列表中仍然存在并发问题。您可能需要在放入地图之前将LinkedList包裹在Collections.synchronizedList()中。

public void add(Object key, Object val) {
        List list = map.get(key);
        if (list == null) {
            list = Collections.synchronizedList(new LinkedList());
            List temp = map.putIfAbsent(list);
            if (temp != null)
                list = temp;
        }
        list.add(val);
    }