Java ConcurrentSkipListMap: атомарное добавление другого объекта Collection

Question

У меня есть параллельный сценарий, когда мне приходится много писать в отсортированной структуре данных.

По этой причине я думал об использовании 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);

Конечно, это не атомно. Использование метода класса 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, но, поскольку у меня очень высокая скорость записи для этого объекта, я бы предпочел что-то, разработанное специально для него. Что-то вроде collections.defaultdict Python будет, конечно, идеально.

Answer 1

Пара вещей.

Во-первых: самый эффективный способ обработки вашего дела "положить-если-нет" - это выполнить псевдо-двойную проверку

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);
    }