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

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

Обычно же, при хорошем хешировании и равномерном распределении, сложность O(1).

Пример плохого hashCode():

@Override
public int hashCode() {
    return 1; // Все объекты попадут в одну корзину
}

В Java 8+ при большом количестве коллизий корзина превращается в сбалансированное дерево, снижая сложность до O(log n).