Jaka jest złożoność dodawania elementu do HashSet?

Złożoność wstawiania elementu do HashSet jest zwykle oceniana jako O(1) — czas stały, pod warunkiem dobrej funkcji hash i niskiego poziomu kolizji.

Jednak w najgorszym przypadku, gdy występuje wiele kolizji i elementy trafiają do tego samego kosza, złożoność może się pogorszyć do O(n), gdzie n to liczba elementów w zbiorze.

Przykład w Java:

HashSet<Integer> set = new HashSet<>();
set.add(42); // Średnio operacja zajmuje czas stały

W związku z tym, wydajność zależy od jakości haszowania i rozkładu elementów.