Какая сложность метода get в HashMap

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

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);

// O(1) в среднем, O(n) в худшем случае
Integer value = map.get("key1");