Kāda ir sarežģītība, pievienojot elementu HashSet?

Ievietošanas sarežģītība HashSet parasti tiek novērtēta kā O(1) — konstants laiks, ja ir laba hash funkcija un zema kolīziju skaita.

Tomēr sliktākajā gadījumā, kad ir daudz kolīziju un elementi nonāk tajā pašā grozā, sarežģītība var samazināties līdz O(n), kur n ir elementu skaits kopā.

Piemērs Java:

HashSet<Integer> set = new HashSet<>();
set.add(42); // Vidēji operācija aizņem konstantu laiku

Tādēļ efektivitāte ir atkarīga no hash funkcijas kvalitātes un elementu sadalījuma.