Хранение объектов в HashMap в Java реализовано с помощью хеш-таблицы, где каждый элемент представляет собой пару ключ-значение (Map.Entry). В основе работы лежат хеш-функция, массив, цепочки (связанная структура) и — с Java 8 — даже красно-чёрные деревья.

Разберём подробно, как устроено хранение, какие структуры используются и как HashMap обрабатывает коллизии.

📦 Структура HashMap

Внутренние компоненты:

Массив:

Основной элемент HashMap — это массив Node<K,V>[] table, где каждая ячейка называется бакетом (bucket).

Node<K,V> (или Entry<K,V>):
В каждой ячейке массива может храниться либо null, либо связанный список объектов Node:

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}

🔄 Алгоритм хранения: по шагам

1. Вычисление хеша

Когда вы вызываете map.put(key, value), сначала вычисляется хеш-код ключа:

int hash = hash(key);

Метод hash() улучшает распределение:

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

2. Определение индекса

Хеш преобразуется в индекс массива:

int index = (n - 1) & hash; // n — длина массива

3. Размещение элемента

• Если бакет пуст (null) → создаётся новая Node и записывается в массив.

• Если в бакете уже есть элементы → начинается поиск по цепочке:

  • Если найден элемент с таким же ключом (equals()), значение перезаписывается.

  • Если не найден — новый узел добавляется в конец цепочки.

⚠️ Коллизии

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

Как обрабатываются:

• До Java 8: односвязный список из Node (цепочка).

• С Java 8: если в одном бакете >8 элементов и размер массива ≥64 — цепочка превращается в красно-чёрное дерево, чтобы ускорить поиск с O(n) до O(log n).

🌳 Почему дерево?

Проблема:

• Если множество ключей попадает в один бакет (плохая хеш-функция), поиск становится медленным (O(n)).

Решение:

• При достижении порога TREEIFY_THRESHOLD = 8 — цепочка преобразуется в TreeNode (вариант Node с поддержкой дерева).

• Обратное происходит при уменьшении количества — раздеревьянивание (UNTREEIFY_THRESHOLD = 6).

🔁 Расширение (resize)

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

По умолчанию:

• initialCapacity = 16

• loadFactor = 0.75

• threshold = 16 * 0.75 = 12

Расширение — дорогая операция, так как:

• Пересчитывается хеш каждого ключа

• Меняется индекс (в зависимости от нового размера массива)

• Все узлы перемещаются в новые бакеты

👓 Пример

Map&lt;String, Integer&gt; map = new HashMap<>();
map.put("Alice", 1);
map.put("Bob", 2);
map.put("Charlie", 3);

1. Вызывается put("Alice", 1)

2. Вычисляется хеш "Alice" → индекс

3. Бакет пуст → создаётся Node(hash, "Alice", 1, null)

4. Добавляется в table[index]

🚀 Производительность

• Операции put, get, remove:
  • В среднем: **O(1)
    **

  • В худшем случае (все ключи в одном бакете):

    • До Java 8: O(n) — из-за линейного поиска

    • С Java 8: O(log n) — из-за использования дерева

⚠️ Требования к ключам

1. Ключ должен правильно реализовать:

   • hashCode()

   • equals()

2. Нельзя изменять ключ после помещения в карту:

   • иначе он "потеряется" — нельзя будет найти/удалить по нему значение

3. null допустим как ключ (один null-ключ), и его бакет всегда будет index = 0.

📌 Вывод

В HashMap:

• Объекты хранятся в массиве бакетов

• По индексу в массиве размещаются цепочки Node

• При избытке — дерево

• Коллизии — нормальная ситуация, но их нужно минимизировать

• Эффективность зависит от hashCode() ключей и выбора размера

Эта структура делает HashMap одной из самых быстрых и часто используемых коллекций в Java.