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

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

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

При вставке ключа HashMap вычисляет индекс бакета, затем проверяет, есть ли в нем элемент с таким ключом. Если есть — обновляет значение, если нет — добавляет новую пару. При поиске ключа происходит аналогичный процесс.

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

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

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