PrepBro
← Назад к вопросам

Какая структура данных лежит в основе HashMap?

1.0 Junior🔥 201 комментариев
#Коллекции#Основы Java

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

# HashMap: Структура и внутреннее устройство

HashMap — одна из наиболее часто используемых структур данных в Java. В его основе лежит массив хеш-таблицы (hash table array) в сочетании с связными списками (linked lists) и, начиная с Java 8, с красно-чёрными деревьями (Red-Black Trees).

Основная структура

Внутренняя реализация HashMap состоит из:

  1. Массив бакетов (buckets) — массив фиксированной длины, где каждый элемент может содержать данные
  2. Связные списки (chain) — для разрешения коллизий (когда несколько ключей имеют одинаковый хеш-код)
  3. Красно-чёрное дерево (TreeMap) — оптимизация для случаев, когда в одном бакете много элементов (Java 8+)

Как работает HashMap

// При добавлении элемента:
HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 100);

Процесс:

  1. Вычисляется хеш-код: hash = key.hashCode()
  2. Определяется индекс в массиве: index = hash & (capacity - 1)
  3. Элемент добавляется в бакет по этому индексу
  4. Если в бакете уже есть элемент (коллизия), новый элемент добавляется в цепь

Пример коллизии

// Два разных ключа могут иметь одинаковый индекс:
HashMap<String, String> map = new HashMap<>();
map.put("AB", "value1");  // hash = 65 + 66 = 131
map.put("BA", "value2");  // hash = 66 + 65 = 131 (коллизия!)

// HashMap разрешает коллизию через цепочку:
// bucket[3] -> Node("AB", "value1") -> Node("BA", "value2")

Оптимизация Java 8+: Tree vs List

Когда в одном бакете накапливается много элементов (TREEIFY_THRESHOLD = 8), HashMap преобразует цепь в красно-чёрное дерево:

// Если в цепи >= 8 элементов, она преобразуется в дерево
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

// Дерево обратно преобразуется в список при удалении элементов

Параметры производительности

  • Load Factor (коэффициент заполнения) — по умолчанию 0.75
  • При достижении size() > capacity * loadFactor массив расширяется в 2 раза
  • Это предотвращает слишком много коллизий
HashMap<String, Integer> map = new HashMap<>(16, 0.75f);
// capacity = 16, load factor = 0.75
// Resize сработает при 12 элементах

Сложность операций

  • Лучший случай (нет коллизий): O(1)
  • Средний случай (хороший хеш-код): O(1)
  • Худший случай (много коллизий): O(n) → O(log n) с деревом (Java 8+)

Внутренняя переменная Node

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;
    }
}

Практическое значение

Понимание этой структуры критично для:

  • Оптимизации производительности (выбор правильного начального capacity)
  • Разработки хороших hashCode() методов
  • Избегания исключений ConcurrentModificationException при одновременном доступе

HashMap — это баланс между памятью и скоростью доступа к элементам, что делает её идеальным выбором для большинства случаев в Java.

Какая структура данных лежит в основе HashMap? | PrepBro