Почему сложность поиска в HashMap O(1)

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

1. Коллизии - если разные ключи попадают в одну корзину, сложность становится O(n) для цепочки (в случае LinkedList) или O(log n) для TreeMap (в Java 8+ при большом количестве коллизий).

2. Рехеширование - при достижении load factor (по умолчанию 0.75) HashMap увеличивает capacity, что требует перераспределения элементов (O(n) операция).

Пример:

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

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