Ответ 1

Эти два класса различаются несколькими способами.

ConcurrentHashMap не гарантирует * время выполнения своих операций как часть его контракта. Он также позволяет настраивать определенные коэффициенты нагрузки (примерно, количество потоков одновременно изменяет его).

ConcurrentSkipListMap, с другой стороны, гарантирует среднюю производительность O (log (n)) при самых разных операциях. Он также не поддерживает настройку для concurrency саке. ConcurrentSkipListMap также имеет ряд операций, которые ConcurrentHashMap не имеет значения: ceilingEntry/Key, floorEntry/Key и т.д. Он также поддерживает порядок сортировки, который в противном случае должен был бы рассчитываться (при значительном расходе), если вы использовали a ConcurrentHashMap.

В принципе, различные варианты реализации предусмотрены для разных вариантов использования. Если вам требуется быстрое добавление одной пары ключей/значений и быстрый поиск одного ключа, используйте HashMap. Если вам требуется более быстрое обход в порядке, и вы можете позволить себе дополнительные затраты на вставку, используйте SkipListMap.

_{* Хотя я ожидаю, что реализация примерно соответствует общим гарантиям хэш-карты O (1) вставки/поиска; игнорирование повторного хеширования}

Ответ 2

Сортировка, навигация и одновременность

См. Пропустить список для определения структуры данных.

ConcurrentSkipListMap сохраняет Map в естественном порядке его ключей (или некотором другом определенном вами порядке ключей). Таким образом, он будет работать медленнее get/put/contains, чем HashMap, но для компенсации этого он поддерживает SortedMap, NavigableMap и ConcurrentNavigableMap интерфейсы.

Ответ 3

С точки зрения производительности, skipList, когда используется в качестве карты, оказывается в 10-20 раз медленнее. Вот результат моих тестов (Java 1.8.0_102-b14, win x32)

Benchmark                    Mode  Cnt  Score    Error  Units
MyBenchmark.hasMap_get       avgt    5  0.015 ?  0.001   s/op
MyBenchmark.hashMap_put      avgt    5  0.029 ?  0.004   s/op
MyBenchmark.skipListMap_get  avgt    5  0.312 ?  0.014   s/op
MyBenchmark.skipList_put     avgt    5  0.351 ?  0.007   s/op

И дополнительно к этому - пример использования, когда сравнение друг с другом действительно имеет смысл. Реализация кеша последних недавно использованных элементов с использованием обеих этих коллекций. Теперь эффективность skipList выглядит как событие более сомнительным.

MyBenchmark.hashMap_put1000_lru      avgt    5  0.032 ?  0.001   s/op
MyBenchmark.skipListMap_put1000_lru  avgt    5  3.332 ?  0.124   s/op

Вот код для JMH (выполняется как java -jar target/benchmarks.jar -bm avgt -f 1 -wi 5 -i 5 -t 1)

static final int nCycles = 50000;
static final int nRep = 10;
static final int dataSize = nCycles / 4;
static final List<String> data = new ArrayList<>(nCycles);
static final Map<String,String> hmap4get = new ConcurrentHashMap<>(3000, 0.5f, 10);
static final Map<String,String> smap4get = new ConcurrentSkipListMap<>();

static {
    // prepare data
    List<String> values = new ArrayList<>(dataSize);
    for( int i = 0; i < dataSize; i++ ) {
        values.add(UUID.randomUUID().toString());
    }
    // rehash data for all cycles
    for( int i = 0; i < nCycles; i++ ) {
        data.add(values.get((int)(Math.random() * dataSize)));
    }
    // rehash data for all cycles
    for( int i = 0; i < dataSize; i++ ) {
        String value = data.get((int)(Math.random() * dataSize));
        hmap4get.put(value, value);
        smap4get.put(value, value);
    }
}

