Где хранятся листы внутри HashMap?

# Где хранятся листы (цепочки) внутри HashMap?

Листы (цепочки, chains) внутри HashMap хранятся непосредственно в массиве table. Каждый элемент массива table — это начало связного списка (или одна нода), который используется для хранения нескольких элементов с одинаковым хешем.

Структура HashMap внутри

HashMap<K, V>
├── table (массив)
│   ├── [0] → null
│   ├── [1] → Node → Node → Node  (цепочка из 3 элементов)
│   ├── [2] → Node (один элемент)
│   ├── [3] → null
│   ├── [4] → Node → Node (цепочка из 2 элементов)
│   └── ...
├── size (количество элементов)
├── threshold (границаразмена)
├── loadFactor (коэффициент загрузки)
└── ...

Исходный код HashMap

public class HashMap<K, V> extends AbstractMap<K, V> {
    // Массив таблицы хешей
    transient Node<K, V>[] table;
    
    // Структура ноды
    static class Node<K, V> implements Map.Entry<K, V> {
        final int hash;      // Хеш ключа
        final K key;         // Ключ
        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;
        }
    }
}

Как видите:

• table — массив нод
• Каждая нода имеет next — ссылку на следующую ноду в цепочке
• Нода содержит ключ, значение и хеш

Процесс добавления элемента

HashMap<String, Integer> map = new HashMap<>();
map.put("Alice", 100);
map.put("Bob", 200);
map.put("Charlie", 150);

Шаг 1: Вычисление индекса

String key = "Alice";
int hash = key.hashCode();              // hash = 2093164
int index = hash & (table.length - 1);  // index = 2093164 & 15 = 12

Шаг 2: Проверка существования

// table[12] содержит цепочку нод
// Проходим по цепочке:
Node<String, Integer> node = table[12];
while (node != null) {
    if (node.hash == hash && node.key.equals(key)) {
        // Ключ найден, обновляем значение
        node.value = 100;
        return;
    }
    node = node.next; // Переходим к следующей ноде
}

Шаг 3: Добавление новой ноды

Если ключ не найден, добавляется новая нода в начало цепочки:

// Создать новую ноду
Node<String, Integer> newNode = new Node<>(hash, "Alice", 100, table[12]);
// Поместить её в начало цепочки
table[12] = newNode;
size++;

Визуальный пример

Добавляем элементы в HashMap размером 16 (индексы 0-15)

Шаг 1: map.put("Alice", 100)
Alice.hashCode() = 2093164, index = 2093164 & 15 = 12
table[12] = Node(2093164, "Alice", 100, null)

Шаг 2: map.put("Bob", 200)
Bob.hashCode() = 66134, index = 66134 & 15 = 6
table[6] = Node(66134, "Bob", 200, null)

Шаг 3: map.put("Charlie", 150)
Charlie.hashCode() = 2093166, index = 2093166 & 15 = 12 (КОЛЛИЗИЯ!)
table[12] = Node(2093166, "Charlie", 150, Node(2093164, "Alice", 100, null))

Шаг 4: map.put("David", 180)
David.hashCode() = 2018416, index = 2018416 & 15 = 0
table[0] = Node(2018416, "David", 180, null)

Результат:
table[0] → David
table[6] → Bob
table[12] → Charlie → Alice
table[остальное] → null

Коллизии и цепочки

Когда два ключа имеют одинаковый хеш (или попадают в одинаковый индекс), возникает коллизия. HashMap решает это, создавая цепочку (linked list):

HashMap<String, Integer> map = new HashMap<>();

// Предположим, оба ключа имеют одинаковый index
map.put("John", 1);
map.put("Jane", 2);  // Коллизия!
map.put("Jack", 3);  // Ещё одна коллизия!

// Внутренняя структура:
// table[i] → Node("Jack", 3) → Node("Jane", 2) → Node("John", 1) → null

Процесс поиска при коллизии:

Integer value = map.get("Jane");

// HashMap:
// 1. Вычисляет index по hashCode("Jane")
// 2. Получает первую ноду: table[index]
// 3. Проходит по цепочке:
Node<String, Integer> node = table[index];
while (node != null) {
    if (node.hash == hash && node.key.equals("Jane")) {
        return node.value;  // Найдено!
    }
    node = node.next;
}
return null;  // Не найдено

От Java 8: Оптимизация с Tree

В Java 8+ при количестве коллизий более 8, список (List) превращается в красно-чёрное дерево (Tree) для оптимизации производительности:

public class HashMap<K, V> {
    static class Node<K, V> { ... }
    static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> { ... }
    
    // Константа для преобразования в дерево
    static final int TREEIFY_THRESHOLD = 8;
    
    // Если в цепочке более 8 элементов:
    // List → Tree (O(n) поиск → O(log n))
}

До Java 8:
table[i] → Node1 → Node2 → ... → Node10 → null (O(10) поиск)

Java 8+:
table[i] →    TreeNode (O(log 10) поиск)
          /         \
      TreeNode     TreeNode
       /    \       /    \
     ...    ...   ...    ...

Полный пример с visualизацией

import java.util.HashMap;

public class HashMapStructure {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>(16);
        
        // Добавляем элементы
        map.put("key1", "value1");
        map.put("key2", "value2");
        map.put("key3", "value3");
        
        // Внутренняя структура примерно такая:
        // table[0] → null
        // table[1] → Node("key1", "value1", 35389) → null
        // table[2] → Node("key2", "value2", 35390) → null
        // table[3] → Node("key3", "value3", 35391) → null
        // table[4-15] → null
        
        // Получение элемента
        System.out.println(map.get("key1")); // value1
        // HashMap:
        // 1. hashCode("key1") → 35389
        // 2. index = 35389 & 15 = 1
        // 3. table[1] → Node("key1", ...) → вернуть value1
    }
}

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

Резизинг таблицы

Когда HashMap заполнится на 75% (loadFactor = 0.75), он увеличивает размер таблицы в 2 раза:

hash map.put(...)
// Если size > capacity * loadFactor:
// 1. Создать новую таблицу большего размера
// 2. Перехешировать все элементы
// 3. Пересчитать индексы: index = hash & (newCapacity - 1)
// 4. Перестроить цепочки

Вывод

Листы (цепочки) в HashMap хранятся в массиве table, где каждый элемент массива — это начало связного списка (или одна нода). Структура:

table[index] → Node(key1, value1, next) → Node(key2, value2, next) → ... → null

Ключевые точки:

• каждая нода содержит key, value, hash и next
• next — это ссылка на следующую ноду в цепочке
• коллизии разрешаются через цепочки (Java 7) или деревья (Java 8+)
• resize происходит автоматически при достижении 75% заполнения