Kokia yra sudėtingumas įterpiant elementą į HashSet?

Įdėjimo sudėtingumas į HashSet paprastai vertinamas kaip O(1) — pastovus laikas, jei yra gera maišos funkcija ir mažas kolizijų skaičius.

Tačiau blogiausiu atveju, kai yra daug kolizijų ir elementai patenka į tą pačią dėžutę, sudėtingumas gali sumažėti iki O(n), kur n — rinkinio elementų skaičius.

Pavyzdys Java:

HashSet<Integer> set = new HashSet<>();
set.add(42); // Vidutiniškai operacija trunka pastovų laiką

Todėl efektyvumas priklauso nuo maišos funkcijos kokybės ir elementų pasiskirstymo.