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

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

Снаружи 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 — это массив корзин, и по ключу она умеет посчитать номер нужной корзины.

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

Массив бакетов маленький, шестнадцать ячеек, а hashCode это любое из четырёх миллиардов чисел, и у многих объектов оно различается только в старших битах. Номер ячейки нужен от 0 до 15, то есть из младших бит, и если взять их как есть, такие ключи лягут в одну ячейку. Поэтому HashMap делает три шага.

1. Берёт у ключа hashCode() — целое число-«отпечаток».
2. Перемешивает биты: старшие 16 бит сдвигаются и складываются (XOR) с младшими, чтобы разница в старших битах дошла до номера ячейки.
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, и такой ключ может быть только один: второй put(null, …) перезапишет значение. Значений null при этом сколько угодно, и отсюда ловушка get: он возвращает null и когда ключа нет, и когда ключ есть, а значение null; различить их может только containsKey. У ConcurrentHashMap, которая появится в конце статьи, ни null-ключей, ни null-значений нет вовсе: в многопоточной карте «нет ключа» и «значение null» нельзя отличить атомарно, и авторы запретили второе.

Посчитаем номера сами — той же формулой, что внутри HashMap. Запустите и посмотрите, как близкие строки («cus-01» и «cus-02») расходятся по разным корзинам:

живой пример

import java.util.*;

public class Bucket {
    static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    public static void main(String[] args) {
        int n = 16;   // длина массива бакетов
        for (String key : List.of("Анна", "Иван", "Пётр", "cus-01", "cus-02")) {
            int h = hash(key);
            System.out.println(key + ": hashCode=" + key.hashCode() + ", hash=" + h
                + ", бакет=" + (h & (n - 1)));
        }
    }
}

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

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

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

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

Как выглядит бакет с коллизией — на схеме выше, второй такт: два узла в одной корзине, связанные полем next.

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

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

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

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

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

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

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

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

Есть и оговорка про сам поиск в дереве. Дерево упорядочено по хешу, а ключи с одинаковым хешем ему надо как-то расставить между собой. Если ключи реализуют Comparable (строки, числа, даты), их сравнивают через compareTo. Если нет, HashMap сравнивает имена классов и системные идентификаторы объектов: порядок получается, но не по смыслу, и поиск среди таких ключей внутри одной корзины снова сводится к перебору с проверкой equals. Поэтому «дерево даёт O(log n)» верно для нормальных ключей, а для ключа с константным hashCode и без Comparable дерево спасает лишь отчасти.

Load factor и ресайз

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

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

Сам массив при этом создаётся лениво: new HashMap<>() не выделяет шестнадцать ячеек, а только запоминает, что их должно быть шестнадцать; table появляется при первом put. Пустая карта поэтому почти ничего не весит, и поле типа Map, которое заполняется не у каждого объекта, стоит дёшево.

// если заранее известно, что элементов будет ~1000,
// лучше задать ёмкость сразу — меньше ресайзов
Map<String, Integer> map = HashMap.newHashMap(1000);  // с Java 19: «мне нужно 1000 пар»
Map<String, Integer> old = new HashMap<>(1400);       // до Java 19 запас под 0.75 считали руками

Ресайз — операция недешёвая: надо переложить все элементы. Если вы знаете примерный размер заранее, скажите его сразу — это избавит от нескольких удвоений по мере роста. Разница между двумя строками только в том, кто делит на 0.75: newHashMap делает это сам, старому конструктору ёмкость с запасом приходится считать руками. 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 сгенерированы правильно

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

живой пример

import java.util.*;

public class Mutable {
    static class Cart {
        final List<String> items;
        Cart(List<String> items) { this.items = items; }
        @Override public boolean equals(Object o) {
            return o instanceof Cart c && items.equals(c.items);
        }
        @Override public int hashCode() { return items.hashCode(); }
    }

    public static void main(String[] args) {
        List<String> items = new ArrayList<>(List.of("наушники"));
        Cart key = new Cart(items);
        Map<Cart, String> owners = new HashMap<>();
        owners.put(key, "cus-01");
        System.out.println("нашли сразу: " + owners.get(key));

        items.add("кабель");   // ключ изменился — изменился и его хеш
        System.out.println("после правки ключа: " + owners.get(key));
        System.out.println("а в карте он есть: " + owners.size() + " запись");
    }
}

