Concurrenthashmap java как работает

SynchronizedMap, ConcurrentHashMap и многопоточность

В сегодняшнем посте, я хочу рассказать как работают synchronizeHashMap и ConcurrentHashMap. Как они ведут себя в многопоточный среде и в чём их главное отличие.

Начнём из далека. Что такое HashMap — это key/value хранилище с особой структурой хранения данных. Ключевое слово здесь Hash(Hashing). Hashing — это процесс вычисления hash-функции ключа записываемого значения. Именно по этому параметру, значение кладется в определённой место в hashTable называемое hash bucket.

Слева от 0 до 6, это так называемые hash buckets. Допустим, мы хотим добавить значение в нашу HashMap — put(‘PIG’,29). Первое что происходит, это вычисление hash по ключу. После это значение пропускатеся через фильтр (остаток от деления по модулю 6 в данном примере). Это необходимо для нахождения определённого hash bucket-а(3). Ключ и значение преобразуются в определённую структуру (Entry).

static class Entry implements Map.Entry  final K key; V value; Entry next; final int hash; . //More code goes here >

И добавляются в коллекцию, подобную LinkedList.

По простому HashMap — это массив hash-bucket-ов, которые хранят в себе данные в структуре связанного списка.

Synchronized Map — это потокобезопасная коллекция данных основанная на взаимоблокировках. Что это нам говорит? Все методы, связанные с добавлением/удалением данных, синхронизированы, и для получения значения из одного потока нам необходимо ждать, пока другой поток завершит работу с Map-ой. Разновидностью синхронизированной мапы является HashTable (JDK 1.0).

Для небольшого количества потоков, или где необходимо обезопасить свои данные в конкуретной среде потоков, это работает более менее приемлемо. Но когда необходимо использовать Map в хаотическом мире многопоточного программирования, на сцену выходит ConcurrentHashMap.

ConcurrentHashMap — это тот же HashMap, но рассчитан для работы в многопоточной среде. Главным отличием является то, что ему не нужно иметь синхронизированные блоки данных для доступа или записи информации. То есть ему ненужно блокировать самого себя для других потоков. Но как же тогда он корректно работает в многопоточной среде ? и какие требования выдвигались со стороны разработчиков?

• Потокобезопасность
• Отсутствие блокировок всей таблицы во время доступа к ней
• Желательно, чтобы отсутствовали блокировки таблицы при выполнении операции чтения

В ConcurrentHashMap был введен новый слой абстракции, называемый сегментами (Segment). Другими слова Segment — это массив хэш-таблиц (концептуально).

ConcurrentHashMap делиться на сегменты (по умолчанию 16) при инициализации. Именно сегменты нам позволяют использовать нашу Map-у, множеством потоков без блокирования всего объекта. Другими словами, когда один поток занят пятым сегментом, 15 сегментов свободны для взаимодействия с другими потоками. То есть, происходит блокировка только одного сегмента, а не целого объекта.

Ниже приведена таблица тестов HashTable и ConcurrentHashMap в многопоточной среде.

Threads	ConcurrentHashMap	Hashtable
1	1.00	1.03
2	2.59	32.40
4	5.58	78.23
8	13.21	163.48
16	27.58	341.21
32	57.27	778.41

HashMap и ConcurrentHashMap популярные вопросы на собеседованиях

В моем прошлом превью я рассказывал о том “Как работает HashMap в Java”. Я рассказывал о внутренностях этого класса и о том как они вписываются в концепцию. Но когда меня спросили о HashMap и связанных с ним вещах опрашивающий не остановился только лишь на основной концепции. В ходе дискуссии затрагиваются разные направления, в итоге все сводится к тому либо вы действительно понимаете эти вещи либо нет. В этом превью я постараюсь освятить все основные темы вопросов на собеседованиях: Затрагиваемые темы:

