Как реализована HashMap

HashMap в Java реализована как массив бакетов (корзин), где каждый бакет — это связный список или дерево (начиная с Java 8).

Ключевые моменты:

1. Хеширование: hashCode() ключа преобразуется в индекс массива через (n - 1) & hash (где n — размер массива).
2. Коллизии: При совпадении хешей элементы хранятся в виде связного списка. Если список превышает TREEIFY_THRESHOLD (8), он преобразуется в красно-черное дерево для ускорения поиска.
3. Динамическое расширение: При достижении loadFactor (по умолчанию 0.75) размер массива удваивается, и элементы перераспределяются.

Пример:

Map<String, Integer> map = new HashMap<>();
map.put("key", 1); // Хеш "key" определяет бакет
int value = map.get("key"); // Быстрый доступ по хешу

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

• Не гарантирует порядок элементов.
• Потокобезопасность: ConcurrentHashMap для многопоточности.
• null разрешён как ключ (хранится в бакете 0).