В каком случае возникает сложность O(n) в HashMap

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

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

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

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