предисловие

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

HashMapОдин из наиболее часто используемых классов инструментов в нашей повседневной разработке, но использованиеHashMapОдна из самых больших проблем заключается в том, что это небезопасно для потоков. Что, если нам нужна безопасность потоков? Затем вы можете использоватьConcurrentHashMap,ConcurrentHashMapа такжеHashMapФункция в основном та же,ConcurrentHashMapдаHashMapПоточно-безопасная версия .

потому чтоConcurrentHashMapа такжеHashMapсуществуетjdk1.8С точки зрения защиты резьбы, другие проекты очень похожи, поэтому есть много одинаковых дизайнерских идей.Эта статья не будет повторяться слишком много, если вы не понимаетеHashMapОсновной принцип реализации, рекомендуется сначала прочитать эту статьюGold Three Silver Four Help интервью - легко читаемый исходный код HashMapК пониманиюHashMapдизайнерское мышление.

Принцип ConcurrentHashMap

ConcurrentHashMapдаHashMapПоточно-безопасная версия , которая внутренне иHashMapТочно так же это реализовано и в виде массива + связанного списка + красно-черного дерева.

Как добиться потокобезопасности? замок. Но как добавить этот замок? существуетHashTable, находится непосредственно вputа такжеgetдобавлено в методsynchronized, теоретическиConcurrentHashMapВы также можете сделать это, но степень детализации блокировки слишком велика, что сильно повлияет на производительность параллелизма.ConcurrentHashMap Он не использует такой прямой, простой и грубый метод, он использует очень тонкий внутренний дизайн, который значительно снижает конкуренцию блокировок и улучшает производительность параллелизма.

ConcurrentHashMapинициализация в иHashMapТо же, что и в , и емкость также будет приведена к N степени числа 2, и причина этого здесь повторяться не будет.

Какие улучшения были внесены в ConcurrentHashMap в JDK1.8

существуетJDK1.7версия,ConcurrentHashMapОн реализован блокировкой массива + сегмента + сегмента, а его внутренняя часть разделена на сегменты (Segment) множество,Segmentпо наследствуReentrantLockзапирать, запирая по одномуsegmentдля уменьшения детализации блокировки и обеспечения того, чтобы каждыйsegmentПотокобезопасность операций внутри него, что обеспечивает глобальную поточно-безопасность. На картинке нижеJDK1.7в версииConcurrentHashMapПринципиальная схема конструкции:

Но недостатком этого является то, что каждый проходhashТребуется подтвердить местоположение2раз, чтобы найти текущийkeyВ какой слот он должен попасть:

пройти черезhashценность и段数组长度-1Выполните битовую операцию для подтверждения текущегоkeyк какому сегменту он принадлежит, то есть подтвердить, что он находится вsegmentsПоложение массива.
пройти сноваhashценность иtableмассив (т.е.ConcurrentHashMapМассив базовых данных хранилища) length — 1 Выполнение побитовых операций для подтверждения своего сегмента.

Для дальнейшей оптимизации производительности вjdk1.8версия, даConcurrentHashMap Оптимизирован, отменен дизайн сегментного замка и заменен наcasоперация иsynchronizedключевые слова для достижения оптимизации, а идея «разделяй и властвуй» также используется для повышения эффективности расширения во время расширения.JDK1.8серединаConcurrentHashMapструктура хранения иHashMapВ основном то же самое, как показано на следующем рисунке:

Почему ключ и значение не могут быть нулевыми

существуетHashMapсередина,keyа такжеvalueвсе может бытьnull, но вConcurrentHashMapВ Китае это запрещено, почему?

авторDoug LeaЯ сам ответил на этот вопрос в параллельном программировании,nullЗначение легко привести к двусмысленности, если первый вызовget(key)Возвращаемый результатnullтогда мы не можем быть уверены, потому что в то время этоkeyсоответствующийvalueположить его в себяnull, или сказать этоkeyЗначение вообще не существует, что могло бы вызвать двусмысленность, и если в непараллельном программировании можно было бы пойти дальше, вызвавcontainsKeyметод для оценки, но в параллельном программировании нет никакой гарантии, что между двумя методами нет других потоков для измененияkeyзначение, так что это прямо запрещеноnullсуществование ценности.

