Как устроен HashMap в Java

HashMap в Java хранит данные в виде пар ключ-значение, используя хеш-таблицу. Основные компоненты:

1. Массив бакетов (корзин): Каждый элемент массива — это связный список или дерево (в Java 8+ при большом количестве коллизий).
2. Хеш-функция: hashCode() ключа преобразуется в индекс массива.
3. Коллизии: При совпадении хешей разные ключи попадают в одну корзину, хранятся в виде списка/дерева.

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 1); // hashCode("key") % capacity определяет корзину
int value = map.get("key"); // быстрый доступ по хешу

Особенности:

• Начальный размер: 16, нагрузка (load factor) по умолчанию 0.75.
• При достижении предела размер удваивается (rehashing).
• В Java 8 при коллизиях в одной корзине (>8 элементов) список преобразуется в красно-черное дерево для оптимизации поиска (O(log n)).