Какова роль equals() и hashCode() в HashMap

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

Алгоритм поиска:

1. Вычисляется hashCode() искомого ключа.
2. По hashCode определяется индекс корзины (hash & (capacity - 1)).
3. В корзине перебираются элементы, для каждого вызывается equals() с искомым ключом.
4. Первый элемент, для которого equals() вернул true, считается найденным.

Контракт: если a.equals(b) == true, то a.hashCode() == b.hashCode(). Обратное не обязательно: объекты с одинаковым hashCode могут быть не equals (коллизия). Нарушение этого контракта приведет к тому, что HashMap не сможет найти элемент, даже если он есть в таблице.

На собеседовании: объясните роль каждого метода: hashCode — находит корзину, equals — находит элемент в корзине. Обязательно сформулируйте контракт hashCode/equals.