Могут ли элементы, хранящиеся в одном ковше, переназначаться, чтобы разделить ведра после повторной посылки?

Question

До сих пор я знаю, что после перезагрузки в HashMap все записи перерисовываются с новой длиной таблицы. Но я хочу знать, что произойдет, когда у меня будут столкновения.

например.

Map<String, String> map = new HashMap<>(5); 
map.put("a", "ape"); 
map.put("b", "bird"); 
map.put("c", "chicken"); 

Пусть они имеют разные hashcodes, но "b" и "c" сохраняются в том же ведре после внутреннего хэширования.

Теперь я вставить четвертую запись, чтобы достигнуть коэффициента нагрузки поэтому перефразируя таблицу:

map.put("d", "dynamite"); 

Могут ли записи с соударений храниться в отдельных ведер, или они всегда будут вместе (в обратном порядке по из того, что я читал) ?.

Я полагаю, что ответ на заголовок - нет, потому что я получаю такое же внутреннее хеширование для "b" и "c", но я не уверен.

Answer 1

Существует два способа просмотра столкновений здесь.

Один из двух объектов, возвращающих то же значение от hashCode(). В этом случае они попадают в одно и то же ведро независимо от размера массива хеш-таблицы.

Другой случай, когда два объекта имеют разные хэш-коды, но в конечном итоге в том же ведро из-за размера массива составляет менее уникальных значений 2 этой hashCode() может вернуться в теории. Обычно значение исходного хэш-кода будет приниматься по модулю размера массива и используется для поиска правильного ведра для записи. Предположим, что размер начального массива равен 16, и у вас есть объект A с хеш-кодом 3 и объектом B с хеш-кодом 19. Поскольку 19% 16 == 3, объект A и объект B будут попадать в одно и то же ведро. Если теперь вы измените размер массива на 18, объект A окажется в ведре 3% 20 == 3, но объект B окажется в ковше 19% 20 == 19. Итак, теперь они находятся в разных ведрах, которые отвечают на вопрос, заданный в название с «да».

Answer 2

Они могут быть сохранены в одной и то же ведре или в разных ковшах на основе остается ли число, представленное HashCode% емкости expresssion той же пост Обточки или нет.

E.g. скажем, хэш-коды, возвращаемые объектами String «b» и «c», равны 27 и 32. Ваша начальная емкость равна 5. Таким образом, выражение hashcode% capacity равно 2 и 2 для «a» и «b». Поэтому они оба будут храниться в одном ковше. Теперь после перезагрузки (когда количество записей в хеш-таблице превышает произведение коэффициента загрузки и текущей емкости), новая емкость примерно удваивается. Предположим, что новая емкость равна 10. Таким образом, выражение hashcode% capacity теперь будет равно 7 и 2 соответственно. Это означает, что теперь два объекта будут сохранены в отдельных перекладинах.

Теперь рассмотрим следующий случай. Скажем, хэш-коды, возвращенные 2-мя объектами, составляют 27 и 37. В этом случае выражение hashcode% емкость равно 2 и 2 перед хэшированием и 7 и 7 после хэширования. Поэтому они все равно будут храниться в одном ведре.