Какой временной показатель у поиска элемента по ключу в хеш-таблице HashMap?

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