How does a Java HashMap handle different objects with the same hash code?

Насколько я понимаю, я думаю:

1. Совершенно законно, чтобы два объекта имели один и тот же хэш-код.


2. Если два объекта равны (с использованием метода equals()), то они имеют одинаковый хэш-код.


3. Если два объекта не равны, то они не могут иметь один и тот же хэш-код

Я прав?

Теперь, если я прав, у меня следующий вопрос: HashMap внутренне использует хэш-код объекта. Итак, если два объекта могут иметь один и тот же хэш-код, то как HashMap может отслеживать, какой ключ он использует?

Кто-нибудь может объяснить, как HashMap внутренне использует хэш-код объекта?

Хэш-карта работает следующим образом (это немного упрощено, но иллюстрирует базовый механизм):

У него есть несколько "корзин", которые он использует для хранения пар ключ-значение. У каждой корзины есть уникальный номер - это то, что идентифицирует корзину. Когда вы помещаете пару ключ-значение в карту, хэш-карта просматривает хэш-код ключа и сохраняет пару в корзине, идентификатором которой является хэш-код ключа. Например: хэш-код ключа равен 235 -> пара хранится в корзине с номером 235. (Обратите внимание, что в одной корзине может храниться более одной пары ключ-значение).

Когда вы ищете значение в хэш-карте, присваивая ему ключ, он сначала просматривает хэш-код указанного вами ключа. Затем хэш-карта заглянет в соответствующую корзину, а затем сравнит ключ, который вы дали, с ключами всех пар в корзине, сравнивая их с equals().

Теперь вы можете видеть, как это очень эффективно для поиска пар ключ-значение на карте: по хэш-коду ключа хэш-карта сразу знает, в какой корзине искать, так что ей остается только протестировать то, что находится в этой корзине.

Глядя на приведенный выше механизм, вы также можете увидеть, какие требования необходимы к hashCode() и equals() методам ключей:

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




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

Ваше третье утверждение неверно.

Совершенно законно, чтобы два неравных объекта имели один и тот же хэш-код. Она используется HashMap как "фильтр первого прохождения", чтобы карта могла быстро находить возможные записи с указанным ключом. Затем ключи с одним и тем же хэш-кодом проверяются на равенство с указанным ключом.

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

HashMap представляет собой массив Entry объектов.

Рассматривайте HashMap просто как массив объектов.

Посмотрите, что это Object такое:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
… 
}

Каждый Entry объект представляет пару ключ-значение. Поле next ссылается на другой Entry объект, если в корзине их более одного Entry.

Иногда может случиться так, что хэш-коды для двух разных объектов совпадают. В этом случае два объекта будут сохранены в одной корзине и будут представлены в виде связанного списка. Точкой входа является объект, добавленный совсем недавно. Этот объект ссылается на другой объект с next полем и так далее. Последняя запись относится к null.

Когда вы создаете HashMap с конструктором по умолчанию

HashMap hashMap = new HashMap();

Массив создается размером 16 и балансом нагрузки по умолчанию 0.75.

Добавление новой пары ключ-значение

1. Вычислить хэш-код для ключа


2. Вычислить позицию hash % (arrayLength-1), куда должен быть помещен элемент (номер ячейки)


3. Если вы попытаетесь добавить значение с ключом, который уже был сохранен в HashMap, значение будет перезаписано.


4. В противном случае элемент добавляется в корзину.

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

Удаление

1. Вычислить хэш-код для данного ключа


2. Вычислить номер корзины hash % (arrayLength-1)


3. Получаем ссылку на объект первой записи в корзине и с помощью метода equals перебираем все записи в данной корзине. В конечном итоге мы найдем правильное Entry. Если нужный элемент не найден, верните null

Вы можете найти отличную информацию на http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html

Подводя итог:

Хэш-карта работает по принципу хэширования

put (ключ, значение): HashMap хранит объект как ключа, так и значения в виде Map.Entry . Hashmap применяет хэш-код (ключ) для получения корзины. при возникновении коллизии HashMap использует LinkedList для хранения объекта.

получить (ключ): HashMap использует хэш-код ключевого объекта, чтобы узнать местоположение корзины, а затем вызвать метод keys.equals() для определения правильного узла в LinkedList и возврата связанного объекта value для этого ключа в Java HashMap.