Расскажи про устройство HashMap.

HashMap в Java — это структура данных, реализующая ассоциативный массив (словарь), где ключи сопоставляются со значениями с помощью хеш-функции.

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

• Массив бакетов (bucket array): каждый элемент массива содержит связный список (или дерево в новых версиях) элементов с одинаковым хешем.
• Хеш-функция: вычисляет индекс бакета по ключу.
• Обработка коллизий: при совпадении хешей ключей элементы хранятся в связном списке или дереве внутри бакета.

При вставке элемента:

1. Вычисляется хеш ключа.
2. Определяется индекс бакета (обычно hash % capacity).
3. Если бакет пуст, элемент помещается туда.
4. Если бакет занят, происходит обход списка/дерева для поиска ключа или добавления нового элемента.

При поиске — аналогично: вычисляется индекс, затем перебираются элементы в бакете для поиска нужного ключа.

Пример простого использования:

Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.put("banana", 5);
int count = map.get("apple"); // 3

HashMap обеспечивает амортизированное время доступа O(1), но при большом количестве коллизий производительность может ухудшаться.