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

В среднем поиск элемента по ключу в HashMap в Java имеет сложность O(1), то есть константное время. Это достигается за счёт использования хеш-функции, которая позволяет быстро определить индекс в массиве, где хранится элемент.

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