Когда я должен использовать ConcurrentSkipListMap?
-
06-07-2019 - |
Вопрос
В Java есть ConcurrentHashMap
для лучшего решения многопоточности
. Тогда когда я должен использовать ConcurrentSkipListMap
? Это избыточность?
Являются ли аспекты многопоточности общими для этих двух?
Решение
Эти два класса различаются по нескольким причинам.
ConcurrentHashMap выполняет не гарантирует * время выполнения своих операций в рамках своего контракта. Это также позволяет настраивать определенные коэффициенты загрузки (примерно, количество потоков, одновременно изменяющих его).
ConcurrentSkipListMap , на с другой стороны, гарантирует среднюю производительность O (log (n)) для широкого спектра операций. Он также не поддерживает настройку ради параллелизма. В ConcurrentSkipListMap
также есть ряд операций, которых нет в ConcurrentHashMap
: terraceEntry / Key, floorEntry / Key и т. д. Он также поддерживает порядок сортировки, который в противном случае должен был бы быть рассчитывается (за ощутимый счет), если вы использовали ConcurrentHashMap
.
В основном, разные реализации предоставляются для разных вариантов использования. Если вам нужно быстрое добавление пары ключ / значение и быстрый поиск по одной клавише, используйте HashMap
. Если вам нужен более быстрый обход заказа и вы можете позволить себе дополнительную плату за вставку, используйте SkipListMap
.
* Хотя я ожидаю, что реализация примерно соответствует общим гарантиям хэш-карты для вставки / поиска O (1); игнорирование повторного хеширования
Другие советы
См. Список пропуска для определения структуры данных. ConcurrentSkipListMap хранит карту в естественном порядке ее ключей (или в другом определенном вами порядке ключей). Так что он будет иметь более медленные операции get / put / contains, чем HashMap, но для компенсации этого он поддерживает интерфейсы SortedMap и NavigableMap.
С точки зрения производительности 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);
}
}
}
}
ConcurrentHashMap: когда вы хотите получить / поставить многопоточный индекс на основе индекса, поддерживаются только операции на основе индекса. Получить / положить имеют O (1)
ConcurrentSkipListMap: больше операций, чем просто получить / поставить, например отсортированные верхние / нижние n элементов по ключу, получить последнюю запись, получить / просмотреть всю карту, отсортированную по ключу и т. д. Сложность равна O (log (n)), поэтому ставим производительность не так велика, как ConcurrentHashMap. Это не реализация ConcurrentNavigableMap с SkipList.
Для подведения итогов используйте ConcurrentSkipListMap, когда вы хотите выполнить больше операций с картой, требующих отсортированных функций, а не просто получить и поставить.