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

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