← назад к разделу

Снаружи HashMap выглядит просто: положили put, достали get, и всё мгновенно. Но как она находит значение по ключу за один шаг, даже когда ключей миллион? И почему иногда она вдруг начинает тормозить? Разберём, что лежит под капотом в Java 21, — это объясняет и скорость, и требования к equals/hashCode.

Массив бакетов

В основе HashMap лежит обычный массив. В коде он называется table, а его ячейки — бакеты (от англ. bucket, «корзина»). Каждый бакет хранит элементы — узлы типа Node, где лежат ключ, значение и ссылка на следующий узел.

// упрощённо, как это объявлено внутри HashMap
Node<K,V>[] table;   // массив бакетов

static class Node<K,V> {
    final int hash;    // сохранённый хеш ключа
    final K key;
    V value;
    Node<K,V> next;    // ссылка на следующий узел в том же бакете
}

Идея простая: вместо того чтобы перебирать все элементы в поисках нужного ключа, HashMap сразу вычисляет, в каком бакете должен лежать ключ, и смотрит только туда. Поэтому доступ в среднем не зависит от размера — это и есть та самая «мгновенность».

Короткая формула: HashMap — это массив корзин, и по ключу она умеет посчитать номер нужной корзины.

Как считается номер бакета

Чтобы превратить ключ в номер ячейки, HashMap делает три шага.

  1. Берёт у ключа hashCode() — целое число-«отпечаток».
  2. Перемешивает биты этого числа: старшие 16 бит сдвигаются и складываются (XOR) с младшими. Это нужно, потому что номер бакета зависит в основном от младших бит, а у многих объектов hashCode различается как раз в старших — без перемешивания они попадали бы в один бакет.
  3. Берёт остаток от деления на размер массива через быструю битовую операцию hash & (n - 1), где n — длина table. Размер массива всегда степень двойки, поэтому & (n - 1) работает как «взять последние биты» и даёт номер от 0 до n−1.
// так HashMap перемешивает биты hashCode (метод hash)
static int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// номер бакета: hash & (n - 1)

Ключ null тоже разрешён — он всегда кладётся в бакет с номером 0.

Коллизии и связный список

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

HashMap решает её просто: в одном бакете хранится не один элемент, а цепочка — связный список узлов (помните поле next?). При put новый узел добавляется в этот список; при get HashMap проходит по списку и сравнивает ключи, чтобы найти нужный.

Map<String, Integer> map = new HashMap<>();
map.put("Анна", 30);   // допустим, попала в бакет 5
map.put("Иван", 25);   // допустим, тоже в бакет 5 — коллизия
// бакет 5: ["Анна"->30] -> ["Иван"->25]

Вот здесь и важен equals: внутри бакета сначала сравниваются хеши, а при совпадении — вызывается equals, чтобы отличить «Анна» от «Иван». Без корректного equals HashMap не сможет понять, тот ли это ключ.

Пока в бакете один-два элемента, перебор списка незаметен. Проблема начинается, когда в одном бакете скапливается много узлов — об этом дальше.

Превращение списка в дерево

Длинный связный список — это медленно: чтобы найти ключ, надо пройти его весь, а это O(n) (время растёт линейно с числом элементов в бакете). Чтобы такой плохой случай не убивал производительность, в Java есть оптимизация.

Когда в одном бакете накапливается 8 и более узлов (и при этом массив достаточно большой), HashMap превращает связный список в красно-чёрное дерево — это называется treeify. Дерево держит элементы в отсортированном по хешу виде, и поиск в нём идёт за O(log n) — заметно быстрее линейного перебора.

до treeify (список):  A -> B -> C -> D -> E -> F -> G -> H
после treeify (дерево):
            D
          /   \
         B      F
        / \    / \
       A   C  E   G ...

Если позже элементы из бакета удаляются и их становится 6 или меньше, дерево сворачивается обратно в список — untreeify. Два разных порога (8 на превращение, 6 на обратное) специально разнесены, чтобы при колебаниях вокруг границы структура не дёргалась туда-сюда.

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

Load factor и ресайз

Чем больше элементов в массиве фиксированного размера, тем длиннее цепочки и тем чаще коллизии. Чтобы этого избежать, HashMap следит за заполненностью через load factor (коэффициент загрузки), по умолчанию 0.75.

