Краткий ответ

HashMap сначала вычисляет хеш ключа, преобразует его в индекс бакета, а затем ищет элемент только внутри выбранного бакета. При равномерном распределении хешей число элементов в каждом бакете невелико, поэтому средняя сложность поиска остаётся близкой к O(1).

Коллизии не нарушают работу коллекции: разные ключи могут иметь одинаковый хеш, после чего HashMap различает их с помощью equals. При большом числе коллизий бакет может быть преобразован из списка в сбалансированное дерево, что снижает сложность поиска внутри него примерно до O(log n), но абсолютной гарантии O(1) для каждого отдельного поиска нет.

Исторический контекст

Хеш-таблицы появились как компромисс между быстрым доступом по ключу и приемлемыми затратами памяти. В отличие от последовательного поиска по всем элементам, хеширование позволяет сразу выбрать небольшой участок структуры данных.

Java Collections Framework предоставляет этот подход через интерфейс Map и реализацию HashMap. Основная решаемая проблема — эффективное хранение пар «ключ—значение» без требования поддерживать порядок ключей или выполнять операции через отсортированную структуру.

Постановка проблемы

Хеш-функция не обязана выдавать уникальное значение для каждого ключа. Поэтому несколько различных ключей могут попасть в один бакет; такая ситуация называется коллизией.

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

Подробное решение

При операции поиска HashMap выполняет несколько шагов:

получает хеш ключа и применяет внутреннее преобразование битов;
вычисляет индекс бакета по размеру внутреннего массива;
проверяет элементы выбранного бакета;
сопоставляет ключи сначала по хешу, а затем по equals.

Совпадение хешей само по себе не означает равенство ключей. Для равных ключей контракт требует одинаковый hashCode, но одинаковый хеш не требует равенства объектов.

При обычном распределении элементов длина бакета мала, поэтому средняя стоимость операций get, put и remove близка к O(1). Это ожидаемая, амортизированная оценка, а не строгая гарантия для любого набора ключей.

В современных реализациях Java слишком длинный бакет при выполнении условий реализации может быть преобразован в сбалансированное дерево. В таком случае поиск внутри него имеет порядок O(log n), что лучше линейного поиска по длинному списку. При уменьшении количества элементов бакет может вернуться к списковой форме; пороги и детали этого поведения относятся к реализации HashMap, а не к общему контракту Map.

Расширение таблицы при достижении порога заполнения также требует перераспределения элементов и может стоить O(n), но такие операции происходят не при каждом добавлении. Поэтому для серии операций используется амортизированная оценка.

Качество hashCode критично: равномерное распределение уменьшает длину бакетов, а постоянный или плохо распределяющий хеш создаёт коллизии. Однако нельзя нарушать контракт: если два ключа равны по equals, их хеши обязаны совпадать; обратное утверждение неверно.

Пример показывает, что одинаковый хеш не мешает хранить разные ключи:

import java.util.HashMap;
import java.util.Map;

final class Key {
    private final String value;
    Key(String value) { this.value = value; }
    @Override public int hashCode() { return 1; }
    @Override public boolean equals(Object o) {
        return o instanceof Key k && value.equals(k.value);
    }
}

Map<Key, Integer> map = new HashMap<>();
map.put(new Key("A"), 10);
map.put(new Key("B"), 20);
System.out.println(map.get(new Key("B"))); // 20

Оба ключа попадают в один бакет из-за одинакового хеша, но equals различает их. В небольшом примере внутри бакета используется последовательный просмотр; при большом числе коллизий реализация может применить древовидную форму.

Ситуация из практики

Сервис хранит результаты обработки по ключам, содержащим идентификатор клиента. После добавления собственного класса ключа время операций резко выросло: разработчик реализовал hashCode как константу, хотя equals корректно различал клиентов.

Рассматривались три варианта. Можно было заменить HashMap на TreeMap, но это дало бы гарантированную логарифмическую сложность и потребовало бы порядка ключей. Можно было оставить константный хеш и рассчитывать на древовидные бакеты, но это зависело бы от деталей реализации и всё равно ухудшало бы распределение.

Выбрали исправление hashCode с использованием стабильных полей ключа. Это сохранило среднюю сложность HashMap, уменьшило длину бакетов и устранило зависимость производительности от внутренних порогов реализации. Важно, что поля, участвующие в equals и hashCode, не изменялись, пока ключ находился в карте.

Что кандидаты часто упускают

Делает ли одинаковый хеш ключи одинаковыми?

Нет. Одинаковый хеш означает только возможность попадания в один бакет. Окончательное сравнение выполняется через equals, поэтому разные ключи могут сосуществовать в HashMap при одинаковом значении hashCode.
Гарантирует ли древовидный бакет сложность O(log n) для всего поиска в HashMap?

Нет. Дерево влияет только на поиск внутри конкретного бакета. Сначала выполняются вычисление хеша и выбор бакета, а сама возможность древовидного представления зависит от условий реализации. Кроме того, стоимость пользовательских методов equals и hashCode не входит в идеализированную оценку и может быть существенной.
Почему нельзя исправить плохое распределение, просто увеличив размер HashMap?

Увеличение таблицы помогает, если хеши распределяются достаточно равномерно: элементы раскладываются по большему числу бакетов. Но при постоянном или сильно вырожденном хеше все ключи по-прежнему могут попадать в один бакет. Поэтому сначала нужно обеспечить корректный и качественный hashCode, а размер таблицы использовать как средство управления загрузкой, а не как замену хеш-функции.