Перефразировка в Hashmap [закрыто]
Начальная емкость и коэффициент нагрузки - два параметра, которые влияют наHashMap
представление. Коэффициент загрузки по умолчанию (.75
) предлагает хороший компромисс между временем и пространственными затратами. Более высокие значения уменьшают затраты пространства, но увеличивают стоимость поиска.
Когда элемент добавляется вHashMap
, он присваивается сегментам на основе значения, полученного из егоhashCode
и размер ведраHashMap
, Чтобы идентифицировать ведро для любого, используйте хэш-картуkey.hashCode()
и выполнить некоторую операцию:
Bucket (index) = HashMap.indexFor(HashMap.hash(key.hashCode()),
entryArray.length)
Когда количество записей в хэш-карте превышает произведение коэффициента загрузки и текущей емкости, хэш-карта перефразируется (внутренние структуры данных перестраиваются), так что хэш-карта имеет примерно вдвое больше сегментов.
Когда вы переферируете и перемещаете все в новое место (сегмент и т. Д.), Старые элементы также снова перефразируются и сохраняются в новом сегменте в соответствии с их новыми хэш-кодами. Старое пространство, которое было выделено для хранения элементов, является сборщиком мусора.
Если бы две нити одновременно обнаружили, что сейчасHashMap
необходимо изменить размер, и они оба пытаются изменить размер может привести к состоянию гонки вHashMap
.
О процессе изменения размеровHashMap
, элемент в корзине, который хранится в связанном списке, переворачивается по порядку во время их миграции в новую корзину, потому что JavaHashMap
не добавляет новый элемент в хвост, вместо этого он добавляет новый элемент в голову, чтобы избежать пересечения хвоста. Если произойдет гонка, то вы получите бесконечный цикл.
У меня есть следующие вопросы:
Почему связанный список для каждого сегмента переворачивается по порядку во время миграции в новый сегмент?Как состояние гонки может привести к бесконечной петле?Как увеличение количества сегментов может уменьшить время ожидания поиска?Элементы, которые находятся в одном и том же ведре, все еще будут вместе в одном и том же ведре после перепрошивки?