Ключ нельзя менять после put

Отсюда третье правило, о котором забывают чаще всего: пока объект лежит в HashMap как ключ, его нельзя изменять. Карта посчитала hashCode в момент put и положила запись в бакет по этому числу; после правки поиск по новому значению идёт в другой бакет, а по старому не совпадает equals. Запись есть, но недостижима: ни прочитать, ни удалить. record здесь не спасает: он запрещает переприсвоить поле, но не мешает менять объект, на который поле ссылается, как список items выше. Защита — копировать изменяемое содержимое в компактном конструкторе (items = List.copyOf(items)) или брать в ключи только неизменяемые типы: строки, числа, record из таких же полей.

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 не потокобезопасна. Если два потока пишут в неё одновременно, внутренняя структура портится молча: часть записей просто исчезает, а size() начинает врать — показывать не то число, сколько пар реально лежит внутри. Никакого исключения при этом не будет, и найти такое в проде тяжело. В старой Java 7 та же гонка умела ещё и зациклить список внутри бакета, и поток навсегда зависал на get(); с Java 8 порядок узлов при расширении сохраняется, и этот симптом ушёл — но данные теряться не перестали. modCount ловит изменения только во время обхода одним потоком, это не защита от параллельного доступа.

Когда к карте обращаются несколько потоков, берите ConcurrentHashMap из пакета java.util.concurrent. Быстрой она остаётся не потому, что блокировок нет, а потому, что блокировка мелкая: с Java 8 запись захватывает только голову той корзины, куда кладут, а не всю карту, и потоки, пишущие в разные корзины, друг другу не мешают; чтение вообще идёт без блокировок. Отсюда три отличия, о которые спотыкаются. size() считается по набору счётчиков и в момент параллельных записей может быть приблизительным, а isEmpty и containsKey отражают состояние на момент вызова, не позже. Итератор не fail-fast: обход одновременно с записью не бросит ConcurrentModificationException, а покажет часть новых записей и часть старых. И составные операции вроде «проверить, потом положить» надо делать одним атомарным методом, putIfAbsent, compute, merge, иначе между проверкой и записью успеет другой поток. Что делать с гонками в целом, разбирает фаза про многопоточность.

import java.util.concurrent.ConcurrentHashMap;

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

Коротко

• HashMap внутри — массив бакетов (Node[] table); номер бакета считается как hash & (n - 1), где hash — перемешанный hashCode ключа.
• Перемешивание бит нужно, чтобы различия в старших битах hashCode тоже влияли на номер бакета.
• Коллизии (разные ключи в одном бакете) разрешаются связным списком узлов; различить ключи помогает equals.
• Девятый узел в бакете превращает список в красно-чёрное дерево (O(n) → O(log n)) — но только если в массиве уже не меньше 64 корзин, иначе HashMap просто удваивает массив. Обратно дерево сворачивается при ресайзе и при удалениях, когда узлов остаётся 6 или меньше.
• Load factor 0.75 считает пары, а не занятые корзины: при 16 корзинах порог равен 12, и тринадцатая пара удваивает массив с рехешированием. Знаете размер заранее — HashMap.newHashMap(n).
• Плохой hashCode (например, константа) загоняет всё в один бакет и убивает скорость; проще всего взять record.
• Итератор fail-fast ловит изменения по modCount; для нескольких потоков HashMap не годится — используйте ConcurrentHashMap.
• null-ключ ровно один и лежит в корзине 0, get не отличает «нет ключа» от «значение null» (для этого containsKey); у ConcurrentHashMap null запрещён вовсе.
• Массив корзин создаётся при первом put, а не в конструкторе; дерево в корзине упорядочено по хешу и compareTo, для ключей без Comparable поиск в нём снова перебор.
• ConcurrentHashMap блокирует корзину, а не карту: size() приблизительный при параллельной записи, итератор не fail-fast, «проверить и положить» делают через putIfAbsent/compute/merge.

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

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