Какая скорость поиска в HashMap (среднее и худшее)?

HashMap в Java обеспечивает среднее время доступа к элементу порядка O(1) благодаря использованию хеш-функции для быстрого поиска по ключу.

Однако в худшем случае, когда происходит много коллизий и все элементы попадают в одну корзину (bucket), скорость доступа может деградировать до O(n), где n — количество элементов в карте.

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

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 100);
Integer value = map.get("key1"); // Среднее время O(1)