1. Как создать ключ для HashMap?
2. Различия между HashMap и ConcurrentHashMap?
3. Различия между Collections.synchronizedMap(HashMap) и HashMap?
4. Различия между ConcurrentHashMap и Collections.synchronizedMap(HashMap)?
5. Различия между HashMap и HashTable?
6. Различия между HashTable и Collections.synchronizedMap(HashMap)?
7. Влияние случайных/фиксированных значений hashCode() для ключа
8. Использование HashMap в несинхронизированном коде многопоточных приложений

Итак приступим:

1. Создание ключа для HashMap Одной из главных необходимостей является то, что мы должны возвращать значение объекта без ошибок. Правильно? В противном случае непонятно как представить себе структуру данных которую вы проектируете. Это будет невозможно использовать. Чтобы решить, что мы создали хороший ключ мы должны знать как работает HashMap. Работа HashMap построена на принципах Хеширования. Ключ в хэш-коде используются прежде всего в сочетании с методом equals(), для добавления и поиска элемента по HashMap. Если хэш-код объекта меняется на другую пару ключ – значение(key-value), то значение от карты(Map) получить практически невозможно. Данный случай называется утечкой памяти. Чтобы избежать этого ключ и карта должны быть неизменны. Это главная причина того что неизменяемые классы такие как String, Integer и остальные классы подобного рода являются хорошим выбором для создания ключа. Но нужно помнить, что неизменность рекомендована, но не является обязательной. Если ты хочешь сделать ключом изменяемый объект, тогда ты должен убедиться в том, что ключевой объект не меняет хэш-код объекта. Это может быть сделано путем переопределения метода hashCode(). Кроме того ключевые классы должны работать корректно с методами hashCode() и equals() чтобы избежать нежелательного и удивительного поведения при выполнении.
2. Различия между HashMap и ConcurrentHashMap Чтобы лучше визуализировать СoncurrentHashMap нужно рассматривать этот класс как группу HashMap’ов. Чтобы брать и класть значения пар(key-value) в HashMap необходимо вычислить хэш-код и найти правильный сегмент массива Collection.Entry. В ConcurrentHashMap отличие заключается во внутренней структуре для хранения пар key-value. ConcurrentHashMap имеет дополнительную концепцию сегментов. Будет легко понять если представить, что один сегмент эквивалентен одному HashMap[концептуально]. ConcurrentHashMap разделена на множество сегментов [по умолчанию их число равно 16] при инициализации. ConcurrentHashMap похожим потокам примерно (16) получать одновременный доступ к этому сегменту, каждый поток работает одновременно с высоким параллелизмом. Отсюда, если ваша пара key-value хранится в сегменте 10 не нужно блокировать остальные 15 сегментов дополнительно. Такая структура обеспечивает очень высокий уровень параллелизма. Другими словами Concurrent HashMap использует множество замков и каждый замок управляет одним сегментом структуры. Установки данных в определенном сегменте заблокированы для получения в этом сегменте так синхронизированы операции обновления. При получении данных, чтения на лету используется без синхронизации. Если считывать данные на лету то сегмент блокируется и запись производится в синхронизированный блок.
3. Различия между HashMap и Collection.synchronizedMap(HashMap) Все на самом деле просто! HashMap не синхронизирована и Collection.synchronizedMap(HashMap) возвращает упакованные методы HashMap которые являются синхронизированными get и put методами. Фактически, Collection.synchronizedMap(HashMap) внутренне созданного внутреннего класса SunchronizedMap содержащего пары key-value передающиеся в HashMap как аргумент. Такой пример внутренних классов ничего не меняет в первоначальных параметрах HashMap и является полностью независимым.
4. Различия между ConcurrentHashMap и Collections.synchronizedMap(HashMap) Оба являются синхронизированными версиями HashMap c различиями в функциональности и внутренней структуре. Как указано выше ConcurrentHashMap состоит из внутренних сегментов, которые могут рассматриваться как независимые HashMap’ы концептуально. Все эти сегменты могу быть заблокированы отдельными потоками выполняемыми одновременно. Таким образом несколько потоков могу одновременно получить/положить пары key-value из ConcurrentHashMap без блокирования/ожидания друг друга. Из Collections.synchronizedMap() мы получаем синхронизированную версию HashMap и доступ в блокировании образом. Это означает то что если несколько потоков пытаются получить доступ к synchronizedMap в одно и тоже время им будет позволено взять/положить пары key-value по одному синхронизированному образу.
5. Различия между HashMap и HashTable Этот вопрос также является простым. Главное различие в том что HashTable синхронизирован а HashMap нет. Если вас спросят по другим причинам то скажите им что HashTable является наследием класса (часть JDK 1.0) который был произведен в рамках коллекции реализовав интерфейс Map позже. В нем все еще есть вещи которых нету в HashMap такие к примеру как Enumerators(счётчики). Другой незначительной причиной является то что HashMap поддерживает ключ со значением null.(Отображаемый как пустая область памяти). HashTable не поддерживает ключ со значением null и вызывает исключение NullPointerException, при попытке его задать.
6. Различия между HashTable и Collection.synchronized(HashMap) До сих пор вы возможно только знали об их сходствах. Оба являются синхронизированными версиями коллекций. Оба имеют синхронизированные методы внутри. Оба блокируют потоки и заставляют ждать когда можно взять/положить что-либо в коллекцию. Так в чем же различия? Хорошо! Нет основных различий для указанных выше причин. Производительность обоих одинакова. Единственное что различает их это то что HashTable наследуемый класс он получил свои дополнительные функции такие как Enumerators(счетчики).
7. Влияние случайных/фиксированных значений для значения ключа. Влияние в обоих случаях будь то фиксированное значение или случайное будет иметь одинаковый результат и это необъяснимое поведение. Большое значение имеет место в HashMap где поставить пару key-value и где восстановить. Если положение объекта ключа меняется каждый раз то его положение будет рассчитываться каждый раз разными способами. Таким образом объект хранящийся в HashMap будет потерян навсегда с минимальной возможностью восстановления. Поэтому значения ключей являются неизменными и каждый раз возвращают уникальные значения.
8. Использование HashMap в несинхронизированном коде многопоточных приложений. — в худшем случае это может вызвать бесконечный цикл. — Да. — Ты был прав это действительно может привести к бесконечному циклу. Ты спросишь: «Как?» — Хорошо! Вот причина! HashMap имеет концепцию повторного хеширования, когда достигает своего верхнего предела. Это процесс создания новой области памяти и копирования туда существующих элементов. Допустим Поток A положил пару key-value в Map и повторное хеширование началось, в то же время поток Б начал манипулировать с областью памяти используя операцию put(положить). Во время повторного хеширования существует возможность для создания циклической зависимости где элемент находящийся в ссылочном листе [в любой области памяти] может указывать на любой предыдущий узел в ту же область памяти. Это приведет к бесконечному циклу так как код повторного хеширования содержит в себе while(TRUE) который будет работать бесконечно. Посмотрите внимательно на этот код содержащий метод передачи использующий операцию повторного хеширования:

    public Object get(Object key) < Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); Entry e = table[i]; //While true is always a bad practice and cause infinite loops while (true) < if (e == null) return e; if (e.hash == hash && eq(k, e.key)) return e.value; e = e.next; >> 

   Различия между ConcurrentHashMap и Collections.synchronizedMap(Map)

   В многопоточных приложениях на Java часто возникает необходимость использования синхронизированных коллекций для обеспечения целостности данных.

   Алексей Кодов
   Автор статьи
   10 июля 2023 в 16:42

   В многопоточных приложениях на Java часто возникает необходимость использования синхронизированных коллекций для обеспечения целостности данных. Особенно актуальным становится вопрос выбора подходящей реализации карты (Map) для таких задач. В стандартной библиотеке Java представлены три основных варианта: Hashtable, Collections.synchronizedMap(Map) и ConcurrentHashMap.

   Рассмотрим пример. Предположим, есть веб-приложение, которое обрабатывает запросы пользователей. Каждый запрос обрабатывается в отдельном потоке, и все эти потоки имеют доступ к общему ресурсу — карте, которая хранит информацию о пользователях. В этом случае для обеспечения целостности данных необходимо использовать синхронизированную карту.

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

   Основное различие между Collections.synchronizedMap(Map) и ConcurrentHashMap заключается в подходе к синхронизации.

   Collections.synchronizedMap(Map) обеспечивает базовую синхронизацию, блокируя всю карту при выполнении любых операций с ней. Это означает, что в любой момент времени только один поток может выполнять любые операции с картой. Это может привести к проблемам производительности при работе с большим количеством потоков.

   В отличие от этого, ConcurrentHashMap использует более сложный подход к синхронизации. Вместо блокировки всей карты, ConcurrentHashMap разделяет ее на несколько сегментов и блокирует только те сегменты, которые в данный момент изменяются. Это позволяет другим потокам параллельно работать с остальными сегментами карты, что значительно улучшает производительность при работе с большим количеством потоков.

   Таким образом, при выборе между Collections.synchronizedMap(Map) и ConcurrentHashMap, следует учесть количество потоков и объем данных. Если количество потоков небольшое и они редко выполняют операции с картой, то можно использовать Collections.synchronizedMap(Map). Если же потоков много и они активно работают с картой, то лучше выбрать ConcurrentHashMap.

   Руководство по ConcurrentMap

   Карты , естественно, являются одним из самых распространенных стилей коллекции Java.

   И, что важно, HashMap не является потокобезопасной реализацией, в то время как Hashtable обеспечивает потокобезопасность за счет синхронизации операций.

   Несмотря на то, что Hashtable является потокобезопасным, он не очень эффективен. Другая полностью синхронизированная карта, Collections.synchronizedMap, также не демонстрирует высокой эффективности. Если мы хотим потокобезопасности с высокой пропускной способностью при высоком уровне параллелизма, эти реализации не подходят.

   Чтобы решить эту проблему, Java Collections Framework представила ConcurrentMap в Java 1.5 .

   Следующие обсуждения основаны на Java 1.8 .

   2. Конкурентная карта ​

   ConcurrentMap — это расширение интерфейса Map . Он призван предоставить структуру и рекомендации по решению проблемы согласования пропускной способности с потокобезопасностью.

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

   Некоторые реализации по умолчанию переопределены, отключив поддержку нулевого ключа/значения:

   • getOrDefault
   • для каждого
   • заменить все
   • вычислитьифабсент
   • ComputeIfPresent
   • вычислить
   • сливаться

   Следующие API также переопределены для поддержки атомарности без реализации интерфейса по умолчанию:

   • поставитьЕслиОтсутствует
   • удалять
   • заменить (ключ, старое значение, новое значение)
   • заменить(ключ, значение)

   Остальные действия наследуются напрямую и в основном соответствуют Map .

   3. ConcurrentHashMap ​

   ConcurrentHashMap — это готовая к использованию реализация ConcurrentMap .

   Для повышения производительности он состоит из массива узлов в виде сегментов таблиц (ранее они были сегментами таблиц до Java 8 ) под капотом и в основном использует операции CAS во время обновления.

   Блоки таблицы инициализируются лениво при первой вставке. Каждое ведро можно заблокировать независимо, заблокировав самый первый узел в ведре. Операции чтения не блокируются, а конфликты при обновлении сведены к минимуму.

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

   До Java 8 количество требуемых «сегментов» зависело от количества потоков, обращающихся к таблице, так что в большинстве случаев выполняемое обновление для каждого сегмента не превышало одного.

   Вот почему конструкторы, по сравнению с HashMap , предоставляют дополнительный аргумент concurrencyLevel для управления количеством предполагаемых используемых потоков:

    public ConcurrentHashMap( 

    public ConcurrentHashMap(   int initialCapacity, float loadFactor, int concurrencyLevel) 

   Два других аргумента: initialCapacity и loadFactor работали точно так же , как и HashMap .

   Однако, начиная с Java 8 , конструкторы присутствуют только для обратной совместимости: параметры могут влиять только на начальный размер карты .

   3.1. Потокобезопасность​

   ConcurrentMap гарантирует согласованность памяти при операциях ключ/значение в многопоточной среде.

   Действия в потоке до помещения объекта в ConcurrentMap в качестве ключа или значения происходят до действий, следующих за доступом или удалением этого объекта в другом потоке.

   Чтобы подтвердить, давайте посмотрим на несовместимый случай с памятью:

    @Test   public void givenHashMap_whenSumParallel_thenError() throws Exception    MapString, Integer> map = new HashMap>();   ListInteger> sumList = parallelSum100(map, 100);    assertNotEquals(1, sumList  .stream()   .distinct()   .count());   long wrongResultCount = sumList  .stream()   .filter(num -> num != 100)   .count();    assertTrue(wrongResultCount > 0);   >    private ListInteger> parallelSum100(MapString, Integer> map,   int executionTimes) throws InterruptedException    ListInteger> sumList = new ArrayList>(1000);   for (int i = 0; i  executionTimes; i++)    map.put("test", 0);   ExecutorService executorService =   Executors.newFixedThreadPool(4);   for (int j = 0; j  10; j++)    executorService.execute(() ->    for (int k = 0; k  10; k++)   map.computeIfPresent(   "test",   (key, value) -> value + 1   );   >);   >   executorService.shutdown();   executorService.awaitTermination(5, TimeUnit.SECONDS);   sumList.add(map.get("test"));   >   return sumList;   > 

   Для каждого параллельного действия map.computeIfPresent HashMap не обеспечивает согласованного представления того, каким должно быть текущее целочисленное значение, что приводит к противоречивым и нежелательным результатам.

   Что касается ConcurrentHashMap , мы можем получить непротиворечивый и правильный результат:

    @Test   public void givenConcurrentMap_whenSumParallel_thenCorrect()   throws Exception    MapString, Integer> map = new ConcurrentHashMap>();   ListInteger> sumList = parallelSum100(map, 1000);    assertEquals(1, sumList  .stream()   .distinct()   .count());   long wrongResultCount = sumList  .stream()   .filter(num -> num != 100)   .count();    assertEquals(0, wrongResultCount);   > 

   3.2. Нулевой ключ/значение​

   Большинство API , предоставляемых ConcurrentMap , не допускают нулевой ключ или значение, например:

    @Test(expected = NullPointerException.class)   public void givenConcurrentHashMap_whenPutWithNullKey_thenThrowsNPE()    concurrentMap.put(null, new Object());   >    @Test(expected = NullPointerException.class)   public void givenConcurrentHashMap_whenPutNullValue_thenThrowsNPE()    concurrentMap.put("test", null);   > 

   Однако для действий calculate* и merge вычисляемое значение может быть null , что указывает на то, что сопоставление ключ-значение удаляется, если оно присутствует, или остается отсутствующим, если оно отсутствовало ранее .

    @Test   public void givenKeyPresent_whenComputeRemappingNull_thenMappingRemoved()    Object oldValue = new Object();   concurrentMap.put("test", oldValue);   concurrentMap.compute("test", (s, o) -> null);    assertNull(concurrentMap.get("test"));   > 

   3.3. Поддержка потоков​

   Java 8 также обеспечивает поддержку Stream в ConcurrentHashMap .

   В отличие от большинства потоковых методов, массовые (последовательные и параллельные) операции допускают безопасное параллельное изменение. ConcurrentModificationException не будет выброшено, что также относится к его итераторам. Для потоков также добавлено несколько методов forEach* , search и reduce* для поддержки расширенных операций обхода и уменьшения карты.

   3.4. Производительность​

   Под капотом ConcurrentHashMap чем-то похож на HashMap , с доступом к данным и обновлением на основе хеш-таблицы (хотя и более сложной).

   И, конечно же, ConcurrentHashMap должен давать гораздо лучшую производительность в большинстве параллельных случаев для извлечения и обновления данных.

   Давайте напишем быстрый микротест производительности get и put и сравним его с Hashtable и Collections.synchronizedMap , выполнив обе операции 500 000 раз в 4 потоках.

    @Test   public void givenMaps_whenGetPut500KTimes_thenConcurrentMapFaster()   throws Exception    MapString, Object> hashtable = new Hashtable>();   MapString, Object> synchronizedHashMap =   Collections.synchronizedMap(new HashMap>());   MapString, Object> concurrentHashMap = new ConcurrentHashMap>();    long hashtableAvgRuntime = timeElapseForGetPut(hashtable);   long syncHashMapAvgRuntime =   timeElapseForGetPut(synchronizedHashMap);   long concurrentHashMapAvgRuntime =   timeElapseForGetPut(concurrentHashMap);    assertTrue(hashtableAvgRuntime > concurrentHashMapAvgRuntime);   assertTrue(syncHashMapAvgRuntime > concurrentHashMapAvgRuntime);   >    private long timeElapseForGetPut(MapString, Object> map)   throws InterruptedException    ExecutorService executorService =   Executors.newFixedThreadPool(4);   long startTime = System.nanoTime();   for (int i = 0; i  4; i++)    executorService.execute(() ->    for (int j = 0; j  500_000; j++)    int value = ThreadLocalRandom   .current()   .nextInt(10000);   String key = String.valueOf(value);   map.put(key, value);   map.get(key);   >   >);   >   executorService.shutdown();   executorService.awaitTermination(1, TimeUnit.MINUTES);   return (System.nanoTime() - startTime) / 500_000;   > 

   Имейте в виду, что микротесты рассматривают только один сценарий и не всегда хорошо отражают реальную производительность.

   При этом в системе OS X со средней системой разработки мы видим средний результат выборки для 100 последовательных запусков (в наносекундах):

   Hashtable: 1142.45 SynchronizedHashMap: 1273.89 ConcurrentHashMap: 230.2 

   В многопоточной среде, где ожидается, что несколько потоков будут обращаться к общей карте , ConcurrentHashMap явно предпочтительнее.

   Однако, когда карта доступна только для одного потока, HashMap может быть лучшим выбором благодаря своей простоте и высокой производительности.

   3.5. Подводные камни​

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

   Следует иметь в виду еще несколько фактов:

   • результаты методов агрегатного состояния, включая size , isEmpty и containsValue , обычно полезны только тогда, когда карта не подвергается параллельным обновлениям в других потоках:

    @Test   public void givenConcurrentMap_whenUpdatingAndGetSize_thenError()   throws InterruptedException    Runnable collectMapSizes = () ->    for (int i = 0; i  MAX_SIZE; i++)    mapSizes.add(concurrentMap.size());   >   >;   Runnable updateMapData = () ->    for (int i = 0; i  MAX_SIZE; i++)    concurrentMap.put(String.valueOf(i), i);   >   >;   executorService.execute(updateMapData);   executorService.execute(collectMapSizes);   executorService.shutdown();   executorService.awaitTermination(1, TimeUnit.MINUTES);    assertNotEquals(MAX_SIZE, mapSizes.get(MAX_SIZE - 1).intValue());   assertEquals(MAX_SIZE, concurrentMap.size());   > 

   Если одновременные обновления находятся под строгим контролем, совокупный статус все равно будет надежным.

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

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

   • hashCode имеет значение : обратите внимание, что использование многих ключей с точно таким же hashCode() — это верный способ замедлить производительность любой хеш-таблицы.

   Чтобы уменьшить влияние, когда ключи Comparable , ConcurrentHashMap может использовать порядок сравнения ключей, чтобы помочь разорвать связи. Тем не менее, мы должны избегать использования одного и того же hashCode() насколько это возможно.

   • итераторы предназначены для использования только в одном потоке, поскольку они обеспечивают слабую согласованность, а не обход с быстрым сбоем, и они никогда не вызовут исключение ConcurrentModificationException.
   • начальная емкость таблицы по умолчанию равна 16, и она регулируется указанным уровнем параллелизма:

    public ConcurrentHashMap(   int initialCapacity, float loadFactor, int concurrencyLevel)     //.   if (initialCapacity  concurrencyLevel)    initialCapacity = concurrencyLevel;   >   //.   > 

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

   4. ConcurrentNavigableMap ​

   Для случаев, когда требуется порядок ключей, мы можем использовать ConcurrentSkipListMap , параллельную версию TreeMap .

   В качестве дополнения к ConcurrentMap , ConcurrentNavigableMap поддерживает общий порядок своих ключей (в порядке возрастания по умолчанию) и может одновременно перемещаться. Методы, возвращающие представления карты, переопределяются для совместимости с параллелизмом:

   • подкарта
   • головаКарта
   • хвостКарта
   • подкарта
   • головаКарта
   • хвостКарта
   • по убываниюКарта

   Итераторы представлений keySet() и разделители улучшены за счет совместимости со слабой памятью:

   • navigableKeySet
   • набор ключей
   • по убываниюKeySet

   5. ConcurrentSkipListMap ​

   Ранее мы рассмотрели интерфейс NavigableMap и его реализацию TreeMap . ConcurrentSkipListMap можно рассматривать как масштабируемую параллельную версию TreeMap .

   На практике в Java нет параллельной реализации красно-черного дерева. Параллельный вариант SkipLists реализован в ConcurrentSkipListMap , предоставляя ожидаемую среднюю стоимость log(n) времени для операций containsKey , get , put и remove и их вариантов.

   В дополнение к функциям TreeMap операции вставки, удаления, обновления и доступа ключа гарантируются потокобезопасностью. Вот сравнение с TreeMap при одновременной навигации:

    @Test   public void givenSkipListMap_whenNavConcurrently_thenCountCorrect()   throws InterruptedException    NavigableMapInteger, Integer> skipListMap  = new ConcurrentSkipListMap>();   int count = countMapElementByPollingFirstEntry(skipListMap, 10000, 4);    assertEquals(10000 * 4, count);   >    @Test   public void givenTreeMap_whenNavConcurrently_thenCountError()   throws InterruptedException    NavigableMapInteger, Integer> treeMap = new TreeMap>();   int count = countMapElementByPollingFirstEntry(treeMap, 10000, 4);    assertNotEquals(10000 * 4, count);   >    private int countMapElementByPollingFirstEntry(   NavigableMapInteger, Integer> navigableMap,   int elementCount,   int concurrencyLevel) throws InterruptedException     for (int i = 0; i  elementCount * concurrencyLevel; i++)    navigableMap.put(i, i);   >    AtomicInteger counter = new AtomicInteger(0);   ExecutorService executorService  = Executors.newFixedThreadPool(concurrencyLevel);   for (int j = 0; j  concurrencyLevel; j++)    executorService.execute(() ->    for (int i = 0; i  elementCount; i++)    if (navigableMap.pollFirstEntry() != null)    counter.incrementAndGet();   >   >   >);   >   executorService.shutdown();   executorService.awaitTermination(1, TimeUnit.MINUTES);   return counter.get();   > 

   Полное объяснение проблем производительности за кулисами выходит за рамки этой статьи. Подробности можно найти в Javadoc ConcurrentSkipListMap , который находится в папке java/util/concurrent в файле src.zip .

   6. Заключение​

   В этой статье мы в основном представили интерфейс ConcurrentMap и функции ConcurrentHashMap , а также рассказали о том, что ConcurrentNavigableMap требует упорядочения ключей.

   Полный исходный код всех примеров, использованных в этой статье, можно найти в проекте GitHub .

   Похожие публикации:

   1. Nexus что это в программировании
   2. Wolfram mathematica как запустить вычисление
   3. Акции линукс сколько стоят
   4. Как добавить единицы измерения в excel