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

Товар положили в HashMap ключом, потом изменили ему цену — и map.get(doll) вернул null, хотя это тот же самый объект, а map.size() по-прежнему равен 1. Ошибки в JDK нет: так работает хеш-таблица, и после этого урока понятно, почему ключ «потерялся» и как этого избежать.

HashMap (java.util.HashMap<K, V>) — самая используемая реализация интерфейса Map в Java: она хранит пары «ключ–значение» в хеш-таблице и находит значение по ключу в среднем за O(1). HashMap допускает один null-ключ и любое количество null-значений, не гарантирует порядок элементов и не синхронизирована. Класс появился в Java 1.2; в Java 8 его внутреннее устройство заметно переработали.

Что такое HashMap в Java

HashMap в Java — класс, который реализует интерфейс Map на основе хеш-таблицы: по хеш-коду ключа вычисляется ячейка массива (бакет), в которой хранится пара «ключ–значение». Поэтому операции put(), get(), containsKey() и remove() выполняются в среднем за постоянное время, независимо от числа элементов.

Объявление класса:

public class HashMap<K, V> extends AbstractMap<K, V>
        implements Map<K, V>, Cloneable, Serializable

Параметр K — тип ключей, V — тип значений. Ключи уникальны: повторный put() с тем же ключом заменяет значение. Сами методы интерфейса Map (put, get, keySet, entrySet, getOrDefault, merge и другие), способы обхода и Map.Entry разобраны в уроке Интерфейс Map. Здесь речь о том, что происходит внутри HashMap, когда эти методы вызываются.

Как создать HashMap: конструкторы

Новую HashMap в Java создают конструктором new HashMap<>() — это пустая карта с ёмкостью 16 и коэффициентом загрузки 0,75. Если заранее известно число элементов, удобнее фабричный метод HashMap.newHashMap(n) из Java 19, а копию другой карты делает конструктор new HashMap<>(map). Переменную обычно объявляют типом интерфейса Map.

Пример: зарплаты сотрудников, где ключ — фамилия, значение — сумма.

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

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Double> salaries = new HashMap<>();

        salaries.put("Иванов", 3434.34);
        salaries.put("Петров", 123.22);
        salaries.put("Сидоров", 1378.00);

        salaries.forEach((name, salary) -> System.out.println(name + ": " + salary));
    }
}

Вывод:

Иванов: 3434.34
Сидоров: 1378.0
Петров: 123.22

Порядок вставки не сохранился: элементы выводятся в порядке бакетов, в которые они попали. Почему так происходит, станет ясно в разделе о вычислении номера бакета. Примитив 1378.00 автоматически упакован в Double — в HashMap хранятся только объекты.

Если в коде встречается Maps.newHashMap(), это метод библиотеки Guava, а не JDK: он появился до оператора «ромб» (<>, Java 7) и просто создаёт пустую HashMap без повторения типов. В современном коде его заменяет new HashMap<>(). Метод JDK HashMap.newHashMap(int) — другое: он рассчитывает ёмкость под заданное число пар. Неизменяемую карту из нескольких пар создают через Map.of(...) — см. урок Интерфейс Map.

Методы HashMap и их сложность

Основные методы HashMap — put(), get(), getOrDefault(), containsKey() и remove() — работают в среднем за O(1), потому что ищут один бакет по хеш-коду ключа. Методы, которые просматривают всю таблицу, — containsValue(), обход keySet(), values(), entrySet() и clear() — зависят от числа элементов и ёмкости.

Как get() ведёт себя с null-ключом и null-значением:

Map<String, String> map = new HashMap<>();
map.put(null, "значение для null-ключа");
map.put("a", null);

System.out.println(map.get(null));         // значение для null-ключа
System.out.println(map.get("a"));          // null - значение null
System.out.println(map.get("b"));          // null - ключа нет
System.out.println(map.containsKey("a"));  // true
System.out.println(map.containsKey("b"));  // false

Вывод:

значение для null-ключа
null
null
true
false

Описание и примеры каждого метода, включая методы Java 8 (computeIfAbsent, merge, putIfAbsent), — в уроке Интерфейс Map.

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

