Set Interface in Java: HashSet and LinkedHashSet - Quiz

Set (java.util.Set<E>) models a mathematical set: every element appears at most once and there is no index access. It extends Collection and adds no new abstract methods, but tightens the contract: add() of an element that is already present changes nothing and returns false.

Main implementations:

• HashSet — a hash table, no guaranteed iteration order, elements are compared with hashCode() and equals();
• LinkedHashSet — a hash table plus a doubly linked list, insertion order;
• TreeSet — keeps elements sorted and compares them with compareTo() or a Comparator.

There are also static factories Set.of(...) (Java 9) and Set.copyOf(...) (Java 10). They create an unmodifiable set: add() throws UnsupportedOperationException, null is rejected, and a repeated argument in Set.of("a", "a") throws IllegalArgumentException.

A HashSet is backed by a HashMap: the elements of the set are stored as its keys, and every key maps to one shared placeholder object. So the elements follow the same rules as HashMap keys, and one null is allowed.

Lookup and insertion take two steps:

1. the element’s hashCode() is turned into a bucket index: (h ^ (h >>> 16)) & (capacity - 1);
2. if the bucket holds several elements (a collision), the right one is picked with equals().

Two consequences follow: a HashSet depends on both methods, and it iterates in bucket order — neither in insertion order nor sorted. null always goes to bucket 0, and the iteration order may change after rehashing.

The contract from the Object documentation:

1. as long as the fields used by equals() do not change, hashCode() of an object returns the same number (within one run of the program);
2. if a.equals(b), then a.hashCode() == b.hashCode();
3. the reverse is not required: equal hash codes do not mean equal objects (that is a collision);
4. therefore, if the hash codes differ, the objects are definitely not equal.

If you override only equals(), “equal” objects get different hash codes from Object, land in different buckets, and equals() is never called: the set accepts a duplicate (size() returns 2), and contains() returns false for an equal object.

A hashCode() that returns a constant does not break the contract, but every object ends up in one bucket and lookups become linear. Let IntelliJ IDEA generate both methods, combine fields with Objects.hash(...), or use a record (Java 16), which gets both methods automatically.

initialCapacity is the initial number of buckets in the hash table (16 by default). It is always rounded up to a power of two: new HashSet<>(100) creates a table with 128 buckets.

loadFactor says how full the table may get (0.75 by default). When the number of elements exceeds capacity * loadFactor, the set rehashes: it creates a table twice as large and redistributes all elements. With 16 and 0.75 this happens on the 13th element, with new HashSet<>(100) on the 97th.

A higher load factor saves memory but causes more collisions; a lower one speeds up lookups at the cost of memory.

To reserve room for exactly N elements, use HashSet.newHashSet(N) on Java 19+ (for a LinkedHashSet — LinkedHashSet.newLinkedHashSet(N)); on older versions pass the capacity (int) (N / 0.75f) + 1.

add(), contains() and remove() take O(1) time on average, provided the hash codes are spread evenly. size() and isEmpty() are always O(1) because the size is kept in a field.

The worst case is when all elements fall into one bucket (for example, hashCode() returns a constant):

• before Java 8 a bucket was a linked list, and a lookup took O(n);
• since Java 8 a bucket with 8 or more elements is converted into a red-black tree (if the table has at least 64 buckets; otherwise the table is simply enlarged), and a lookup takes O(log n); this works best when the elements implement Comparable.

Iterating over a HashSet takes time proportional to its size plus its capacity, because the iterator also walks the empty buckets. A LinkedHashSet iterates in time proportional to its size only.

LinkedHashSet is a subclass of HashSet that uses a LinkedHashMap inside and links its elements in a doubly linked list. So it guarantees insertion order, while a HashSet guarantees no order at all. Operations stay O(1) on average, but each element takes more memory (references to the previous and next element), and inserts and removals are slightly slower.

Adding an element that is already present does not change its position. A typical use is removing duplicates from a list while keeping the order: new ArrayList<>(new LinkedHashSet<>(list)).

In Java 21 LinkedHashSet implements SequencedSet and gets getFirst(), getLast(), addFirst(), addLast(), removeFirst(), removeLast() and reversed(). Unlike add(), addFirst()/addLast() move an existing element to the beginning or the end. The variable must be declared as LinkedHashSet or SequencedSet: the Set interface has none of these methods.