Найти в Дзене
Записки о Java
2 подписчика

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

4
1 мин
HashMap — один из самых часто используемых классов в Java. Он позволяет хранить данные в формате ключ → значение и получать их очень быстро. Пример:
map.put("имя", "Анна");
String name = map.get("имя"); // → "Анна" Но как это работает под капотом? В этой статье вы узнаете: HashMap<K, V> — это хэш-таблица, реализующая интерфейс Map. Она: HashMap состоит из: Каждый элемент — это объект Node<K,V>, содержащий: Шаг 1: Вычисление хэш-кода int hash = key.hashCode(); Хэш-код — это целое число, уникальное для объекта (но не всегда!) Шаг 2: Определение индекса в массиве int index = (array.length - 1) & hash; // аналог hash % array.length Шаг 3: Поиск или вставка int hash = key.hashCode(); int index = (array.length - 1) & hash; Node<K,V> node = table[index]; while (node != null) { if (node.hash == hash && key.equals(node.key)) { return node.value; } node = node.next; } return null; Алгоритм: Если в одной корзине накапливается много элементов (по умолчанию 8) HashMap преобразует цепочку в красно-ч
Оглавление
Рисунок: как устроена и работает HashMap в Java
Рисунок: как устроена и работает HashMap в Java

Введение

HashMap — один из самых часто используемых классов в Java. Он позволяет хранить данные в формате ключ → значение и получать их очень быстро.

Пример:
map.put("имя", "Анна");
String name = map.get("имя"); // → "Анна"

Но как это работает под капотом? В этой статье вы узнаете:

  • Как HashMap хранит данные
  • Что такое хэш-код и цепочки коллизий
  • Как происходит вставка, чтение, удаление
  • Почему hashCode() и equals() так важны

Что такое HashMap?

HashMap<K, V> — это хэш-таблица, реализующая интерфейс Map. Она:

  • Хранит пары ключ-значение
  • Обеспечивает среднее время доступа O(1)
  • Не гарантирует порядок элементов
  • Разрешает один null ключ и любое количество null значений

Архитектура HashMap: как устроена хэш-таблица

HashMap состоит из:

  • Массива корзин (buckets) — это основной массив
  • Связанных списков или деревьев — в каждой корзине хранятся элементы

Каждый элемент — это объект Node<K,V>, содержащий:

  • key
  • value
  • next — ссылка на следующий узел (при коллизии)

Схема 1: Структура HashMap

Рисунок: схема работы HashMap
Рисунок: схема работы HashMap

Как работает put(key, value)?

Шаг 1: Вычисление хэш-кода

int hash = key.hashCode();

Хэш-код — это целое число, уникальное для объекта (но не всегда!)

Шаг 2: Определение индекса в массиве

int index = (array.length - 1) & hash; // аналог hash % array.length

Шаг 3: Поиск или вставка

  • Если корзина пуста — создаём новый узел
  • Если нет — проверяем цепочку: если ключ уже есть → обновляем значение
    Если нет — добавляем в конец

Как работает get(key)?

int hash = key.hashCode();

int index = (array.length - 1) & hash;

Node<K,V> node = table[index];

while (node != null) {

if (node.hash == hash && key.equals(node.key)) {

return node.value;

}

node = node.next;

}

return null;

Алгоритм:

  • Найти корзину по хэшу
  • Пройти по цепочке
  • Найти узел с нужным ключом через equals()

Когда список превращается в дерево?

Если в одной корзине накапливается много элементов (по умолчанию 8) HashMap преобразует цепочку в красно-чёрное дерево. Условия:

  • Коллизии из-за плохого хэширования
  • Много элементов в одной корзине

Динамическое изменение размера (resize)

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

Заключение

HashMap — это:

  • Быстрый способ хранить и искать данные
  • Основан на хэшировании и массивах
  • Требует правильные hashCode() и equals()