Внутри HashMap лежит массив Node<K,V>[] table — это и есть бакеты. Каждая ячейка массива — либо null (пустой бакет), либо первый узел цепочки. Узел Node хранит хеш ключа, сам ключ, значение и ссылку на следующий узел того же бакета.

// упрощённо, из исходного кода java.util.HashMap
static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;     // хеш ключа, вычисленный один раз при put()
    final K key;
    V value;
    Node<K, V> next;    // следующий узел в том же бакете
}

transient Node<K, V>[] table;  // массив бакетов, длина - степень двойки
transient int size;            // число пар
int threshold;                 // при каком size будет resize()
final float loadFactor;        // по умолчанию 0.75f

Схема таблицы на 16 бакетов с ключами "Aa", "BB" и "Java", где два первых ключа попали в один бакет (номера бакетов рассчитаны в следующих разделах):

table
[0]  Node("Aa", hash=2112) -> Node("BB", hash=2112) -> null
[1]  Node("Java", hash=2301537) -> null
[2]  null
...
[15] null

Три важных следствия такого устройства:

• Хеш хранится в узле. При поиске сначала сравниваются числа hash, и только при совпадении вызывается equals() — так дешевле.
• Массив создаётся лениво. С Java 8 new HashMap<>() не выделяет таблицу: она появляется при первом put().
• Узел и есть Map.Entry. Обход entrySet() отдаёт сами узлы таблицы, поэтому entry.setValue() меняет значение прямо в карте.

Начиная с Java 8 длинная цепочка в бакете может превратиться в дерево из узлов TreeNode — об этом в разделе Деревья в бакетах.

Как вычисляется номер бакета: hash() и (n - 1) & hash

Номер бакета HashMap вычисляет в два шага: метод hash() перемешивает старшие биты hashCode() с младшими по формуле h ^ (h >>> 16), а затем берёт младшие биты результата: index = (n - 1) & hash, где n — длина таблицы. Для null-ключа хеш равен 0, поэтому он всегда лежит в бакете 0.

// из исходного кода java.util.HashMap (Java 8+)
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Посчитаем бакет для ключа "Java" и проверим расчёт кодом:

public class BucketIndexExample {
    public static void main(String[] args) {
        String key = "Java";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);

        System.out.println(h);              // хеш-код строки
        System.out.println(spread);         // после перемешивания
        System.out.println(h & 15);         // бакет без перемешивания, n = 16
        System.out.println(spread & 15);    // реальный бакет, n = 16
        System.out.println(spread & 31);    // n = 32
        System.out.println(spread & 63);    // n = 64
    }
}

Вывод:

2301506
2301537
2
1
1
33

Что здесь произошло: "Java".hashCode() = 2301506 = 0x231E42. Старшие 16 бит (0x23) сдвигаются вниз и смешиваются с младшими: 0x1E42 ^ 0x0023 = 0x1E61. В таблице на 16 бакетов важны только 4 младших бита: 0x1E61 & 0xF = 1. Без перемешивания ключ попал бы в бакет 2.

Зачем перемешивать биты

В маленькой таблице индекс зависит только от нескольких младших бит хеша. Если ключи различаются лишь старшими битами, все они попадут в один бакет. Пример — ключи Integer 0, 65536 и 131072 (хеш-код Integer равен самому числу): у всех трёх младшие 16 бит нулевые, и без hash() они легли бы в бакет 0. После h ^ (h >>> 16) получаются хеши 0, 65537 и 131074 — бакеты 0, 1 и 2.

Почему ёмкость HashMap — степень двойки

Когда n — степень двойки, n - 1 в двоичной записи состоит из одних единиц (15 = 0b1111), и hash & (n - 1) даёт тот же результат, что hash % n для неотрицательных чисел, но без деления и без проблем с отрицательными хешами. Поэтому HashMap всегда округляет ёмкость вверх до степени двойки (внутренний метод tableSizeFor()), а таблица растёт только удвоением. Как ёмкость связана с числом элементов, на примере HashSet показано в уроке Set и HashSet.

Как работает HashMap: put() и get() по шагам

