Quelle est la complexité lors de l'insertion d'un élément dans HashSet?

La complexité d'insertion d'un élément dans un HashSet est généralement estimée à O(1) — temps constant, à condition que la fonction de hachage soit bonne et que le taux de collisions soit faible.

Cependant, dans le pire des cas, lorsque de nombreuses collisions se produisent et que plusieurs éléments tombent dans la même case, la complexité peut se dégrader à O(n), où n est le nombre d'éléments dans l'ensemble.

Exemple en Java:

HashSet<Integer> set = new HashSet<>();
set.add(42); // En moyenne, l'opération prend un temps constant

Ainsi, l'efficacité dépend de la qualité du hachage et de la distribution des éléments.