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

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

Пример:

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