Как устроена HashMap изнутри

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

Вопрос с собеседования: «Как HashMap находит значение по ключу так быстро? И что будет, если два разных объекта дадут одинаковый хеш-код?»

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

Что выведет этот код?

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Аня", 20);
        ages.put("Боря", 22);
        ages.put("Аня", 21); // перезаписывает значение по тому же ключу

        System.out.println(ages.get("Аня"));
        System.out.println(ages.size());
    }
}

Вывод:

21
2

Второй put("Аня", 21) не добавил новую запись, а перезаписал старую — потому что HashMap считает ключи одинаковыми, если у них совпадают и hashCode(), и equals(). У строк оба метода уже переопределены в классе String, поэтому всё работает «из коробки». Но если ключом станет твой собственный класс — начинаются сюрпризы.

Как это работает под капотом: бакеты и хеш-функция

Внутри HashMap лежит массив, каждую ячейку которого называют бакетом (bucket, «корзина»). Когда ты вызываешь put(key, value), происходит следующее:

1. Java вычисляет key.hashCode() — целое число, «отпечаток» объекта.
2. Этот хеш дополнительно «перемешивается» служебной функцией внутри HashMap (чтобы сгладить плохие хеш-функции) и сжимается до индекса бакета — грубо говоря, hash % количество_бакетов.
3. Java идёт сразу в этот бакет — не перебирая остальные — и либо кладёт туда пару ключ-значение, либо, если бакет уже занят, разбирается с коллизией (см. ниже).

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

Что такое коллизия и как HashMap с ней справляется

Бакетов конечное число (по умолчанию 16, с ростом карты — увеличивается), а возможных ключей — бесконечно много. Значит, рано или поздно два разных ключа попадут в один и тот же бакет. Это называется коллизией — и это нормальная, ожидаемая ситуация, а не баг.

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

Начиная с Java 8, если в одном бакете скапливается больше 8 элементов (константа TREEIFY_THRESHOLD), список внутри бакета превращается в красно-чёрное дерево — сбалансированную структуру, где поиск занимает O(log n) вместо O(n). Это защита от намеренной или случайной атаки, когда кто-то специально подбирает ключи с одинаковым хешем, чтобы замедлить твою программу.

Почему equals() и hashCode() нужно переопределять вместе

Вот классическая ошибка. Представим класс Point без переопределённых методов:

class Point {
    int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }
    // hashCode() и equals() НЕ переопределены —
    // используются версии по умолчанию из Object
}

public class Main {
    public static void main(String[] args) {
        Map<Point, String> labels = new HashMap<>();
        labels.put(new Point(1, 1), "начало");

        System.out.println(labels.get(new Point(1, 1)));
    }
}

Вывод:

null

Хотя оба объекта Point(1, 1) «логически» одинаковые, стандартный hashCode() из класса Object считает хеш по адресу объекта в памяти — а это два разных объекта, значит, разные хеши, разные бакеты. Даже если бы хеши совпали, стандартный equals() тоже сравнивает по ссылке (==), а не по значениям полей. Поэтому HashMap ищет второй объект совсем не в том бакете, где лежит первый, — и получает null.

Правило простое: если два объекта равны по equals(), у них обязан быть одинаковый hashCode(). Обратное необязательно (разные объекты могут случайно дать одинаковый хеш — это и есть коллизия), но нарушение первого правила ломает HashMap насквозь: объекты «телепортируются» в разные бакеты, и карта перестаёт находить то, что явно там лежит.

Почему плохой hashCode() убивает производительность

Представь крайний случай: кто-то переопределил hashCode() так, что он всегда возвращает 0, — например, забыл дописать логику. Формально это не ошибка компиляции и даже не нарушение контракта equals/hashCode. Но все элементы будут падать в один и тот же бакет. HashMap из структуры со средним поиском O(1) вырождается в обычный список с поиском O(n) — а до Java 8 (или пока в бакете не набралось 8 элементов для дерева) это ощущается как настоящее замедление всей программы на больших объёмах данных.

Частые ошибки на собеседовании

• Путать hashCode() и equals(). Хеш определяет, в какой бакет попадёт объект; equals — сравнивает объекты внутри одного бакета при коллизии. Нужны оба, и они должны быть согласованы.
• Не знать про переход в дерево с Java 8. Это частый уточняющий вопрос: «А что, если у меня 1000 коллизий в одном бакете?» — ответ: с некоторого порога Java сама превращает список в дерево, чтобы избежать деградации до O(n).
• Не понимать разницу между «средним» и «худшим» случаем. HashMap — это O(1) в среднем случае при хорошем распределении хешей, а не гарантированно всегда.
• Забывать, что мутабельные поля в ключе — плохая идея. Если ты положил объект в HashMap как ключ, а потом изменил поле, от которого зависит hashCode(), — карта «потеряет» этот элемент: он физически лежит в старом бакете, а поиск теперь идёт по новому хешу.

Итоги-шпаргалка

• HashMap хранит данные в бакетах — ячейках массива, куда объект попадает по значению своего hashCode().
• Коллизия — это когда два разных ключа попадают в один бакет; до Java 8 разрешалась связным списком, с Java 8 — деревом при больших коллизиях (O(log n) вместо O(n)).
• equals() и hashCode() нужно переопределять вместе и согласованно — иначе объекты «теряются» в карте.
• Плохой (или константный) hashCode() сводит все преимущества HashMap на нет, превращая O(1) в O(n).