HashSet

In short: The most common Set implementation — internally uses a hash table, so inserting, removing, and containment checks are very fast on average (constant time).

In more detail: The order of elements in a HashSet is not guaranteed and can even differ between program runs — anyone needing a predictable order should use TreeSet (sorted) or LinkedHashSet (insertion order) instead. For a custom object to work correctly in a HashSet, equals() and hashCode() have to be overridden consistently.

In Depth

Set<String> names = new HashSet<>();
names.add("Anna");
names.add("Ben");
names.add("Anna"); // ignored - already contained
System.out.println(names.size()); // 2
 
System.out.println(names.contains("Ben")); // true, O(1) on average
 
record Person(String name, int age) {
    // equals()/hashCode() automatically generated by the record
    // -> two Person objects with the same values are considered "equal"
}
 
Set<Person> people = new HashSet<>();
people.add(new Person("Anna", 30));
people.add(new Person("Anna", 30)); // recognized as a duplicate and ignored
System.out.println(people.size()); // 1

HashSet internally uses a hash table: when inserting, the object’s hashCode() is computed to determine which “bucket” it’s sorted into, and equals() then checks for actual equality within that bucket. If a custom class overrides equals() without also overriding hashCode() consistently (rule: equal objects must return the same hash code), HashSet/HashMap don’t work reliably — two objects that are equal according to equals() could end up in different buckets and would then be wrongly treated as different. A record (since Java 16) automatically generates both methods correctly, which is why records are especially well suited as set/map keys.

Why O(1) “on average” — and when not

The constant access time of HashSet only holds for a WELL-DISTRIBUTED hash function — if many elements end up in the same bucket (e.g. because hashCode() is poorly implemented and often returns the same value for different objects), the bucket internally degenerates into a linear list, and searching within it becomes O(n) instead of O(1). Java 8 mitigated this worst-case scenario by automatically turning heavily filled buckets into a balanced tree instead of a simple list internally (O(log n) instead of O(n) in the worst case) — nevertheless, a good, well-distributing hashCode() implementation remains important for genuinely constant performance.

Initial capacity and load factor

new HashSet<>() starts with a default capacity (16 buckets) and a load factor of 0.75 — as soon as the number of elements exceeds 75% of the capacity, the internal table is automatically enlarged (doubled) and all elements are re-sorted (“rehashing”). If the approximate final size is known in advance, this repeated rehashing can be avoided with a suitably chosen initial capacity: new HashSet<>(1000) reserves enough space for about 750 elements from the start, without having to restructure in between.

HashSet vs. HashMap internally

Little known: HashSet is internally nothing other than a HashMap<E, Object>, where every element serves as a key and a single, shared placeholder value is used as the value — all the hash table logic (buckets, rehashing, tree conversion for many collisions) comes directly from HashMap. This also explains why both classes have practically identical performance characteristics.

See also: Set, TreeSet, LinkedHashMap