Qual é, em média, o nível de dificuldade de procurar um elemento por chave numa HashMap?

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

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