и авторDoug Leaсама также считает, что если разрешено в таких наборах, какmapа такжеsetждать, чтобы существоватьnullзначение, даже в непараллельных коллекциях, имеет смысл публично разрешать ошибки в программе, что такжеDoug Leaа такжеJosh Bloch(HashMapодин из авторов) был одним из немногих особых мнений по вопросам дизайна, в то время какConcurrentHashMapдаDoug LeaОн был разработан одним человеком, поэтому был забанен напрямуюnullсуществование ценности.

Как ConcurrentHashMap гарантирует безопасность потоков

существуетConcurrentHashMapВ , большое количество идей «разделяй и властвуй» используется для уменьшения детализации блокировок и повышения производительности параллелизма. Его исходный код использует многоcasоперации по обеспечению безопасности, а неHashTableТо же, каким бы методом ни пользоваться, прямо и грубоsynchronizedключевые слова для достижения, следующий анализ принципа, часть иHashMapВ этой статье сходства не повторяются, в этой статье в основном анализируются аспекты безопасности.ConcurrentHashMapдизайн.

Как использовать CAS для обеспечения безопасности инициализации массива

Вот как инициализировать:

Есть очень важная переменнаяsizeCtl, эта переменная важна для понимания всегоConcurrentHashMap Принцип очень важен.

sizeCtlИмеет четыре значения:

sizeCtl<-1указывает на то, что естьN-1потоки выполняют операции масштабирования, такие как-2значит есть2-1нити расширяются.
sizeCtl=-1Заполнитель, указывающий, что массив в данный момент инициализируется.
sizeCtl=0Состояние по умолчанию, указывающее, что массив не был инициализирован.
sizeCtl>0Запишите размер, который необходимо увеличить в следующий раз.

Зная значение этой переменной, описанный выше метод легко понять, и вторая ветвь принимаетCASоперация, потому чтоSIZECTLПо умолчанию0, поэтому, если замена может быть успешной, текущий поток может выполнить операцию инициализации,CASНе удалось, что указывает на то, что другие потоки взяли на себя инициативуsizeCtlизменился на-1. После успешного расширения порог для следующего расширения будет назначен наsc,Прямо сейчасsizeClt.

Как операция put гарантирует видимость элементов массива

ConcurrentHashMap данные, хранящиеся вNodeиспользуется массивvolatileЧтобы изменить, но это может только гарантировать, что ссылка на массив доступна между разными потоками, это не гарантирует, что элементы внутри массива также видны между потоками, поэтому здесь мы определяем, есть ли в индексе элемент, и Он не может доступ напрямую через индексы, так как же к нему обращаться? Исходный код дает вам ответ:

Как видите, здесь черезtabAtметод для получения элемента, в то время какtableAtметод на самом деле являетсяCASработать:

Если текущий элемент узла оказывается пустым, он также передается черезCASработать(casTabAt) для сохранения текущего элемента.

Если текущий элемент узла не пуст, он будет использоватьсяsynchronizedКлючевое слово блокирует текущий узел и выполняет соответствующую операцию настройки:

тонкий способ подсчета

существуетHashMap, вызовputзатем метод пройдет++sizeспособ хранения количества элементов в текущей коллекции, но в параллельном режиме эта операция не безопасна, поэтому ее нельзя сделать таким способом, то можно ли это сделать с помощьюCASоперация по изменениюsizeШерстяная ткань?

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

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

//用来计数的数组，大小为2的N次幂，默认为2
private transient volatile CounterCell[] counterCells;

@sun.misc.Contended static final class CounterCell {//数组中的对象
        volatile long value;//存储元素个数
        CounterCell(long x) { value = x; }
    }

