Java HashMap collision

Ответ 1

Нет, первый не переопределяется только потому, что второй имеет тот же hashCode.

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

При извлечении ключа все узлы с тем же hashCode будут сравниваться с предоставленным ключом, пока он не станет равным, тогда его значение будет возвращено (с использованием метода equals).

Если ни один ключ на карте не равен, вы получите null.

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

Ответ 2

Позвольте мне объяснить работу hashmap.

Работа метода put:

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

Работа метода get:

Когда мы передаем объект Key и Value методу put() на Java HashMap, реализация HashMap вызывает метод hashCode для объекта Key и применяет возвращенный hashcode в свою собственную функцию хэширования, чтобы найти местоположение в ведре для хранения объекта Entry, что важно указать что HashMap в Java хранит как ключ, так и объект value как Map.Entry в ведре. Если в ковке найдено более одного объекта Entry, он будет вызывать метод ke.equals каждого node в том же ведро.

Ответ 3

Предполагая, что вы следуете правилам определяющим hashCode и equals, описанный вами сценарий не приведет к потере данные. В лучшем случае производительность со временем ухудшится.

Ответ 4

В хэш-карте Java они могут использовать несколько способов сделать это. Из моего старого класса CS 201 Data Structures обратно в темные века:

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

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

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

Примечание @dystroy сделал комментарий о правиле, что вы не можете иметь две записи на карте с этим соответствием в соответствии с методом equals().