Что такое хеш-таблица (HashMap) и как она работает?

Хеш-таблица (HashMap в Java) — это структура данных, реализующая интерфейс Map<K,V> и хранящая пары ключ-значение. Она обеспечивает амортизированное O(1) время для операций put(), get() и remove() за счет хеширования ключей.

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

1. Массив бакетов (buckets) — каждый элемент массива содержит цепочку узлов
2. Хеш-функция — преобразует ключ в индекс массива: index = hash(key) & (n-1)
3. Узлы (Node) — хранят ключ, значение, хеш и ссылку на следующий узел

Принцип работы:

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 10);  // 1. Вычисляется hash("apple")
                        // 2. Определяется индекс: hash & (capacity-1)
                        // 3. Если бакет пуст — создается Node
                        // 4. Если есть коллизия — добавляется в цепочку

int value = map.get("apple"); // 1. Тот же hash("apple")
                              // 2. Поиск в цепочке соответствующего Node

Разрешение коллизий (Java 8+):

• При малом количестве элементов в бакете — связный список
• При достижении порога (TREEIFY_THRESHOLD = 8) — преобразуется в красно-черное дерево
• При уменьшении элементов (UNTREEIFY_THRESHOLD = 6) — обратно в список

Критические параметры:

• Начальная емкость (initialCapacity) — размер массива бакетов (по умолчанию 16)
• Коэффициент загрузки (loadFactor) — при каком заполнении увеличивать размер (по умолчанию 0.75)
• Порог (threshold) — capacity * loadFactor — при достижении происходит рехеширование

Пример с настройками:

// HashMap с начальной емкостью 32 и коэффициентом 0.5
HashMap<String, Integer> map = new HashMap<>(32, 0.5f);
// Рехеширование произойдет при 16 элементах (32 * 0.5)

Важные особенности:

• Ключи должны быть immutable — изменение ключа после добавления нарушит хеширование
• Не гарантирует порядок — для сохранения порядка вставки используйте LinkedHashMap
• Не потокобезопасна — для многопоточности используйте ConcurrentHashMap или Collections.synchronizedMap()
• Null-значения — разрешены и для ключей, и для значений (однако только один null-ключ)

Производительность:

• В лучшем случае: O(1)
• В худшем случае (все ключи в одном бакете): O(n) для списка, O(log n) для дерева
• Рехеширование — дорогая операция O(n), старайтесь задавать адекватную начальную емкость