В большинстве интервью интервьюер задает вопросы о структуре данных. Если вы представляете какую-либо компанию, основанную на продукте, то это должны быть темы. Ни одно интервью не может пройти, не касаясь чего-либо из пакета java.util. * И Карт.
Недавно это случилось со мной, когда я давал интервью в Кремниевой долине. На этом этапе я должен признать, что Кремниевая долина любит структуру данных :). Обсуждение началось с пакета утилит и закончилось на ConcurrentHashMap. Хотя все пошло не так, как кажется, интервьюер обладал обширными знаниями о Map, особенно о ConcurrentHashMap :).
Итак, я подумал, что нужно больше вникнуть в него и написать о том, что такого любопытного в ConcurrentHashMap. Зачем это нужно, когда уже есть Hashtable и HashMap? Действительно ли это эффективно с точки зрения производительности и безопасности потоков? Как он справляется с перехешированием?
Сегодня я углублюсь в ConcurrentHashMap и попытаюсь ответить на все эти кипящие вопросы. Прежде чем углубиться, я хотел бы подчеркнуть, что эта реализация ConcurrentHashMap действительна до Java 8. В Java 8 были внесены некоторые изменения и добавлены новые методы, о которых я расскажу в отдельной статье.
Необходимость ConcurrentHashMap, когда уже есть Hashtable и HashMap.
Я предполагаю, что вы должны знать Hashtable и HashMap, прежде чем читать эту статью.
Итак, давайте рассмотрим сценарий, в котором требуется частое чтение и меньше операций записи и в то же время без ущерба для безопасности потоков.
Является ли Hashtable жизнеспособным решением? - Итак, если кто-то знает, как работает Hashtable, сразу скажет НЕТ. Хотя Hashtable является потокобезопасным, но дает низкую производительность в многопоточном сценарии, потому что все методы, включая метод get () Hashtable, синхронизированы, и из-за чего вызов любого метода должен ждать, пока любой другой поток, работающий с хеш-таблицей, завершит свою операцию (get, поставил и тд).
Является ли HashMap жизнеспособным решением? - Hashmap может решить проблему с производительностью, предоставляя параллельный доступ нескольким потокам, одновременно читающим хэш-карту.
Но Hashmap не является потокобезопасным, поэтому что произойдет, если один поток попытается помещает данные и требует повторного хеширования, и в то же время другой поток пытается прочитать данные из Hashmap, он зайдет в бесконечный цикл.
Я думаю, что по вышеуказанным причинам Java представила ConcurrentHashMap в версии 5.0. Поскольку это приносит пользу обоим и служит цели.
Теперь давайте погрузимся в понимание базовой структуры данных, используемой всеми 3. Hashtable и HashMap используют массив и связанный список в качестве структуры данных для хранения данных.
ConcurrentHashMap создает массив поверх него, и каждый индекс этого массива представляет HashMap. (В Java 8 это древовидная структура вместо связанного списка для дальнейшего повышения производительности)
Операции чтения, записи и удаления в ConcurrentHashMap
a) Если посмотреть на приведенную выше диаграмму, ясно, что независимо от того, является ли это операцией вставки или чтения, необходимо сначала определить индекс сегмента, в котором предполагается выполнение операции вставки / чтения.
б) После того, как это идентифицировано, нужно идентифицировать внутреннюю корзину / массив хэш-карты, чтобы найти точную позицию для вставки / чтения.
c) После идентификации сегмента выполните итерацию по связанному списку, чтобы проверить пару «ключ-значение».
i) В случае вставки, если ключ совпадает, замените значение новым, в противном случае вставьте ключ со значением в конец связанного списка.
ii) В случае чтения везде, где совпадают ключи, получить значение и вернуть это значение. если совпадений нет, вернуть null.
iii) В случае удаления, если ключ соответствует, удалите ссылку, соответствующую этому ключу.
Производительность и безопасность потоков в ConcurrentHashMap вместо HashMap / Hashtable
HashMap не синхронизируется и поэтому не обеспечивает безопасность потоков. Напротив, Hashtable синхронизируется и обеспечивает безопасность потоков, но на карту ставится производительность. Операция быстрой записи использует блокировку всей карты, что означает блокировку всего объекта карты.
Итак, если 2 потока пытаются выполнить операцию get () или put () на Hashtable,
Поток T1 вызывает операцию get () / put () в Hashtable и получает блокировку для всего объекта хеш-таблицы.
Теперь, если поток T2 вызывает операцию get () / put (), он должен дождаться, пока T1 завершит операцию get () / put () и снимет блокировку объекта, как показано ниже.
Это делает Hashtable неэффективным, и именно поэтому Java придумала ConcurrentHashMap.
ConcurrentHashMap работает немного по-другому, поскольку он получает блокировку для каждого сегмента, что означает, что вместо блокировки по всей карте у него есть несколько блокировок на уровне сегмента.
Таким образом, 2 потока, работающие с разными сегментами, могут получить блокировку этих сегментов, не мешая друг другу, и могут работать одновременно, поскольку они работают с блокировками отдельных сегментов.
Поток T1 вызывает concurrentHashMap.put (key, value), он получает блокировку, скажем, на сегменте 1, и вызывает метод put.
Поток T2 вызывает concurrentHashMap.put (key, value), он получает блокировку, скажем, на сегменте 15 и вызывает метод put как показано ниже.
Таким образом ConcurrentHashMap улучшает производительность, а также обеспечивает безопасность потоков.
Одновременные операции чтения и записи несколькими потоками в одном или разных сегментах ConcurrentHashMap
Операция чтения / получения: - два потока T1 и T2 могут одновременно считывать данные из одного и того же или другого сегмента ConcurrentHashMap, не блокируя друг друга. .
Операция записи / размещения: - два потока T1 и T2 могут записывать данные в разные сегменты одновременно, не блокируя другой.
Но два потока не могут записывать данные в одни и те же сегменты одновременно. Один должен ждать, пока другой завершит операцию.
Операция чтения-записи: - Два потока могут читать и записывать данные в разных сегментах одновременно, не блокируя друг друга. Как правило, операции извлечения не блокируются, поэтому могут перекрываться с операциями записи (размещения / удаления). Последнее обновленное значение будет возвращено операцией получения, которая является самым последним обновленным значением операцией записи (включая вставку / удаление).
Размер сегментов и уровень параллелизма ConcurrentHashMap
По умолчанию ConcurrentHashMap имеет размер массива сегментов как 16, поэтому одновременно 16 потоков могут помещать данные в карту, учитывая, что каждый поток работает с отдельным индексом массива сегментов.
ConcurrentHashMap имеет конструктор с 3 аргументами, который помогает настроить размер массива сегментов путем определения concurrencyLevel.
ConcurrentHashMap map = new ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
Например :-
ConcurrentHashMap map = new ConcurrentHashMap(100, 0.75f, 10)
Первоначальная емкость карты равна 100, что означает, что ConcurrentHashMap обеспечит наличие места для добавления 100 пар ключ-значение после создания.
LoadFactor равен 0,75f, что означает, что когда среднее количество элементов на карте превышает 75 (начальная емкость * коэффициент загрузки = 100 * 0,75 = 75), в это время размер карты будет увеличен, а существующие элементы на карте будут перехешированы для добавления новой карты большего размера. .
Уровень параллелизма равен 10, это означает, что в любой момент времени размер массива сегментов будет 10 или больше 10, так что 10 потоков могут записывать на карту параллельно.
Но как рассчитать размер массива сегментов -
Размер массива сегментов = 2 в степени x, где результат должен быть ≥ concurrencyLevel (в нашем случае это 10)
Размер массива сегментов = 2 ^ 4 = 16 ≥ 10, что означает, что размер массива сегментов должен быть 16.
Другой пример: -
concurrenyLevel = 8, тогда размер массива сегментов =?
Найти 2 ^ x ≥ 8
2 ^ 3 ≥ 8
Размер массива сегментов будет 8.
Теперь, когда кто-то знает, как рассчитать размер массива сегментов, сразу может возникнуть вопрос, каков будет размер внутренней хэш-карты в сегменте.
Как показано на диаграмме выше, каждый индекс массива Segment представляет собой HashMap, а в HashMap корзина / массив имеет класс Entry [], а в ConcurrentHashMap массив имеет класс HashEntry [] (в Java 8 это древовидная структура вместо связанный список). Таким образом, размер HashEntry [] равен
Размер массива HashEntry [] = 2 ^ x ≥ (initialCapacity / concurrencyLevel)
Например -
ConcurrentHashMap map = new ConcurrentHashMap(64, 0.75f, 8)
Размер массива HashEntry [] = 2 ^ x ≥ 8 (64/8)
Найдите 2 ^ x ≥ 8
2 ^ 3 ≥ 8 ≥ 8
Размер массива HashEntry [] будет 8.
Это означает, что после создания каждого сегмента в ConcurrentHashMap всегда будет 8 пар ключ-значение.
LoadFactor и повторное хеширование
ConcurrentHashMap имеет loadFactor, который решает, когда именно увеличить емкость ConcurrentHashMap, вычисляя порог (initialCapacity * loadFactor) и, соответственно, повторно хешируя карту.
По сути, повторное хеширование - это процесс повторного вычисления хэш-кода уже сохраненных записей (пар ключ-значение), чтобы переместить их на другую карту большего размера при достижении порогового значения коэффициента загрузки. Кроме того, это делается не только для распределения элементов по новой карте длины, но и при слишком большом количестве конфликтов ключей, которые увеличивают количество записей в одном сегменте, так что сложность операций получения и размещения остается равной O (1).
В ConcurrentHashMap каждый сегмент отдельно перефразируется, поэтому нет конфликта между записью потока 1 в индекс 1 сегмента и потоком 2 записи в индекс 4 сегмента.
Например: - Если, скажем, поток 1 помещает данные в индекс массива 3 Segment [] и обнаруживает, что массив HashEntry [] необходимо перехешировать из-за превышения емкости коэффициента нагрузки, он повторно хеширует массив HashEntry [], присутствующий в индексе массива Segment []. Только 3. Массив HashEntry [] в других индексах Сегмента по-прежнему будет неповрежденным, не затронутым и продолжит обслуживать запросы на размещение и получение параллельно.
Я считаю, что это должно помочь в понимании реализации и внутренней работы ConcurrentHashMap.
Поделитесь своими мыслями, отзывами, комментариями и пояснениями. Это поможет мне импровизировать.
Если вам понравился этот пост, вы можете помочь мне поделиться им, порекомендовав его ниже ❤