метод подсчета addCount

Далее посмотримaddCountметод:

первый судьяCounterCellЯвляется ли массив пустым, что должно быть здесь, здесьCASоперация заключается вBASECOUNTа такжеbaseCountСравните, если они равны, это означает, что нет других потоков для измененияbaseCount(которыйCASоперация выполнена успешно), вам не нужно использоватьCounterCellмассив, при непосредственном использованииbaseCountсчитать.

еслиCounterCellБыть пустым иCASНе удается, это будет звонитьfullAddCountпуть кCounterCellМассив инициализирован.

метод fullAddCount

Этот метод тоже очень длинный и выглядит более сложным, в котором содержится правильноеCounterCellИнициализация массива и операции присваивания.

Инициализировать массив CounterCell

Проигнорируем его и перейдем непосредственно к логике инициализации:

Есть еще одна важная переменнаяcellsBusy, по умолчанию0, указывающее, что ни один поток в настоящее время не инициализируется или не расширяется, поэтому здесь оценивается, еслиcellsBusy==0,а такжеasНа самом деле впереди стоит поместить глобальную переменнуюCounterCellНазначение массива, причина повторной оценки здесь - подтвердить, изменили ли другие потоки глобальный массив.CounterCell, так что если условие выполнено, оно пройдетCASМодификация операцииcellsBusyдля1, указывая на то, что в данный момент он инициализирует себя, и другие потоки не могут одновременно выполнять операцию инициализации.

Наконец, вы можете видеть, что по умолчанию используется длина2Массив , то есть использование2Расположение места для храненияConcurrentHashMapКоличество элементов.

Как назначается CounterCell

После завершения инициализации, если вы позвоните сноваputметод, то он войдетfullAddCountДругая ветвь метода:

Вот первое решениеCounterCellМассив не пустой, то снова будем определять, что элементы в массиве не пусты, потому что, если элемент пуст, вам нужно инициализироватьCounterCellобъект в массив, и если элемент не пустой, вам нужно толькоCASОперация заменяет количество в элементе.

Так что логика тут тоже очень понятная, инициализацияCounterCellобъект также должен бытьcellBusyЗависит от0изменить на1.

Может ли массив счетчиков CounterCell также расширяться?

Наконец, продолжаем смотреть на другие ветки:

В основном смотрите на ветку в красном поле на рисунке выше.Раз вы заходите в эту ветку, значит все предыдущие ветки не выполняются, а именно:

токCounterCellМассив инициализирован.
В настоящее время прошлоhashрассчитанныйCounterCellЭлемент в индексе массива неnull.
непосредственно черезCASМодификация операцииCounterCellЧисло объектов в указанной позиции индекса в массиве не удалось, что указывает на то, что другие потоки конкурируют за изменение элементов в одном и том же индексе массива.
Текущая операция не соответствует условиям, запрещающим расширение.
Никакие другие темы в настоящее время не создают новыеCounterCellМассивы и текущийCounterCellРазмер массива по-прежнему меньше, чемCPUколичество.

Итак, далее вам нужноCounterCellМассив также расширяется.Метод расширения иConcurrentHashMapТо же, что расширение2, так на самом делеCounterCellЕмкость массива также должна удовлетворять степени N числа 2.

Расширение ConcurrentHashMap

Далее нам нужно вернуться кaddCountметод, потому что этот метод также определяет текущее количество элементов при добавлении количества элементов.ConcurrentHashMapДостиг ли размер порога расширения, и если да, то его необходимо расширить.

Может ли расширение также поддерживать параллелизм?

Что может вас здесь удивить, так это то,ConcurrentHashMapРасширение также поддерживает многопоточность одновременно, как это делается? Вернемся кaddCountспособ узнать.

здесьcheckдлина передаваемого связанного списка,>=0Только начал проверять, нужно ли расширение, и сразу послеwhileЦикл в основном удовлетворяет двум условиям:

