What is the complexity of inserting an element into a HashSet?

The complexity of inserting an element into a HashSet is usually estimated as O(1) — constant time, assuming a good hash function and low collision rate.

However, in the worst case, when there are many collisions and elements end up in the same bucket, the complexity can degrade to O(n), where n is the number of elements in the set.

Example in Java:

HashSet<Integer> set = new HashSet<>();
set.add(42); // On average, the operation takes constant time

Thus, the efficiency depends on the quality of hashing and element distribution.