Care este complexitatea la inserarea unui element în HashSet?

Complexitatea inserției unui element într-un HashSet este de obicei estimată ca O(1) — timp constant, cu condiția ca funcția hash să fie bună și coliziunile să fie scăzute.

Cu toate acestea, în cel mai rău caz, când există multe coliziuni și elementele cad în aceeași coș, complexitatea poate degrada la O(n), unde n este numărul de elemente din set.

Exemplu în Java:

HashSet<Integer> set = new HashSet<>();
set.add(42); // În medie, operația durează timp constant

Prin urmare, eficiența depinde de calitatea hash-ului și de distribuția elementelor.