@Benchmark
public void skipList_put() {
    for( int n = 0; n < nRep; n++ ) {
        Map<String,String> map = new ConcurrentSkipListMap<>();

        for( int i = 0; i < nCycles; i++ ) {
            String key = data.get(i);
            map.put(key, key);
        }
    }
}

@Benchmark
public void skipListMap_get() {
    for( int n = 0; n < nRep; n++ ) {
        for( int i = 0; i < nCycles; i++ ) {
            String key = data.get(i);
            smap4get.get(key);
        }
    }
}

@Benchmark
public void hashMap_put() {
    for( int n = 0; n < nRep; n++ ) {
        Map<String,String> map = new ConcurrentHashMap<>(3000, 0.5f, 10);

        for( int i = 0; i < nCycles; i++ ) {
            String key = data.get(i);
            map.put(key, key);
        }
    }
}

@Benchmark
public void hasMap_get() {
    for( int n = 0; n < nRep; n++ ) {
        for( int i = 0; i < nCycles; i++ ) {
            String key = data.get(i);
            hmap4get.get(key);
        }
    }
}

@Benchmark
public void skipListMap_put1000_lru() {
    int sizeLimit = 1000;

    for( int n = 0; n < nRep; n++ ) {
        ConcurrentSkipListMap<String,String> map = new ConcurrentSkipListMap<>();

        for( int i = 0; i < nCycles; i++ ) {
            String key = data.get(i);
            String oldValue = map.put(key, key);

            if( (oldValue == null) && map.size() > sizeLimit ) {
                // not real lru, but i care only about performance here
                map.remove(map.firstKey());
            }
        }
    }
}

@Benchmark
public void hashMap_put1000_lru() {
    int sizeLimit = 1000;
    Queue<String> lru = new ArrayBlockingQueue<>(sizeLimit + 50);

    for( int n = 0; n < nRep; n++ ) {
        Map<String,String> map = new ConcurrentHashMap<>(3000, 0.5f, 10);

        lru.clear();
        for( int i = 0; i < nCycles; i++ ) {
            String key = data.get(i);
            String oldValue = map.put(key, key);

            if( (oldValue == null) && lru.size() > sizeLimit ) {
                map.remove(lru.poll());
                lru.add(key);
            }
        }
    }
}

Ответ 4

В зависимости от рабочих нагрузок ConcurrentSkipListMap может работать медленнее, чем TreeMap с синхронизированными методами, как в KAFKA-8802, если необходимы запросы диапазона.

Ответ 5

ConcurrentHashMap: когда вы хотите получить/поставить многопоточный индекс на основе, поддерживаются только операции на основе индекса. Получить/положить имеют O (1)

ConcurrentSkipListMap: больше операций, чем просто получить/поставить, например отсортировать верхний/нижний n элементов по ключу, получить последнюю запись, получить/просмотреть всю карту, отсортированную по ключу и т.д. Сложность равна O (log (n)), поэтому производительность по положению не так же хорошо, как ConcurrentHashMap. Это не реализация ConcurrentNavigableMap с SkipList.

Подводя итог, используйте ConcurrentSkipListMap, когда вы хотите выполнить больше операций с картой, требующих отсортированных функций, а не просто получить и положить.

Ответ 6

  Тогда когда я должен использовать ConcurrentSkipListMap?

Когда вам (а) нужно сохранять ключи отсортированными и/или (б) нужны функции первой/последней, головы/хвоста и подкарты навигационной карты.

Класс ConcurrentHashMap реализует интерфейс ConcurrentMap, как и ConcurrentSkipListMap. Но если вам также нужно поведение SortedMap и NavigableMap, используйте ConcurrentSkipListMap

ConcurrentHashMap

• Orted отсортировано
• ❌ навигационный
• ✅ одновременно

ConcurrentSkipListMap

• Orted отсортировано
• ✅ навигационный
• ✅ одновременно

Вот таблица, в которой описаны основные функции различных реализаций Map, связанных с Java 11.

Помните, что вы можете получить другие Map реализации и подобные структуры данных из других источников, таких как Google Guava.