tgoop.com/javaproglib/6993
Last Update:
HashMap — один из базовых и в то же время самых хитро устроенных контейнеров в JDK. На поверхности простая структура «ключ–значение», но под капотом она сочетает массивы, списки и даже деревья, чтобы оставаться быстрой в разных сценариях нагрузки.
📦 Базовая структура
HashMap хранит данные в массиве бакетов (Node<K,V>[] table). Каждый бакет — это «корзина» для элементов, чей hashCode после хеширования и применения & (n-1) (где n — длина массива) указывает на конкретный индекс.
🔑 Хэш и распределение
1. Вызов hashCode() у ключа.
2. Дополнительное хеширование (spread), чтобы снизить коллизии из-за плохой реализации hashCode.
3. Индекс бакета = hash & (table.length - 1).
🌊 Коллизии
Если несколько ключей попали в один бакет:
— до Java 8 это всегда был связанный список (linked list),
— начиная с Java 8: при росте числа элементов в бакете больше 8 и достаточном размере таблицы он превращается в сбалансированное красно-чёрное дерево. Это резко ускоряет поиск в «плохих» случаях (с O(n) до O(log n)).
⚡️ Ресайзинг
Когда количество элементов превышает capacity * loadFactor (по умолчанию 0.75), создаётся новый массив в 2 раза больше, все элементы перехешируются и раскладываются по новым бакетам. Это дорогостоящая операция, но благодаря амортизации остаётся приемлемой.
📊 Производительность
— Поиск/вставка/удаление в среднем: O(1).
— В худшем случае (плохой hashCode + коллизии): O(log n) благодаря деревьям.
⚖️ Важные нюансы
— Ключи неупорядочены. Для упорядоченности есть LinkedHashMap.
— HashMap не потокобезопасен. Для многопоточной среды нужен ConcurrentHashMap или синхронизация.
— Хорошо реализованный hashCode и equals критичны, иначе получите «забитые» бакеты и деградацию.
🧮 loadFactor и capacity
— Capacity — размер массива бакетов. По умолчанию 16.
— LoadFactor — коэффициент заполнения. По умолчанию 0.75.
Почему именно 0.75? Это компромисс: выше → меньше памяти, но больше коллизий; ниже → быстрее доступ, но больше памяти уходит впустую. Capacity всегда степень двойки, чтобы можно было вычислять индекс через hash & (n-1) вместо затратного %.
🔄 Итераторы и fail-fast
Если во время обхода карта меняется (кроме iterator.remove()), бросается ConcurrentModificationException. Под капотом это работает через счётчик модификаций (modCount), который проверяется в каждом next().
🌳 Деревья в деталях
Коллизии превращаются в красно-чёрное дерево, если размер списка в бакете > 8 и общее количество бакетов ≥ 64. Обратно в список (untreeify) при падении количества элементов < 6. Это сделано, чтобы не тратить память и CPU на лишнюю балансировку при малых размерах.
Ставьте 🔥, если хотите такой же пост по другим коллекциям.
#CoreJava
