Вопрос реализации HashMap

Question

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

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

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

например ключ * простой% размер

так как это работает?

Answer 1

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

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

Подробнее в Java SpecialistБюллетени, выпуски 54 и 54b .

Answer 2

Если вы посмотрите на код метода addEntry(..), вы увидите:

if (size++ >= threshold)
   resize(2 * table.length);

При изменении размера вызывается метод transfer(..), который:

Переводит все записи из текущей таблицы в newTable.

Answer 3

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