Java HashMap

HashMap<K, V> — это стандартная реализация Map в JDK и наиболее используемая структура данных в коде Java-приложений. Она лежит в основе HashSet (который является HashMap, где все значения установлены в одну заглушку), именно её строит Collectors.toMap, и именно она стоит за каждой «таблицей поиска», которую вы пишете, если данные не нужно сортировать или обеспечивать конкурентный доступ. Операции выполняются за ожидаемое O(1) — хеш, индекс бакета, одна-две проверки equals — независимо от размера.

Основные операции

Это методы, которыми вы пользуетесь ежедневно. Каждый из них выполняется за ожидаемое O(1).

Перебирайте записи (а не ключи, когда нужны и значения), чтобы избежать повторного поиска по каждому ключу:

Map<String, Integer> scores = new HashMap<>();
scores.put("alice", 90);
scores.put("bob", 75);

for (Map.Entry<String, Integer> e : scores.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}

// Or the lambda form:
scores.forEach((name, score) -> System.out.println(name + " -> " + score));

Устройство таблицы

HashMap хранит массив бакетов, размер которого является степенью двойки. Вставка записи включает пять шагов:

1. Вычислить h = hashCode(key). Смешать старшие и младшие 16 бит — h ^ (h >>> 16) — чтобы хеш вроде 0x12340000 не терял старшие биты при маскировании.
2. Маскировка: i = h & (table.length - 1). Это h mod length для длин, являющихся степенью двойки, и работает быстрее оператора деления по модулю.
3. Пройти по цепочке в table[i]. Если узел с равным ключом существует, перезаписать его значение и вернуть старое.
4. Иначе добавить новый узел в начало (или, начиная с Java 8, в конец) цепочки.
5. Если size > capacity * loadFactor, изменить размер: удвоить таблицу и перераспределить все записи по бакетам.

До Java 7 цепочка бакета была обычным односвязным списком. Начиная с Java 8, когда цепочка достигает восьми записей, бакет преобразуется в небольшое сбалансированное дерево (красно-чёрное дерево), ключами которого служат хеши. Поиск в таком бакете становится O(log n) вместо O(n), что ограничивает ущерб от атаки типа «отказ в обслуживании», при которой намеренно генерируются коллизии хешей. Если дерево уменьшается до шести и менее записей, оно снова превращается в список. В обычном коде вы этого не заметите — это важно лишь когда ваш hashCode специально или по случайности очень плох.

Ёмкость, коэффициент загрузки и предварительное выделение размера

Те же параметры, что и у HashSet:

• Начальная ёмкость — по умолчанию 16, округляется до степени двойки.
• Коэффициент загрузки — по умолчанию 0.75. Когда size > capacity * 0.75, таблица удваивается.

Если размер известен заранее, выделяйте память заранее:

Map<String, User> users = new HashMap<>(expectedSize * 4 / 3); // skip the doublings

Или, начиная с Java 19, с помощью явного фабричного метода:

Map<String, User> users = HashMap.newHashMap(expectedSize);

Это самый понятный способ выразить намерение — он вычисляет правильную начальную ёмкость по целевому размеру, чтобы таблица не нуждалась в увеличении.

Null-ключи и null-значения

HashMap допускает один null-ключ (он хранится в бакете 0 с хешем 0) и произвольное количество null-значений. Это удобнее, чем Hashtable (который отвергает и то, и другое), но размывает смысл get(k) == null:

m.put("key", null);
m.get("key");          // returns null
m.containsKey("key"); // returns true

Стоимость разрешения неоднозначности реальна. Предпочтительнее не хранить null-значения; используйте Optional, метку-заглушку или просто не добавляйте ключ. Фабрика Map.of(...) из Java 9+ принудительно соблюдает это правило.

hashCode и equals — ваш контракт

Добавление собственного класса в HashMap работает только при условии согласованности hashCode и equals. Те же правила, что и для HashSet:

• Равные объекты должны иметь равные хеш-коды.
• Неравные объекты могут коллидировать (это допустимо, именно поэтому бакеты — цепочки).
• Мутация ключа после вставки является неопределённым поведением.

По возможности используйте record — оба метода генерируются корректно. Или позвольте IDE сгенерировать их. Никогда не пишите hashCode вручную, если этого можно избежать.

record UserId(String tenant, String localPart) {}
Map<UserId, User> directory = new HashMap<>();
directory.put(new UserId("acme", "alice"), new User(/*...*/));
directory.get(new UserId("acme", "alice")); // hit

Порядок итерации — явно не определён

HashMap не даёт никаких гарантий относительно порядка итерации. Порядок зависит от расположения бакетов, которое определяется хешем, ёмкостью и историей изменения размера — он может меняться между запусками и между версиями JVM. Если вы полагаетесь на порядок, ваш код сломан; если на порядок полагаются ваши тесты, они нестабильны.

Если порядок итерации важен, используйте LinkedHashMap для сохранения порядка вставки или TreeMap для сортированного порядка. Оба являются взаимозаменяемыми заменами.

Не потокобезопасен

HashMap при конкурентной мутации повредится — и исторически печально известным режимом отказа был бесконечный цикл при конкурентном изменении размера. Не передавайте HashMap между потоками. Правильная структура для многопоточного кода — ConcurrentHashMap (рассматривается позже в разделе о конкурентности). Collections.synchronizedMap(new HashMap<>()) существует, но использует единственную блокировку для каждой операции, что медленнее и редко является правильным решением.

Развёрнутый пример: счётчик, таблица поиска и современные идиомы

Программа ниже использует HashMap несколькими способами: счётчик слов через merge, кэш рекурентной мемоизации, демонстрация неоднозначности null-значений, фабрика newHashMap из Java 19 и запись в качестве составного ключа.

Что следует вынести из запуска:

• merge сворачивает трёхшаговую конструкцию «получить, взять дефолт или прибавить единицу, сохранить» в один вызов. Используйте его всякий раз, когда ведёте счётчик или сумму по ключу.
• Кэш Фибоначчи превращает экспоненциальную рекурсию в линейную: проверить в карте, рекурсировать при промахе, затем сохранить результат через put. Заметьте, что используется get + put, а не computeIfAbsent — рекурсивный computeIfAbsent мутирует карту, пока ещё выполняется его собственная функция отображения, а начиная с Java 9 это приводит к ConcurrentModificationException. Применяйте computeIfAbsent для нерекурсивных поисков «загрузить или вычислить».
• Неоднозначность null-значений реальна. get вернул null как для присутствующего ключа, так и для отсутствующего одинаковым образом. Единственный способ их различить — containsKey или решение вообще не хранить null-значения.
• Предварительное выделение через HashMap.newHashMap(1_000_000) позволяет завершить миллион вставок без каких-либо перехеширований — таблица начинается с нужной ёмкостью.
• Запись UserId бесплатно обеспечивает корректные equals/hashCode. Это современный способ составлять ключи хеш-карты из нескольких полей.

Что дальше

HashMap не гарантирует порядок итерации. Если нужно запоминать порядок вставки — например, при сериализации карты в JSON для получения стабильного вывода — подходящим инструментом является LinkedHashMap. Он также лежит в основе классического LRU-кэша, который мы рассматриваем в той же главе.

Практика