Ранее мы упоминали,sizeCtlПри инициализации ему будет присвоен размер следующего расширения (тоже после расширения), поэтому>=sizeCtlУказывает, достигнут ли порог расширения.
tableне дляnullИ текущая длина массива меньше 30-й степени максимального значения 2.

Какая польза от штампа расширения

Когда условия расширения выполняются, сначала вызывается метод для получения штампа расширения. Этот штамп расширения интересен. Чтобы понять штамп расширения, его необходимо проанализировать с двоичной точки зрения.resizeStampМетод в одном предложении, в которомRESIZE_STAMP_BITSЯвляется значением по умолчанию16.

 static final int resizeStamp(int n) {
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }

Ключ здесьInteger.numberOfLeadingZeros(n)Этот метод, исходный код этого метода не будет опубликован, на самом деле этот метод должен делать одну вещь, то естьПолучить наибольшее незначение после преобразования текущих данных в двоичные0передний0номер.

Это предложение немного неуклюже. Давайте возьмем пример.16превалирует,16Преобразованный в двоичный файл10000, высший не-0бит находится в5немного, потому чтоintтип32положение, поэтому он до сих пор27немного, и то и другое0, то результатом этого метода является27(1спереди27индивидуальный0).

потом1 << (RESIZE_STAMP_BITS - 1)В текущей версии это1<<15, то есть получить двоичное число1000000000000000, вот тоже одно дело, поставить это1перейти к16кусочек. Последние два числа проходят|Результат операции должен быть первым16бит1,потому чтоintда32биты, максимум32индивидуальный0, и потому чтоnРазмер по умолчанию16(ConcurrentHashMapразмер по умолчанию), так что на практике самое большее27(11011), то есть старшая цифра числа1Также только на пятом месте, выступая|Большинство операций означает низкое воздействие5битый результат.

27преобразовать в двоичный0000000000000000000000000011011, затем с00000000000000001000000000000000воплощать в жизнь|операции, конечный результат00000000000000010000000000011011,

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

Почему первое расширение считает +2 вместо +1

Первое расширение будет следовать не первым двум условиям, а последнему условию красного прямоугольника, которое проходитCASоперация будетrsсдвинулся влево16(Resize_stamp_shift), затем плюс один2Что это значит? Почему он добавлен?2Шерстяная ткань?

Чтобы ответить на этот вопрос, давайте сначала ответим на другой вопрос, штамп расширения, полученный вышеописанным способом.rsКакая польза? На самом деле этот штамп расширения представляет собой два значения:

высоко16Бит представляет текущую метку расширения, которую можно понимать как эпоху.
Низкий16Биты представляют количество потоков для масштабирования.

Знание этих двух условий легко понять, потому чтоrsв конечном итоге назначаетсяsizeCtl, покаsizeCtlОтрицательные числа представляют собой расширение, в то время какrsсдвиг влево16бит просто так, что старший бит1, в это время низкий16биты все0, а поскольку низкая16бит для записи количества потоков расширения, так что должно быть+1, но вот+2, Причина вsizeCtlсередина-1Это значение было использовано для замены текущего потока, готового к расширению, поэтому, если вы напрямую+1Это будет конфликтовать с битом флага.

Итак, продолжайте возвращаться ко второму красному квадрату на картинке выше, то есть продолжайте в обычном режиме.+1Теперь это требуется только при инициализации первой записи количества потоков расширения.+2.

Условия расширения

Далее продолжаем смотреть на первое красное поле на картинке выше, которое содержит5состояние, а это означает, что5Ни одно из условий не будет расширено:

