Как выполняется процесс перезаписи в хэш-карте или хеш-таблице, когда размер превышает значение maxthreshold?
Все пары просто скопированы в новый массив ведер?
EDIT:
Что происходит с элементами в одном и том же ведре (в связанном списке) после переигрывания? Я имею в виду, останутся ли они в одном ковше после повторного рейса?
Максимальный порог в вопросе называется коэффициентом нагрузки.
Желательно иметь коэффициент нагрузки около 0,75. Коэффициент нагрузки определяется как (m/n), где n - это общий размер хеш-таблицы, а m - это предпочтительное количество записей, которое может быть вставлено до того, как потребуется увеличение размера базовой структуры данных.
Повторная обработка может быть выполнена в двух случаях:
Когда существующее отношение m '/n увеличивается за пределами коэффициента нагрузки
Отношение M '/n падает до очень низкого значения, скажем 0,1
В обоих случаях m '- это текущее количество записей. Кроме того, оба случая требуют смещения настоящих записей в большую или меньшую хэш-таблицу.
В контексте вопроса rehashing - это процесс применения хэш-функции к записям, чтобы переместить их в другую хеш-таблицу. Можно использовать хеш-функцию, которая использовалась ранее или вообще использовать новую функцию.
Обратите внимание: повторное воспроизведение также выполняется при столкновении. (Это способ обработки столкновений тоже.)
Чтобы добавить еще несколько контекстов и подробное обсуждение, посетите мой блог Основы хэширования
Перестановка хэш-карты выполняется, когда количество элементов на карте достигает максимального порогового значения.
Обычно значение коэффициента загрузки равно 0,75, а начальное значение емкости по умолчанию - 16. Как только количество элементов достигнет или пересечет 0,75-кратную пропускную способность, происходит перекраска карты. В этом случае, когда число элементов равно 12, происходит повторное воспроизведение. (0,75 * 16 = 12)
При повторном вызове может быть использована новая хеш-функция или даже одна и та же хеш-функция, но ведра, в которых присутствуют значения, могут измениться. В основном при повторном обращении количество ковшей приблизительно удваивается, и, следовательно, новый индекс, в который должно быть внесено значение, изменяется.
Во время перезаписи связанный список для каждого ведра меняет порядок. Это происходит потому, что HashMap не добавляет новый элемент в хвост, а добавляет новый элемент в голову. Поэтому, когда происходит повторная запись, он считывает каждый элемент и вставляет его в новое ведро в голове, а затем продолжает добавлять следующие элементы со старой карты в начале новой карты, что приводит к изменению связанного списка.
Если несколько потоков обрабатывают одну и ту же карту хэша, это может привести к бесконечному циклу.
Подробное объяснение того, как бесконечный цикл встречается в приведенном выше случае, можно найти здесь: http://mailinator.blogspot.hu/2009/06/beautiful-race-condition.html
Если элементы, вставленные в карту, должны быть отсортированы по клавишам, то можно использовать TreeMap. Но HashMap будет более эффективным, если порядок ключей не имеет значения.
В основном, при создании коллекции хеш-карт присваивайте ей емкость по умолчанию (2 ^ 4, т.е. 16.). На более позднем этапе, когда элементы добавляются на карту, и после определенного этапа, когда вы приближаетесь к своей первоначальной определенной емкости, требуется повторное хеширование для сохранения производительности.
Для коллекции определен LoadFactor (считается, что он равен 0,75), и это указывает хороший индекс для времени и пространства.
Спецификация Java предполагает, что Хорошее значение коэффициента загрузки равно 0,75.
Следовательно, предположим, что у вас есть максимальное требование хранить 10 элементов в хэше, после чего следует учитывать, что Good Loadfactor.75 = Перефразировка произойдет после добавления 7 элементов в коллекцию. В случае, если ваше требование в этом случае не будет соответствовать 7, тогда перефразировка никогда не произойдет.
Если в хэш-карте действительно нет большого количества элементов, которые будут сохранены, то всегда полезно создать HashMap с достаточной емкостью; это более эффективно, чем автоматическая перефразировка.
Условие RACE: при выполнении повторного выделения внутренних элементов, которые хранятся в связанном списке для данного сегмента. Они получают обратный порядок. Предположим, что два потока сталкиваются с состоянием гонки в одно и то же время, тогда есть вероятность, что второй терад может зайти в бесконечный цикл во время обхода, так как порядок был изменен.