Qual é a complexidade ao inserir um elemento no HashSet?

A complexidade de inserir um elemento em um HashSet é geralmente avaliada como O(1) — tempo constante, assumindo uma boa função de hash e baixa taxa de colisões.

No entanto, no pior caso, quando há muitas colisões e os elementos caem na mesma caixa, a complexidade pode degradar para O(n), onde n é o número de elementos no conjunto.

Exemplo em Java:

HashSet<Integer> set = new HashSet<>();
set.add(42); // Em média, a operação leva tempo constante

Assim, a eficiência depende da qualidade do hash e da distribuição dos elementos.