(sc >>> RESIZE_STAMP_SHIFT) != rsЭто состояние на самом деле имеетbug,существуетJDK12был заменен.
sc == rs + 1Указывает, что последний поток расширения выполняет первую работу, а также означает, что расширение подходит к концу.
sc == rs + MAX_RESIZERSУказывает, что максимальное количество расширенных потоков было достигнуто, поэтому потоки не могут продолжать добавлять к расширению.
После того, как расширение будет завершено,nextTable(новый массив для расширения) установлен вnull.
transferIndex <= 0Указывает, что все индексы, доступные в настоящее время для расширения, выделены, что также представляет собой конец расширения текущего потока.

Как реализовать расширение в условиях множественного параллелизма

Как добиться расширения при множественном параллелизме без конфликтов? Возможно, все думали о принятии идеи «разделяй и властвуй».ConcurrentHashMapИспользуется метод сегментированного расширения, то есть каждый поток отвечает за один сегмент, а минимум по умолчанию равен16, то есть еслиConcurrentHashMapтолько в16slot, то в расширении будет участвовать только один поток. если больше, чем16то по текущемуCPUМаксимальное количество потоков, участвующих в расширении, не будет превышатьCPUколичество.

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

Как обеспечить безопасность переноса данных при расширении

После инициализации нового массива следующим шагом будет подготовка к подтверждению границ. То есть необходимо подтвердить слот, за который отвечает текущий поток, после подтверждения он будет двигаться вперед от большого к меньшему, например, первый поток отвечает за1-16, то соответствующая граница массива0-15, то начнется с последней цифры15Начните перенос данных:

И сравнивались три ключевые переменные:

fwdУзел, это представляет собой узел-заполнитель, наиболее важным является узелhashзначение-1, так что когда-то найденный в узлеhashзначение-1Вы можете знать, что текущий узел был перенесен.
advance: указывает, можно ли переместить следующий слот.Его можно установить на текущий слот только после переноса данных.true
finishing: завершена ли миграция данных.

Зная эти переменные, посмотрите еще раз на приведенный выше код, он обязательно войдет с первого разаwhileцикл, потому что по умолчаниюadvanceдляtrue, целью первого входа в цикл является подтверждение границы, так как граничное значение не было подтверждено, он пойдет сразу на последнюю ветвь, черезCASДействие Подтвердить границу.

Здесь трудно понять прямое выражение границы подтверждения, проиллюстрируем его на примере:

Предположим, что начальное пространство16, то расширенное пространство равно32,В настоящее времяtransferIndexэто старый размер массива16, а во второмifсудить,transferIndexназначен наnextIndex,такnextIndexдля1,а такжеstrideПредставляет количество слотов, за которые отвечает каждый поток, минимум16,такstrideСлишком16,такnextBound= nextIndex > stride ? nextIndex - stride : 0Все могут получить:nextBound=0а такжеi=15Это также текущий поток0-15индексы массива , и от0Начать продвижение, сразу после подтверждения границыadvanceУстановить какfalse, то есть выскочитwhileцикл для выполнения следующей части логики переноса данных.

ПС: потому чтоnextBound=0,такCASОперация на самом делеtransferIndexстал0, что указывает на то, что все индексы текущего расширенного массива были выделены, что также является первой проблемой, которая не удовлетворяет расширению.5состояние.

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

После того, как текущий узел завершит миграцию данных,advanceпеременная будет установлена вtrue, то есть вы можете продолжать продвигать узел, так что он снова войдет в указанное вышеwhileПервые две ветви цикла, нижний индексiдвигаться вперед сноваadvanceУстановить какfalse, затем повторяйте до тех пор, пока нижний индекс не перейдет к0Полная миграция данных.

whileПосле того, как цикл полностью завершится, он войдет в следующееifСудя по красному квадратику, после того, как текущий поток завершит сам миграцию, количество потоков расширения будет уменьшено.После уменьшения снова будет передано условие.Это условие фактически является обратным предыдущему условию перед входом в расширения. Если он установлен, расширение было завершено. , после завершения расширения,nextTableУстановить какnull, поэтому приведенное выше не удовлетворяет разложению4Здесь ставится условие.

Суммировать

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