В Java HashMap время работы операций (например, get, put) в среднем составляет O(1) благодаря хешированию ключей. Однако при коллизиях (когда разные ключи имеют одинаковый хеш) элементы хранятся в одной корзине (bucket).

Ранее в Java (до версии 8) при коллизиях элементы в корзине хранились в виде связного списка, что ухудшало время доступа до O(n) в худшем случае, если все элементы попали в одну корзину.

Начиная с Java 8, при достижении определённого порога элементов в корзине (обычно 8) связный список преобразуется в сбалансированное дерево (например, красно-чёрное дерево). Это улучшает время доступа до O(log n) в худшем случае.

Таким образом, при наличии коллизий время работы HashMap меняется:

Мало коллизий — время близко к O(1)
Много коллизий — время может ухудшиться до O(log n) благодаря дереву

Пример:

Map<String, String> map = new HashMap<>();
map.put("key1", "value1");
map.put("key2", "value2");
String val = map.get("key1");

Если "key1" и "key2" имеют одинаковый хеш, они попадут в одну корзину, и поиск будет проходить по структуре внутри корзины.

Как определяется время работы при наличии коллизий в HashMap?