Milline on keerukus, kui lisada element HashSet-i?

Lisamise keerukus HashSet-i lisamisel on tavaliselt hinnatud kui O(1) — konstantne aeg, eeldusel, et hea hash-funktsioon ja madal kokkupõrke määr.

Kuid halvimates tingimustes, kui on palju kokkupõrkeid ja elemendid satuvad samasse ämbrisse, võib keerukus halveneda kuni O(n), kus n on kogumi elementide arv.

Näide Java-s:

HashSet<Integer> set = new HashSet<>();
set.add(42); // Keskmiselt võtab operatsioon konstantselt aega

Seega sõltub tõhusus hash-funktsiooni kvaliteedist ja elementide jaotusest.