Метод put(key, value) вычисляет хеш ключа, находит бакет и либо кладёт туда новый узел, либо проходит по цепочке и заменяет значение у узла с равным ключом. Метод get(key) проходит тот же путь, но только читает. Ключ считается найденным, если совпали хеши и при этом ключи равны по == или по equals().

Что делает put() (метод putVal() в исходном коде):

1. Вычисляет hash = hash(key).
2. Если таблица ещё не создана, вызывает resize(), который создаёт массив на 16 бакетов.
3. Находит бакет i = (n - 1) & hash. Если он пуст — кладёт туда новый Node и переходит к шагу 6.
4. Иначе идёт по цепочке. Для каждого узла проверяет p.hash == hash && (p.key == key || key.equals(p.key)). Нашёлся такой узел — заменяет значение и возвращает старое; размер карты не меняется.
5. Не нашёлся — добавляет новый узел в конец цепочки (в Java 7 — в начало). Если в цепочке стало больше 8 узлов, бакет превращается в дерево.
6. Увеличивает size; если size > threshold, вызывает resize(). Метод возвращает null — старого значения не было.

get(key) повторяет шаги 1, 3 и 4: вычисляет хеш, смотрит первый узел бакета, затем идёт по списку или ищет в дереве. Если бакет пуст или равный ключ не найден, возвращается null.

Коллизии и роль equals() и hashCode()

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

Строки "Aa" и "BB" имеют одинаковый хеш-код 2112 (65 * 31 + 97 и 66 * 31 + 66), но карта хранит их как разные ключи:

Map<String, Integer> map = new HashMap<>();
map.put("Aa", 1);
map.put("BB", 2);

System.out.println("Aa".hashCode() + " " + "BB".hashCode());
System.out.println(map.get("Aa") + " " + map.get("BB"));
System.out.println(map.size());

Вывод:

2112 2112
1 2
2

Старшие 16 бит числа 2112 нулевые, поэтому hash() его не меняет. 2112 = 0x840, четыре младших бита равны 0 — оба ключа лежат в бакете 0 одной цепочкой, а различает их equals().

Почему изменяемый ключ «теряется»

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

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

public class MutableKeyExample {
    static class Product {
        private final String name;
        private int cost;

        Product(String name, int cost) {
            this.name = name;
            this.cost = cost;
        }

        void setCost(int cost) {
            this.cost = cost;
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof Product p && cost == p.cost && name.equals(p.name);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name, cost);
        }
    }

    public static void main(String[] args) {
        Map<Product, String> shops = new HashMap<>();
        Product doll = new Product("Кукла", 534);
        shops.put(doll, "Антошка");
        System.out.println(shops.get(doll));

        doll.setCost(434);
        System.out.println(shops.get(doll));
        System.out.println(shops.containsKey(doll));
        System.out.println(shops.size());

        shops.put(doll, "Детский мир");
        System.out.println(shops.size());
    }
}

Вывод:

Антошка
null
false
1
2

После setCost(434) метод hashCode() возвращает другое число, а в узле осталось старое, поэтому проверка p.hash == hash не проходит — хотя в карте лежит тот же самый объект. Повторный put() того же объекта создаёт второй узел: в карте теперь два ключа, указывающих на один Product, а первую пару уже не найти и не удалить через remove(doll).

Ёмкость, load factor и resize()

Ёмкость (capacity) — длина массива бакетов, по умолчанию 16. Коэффициент загрузки (load factor, по умолчанию 0,75) задаёт порог threshold = capacity * loadFactor: как только число пар становится больше порога, HashMap вызывает resize() — создаёт массив вдвое длиннее и переносит в него все узлы. Для карты по умолчанию это происходит на 13-м элементе.

Как узлы переезжают при resize

При удвоении таблицы HashMap не вызывает hashCode() повторно: хеш уже сохранён в узле. Новый индекс зависит от одного бита — hash & oldCap. Если бит равен 0, узел остаётся в бакете с тем же номером j (список «lo»), если 1 — переезжает в бакет j + oldCap (список «hi»). Так бакет делится на две части без пересчёта индексов.

