При применении HashMap в многопоточной среде Java в основном имеются следующие варианты: В качестве альтернативы используйте потокобезопасную таблицу java.util.Hashtable. Используйте метод java.util.Collections.synchronizedMap для переноса существующего объекта HashMap в виде потока. -безопасный. В качестве альтернативы используйте класс java.util.concurrent.ConcurrentHashMap, который имеет очень хорошую производительность.
Все вышеперечисленные методы в той или иной степени используют блокировки мьютексов в конкретных деталях реализации. Блокировки мьютексов вызовут блокировку потоков, снизят эффективность работы и могут вызвать ряд проблем, таких как взаимоблокировки и переключение приоритетов.
CAS (сравнение и замена) — это функция, предоставляемая базовым оборудованием, которая может атомизировать операцию оценки и изменения значения.
Атомарные операции в Java
В пакете java.util.concurrent.atomic Java предоставляет нам множество удобных атомарных типов, которые полностью основаны на операциях CAS.
Например, если мы хотим реализовать глобальный публичный счетчик, мы можем:
Скопируйте код кода следующим образом:
счетчик PrivateAtomicInteger =newAtomicInteger(3);
publicvoidaddCounter () {
для(;;) {
inoldValue = counter.get();
intnewValue = oldValue +1;
если (counter.compareAndSet(oldValue, newValue))
возвращаться;
}
}
Среди них метод CompareAndSet проверяет, является ли существующее значение счетчика oldValue. Если да, ему присваивается новое значение newValue. Операция успешна, и возвращается true; в противном случае операция завершается неудачей и возвращается false.
Если при вычислении нового значения счетчика другие потоки изменят значение счетчика, то сравнениеAndSwap завершится неудачно. На этом этапе нам нужно только добавить внешний слой цикла и продолжать пробовать этот процесс, тогда мы в конечном итоге успешно увеличим значение счетчика на 1. (На самом деле, в AtomicInteger уже определены методы ignoreAndGet и decrementAndGet для часто используемых операций +1/-1. В будущем нам нужно будет просто вызывать их)
Помимо AtomicInteger, пакет java.util.concurrent.atomic также предоставляет типы AtomicReference и AtomicReferenceArray, которые представляют атомарные ссылки и массивы атомарных ссылок (массивы ссылок) соответственно.
Реализация связанного списка без блокировки
Прежде чем реализовывать HashMap без блокировки, давайте сначала взглянем на относительно простой метод реализации связанного списка без блокировки.
Возьмем в качестве примера операцию вставки:
Сначала нам нужно найти узел A перед позицией, которую нужно вставить, и узел B за ней.
Затем создайте новый узел C и наведите его следующий указатель на узел B. (См. рисунок 1)
Наконец, сделайте так, чтобы следующий указатель узла A указывал на узел C. (См. рисунок 2)
Однако во время операции возможно, что другие потоки напрямую вставили некоторые узлы в A и B (предполагается, что это D). Если мы не примем никакого решения, это может привести к потере узлов, вставленных другими потоками. (См. рисунок 3) Мы можем использовать операцию CAS, чтобы определить, указывает ли следующий указатель узла A на B при присвоении значения. Если следующий указатель узла A изменится, повторите всю операцию вставки. Примерный код выглядит следующим образом:
Скопируйте код кода следующим образом:
PrivatevoidlistInsert (головка узла, узел c) {
для(;;) {
Узел a = findInsertionPlace(head), b = a.next.get();
c.next.set(б);
если (a.next.compareAndSwap (b, c))
возвращаться;
}
}
(Следующее поле класса Node имеет тип AtomicReference<Node>, который представляет собой атомарную ссылку, указывающую на тип Node.)
Операция поиска в связанном списке без блокировок ничем не отличается от операции поиска в обычном связанном списке. Операция удаления требует найти узел A перед удаляемым узлом и узел B за ним, а также использовать операцию CAS для проверки и обновления следующего указателя узла A, чтобы он указывал на узел B.
Трудности и достижения HashMap без блокировки
HashMap в основном выполняет четыре основные операции: вставку, удаление, поиск и ReHash. Типичная реализация HashMap использует массив, и каждый элемент массива представляет собой связанный список узлов. Для этого связанного списка мы можем использовать упомянутые выше методы операций для выполнения операций вставки, удаления и поиска, но операция ReHash более сложна.
Как показано на рисунке 4, во время процесса ReHash типичной операцией является обход каждого узла в старой таблице, вычисление его положения в новой таблице, а затем перемещение его в новую таблицу. За этот период нам нужно трижды манипулировать указателем:
Следующий указатель точки A на D
Следующий указатель точки B на C
Следующий указатель точки C на E
Эти три операции с указателями должны выполняться одновременно, чтобы обеспечить атомарность операции перемещения. Но нетрудно увидеть, что операция CAS может гарантировать только то, что значение одной переменной проверяется и обновляется одновременно, и не может удовлетворить потребность в проверке и обновлении трех указателей одновременно.
Таким образом, мы могли бы также изменить наше мышление. Поскольку операция перемещения узлов настолько сложна, мы можем постоянно поддерживать все узлы в упорядоченном состоянии, избегая таким образом операции перемещения. В типичной реализации HashMap длина массива всегда остается равной 2i, а процесс сопоставления значения хеша с индексом массива просто выполняет операцию по модулю над длиной массива (то есть только последние i бит двоичного хеш-кода являются сохранен). При ReHash длина массива удваивается до 2i+1, и каждый узел в j-м списке ожерелья старого массива либо перемещается на j-й элемент нового массива, либо перемещается на j+2i-й элемент. элемент в новом массиве и их единственное различие заключается в i+1-м бите значения хеша (если i+1-й бит равен 0, это все равно j-й элемент, в противном случае это j+2-й элемент).
Как показано на рисунке 5, мы располагаем все узлы в порядке возрастания в соответствии с инвертированным порядком значения хеша (например, 1101->1011). Если размер массива равен 8, 2 и 18 находятся в одной группе, 3, 11 и 27 — в другой группе; В начале каждой группы вставляется сторожевой узел для облегчения последующих операций. Чтобы правильно расположить сторожевой узел в начале группы, мы устанавливаем старший бит хэша обычного узла (который становится младшим битом после переворота) в 1, в то время как сторожевой узел не устанавливает этот бит.
Когда массив расширяется до 16 (см. рисунок 6), вторая группа разделяется на группу, содержащую только 3, и группу, содержащую 11 и 27, но относительный порядок между узлами не изменился. Таким образом, нам не нужно перемещать узлы во время ReHash.
Детали реализации
Поскольку копирование массива при расширении занимает много времени, здесь мы принимаем метод разделения всего массива на блоки и ленивого его создания. Таким образом, при обращении к определенному индексу необходимо только оценить, установлен ли блок, в котором находится индекс (если нет, то создать его).
Кроме того, размер определяется как используемый в настоящее время диапазон индексов, и его начальное значение равно 2. Когда массив расширяется, размер необходимо только удвоить; счетчик определяется для представления общего количества узлов, включенных в настоящее время в HashMap ( не считая сторожевых узлов).
Изначально все элементы массива, кроме нулевого элемента, имеют значение NULL. Элемент 0 указывает на связанный список только с одним сторожевым узлом, представляющим начальную точку всей цепочки. Исходное полное изображение показано на рисунке 7, на котором светло-зеленый цвет представляет неиспользуемый в настоящее время диапазон индексов, а пунктирные стрелки представляют блоки, которые логически существуют, но фактически не установлены.
Инициализировать операцию индекса
Считается, что нулевые элементы массива находятся в неинициализированном состоянии. Инициализация определенного нижнего индекса означает установление соответствующего ему сторожевого узла. Инициализация выполняется рекурсивно, то есть, если его родительский индекс не инициализирован, сначала инициализируется его родительский индекс. (Родительский индекс индекса — это индекс, полученный удалением старшего двоичного бита.) Приблизительный код выглядит следующим образом:
Скопируйте код кода следующим образом:
PrivatevoidinitializeBucket (intbucketIdx) {
intparentIdx = BucketIdx ^ Integer.highestOneBit(bucketIdx);
если (getBucket (parentIdx) == null)
инициализироватьBucket (parentIdx);
Узел-макет =newNode();
dummy.hash = Integer.reverse(bucketIdx);
dummy.next =newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy));
}
Среди них getBucket — это инкапсулированный метод для получения содержимого определенного индекса в массиве, и setBucket — то же самое. listInsert вставит данный узел в подходящую позицию, начиная с указанной позиции. Если узел с таким же хешем уже существует в связанном списке, он вернет существующий узел, в противном случае он вернет вновь вставленный узел.
операция вставки
Во-первых, используйте размер HashMap по модулю hashCode ключа, чтобы получить индекс массива, который следует вставить.
Затем определите, является ли нижний индекс нулевым, и, если он равен нулю, инициализируйте нижний индекс.
Создайте новый узел и вставьте его в соответствующую позицию. Обратите внимание, что значение хеш-функции в узле должно быть значением исходного хеш-кода после переворота битов и установки самой низкой позиции на 1.
Добавьте 1 к счетчику количества узлов. Если после добавления 1 узлов становится слишком много, вам нужно только изменить размер на размер * 2, что означает расширение массива (ReHash).
Найти операцию
Найдите индекс узла, который нужно найти в массиве.
Определите, является ли нижний индекс нулевым. Если он равен нулю, будет возвращена ошибка поиска.
Введите связанный список с соответствующей позиции и выполните последовательный поиск до тех пор, пока искомый узел не будет найден или не выйдет за пределы диапазона этой группы узлов.
операция удаления
Найдите индекс узла массива, который следует удалить.
Определите, является ли нижний индекс нулевым, и если он равен нулю, инициализируйте нижний индекс.
Найдите узел, который нужно удалить, и удалите его из связанного списка. (Обратите внимание, что из-за существования сторожевого узла на любой нормальный элемент ссылается только его единственный узел-предшественник. Не бывает ситуации, когда на него ссылаются узел-предшественник и указатель в массиве одновременно, поэтому существует нет необходимости изменять несколько указателей одновременно.)
Уменьшите счетчик количества узлов на 1.