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

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

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

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

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

Сортировка, навигация и параллелизм

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

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

С точки зрения производительности, 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);
            }
        }
    }
}

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

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

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

ConcurrentHashMap

• ❌ Отсортировано
• ❌ Навигация
• ✅ Одновременно

ConcurrentSkipListMap

• ✅ Сортировка
• ✅ Навигация
• ✅ Одновременно

В этой таблице представлены основные функции различных Map в комплекте с Java 11. Нажмите/коснитесь, чтобы увеличить.

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

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

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

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

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