Расскажите принцип работы HashMap

HashMap в Java — это структура данных, реализующая интерфейс Map, которая хранит пары ключ-значение и обеспечивает быстрый доступ к значениям по ключу.

Принцип работы основан на использовании хеш-функции для вычисления индекса в массиве бакетов (корзин). Когда добавляется пара ключ-значение, у ключа вызывается метод hashCode(), результат которого преобразуется в индекс массива. Если в этом бакете уже есть элементы (коллизия), они хранятся в виде связанного списка или дерева (начиная с Java 8, при большом числе коллизий список преобразуется в сбалансированное дерево для повышения производительности).

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

Пример:

Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
int value = map.get("apple"); // вернет 5

Важно, чтобы у ключей были корректно реализованы методы hashCode() и equals(), чтобы избежать ошибок при поиске и хранении.