Комикс: HashMap с высокой степенью параллелизма

Java задняя часть алгоритм программист

​В прошлом выпуске мы познакомили с основными принципами HashMap, для тех, кто не видел, можете перейти по ссылке ниже:


Комикс: Что такое HashMap?


В этом выпуске мы расскажем о фатальных проблемах, которые могут возникнуть у HashMap в среде с высокой степенью параллелизма.















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


В это время HashMap необходимо расширить свою длину, т. е. выполнитьResize.





На появление Resize влияют два фактора:


1.Capacity

Текущая длина HashMap. В прошлом выпуске я сказал, что длина HashMap равна степени двойки.


2.LoadFactor

Коэффициент загрузки HashMap, значение по умолчанию — 0,75f.



Условия для измерения изменения размера HashMap следующие:


HashMap.Size >= Capacity * LoadFactor







1. Расширение

Создайте новый пустой массив Entry, длина которого вдвое превышает размер исходного массива.



2.ReHash

Пройдите по исходному массиву Entry и повторно хэшируйте все Entry в новый массив. Зачем повторно хэшировать? Потому что после увеличения длины меняются и правила Hash.


Давайте рассмотрим формулу хеша:

индекс = хэш-код (Key) & (Length - 1)


Когда исходная длина массива равна 8, операция хеширования представляет собой операцию И со 111 байтами; новая длина массива равна 16, операция хэширования представляет собой операцию И со 1111 байтами. Результаты хеширования явно отличаются.



HashMap перед изменением размера:




HashMap после изменения размера:




Java-код ReHash выглядит следующим образом:


/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}








Примечание. Следующий контент очень утомляет мозги, пожалуйста, сидите смирно и поддержите своих друзей.



Предположим, что HashMap достиг критической точки Resize. На данный момент есть два потока A и B, которые одновременно выполняют операцию Put на HashMap:







В этот момент достигается условие Resize, и каждый из двух потоков выполняет первый шаг Rezie, то есть расширение:




В это время оба потока достигли шага ReHash. Давайте рассмотрим код для ReHash:



Если в это время поток B переходит к объекту Entry3 сразу после выполнения строки кода в красном поле, поток приостанавливается. Для потока Б:


e = Entry3

next = Entry2


В это время поток A беспрепятственно выполняет ReHash. Когда ReHash завершен, результат выглядит следующим образом (e и next на рисунке представляют две ссылки на поток B):




До этого момента ничего не выглядит не так. Затем поток B возобновляет работу и продолжает выполнять свой собственный ReHash. Состояние потока B только что:


e = Entry3

next = Entry2


Когда приведенная выше строка выполняется, очевидно, что i = 3, потому что результат хеширования потока A для Entry3 также равен 3.



Мы продолжаем выполнять эти две строки, Entry3 помещается в массив потока B с индексом 3, аe указывает на Entry2. В это время точки e и next выглядят следующим образом:


e = Entry2

next = Entry2


Общая ситуация показана на рисунке:





Затем происходит новый раунд цикла, и выполняется строка кода в красном поле:



e = Entry2

next = Entry3


Общая ситуация показана на рисунке:




Затем выполните следующие три строки, чтобы вставить Entry2 в головной узел массива потока B, используя метод вставки заголовка:



Общая ситуация показана на рисунке:




Запускается третий цикл, и снова выполняется код в красном поле:



e = Entry3

next = Entry3.next = null


На последнем шаге, когда мы выполняем следующую строку, наступает момент стать свидетелем чуда:


newTable[i] = Entry2

e = Entry3

Entry2.next = Entry3

Entry3.next = Entry2


Связанный список появляется в цикле!


Общая ситуация показана на рисунке:





На данный момент проблема не возникла напрямую. При вызове Get для поиска несуществующего ключа, а результат Hash этого ключа точно равен 3, поскольку позиция 3 имеет круговой связанный список, программа войдетбесконечный цикл!


Эта ситуация не может не напоминать людям классический вопрос на собеседовании:


Комический алгоритм: как определить, есть ли цикл в связном списке?












1. При вставке слишком большого количества элементов необходимо изменить размер хэш-карты.

HashMap.Size >= Capacity * LoadFactor.


2.Хэш-картаИзменение размера включает два шага: расширение и ReHash. ReHash может формировать кольцо связанного списка в случае параллелизма.






----КОНЕЦ----




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



Категории