Что происходит с индексом значений в HasMap, когда он увеличивает свой размер?

Question

Я понимаю, что когда мы объявляем карту следующим образом:

Map <String, Integer> map = new HashMap ();

Коэффициент загрузки по умолчанию равен 0,75, а его размер равен 16, когда области памяти превышают количество из 12 элементов, размер изменяется до 32.

Однако способ, которым карта выбирает индекс корзины, в которую будет помещен объект при использовании функции put, определяется hascode % n, но что происходит, когда размер карты превышает коэффициент загрузки? n больше не имеет того же значения, поэтому, как вы можете найти ранее установленные записи, если при применении hascode % n результирующий индекс не будет таким же, как раньше?

Мой последний вопрос:

как индекс корзины может быть таким же после того, как мы увеличили размер?

Answer 1

Я думаю, что вы спрашиваете: «Как индекс корзины может быть одинаковым после того, как мы увеличили размер?»

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

См. Следующий метод:

/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {

, который вызывается resize.JavaDoc, для которого написано

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

_{Акцент на шахте}

См. Также:

• Процесс перефразировки в hashmap или hashtable
• как и когда выполняется перефразировка в HashMap
• Перефразировка в HashMap в Java

Answer 2

Внутренние данные структуры перестроены. Из документов: https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html:

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

Answer 3

Хеш-карты не сохраняют порядок.Посмотрите на использование LinkedHashMaps вместо.

Answer 4

По умолчанию начальная емкость дублей HashMap равна 16, а коэффициент загрузки равен 0,75f (т. Е. 75% от текущего размера карты). Коэффициент загрузки показывает, на каком уровне емкость HashMap должна быть удвоена.

Например, произведение емкости и коэффициента нагрузки на 16 * 0.75 = 12. Это означает, что после сохранения 12-й пары ключ-значение в HashMap ее емкость становится 32.

для дальнейшего воздействия

Дальнейшее объяснение процесса

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

Обычно значение коэффициента нагрузки составляет 0,75 и начальная емкость по умолчанию значение равно 16. Как только количество элементов достигает или пересекает 0,75 раза емкость, затем происходит перефразировка карты. В этом случае, когда количество элементов 12, затем происходит перефразировка. (0,75 * 16 = 12)

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

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

Если несколько потоков обрабатывают одну и ту же хеш-карту, это может результат в бесконечном цикле.

Подробное объяснение о том, как происходит бесконечный цикл в приведенном выше дело можно найти здесь:

Прочитайте эту статью для более понимания

Если элементы, вставленные в карту, должны быть отсортированы по ключам, то TreeMap может быть использован. Но HashMap будет более эффективным, если порядок ключи не имеют значения.