Это значит: как только число элементов превысит 75% от размера массива, происходит ресайз — массив увеличивается вдвое, и все элементы перекладываются (рехешируются) в новый, более просторный массив по новым номерам бакетов. Стартовый размер — 16, то есть первый ресайз случается примерно на 12-м элементе (16 × 0.75).

// если заранее известно, что элементов будет ~1000,
// лучше задать начальную ёмкость — меньше ресайзов
Map<String, Integer> map = new HashMap<>(1400);

Ресайз — операция недешёвая: надо переложить все элементы. Если вы знаете примерный размер заранее, передайте его в конструктор — это избавит от нескольких удвоений по мере роста. 0.75 — компромисс: меньше значение тратит больше памяти, но даёт меньше коллизий; больше — наоборот.

Почему так важен hashCode

Вся скорость HashMap держится на одном условии: элементы должны равномерно размазываться по бакетам. Отвечает за это hashCode.

Представьте класс, у которого hashCode всегда возвращает одно и то же число:

class BadKey {
    int id;
    @Override public int hashCode() { return 42; }  // так делать нельзя
}

Все объекты попадут в один бакет. HashMap выродится в один длинный список (или дерево), и get/put станут работать за O(n) вместо почти-мгновенного доступа — то есть пропадёт весь смысл HashMap.

Поэтому два правила. Первое: equals и hashCode должны быть согласованы — если два объекта равны по equals, у них обязан совпадать hashCode. Второе: hashCode должен хорошо разбрасывать значения, а не возвращать константу. Самый надёжный способ получить оба свойства бесплатно — сделать тип record: он генерирует корректные equals и hashCode по всем полям.

record UserId(long value) {}   // equals и hashCode сгенерированы правильно

Fail-fast и потокобезопасность

HashMap хранит внутри счётчик изменений — modCount. Каждое put/remove его увеличивает. Когда вы перебираете коллекцию итератором (в том числе через for-each), итератор запоминает значение modCount и сверяет его на каждом шаге. Если за время обхода кто-то изменил коллекцию, счётчик разойдётся, и итератор бросит ConcurrentModificationException. Такое поведение называется fail-fast — «упасть сразу», чтобы вы заметили проблему здесь же, а не получили молча испорченные данные.

Map<String, Integer> map = new HashMap<>(Map.of("a", 1, "b", 2));
for (String key : map.keySet()) {
    if (key.equals("a")) {
        map.remove(key);   // ConcurrentModificationException
    }
}

Отдельно важно: HashMap не потокобезопасна. Если два потока пишут в неё одновременно, можно повредить внутреннюю структуру (вплоть до зацикливания при ресайзе) — и никакого исключения вы не получите. modCount ловит изменения только во время обхода одним потоком, это не защита от параллельного доступа.

Когда к карте обращаются несколько потоков, берите ConcurrentHashMap из пакета java.util.concurrent — она спроектирована для одновременного доступа и при этом остаётся быстрой.

import java.util.concurrent.ConcurrentHashMap;

Map<String, Integer> safe = new ConcurrentHashMap<>();  // безопасно из многих потоков

Коротко

  • HashMap внутри — массив бакетов (Node[] table); номер бакета считается как hash & (n - 1), где hash — перемешанный hashCode ключа.
  • Перемешивание бит нужно, чтобы различия в старших битах hashCode тоже влияли на номер бакета.
  • Коллизии (разные ключи в одном бакете) разрешаются связным списком узлов; различить ключи помогает equals.
  • При 8+ узлах в бакете список превращается в красно-чёрное дерево (O(n) → O(log n)), при 6 и меньше — сворачивается обратно.
  • Load factor 0.75: при заполнении на 75% массив удваивается и все элементы рехешируются; знаете размер — задайте ёмкость в конструкторе.
  • Плохой hashCode (например, константа) загоняет всё в один бакет и убивает скорость; проще всего взять record.
  • Итератор fail-fast ловит изменения по modCount; для нескольких потоков HashMap не годится — используйте ConcurrentHashMap.

Что почитать дальше

  • Коллекции Java — обзор List, Set, Map и когда что выбирать.
  • Дженерики (generics) — что означают <K, V> в объявлении HashMap.
  • Сборка мусора — что происходит с объектами и старым массивом после ресайза.