Как HashMap хранит ключи и выполняет поиск по ключу?

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

Внутренняя структура:

• HashMap использует массив бакетов (bucket array).
• Для ключа вычисляется хеш-код (hashCode), который затем преобразуется в индекс массива.
• В каждом бакете хранятся элементы с одинаковым индексом, обычно в виде связного списка или дерева (с Java 8, если много коллизий).

Работа:

• При вставке объекта вычисляется индекс по хешу ключа.
• Если бакет пуст, элемент помещается туда.
• Если бакет занят, происходит проверка ключей на равенство (equals), чтобы обновить значение или добавить новый элемент.
• При поиске по ключу также вычисляется индекс, затем перебираются элементы в бакете для поиска совпадения.

Пример:

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

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