Какая сложность доступа к элементу по ключу в HashMap

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

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

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 42);
int value = map.get("key");  // O(1) в среднем