Что произойдет, если два разных объекта имеют один и тот же хэш-код?

Ответ 1

Они будут добавлены в один и тот же ковш, и equals() будет использоваться для их различения. Каждое ведро может содержать список объектов с одним и тем же хеш-кодом.

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

Ответ 2

В HashMap ключи вместе со своими ассоциативными значениями хранятся в связанном списке node в ковше, и ключи по существу сравниваются в hashmap с использованием метода equals(), а не с помощью hashcode.

hm.put("a","aValue"); // Suppose hashcode created for key "a" is 209 
hm.put("b","bValue"); // Here hashcode created for key "b" is 209 as well.

• Если a.equals(b) возвращает true, bValue заменит aValue и будет возвращен bValue.
• Если a.equals(b) возвращает false, в списке ведер будет создан другой node, поэтому при вызове get("b") вы получите bValue, так как a.equals(b) есть false.

Ответ 3

HashMap работает над концепцией хэширования и индексирования. Внутренне HashMap сохраняет значения в массиве узлов. Каждый node ведет себя как LinkedList.

Каждый node связанного списка имеет 4 значения:

• int hash
• K key
• V value
• Node<K, V> next

HashMap Внутренняя структура:

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

Таким образом, наше значение будет храниться в определенном индексе с hashcode, ключом, значением и адресом следующего элемента.

При извлечении значения из HashMap первый хэш-код будет генерировать и затем индексировать (так же, как и во время вставки). Получая значение из индекса, сначала он проверяет hashcode, если hashcode будет соответствовать, тогда только он будет проверять ключ от node с помощью метода equals. Если ключ будет соответствовать, то он вернет это значение, иначе он будет проверять следующий node с тем же хэш-кодом.

Ответ 4

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

Ответ 5

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

• Найдите следующий пустой слот в хеш-таблице и поместите туда объект. Плюсы: легко реализовать, минусы: могут привести к кластеризации объектов и ухудшить производительность, емкость может быть превышена.
• У вас есть вспомогательная хеш-функция, когда есть конфликт: Плюсы: обычно быстрая, минус: нужно написать вторую хеш-функцию и все равно столкнуться, а емкость может быть превышена
• Сделать связанный список объектов из конфликтного слота хеш-таблицы. Плюсы/минусы: обычно быстрые для достойной хеш-функции и коэффициенты нагрузки, но могут ухудшаться до линейного поиска в худшем случае.

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

Хеш-функция зависит от программиста. Вы можете просто вернуть 0 для всех объектов, но это будет означать, что хеширование (как хранилище, так и извлечение) станет O (n) вместо O (1)... или в несрочных терминах, это будет медленным.

Ссылка: http://www.coderanch.com/t/540275/java/java/objects-hashcode-HashMap-retrieve-objects