Как HashMap в Java сравнивает ключи для поиска и вставки?

HashMap использует комбинацию методов hashCode() и equals() для эффективного хранения и поиска объектов-ключей. Этот процесс состоит из двух этапов.

Алгоритм работы при map.get(key) или map.put(key, value):

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

Критически важный контракт между hashCode() и equals():

• Если equals() для двух объектов возвращает true, то и hashCode() обязан возвращать для них одинаковое целое число.
• Обратное не обязательно: разные объекты (equals() -> false) могут иметь одинаковый hashCode() (коллизия).

Пример корректной реализации ключа:

class PersonKey {
    private final String name;
    private final int id;

    public PersonKey(String name, int id) {
        this.name = name;
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        PersonKey personKey = (PersonKey) o;
        return id == personKey.id && name.equals(personKey.name); // Сравнение по полям
    }

    @Override
    public int hashCode() {
        // Используем те же поля, что и в equals()
        int result = name.hashCode();
        result = 31 * result + id; // 31 — простое число, помогает распределению
        return result;
    }
}
// Использование:
HashMap<PersonKey, String> map = new HashMap<>();
map.put(new PersonKey("Alice", 1), "Engineer");
// Успешный поиск, т.к. hashCode и equals совпадают
String job = map.get(new PersonKey("Alice", 1)); // Вернет "Engineer"

Что произойдет при нарушении контракта?

• Если equals() переопределен, а hashCode() — нет, два логически равных объекта попадут в разные корзины. get() по новому экземпляру ключа не найдет существующее значение, что сломает логику HashMap.
• Плохая реализация hashCode() (возвращающая константу) приведет к тому, что все объекты попадут в одну корзину, превращая HashMap в связный список с производительностью O(n).