How does a Java HashMap handle different objects with the same hash code?
Как Java HashMap обрабатывает разные объекты с одним и тем же хэш-кодом?
Насколько я понимаю, я думаю:
Совершенно законно, чтобы два объекта имели один и тот же хэш-код.
Если два объекта равны (с использованием метода equals()), то они имеют одинаковый хэш-код.
Если два объекта не равны, то они не могут иметь один и тот же хэш-код
Я прав?
Теперь, если я прав, у меня следующий вопрос: HashMap внутренне использует хэш-код объекта. Итак, если два объекта могут иметь один и тот же хэш-код, то как HashMap может отслеживать, какой ключ он использует?
Кто-нибудь может объяснить, как HashMap внутренне использует хэш-код объекта?
Переведено автоматически
Ответ 1
Хэш-карта работает следующим образом (это немного упрощено, но иллюстрирует базовый механизм):
У него есть несколько "корзин", которые он использует для хранения пар ключ-значение. У каждой корзины есть уникальный номер - это то, что идентифицирует корзину. Когда вы помещаете пару ключ-значение в карту, хэш-карта просматривает хэш-код ключа и сохраняет пару в корзине, идентификатором которой является хэш-код ключа. Например: хэш-код ключа равен 235 -> пара хранится в корзине с номером 235. (Обратите внимание, что в одной корзине может храниться более одной пары ключ-значение).
Когда вы ищете значение в хэш-карте, присваивая ему ключ, он сначала просматривает хэш-код указанного вами ключа. Затем хэш-карта заглянет в соответствующую корзину, а затем сравнит ключ, который вы дали, с ключами всех пар в корзине, сравнивая их с equals().
Теперь вы можете видеть, как это очень эффективно для поиска пар ключ-значение на карте: по хэш-коду ключа хэш-карта сразу знает, в какой корзине искать, так что ей остается только протестировать то, что находится в этой корзине.
Глядя на приведенный выше механизм, вы также можете увидеть, какие требования необходимы к hashCode() и equals() методам ключей:
Если два ключа совпадают (equals() возвращает true при их сравнении), их hashCode() метод должен возвращать одинаковое число. Если ключи нарушают это, то равные ключи могут храниться в разных сегментах, и хэш-карта не сможет найти пары ключ-значение (потому что она будет выглядеть в одном и том же сегменте).
Если два ключа разные, то не имеет значения, совпадают ли их хэш-коды или нет. Они будут храниться в одной корзине, если их хэш-коды совпадают, и в этом случае хэш-карта будет использовать equals(), чтобы отличить их друг от друга.
Ответ 2
Ваше третье утверждение неверно.
Совершенно законно, чтобы два неравных объекта имели один и тот же хэш-код. Она используется HashMap как "фильтр первого прохождения", чтобы карта могла быстро находить возможные записи с указанным ключом. Затем ключи с одним и тем же хэш-кодом проверяются на равенство с указанным ключом.
Вам не хотелось бы требовать, чтобы два неравных объекта не могли иметь один и тот же хэш-код, поскольку в противном случае это ограничило бы вас 232 возможными объектами. (Это также означало бы, что разные типы не могли бы даже использовать поля объекта для генерации хэш-кодов, поскольку другие классы могли бы генерировать один и тот же хэш.)
Ответ 3
HashMap представляет собой массив Entry объектов.
Рассматривайте HashMap просто как массив объектов.
Посмотрите, что это Object такое:
staticclassEntry<K,V> implementsMap.Entry<K,V> { final K key; V value; Entry<K,V> next; finalint hash; … }
Каждый Entry объект представляет пару ключ-значение. Поле next ссылается на другой Entry объект, если в корзине их более одного Entry.
Иногда может случиться так, что хэш-коды для двух разных объектов совпадают. В этом случае два объекта будут сохранены в одной корзине и будут представлены в виде связанного списка. Точкой входа является объект, добавленный совсем недавно. Этот объект ссылается на другой объект с next полем и так далее. Последняя запись относится к null.
Когда вы создаете HashMap с конструктором по умолчанию
HashMaphashMap=newHashMap();
Массив создается размером 16 и балансом нагрузки по умолчанию 0.75.
Добавление новой пары ключ-значение
Вычислить хэш-код для ключа
Вычислить позицию hash % (arrayLength-1), куда должен быть помещен элемент (номер ячейки)
Если вы попытаетесь добавить значение с ключом, который уже был сохранен в HashMap, значение будет перезаписано.
В противном случае элемент добавляется в корзину.
Если в корзине уже есть хотя бы один элемент, добавляется новый и помещается в первую позицию корзины. Его next поле ссылается на старый элемент.
Удаление
Вычислить хэш-код для данного ключа
Вычислить номер корзины hash % (arrayLength-1)
Получаем ссылку на объект первой записи в корзине и с помощью метода equals перебираем все записи в данной корзине. В конечном итоге мы найдем правильное Entry. Если нужный элемент не найден, верните null
put (ключ, значение): HashMap хранит объект как ключа, так и значения в виде Map.Entry . Hashmap применяет хэш-код (ключ) для получения корзины. при возникновении коллизии HashMap использует LinkedList для хранения объекта.
получить (ключ): HashMap использует хэш-код ключевого объекта, чтобы узнать местоположение корзины, а затем вызвать метод keys.equals() для определения правильного узла в LinkedList и возврата связанного объекта value для этого ключа в Java HashMap.