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

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

Пример:

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