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

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

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