Каким образом структура данных HashMap определяет равенство ключей при вставке и поиске элементов?

В Java структура данных HashMap использует методы hashCode() и equals() для определения равенства ключей при вставке и поиске элементов.

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

Важно, чтобы:

• Метод hashCode() был переопределён так, чтобы равные объекты имели одинаковый хэш-код.
• Метод equals() корректно сравнивал объекты по смыслу равенства.

Пример:

class Key {
    private int id;

    @Override
    public int hashCode() {
        return Integer.hashCode(id);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Key other = (Key) obj;
        return this.id == other.id;
    }
}

HashMap<Key, String> map = new HashMap<>();
map.put(new Key(1), "value1");
String val = map.get(new Key(1)); // вернёт "value1"