Как устроена хеш-таблица (HashMap)

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

Основные моменты:

1. Хеширование: ключи преобразуются в хеш-код (метод hashCode()), который затем модифицируется для равномерного распределения.
2. Размер таблицы: обычно степень двойки (для быстрого вычисления индекса через hash & (capacity - 1)).
3. Коллизии: если разные ключи попадают в один бакет, они хранятся в списке/дереве.
4. Динамическое расширение: при достижении loadFactor (по умолчанию 0.75) таблица увеличивается вдвое и перехешируется.

Пример:

Map<String, Integer> map = new HashMap<>();
map.put("key1", 1);  // Хеш "key1" → индекс в массиве
map.get("key1");     // Поиск по хешу → O(1) в среднем

Нюансы:

• hashCode() и equals() должны быть согласованы.
• В Java 8 при коллизиях (>8 элементов) список преобразуется в красно-черное дерево (O(log n)).
• Не потокобезопасна — используй ConcurrentHashMap для многопоточности.