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

В среднем случае операция поиска элемента в HashMap в Java имеет временную сложность O(1) — константное время.

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

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

Таким образом, в большинстве практических случаев можно считать, что поиск в HashMap — это операция с амортизированной сложностью O(1).