1. Диаграммы иерархии хеш-таблицы и параллельной HashMap

2. свойства HashTable и параллельного HashMap

Несмотря на то, что все свойства HashTable и Concurrent HashMap схожи, но «Если это потокобезопасная высокопараллельная реализация, то рекомендуется использовать Concurrent HashMap вместо Hashtable». почему .. ???

  • Хотя и Concurrent HashMap, и Hashtable являются потокобезопасными. Но хеш-таблица имеет низкую производительность при использовании многопоточности.
  • Если один поток позволяет выполнять какие-либо операции (положить или получить), другой поток должен и должен ждать, пока операция не будет завершена потоком, который работает с хеш-таблицей. .

Чтобы четко понять эти пункты, нам необходимо понять внутреннюю работу HashTable и ConcurrentHashMap. Для лучшего понимания внутренней работы HashTable и ConcurrentHashMap. пройти внутреннюю работу HashMap



Hash Map и ее реализация на Java
1. Иерархия HashMap в Java medium.com



3. Внутренняя работа HashTable

Эта диаграмма похожа на внутреннюю реализацию HashMap, но Hashtable синхронизируется и обеспечивает безопасность потоков, как concurrentHashMap, но с точки зрения производительности операция записи Hashtable использует блокировка всей карты, что означает блокировку всего объекта карты.

Пример для лучшего понимания

Поток T1 вызывает операцию get () / put () для Hashtable и получает блокировку для всего объекта хеш-таблицы.

Теперь, если поток T2 вызывает операцию get () / put (), он должен дождаться, пока T1 завершит операцию get () / put () и снимет блокировку объекта. .

Чтобы преодолеть эту неэффективность с помощью HashTable Java представляет параллельную HashMap

4. Внутренняя работа Concurrent HashMap

4.1 Блокировка потоков на ConcurrentHashMap для многопоточной среды

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

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

Одновременные операции чтения и записи несколькими потоками в одном или разных сегментах ConcurrentHashMap

Операция чтения / получения: - Два потока T1 и T2 могут одновременно считывать данные из одного или разных сегментов ConcurrentHashMap, не блокируя каждый Другие.

Операция записи / размещения: - Два потока T1 и T2 могут записывать данные в разных сегментах одновременно без блокируя другого.

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

Операция чтения-записи: - Два потока могут читать и записывать данные в разных сегментах одновременно время, не блокируя друг друга.

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

Поток T1 вызывает concurrentHashMap.put (ключ, значение), он получает блокировку, скажем, для сегмента 1 и вызывает put метод.

Поток T2 вызывает concurrentHashMap.put (ключ, значение), получает блокировку, скажем, для сегмента 15 и вызывает метод put, как показано на диаграмме выше.

Таким образом, благодаря этой возможности мы не столкнулись с исключением одновременной модификации

5. Глубокое понимание того, как будет осуществляться добавление и добавление в Concurrent HashMap

5.1 Конструктор для параллельной HashMap

ConcurrentHashMap map = new ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)

segment array size = 2 to the power x = concurrency level
Bucket array size inside the segment = 2 ^ x ≥ (initialCapacity / concurrencyLevel)

Если мы зададим уровень параллелизма или initialCapacity = 10 , и он будет рассматривать уровень параллелизма или initialCapacity как 16 (следующие 2 после степени x равны 16)

Количество потоков, обрабатываемых одновременно в concurrentHashMap, равно уровню параллелизма

5.2 Операции PUT и GET в параллельной HashMap

ШАГ-1: вычисление хэш-кода (хеш-индекса для сегмента (массива), который присутствует внутри сегмента) для ключа

ШАГ-2: Подготовка HashEntry ‹K, V›

ШАГ-3: Расчет сдвига сегмента и маски сегмента с помощью уровня параллелизма, предоставленного в конструкторе

ШАГ-4: Рассчитайте уровень сегмента (индекс массива сегментов)

ШАГ 5: ПОСТАВИТЬ и ПОЛУЧИТЬ

у нас есть hashindex (массив внутри сегмента), ключ, значение, индекс сегмента

ПОЛОЖИЛ :

На основе индекса сегмента, HashEntry ‹K, V› (узел) помещается в определенный сегмент, затем на основе hashindex, HashEntry ‹K, V› (узел) помещается в массив внутри сегмента, который аналогичным образом например, как узлы размещаются внутри сегмента в HashMap

ПОЛУЧАТЬ:

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

6. LoadFactor и повторное хеширование

  1. ConcurrentHashMap имеет loadFactor, который решает , когда именно увеличивать емкость ConcurrentHashMap, вычисляя порог (initialCapacity * loadFactor) и, соответственно, повторно хешируя карту.
  2. По сути, повторное хеширование - это процесс повторного вычисления хэш-кода уже сохраненных записей (пар "ключ-значение"). , чтобы переместить их на другую карту большего размера при достижении порогового значения коэффициента загрузки корзины внутри сегмента. Кроме того, это делается не только для распределения элементов по новой карте длины, но и при слишком большом количестве конфликтов ключей, которые увеличивают количество записей в одном сегменте, так что сложность операций получения и размещения остается равной O (1).

В ConcurrentHashMap каждый сегмент отдельно перефразируется, поэтому нет конфликта между записью потока 1 в индекс 1 сегмента и записи потока 2 в индекс 4 сегмента.

Пример: - Если, скажем, поток 1 помещает данные в массив Segment [] с индексом 3 и обнаруживает, что массив HashEntry [] должен быть перехеширован из-за превышения емкости коэффициента нагрузки, он повторно хеширует массив HashEntry [], присутствующий в Только индекс массива Segment [] 3. Массив HashEntry [] в других индексах Сегмента по-прежнему будет неповрежденным, не затронутым и продолжит обслуживать запросы на размещение и получение параллельно.

7. Методы параллельной HashMap не являются атомарными

  1. В приведенной выше программе я взял ConcurrentHashMap, состоящий из имени стороны в качестве ключа и количества голосов в качестве значения.
  2. Я взял 5 цепочек и Каждая ветка голосует по 1000 голосов каждой партии, т. Е. Соответствует нашим ожиданиям, после ведение всех цепочек каждая партия должна и должна иметь 5000 голосов
  3. Но Я запускаю эти 5 потоков в многопоточной среде. Благодаря этому я получил другой результат, как показано как показано ниже

Причина: из-за общей изменчивости переменных голосов в методе polling () результат отличается. если методы ConcurrentHashMap имеют атомарную природу, мы не сталкивались с этой проблемой.

Решение :

Я использовал AtomicLong Variable вместо Long, чтобы уйти от shared-Mutability. мы также можем использовать другие подходы, такие как синхронизированный блок, для решения вышеуказанной проблемы.

8. Временные сложности и тест производительности

Временные сложности

Тест производительности

  1. Я провел тест производительности между HashTable, ConcurrentHashMap и HashMap с синхронизированными блоками и Collections.synchronizedMap (hashMap)
  2. Я взял Пул потоков из 5 потоков, и каждый поток может выполнять 5,00 000 операций вставки и получения. Я сделал это 5 раз и каждый раз вычислял время выполнения для каждого пула потоков и, наконец, Я рассчитал среднее время

Результат :