Вопрос по java, algorithm, hash, hashtable, hashmap – Процесс перефразировки в hashmap или hashtable

13

Как процесс перефразировки выполняется в хэш-карте или хэш-таблице, если размер превышает максимальное пороговое значение?

Все ли пары просто скопированы в новый массив блоков?

EDIT:

Что происходит с элементами в том же сегменте (в связанном списке) после перефразирования? Я имею в виду, они останутся в том же ведре после перепрошивки?

Да .. Вы абсолютно правы :) dharam
@dharam: Таким образом, вывод заключается в том, что элементы, которые находятся в одном и том же сегменте, могут не находиться в одном и том же сегменте после повторной перефразировки, а элементы, которые не находятся в одном и том же сегменте, могут находиться в одном и том же сегменте после повторной компоновки? a Learner
Когда вы переферируете и перемещаете все в новое место (сегмент и т. Д.), Старые элементы также повторно перефразируются и сохраняются в новом сегменте в соответствии с их новыми хэш-кодами. Старое пространство, которое было выделено для хранения элементов, является сборщиком мусора. dharam

Ваш Ответ

3   ответа
17

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

Перефразировка может быть сделана в двух случаях:

When the present m'/n ratio increases beyond the load factor

M'/n ratio falls to a very low value say 0.1

В обоих случаях m & a; текущее количество записей. Кроме того, в обоих случаях требуется смещение существующих записей в большую или меньшую хэш-таблицу.

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

Обратите внимание: перефразировка также выполняется при столкновении. (Это способ обработки столкновений тоже.)

Чтобы добавить больше контекста и подробное обсуждение, пожалуйста, посетите мой блогОсновы хеширования

& quot; можно использовать ту же хеш-функцию & quot ;: как тогда будут использоваться новые сегменты при увеличении количества сегментов?
Так что во время перефразирования мыfree исходный массив, который мы создали в куче после того, как мы создадим новый с другим размером и скопируем все данные из старой хеш-таблицы в новую с измененным размером. Правильный?
@dharam & quot; Обратите внимание: перефразировка также выполняется при столкновении. & quot; Какой порог в этом случае? Как посчитать максимально допустимое количество элементов в корзине?
Я считаю, что новые сегменты (и перефразированная таблица) будут использоваться не иначе, как исходная хеш-таблица, а это означает, что после перефразирования будет работать как обычно с большим количеством сегментов.
Вы получили суть .. В продвинутых реализациях Карт перефразирование - сложный процесс. Это делается в течение определенного периода времени, когда задействованы несколько потоков, чтобы уменьшить амортизированную стоимость одного потока. Таким образом, потребуется достаточно времени, чтобы освободить место для исходного массива. до этого времени оба массива существуют и полностью функциональны :)
6
Hashing – ReHashing and Race condition

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

Для коллекции определен LoadFactor (считается, что он равен 0,75), и это указывает хороший индекс для времени и пространства.

LARGER load factor => lower space consumption but higher lookups SMALLER Load factor => Larger space consumption compare to the required no of elements.

Спецификация Java предполагает, что Хорошее значение коэффициента загрузки равно 0,75.

Следовательно, предположим, что у вас есть максимальное требование хранить 10 элементов в хэше, после чего следует учитывать, что Good Loadfactor .75 = Перефразировка произойдет после добавления 7 элементов в коллекцию. В случае, если ваше требование в этом случае не будет соответствовать 7, тогда перефразировка никогда не произойдет.

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

Условие RACE: при выполнении повторного выделения внутренних элементов, которые хранятся в связанном списке для данного сегмента. Они получают обратный порядок. Предположим, что два потока сталкиваются с состоянием гонки в одно и то же время, тогда есть вероятность, что второй терад может зайти в бесконечный цикл во время обхода, так как порядок был изменен.

Размер по умолчанию Hashmap 16
Прежде чем публиковать ответы, проверьте, как ваш ответ будет выглядеть в окне предварительного просмотра. Вам не хватает нескольких разрывов строк, которые можно исправить, добавив два пробела в конец предыдущих строк.
10

когда количество элементов в карте достигает максимального порогового значения.

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

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

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

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

Подробное объяснение того, как происходит бесконечный цикл в описанном выше случае, можно найти здесь:http://mailinator.blogspot.hu/2009/06/beautiful-race-condition.html

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

Похожие вопросы