За счет чего достигается константное время операций в HashMap, если нет коллизий

HashMap обеспечивает константное время O(1) для операций get() и put() благодаря хеш-функции и массиву бакетов.

1. Хеш-функция преобразует ключ в целое число (хеш-код), определяющее индекс бакета.
2. Массив бакетов хранит элементы. При отсутствии коллизий каждый ключ попадает в уникальный бакет.

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 1); // Хеш "key1" → индекс, доступ за O(1)
map.get("key1");    // Прямой доступ по индексу

Нюансы:

• Коллизии (ключи с одинаковым хешем) превращают O(1) в O(n) для цепочки в бакете.
• При большом заполнении (load factor) массив расширяется, что требует рехеширования (временные затраты).