Ключ "Java" из примера выше: перемешанный хеш оканчивается на 0x61 (0b0110_0001). При росте с 16 до 32 проверяется бит 16 (0x10) — он равен 0, ключ остаётся в бакете 1. При росте с 32 до 64 проверяется бит 32 (0x20) — он равен 1, ключ переезжает в бакет 1 + 32 = 33. Это ровно те значения, которые вывела программа BucketIndexExample.

С Java 8 узлы в списках lo и hi сохраняют свой относительный порядок. В Java 7 перенос переворачивал цепочку, и при одновременном resize() из двух потоков список мог замкнуться в кольцо — после этого get() зависал в бесконечном цикле. Это самый известный пример того, к чему приводит использование HashMap из нескольких потоков без синхронизации.

Как задать размер HashMap заранее

Каждый resize() перебирает все узлы, поэтому для больших карт с известным размером таблицу выделяют сразу. На Java 19+ для этого есть HashMap.newHashMap(n): он сам учитывает коэффициент 0,75. На более ранних версиях ёмкость считают вручную: new HashMap<>((int) Math.ceil(n / 0.75)). Частая ошибка — new HashMap<>(n): такая карта вырастет раньше, чем в неё поместятся n пар.

Map<String, Integer> a = new HashMap<>(1000);       // таблица 1024, порог 768 - resize на 769-м элементе
Map<String, Integer> b = HashMap.newHashMap(1000);  // Java 19+: таблица 2048, 1000 пар без resize

Уменьшаться HashMap не умеет: после remove() и clear() длина массива остаётся прежней.

Деревья в бакетах: что изменилось в Java 8

Начиная с Java 8 HashMap превращает слишком длинную цепочку в красно-чёрное дерево: когда в одном бакете оказывается больше 8 узлов, а таблица содержит не меньше 64 бакетов. Поиск в таком бакете занимает O(log n) вместо O(n). Если таблица меньше 64 бакетов, вместо дерева HashMap просто удваивает таблицу. Изменение внесено JEP 180 — в том числе как защита от атак, в которых сервер нагружали запросами с тысячами ключей-строк с одинаковым хеш-кодом.

Узлы дерева (TreeNode) упорядочиваются сначала по хешу. Если хеши равны, а ключи реализуют Comparable и относятся к одному классу, используется compareTo() — поэтому String, Integer и собственные классы с Comparable лучше всего переживают массовые коллизии. Для несравнимых ключей с одинаковым хешем дерево не помогает выбрать ветку, и поиск может обойти большую его часть.

HashMap и многопоточность

HashMap не потокобезопасна: если несколько потоков меняют карту одновременно, изменения теряются, а size() может не совпадать с реальным числом пар. Для общей карты в многопоточном коде используют ConcurrentHashMap, для редкого доступа к готовой карте — обёртку Collections.synchronizedMap(map).

Даже в одном потоке итераторы HashMap работают по принципу fail-fast: если во время обхода keySet() или entrySet() вызвать map.put() с новым ключом или map.remove(), следующий шаг цикла бросит ConcurrentModificationException. Замена значения у существующего ключа структурным изменением не считается. Удалять при обходе нужно через iterator.remove() или map.entrySet().removeIf(...). Сравнение потокобезопасных коллекций и пример счётчика на ConcurrentHashMap — в уроке Коллекции в Java.

HashMap, TreeMap и Hashtable: в чём разница

HashMap хранит ключи в хеш-таблице без порядка и работает за O(1) в среднем; TreeMap хранит ключи отсортированными в красно-чёрном дереве за O(log n); Hashtable — устаревшая синхронизированная хеш-таблица из Java 1.0, которая запрещает null. В новом коде выбор обычно между HashMap (порядок не нужен) и TreeMap (нужна сортировка или поиск ближайшего ключа).

Методы TreeMap, интерфейсы SortedMap и NavigableMap разобраны в уроке TreeMap, SortedMap и NavigableMap, а история Hashtable и других классов Java 1.0 — в уроке Legacy Classes. Если нужен порядок вставки, а не сортировка, подходит LinkedHashMap — наследник HashMap со связным списком узлов. Описание изменений Java 8 в первоисточнике — JEP 180: Handle Frequent HashMap Collisions with Balanced Trees.