← Назад к вопросам
Что происходит с внутренней структурой бакета в HashMap при добавлении большого количества элементов
2.2 Middle🔥 181 комментариев
#Коллекции#ООП
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Внутренняя структура HashMap при добавлении большого количества элементов
HashMap — одна из самых часто используемых коллекций в Java. Её внутренняя структура и поведение при добавлении элементов — это критически важные знания для разработчика. Давайте разберём, как HashMap развивается по мере увеличения количества элементов.
1. Начальная структура HashMap
public class HashMap<K, V> {
static final int DEFAULT_INITIAL_CAPACITY = 16; // По умолчанию
static final float DEFAULT_LOAD_FACTOR = 0.75f; // Коэффициент заполнения
Node<K, V>[] table; // Массив бакетов
}
При создании HashMap выглядит так:
HashMap<String, Integer> map = new HashMap<>();
┌────────────────────────────────────────┐
│ table[] — массив из 16 бакетов │
├──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┤
│ 0│ 1│ 2│ 3│ 4│ 5│ 6│ 7│ 8│ 9│10│11│12│13│14│15│ (индексы бакетов)
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ (пусто, null)
└────────────────────────────────────────┘
size = 0
load factor = 0.75
threshold = 16 * 0.75 = 12 (при 12 элементах произойдёт resize)
2. Добавление элементов и коллизии (Collisions)
map.put("Alice", 1);
map.put("Bob", 2);
map.put("Charlie", 3);
Как происходит добавление:
1. Вычисляется hash код ключа:
hash("Alice") = 12345
2. Вычисляется индекс в массиве table:
index = hash & (table.length - 1)
index = 12345 & (16 - 1) = 12345 & 15 = 9
3. Проверяется бакет по индексу 9:
- Если пусто: добавляем новый Node
- Если занято: проверяем на коллизию (другой ключ?)
Визуально:
┌────────────────────────────────────────┐
│ table[] после добавления 3 элементов │
├──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┤
│ 0│ 1│ 2│ 3│ 4│ 5│ 6│ 7│ 8│ 9│10│11│12│13│14│15│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
│ │ │ │ │ │ │ │ │ │A │ │ │ │B │ │C │ (ключи в разных бакетах)
└────────────────────────────────────────┘
size = 3
3. Коллизии (Hash Collisions)
Если два разных ключа получают один индекс:
map.put("Alice", 1);
map.put("Bob", 2);
map.put("Charlie", 3);
map.put("David", 4); // hash("David") % 16 совпадает с hash("Bob")
До Java 8: связный список (Linked List)
┌──────────────────────────────────────┐
│ table[9] (коллизия!) │
├──────────────────────────────────────┤
│ │
│ Node(key="Bob", hash=hash("Bob")) │
│ ↓ next │
│ Node(key="David", hash=...) │
│ ↓ next │
│ Node(key="Frank", hash=...) │
│ ↓ next │
│ null │
└──────────────────────────────────────┘
Проблема: При поиске элемента нужно пройти весь список O(n), что очень медленно.
4. Java 8+: Дерево вместо списка
В Java 8 добавлена оптимизация: когда в одном бакете становится слишком много элементов, связный список преобразуется в красно-чёрное дерево (Red-Black Tree):
static final int TREEIFY_THRESHOLD = 8; // При 8+ элементах в списке
static final int UNTREEIFY_THRESHOLD = 6; // При уменьшении до 6
Превращение в дерево:
// Состояние 1: 7 элементов в бакете (всё ещё список)
HashMap[i] → Node → Node → Node → Node → Node → Node → Node
(O(7) для поиска - медленно)
// Состояние 2: добавили 8-й элемент (TREEIFY_THRESHOLD = 8)
HashMap[i] → TreeNode
/ \
TreeNode TreeNode (красно-чёрное дерево)
/ \ / \
... ... ... ...
(O(log 8) ≈ 3 для поиска - быстро!)
5. Процесс Resize (Переизменение размера)
Когда размер HashMap достигает threshold (порог):
threshold = capacity * loadFactor
threshold = 16 * 0.75 = 12
При добавлении 12-го элемента происходит resize (увеличение):
map.put("element1", 1);
map.put("element2", 2);
// ...
map.put("element12", 12); // TRIGGER: size == threshold, происходит RESIZE!
Процесс resize:
1. Создаётся новый массив БОЛЬШЕГО размера:
oldCapacity = 16
newCapacity = 16 * 2 = 32
2. Все элементы ПЕРЕХЭШИРУЮТСЯ (rehash):
Для каждого элемента:
- Вычисляется новый хэш: hash & (32 - 1)
- Элемент добавляется в новую позицию
3. Старый массив заменяется новым
threshold = 32 * 0.75 = 24
Визуально:
┌──────────────────────────────┐
│ OLD table[] (16 элементов) │
├──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┤
│ │A │ │B │ │C │ │ │ │D │ │E │ │ │ │F │
└─────────────────────────────┘
↓ (rehash all elements)
┌───────────────────────────────────────────────────┐
│ NEW table[] (32 элемента) │
├──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┤
│ │ │A │ │ │ │ │ │B │ │ │C │ │D │ │ │ │ │ │E │ │ │F │ │ │ │ │ │ │ │ │ │
└──────────────────────────────────────────────────┘
6. Цепочка resize операций
public class HashMapGrowthDemo {
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap<>();
// Отслеживаем рост HashMap
for (int i = 0; i < 30; i++) {
map.put(i, i);
System.out.printf("После добавления %d: size=%d, capacity=%d%n",
i + 1,
map.size(),
getCapacity(map));
}
}
private static int getCapacity(HashMap<?, ?> map) {
try {
Field f = HashMap.class.getDeclaredField("table");
f.setAccessible(true);
Object[] table = (Object[]) f.get(map);
return table.length;
} catch (NoSuchFieldException | IllegalAccessException e) {
return -1;
}
}
}
// Вывод:
// После добавления 1: size=1, capacity=16
// ...
// После добавления 12: size=12, capacity=16 <- threshold!!
// После добавления 13: size=13, capacity=32 <- RESIZE!
// ...
// После добавления 24: size=24, capacity=32 <- threshold!!
// После добавления 25: size=25, capacity=64 <- RESIZE!
// После добавления 30: size=30, capacity=64
7. Процесс для большого количества элементов
Добавляем 10,000 элементов:
0-16 элементов: capacity = 16
16-32 элементов: capacity = 32 (после resize)
32-64 элементов: capacity = 64 (после resize)
64-128 элементов: capacity = 128 (после resize)
128-256: capacity = 256
256-512: capacity = 512
512-1024: capacity = 1024
1024-2048: capacity = 2048
2048-4096: capacity = 4096
4096-8192: capacity = 8192
8192-16384: capacity = 16384 ← для 10,000 элементов
Процесс: 16 → 32 → 64 → 128 → 256 → 512 → 1024 → 2048 → 4096 → 8192 → 16384
8. Внутренняя структура Node
static class Node<K, V> implements Map.Entry<K, V> {
final int hash; // Кэшированный хэш (для быстрого сравнения)
final K key; // Ключ (immutable для надёжности)
V value; // Значение (может меняться)
Node<K, V> next; // Следующий элемент (для коллизий)
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
// Для больших коллизий (Java 8+): TreeNode вместо Node
static final class TreeNode<K, V> extends LinkedHashMap.LinkedHashEntry<K, V> {
TreeNode<K, V> parent;
TreeNode<K, V> left;
TreeNode<K, V> right;
TreeNode<K, V> prev;
boolean red; // Red-Black Tree
// ... методы для сбалансированного дерева
}
9. Сложность операций при разном количестве элементов
┌────────────────────────────────────────────────┐
│ Поведение при росте элементов │
├────────────────┬──────────────┬────────────────┤
│ Элементы │ Структура │ Поиск / Вставка│
├────────────────┼──────────────┼────────────────┤
│ 1-7 │ Массив + узлы│ O(1) avg │
│ 8-15 │ Массив + узлы│ O(1) avg │
│ При коллизии │ Список │ O(n) worst │
│ 8+ в одном │ Дерево │ O(log n) │
│ бакете (Java 8)│ │ │
├────────────────┼──────────────┼────────────────┤
│ После resize │ Новый массив │ O(1) (если │
│ (load > 0.75) │ больший │ распредел. │
│ │ │ равномерно) │
└────────────────┴──────────────┴────────────────┘
10. Практический пример: мониторинг структуры
import java.lang.reflect.Field;
import java.util.*;
public class HashMapAnalysis {
public static void main(String[] args) throws Exception {
HashMap<Integer, String> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
map.put(i, "Value-" + i);
if (i % 100 == 99) {
analyzeHashMap(map, i + 1);
}
}
}
private static void analyzeHashMap(HashMap<?, ?> map, int count) throws Exception {
Field tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
Object[] table = (Object[]) tableField.get(map);
Field sizeField = HashMap.class.getDeclaredField("size");
sizeField.setAccessible(true);
int size = sizeField.getInt(map);
int emptyBuckets = 0;
int maxChainLength = 0;
int totalChainLength = 0;
for (Object node : table) {
if (node == null) {
emptyBuckets++;
} else {
int chainLength = 1;
Object current = node;
// Следуем цепочке
while (true) {
try {
Field nextField = current.getClass().getDeclaredField("next");
nextField.setAccessible(true);
Object next = nextField.get(current);
if (next == null) break;
current = next;
chainLength++;
} catch (NoSuchFieldException e) {
break;
}
}
totalChainLength += chainLength;
maxChainLength = Math.max(maxChainLength, chainLength);
}
}
System.out.printf(
"После добавления %d элементов: capacity=%d, empty=%d, max_chain=%d, avg_chain=%.2f%n",
count,
table.length,
emptyBuckets,
maxChainLength,
(double) totalChainLength / (table.length - emptyBuckets)
);
}
}
// Вывод:
// После добавления 100 элементов: capacity=128, empty=90, max_chain=3, avg_chain=1.30
// После добавления 200 элементов: capacity=256, empty=190, max_chain=2, avg_chain=1.05
// После добавления 300 элементов: capacity=512, empty=450, max_chain=1, avg_chain=1.00
// После добавления 400 элементов: capacity=512, empty=394, max_chain=2, avg_chain=1.02
// ...
// После добавления 1000 элементов: capacity=1024, empty=816, max_chain=2, avg_chain=1.02
11. Оптимизация при создании HashMap
// ПЛОХО: много resize операций
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < 10000; i++) {
map.put("key-" + i, i); // Будет 10 resize операций!
}
// ХОРОШО: указываем начальный размер
HashMap<String, Integer> map = new HashMap<>(10000);
for (int i = 0; i < 10000; i++) {
map.put("key-" + i, i); // Один resize (если вообще будет)
}
// Правильный расчёт начального размера:
// initialCapacity = (expectedSize / 0.75) + 1
int expectedSize = 10000;
HashMap<String, Integer> optimizedMap = new HashMap<>(
(int) (expectedSize / 0.75) + 1
);
Ключевые выводы
- HashMap начинается с 16 бакетов и capacity = 2^n (степени двойки)
- Коллизии разрешаются через связные списки (которые с Java 8 превращаются в деревья)
- Resize происходит при size > threshold = capacity * 0.75
- При resize все элементы перехэшируются и перемещаются в новый массив
- Java 8+: когда в одном бакете > 8 элементов, связный список становится красно-чёрным деревом
- При большом количестве элементов: capacity растёт: 16 → 32 → 64 → 128 → ... → 16384
- Поиск остаётся O(1) в среднем, даже с коллизиями (благодаря равномерному распределению и деревьям)
Это одна из причин, почему HashMap так популярна — она автоматически оптимизирует свою структуру по мере роста данных!