Насколько я понимаю, два неравных объекта могут иметь один и тот же хэш-код. Как это будет обрабатываться при добавлении или извлечении из java-файла HashMap?Что произойдет, если два разных объекта имеют один и тот же хэш-код?
Они будут добавлены в одно и то же ведро, и equals() будет использоваться для их различения. Каждое ведро может содержать список объектов с одинаковым хеш-кодом.
Теоретически вы можете вернуть то же целое число, что и хэш-код для любого объекта данного класса, но это будет означать, что вы потеряете все преимущества производительности хэш-карты и, по сути, сохраните объекты в списке.
Не является ли дополнительный хэш, применяемый по умолчанию для Hashmap, чтобы это не происходило, что вводит некоторый дистрибутив? – Ajay
Дополнительная информация о производительности. В java8, когда у нас слишком много неравных ключей, которые дают один и тот же хэш-код (индекс) - тогда количество элементов в хэш-ведре растет выше определенного порога (TREEIFY_THRESHOLD = 8), содержимое этого ковша переключается с использования связанный список объектов Entry для сбалансированного дерева. Это теоретически улучшает производительность наихудшего случая от O (n) до O (log n). –
В HashMap ключи вместе со своими ассоциативными значениями хранятся в узле связанного списка в ведре, а ключи по существу сравниваются в 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 другой узел будет создан в списке ведра, так что, когда вы звоните get("b") вы получите bValue так a.equals(b) является false.Как я могу получить значение if if hashcode? Это даст мне bValue, но я хочу aValue. Это возможно ? – Sanket
В этом случае вы можете использовать IdentityHashMap, где разные объекты с одинаковым хешем считаются разными в зависимости от их идентификаторов.
Если два неравных объекта имеют одно и то же значение хэша, это вызывает столкновение в хеш-таблице, поскольку оба объекта хотят находиться в одном слоте (иногда называемом ведром). Алгоритм хэша должен разрешать такие столкновения. Возвращаясь к исчезающим воспоминаниям о курсах алгоритмов моего колледжа, я помню три основных способа сделать это:
Я думаю, что классы хэша Java используют третий метод, но они могут использовать комбинированный подход. Ключ к хорошему хэшированию заключается в том, чтобы убедиться, что хеш-таблица имеет достаточно большую емкость и писать хорошие хэш-функции. Хэш-таблица, в которой есть только столько ведер, что объекты, которые она удерживает, вероятно, будет иметь конфликты. Обычно вы хотите, чтобы хэш-таблица была примерно в два раза больше, чем количество объектов, которые она хранит. Java HashMap будет расти по мере необходимости, но вы можете дать ему начальную емкость и коэффициент загрузки, если хотите.
Хеш-функция до программиста. Вы можете просто вернуть 0 для всех объектов, но это будет означать, что хеширование (как хранилище, так и извлечение) станет O (n) вместо O (1) ... или в несрочных терминах, это будет медленным.
Ссылка: http://www.coderanch.com/t/540275/java/java/objects-hashcode-HashMap-retrieve-objects
HashMap работает над концепцией хэширования и индексации. Внутренне HashMap сохраняет значения в массиве узлов. Каждый узел ведет себя как LinkedList.
Каждый узел связанного списка имеют 4 значения:
int hashK keyV valueNode<K, V> nextHashMap Внутренняя структура:
При вводе значения в HashMap генерируется первый хэш-код ключа и на основе некоторого алгоритма вычисляется индекс.
Таким образом, наше значение будет храниться в определенном индексе с помощью hashcode, key, value и address следующего элемента.
При извлечении значения из HashMap первый хэш-код будет генерировать и затем индексировать (так же, как и во время вставки). Получая значение из индекса, сначала он проверяет hashcode, если hashcode будет соответствовать, тогда только он будет проверять ключ от Node, используя метод equals. Если ключ будет соответствовать, то он вернет это значение, иначе он будет проверять следующий узел с тем же хэш-кодом.
BTW: Вы можете создать много длинных значений с помощью одного и того же хеш-кода, чтобы попробовать это. 'new Long (n * 0x100000001L)' все имеют hashCode 0 для 'n> = 0' –