What is the difference between HashSet, LinkedHashSet and TreeSet

The Set interface (java.util.Set) represents an unordered or ordered collection of unique elements (duplicates are strictly prohibited). In the Java Collections Framework, three...

🟢 Junior Level

The Set interface (java.util.Set) represents an unordered or ordered collection of unique elements (duplicates are strictly prohibited). In the Java Collections Framework, three standard general-purpose implementations exist, each differing in element ordering, time complexity, and internal mechanics:

Characteristic	`HashSet`	`LinkedHashSet`	`TreeSet`
Element Ordering	Unordered / Chaotic (depends on hash codes)	Insertion-Order (retained across lifecycles)	Sorted Order (Natural or custom `Comparator`)
Underlying Data Structure	Hash Table (`HashMap`)	Hash Table + Doubly-Linked List	Red-Black Tree (`TreeMap`)
Lookup / Add Complexity	$O(1)$ average	$O(1)$ average	$O(\log N)$ guaranteed
`null` Element Support	✅ Allowed (maximum 1 `null`)	✅ Allowed (maximum 1 `null`)	❌ Prohibited (`NullPointerException`)
Primary Use Case	Maximum throughput uniqueness filtering	Uniqueness with deterministic iteration order	Uniqueness with sorting and range queries

// 1. HashSet: Unpredictable, non-deterministic order
Set<String> hashSet = new HashSet<>();
hashSet.add("Charlie"); hashSet.add("Alice"); hashSet.add("Bob");
// Output depends on JVM version & hash table capacity: e.g., [Alice, Charlie, Bob]

// 2. LinkedHashSet: Strictly preserves insertion order
Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("Charlie"); linkedHashSet.add("Alice"); linkedHashSet.add("Bob");
// Output is GUARANTEED: [Charlie, Alice, Bob]

// 3. TreeSet: Automatically sorted
Set<String> treeSet = new TreeSet<>();
treeSet.add("Charlie"); treeSet.add("Alice"); treeSet.add("Bob");
// Output is GUARANTEED lexicographical: [Alice, Bob, Charlie]

🟡 Middle Level

1. Internal Architecture: Map Backing Mechanics

All three set implementations are implemented as lightweight adapter wrappers around corresponding Map implementations:

HashSet<E>        ──► encapsulates ──► HashMap<E, Object>
LinkedHashSet<E>  ──► encapsulates ──► LinkedHashMap<E, Object>
TreeSet<E>        ──► encapsulates ──► TreeMap<E, Object>

Elements added to the Set serve as the keys of the underlying map, while the value slot is populated with a single, shared static dummy sentinel object:

// OpenJDK java.util.HashSet:
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

2. The Iteration Performance Paradox: `HashSet` vs. `LinkedHashSet`

While both HashSet and LinkedHashSet provide average $O(1)$ time complexity for add(), remove(), and contains(), their full iteration characteristics differ dramatically:

HashSet Iteration Complexity: $O(\text{capacity} + \text{size})$ The HashSet iterator must scan sequentially through every single bucket slot in the backing array (Node<K,V>[] table), checking for non-empty chains.

[!WARNING] Capacity Pitfall: If you pre-allocate new HashSet<>(1_000_000) and insert only 10 elements, iterating over the set still requires inspecting all 1,000,000 array slots, wasting millions of CPU clock cycles!
LinkedHashSet Iteration Complexity: Strictly $O(\text{size})$ Each node (LinkedHashMap.Entry) contains before and after pointers forming a continuous doubly-linked list. The iterator walks directly from node to node across this linked list, bypassing empty buckets entirely.

3. Range Queries with `TreeSet` (`NavigableSet`)

Because TreeSet implements NavigableSet (and SortedSet), it provides rich bidirectional navigation and sub-range extraction routines:

NavigableSet<Integer> scores = new TreeSet<>(List.of(10, 20, 30, 40, 50));

scores.lower(30);   // 20 (Strictly greatest element < 30)
scores.floor(30);   // 30 (Greatest element <= 30)
scores.ceiling(35); // 40 (Smallest element >= 35)
scores.higher(40);  // 50 (Strictly smallest element > 40)

// Extracting a bounded subset view in O(1) space:
NavigableSet<Integer> slice = scores.subSet(20, true, 40, true); // [20, 30, 40]

🔴 Senior Level

1. The “Lost Object” Hazard with Mutable Elements

If a mutable object is inserted into a HashSet or LinkedHashSet, and fields that participate in hashCode() or equals() are subsequently modified, the object becomes permanently corrupted inside the hash table:

class User {
    private String username;
    public User(String username) { this.username = username; }
    public void setUsername(String username) { this.username = username; }
    @Override public int hashCode() { return Objects.hash(username); }
    @Override public boolean equals(Object o) {
        return o instanceof User u && Objects.equals(this.username, u.username);
    }
}

Set<User> set = new HashSet<>();
User user = new User("Alice");
set.add(user);

// Mutate hash-dependent state while stored in the Set:
user.setUsername("Bob"); // hashCode changes!

// CATASTROPHIC FAILURE:
System.out.println(set.contains(user)); // false!
System.out.println(set.remove(user));   // false!
System.out.println(set.size());         // 1 (Memory leak: object cannot be removed!)

Under the Hood:

During add(), the object is assigned to a bucket based on hash("Alice") & mask.
After mutation, contains(user) evaluates hash("Bob") & mask, searching a completely different bucket.
The object remains stuck in its original bucket forever, unretrievable and uncollectible by the garbage collector.

[!IMPORTANT] Production Best Practice: Set elements and Map keys must be strictly immutable (e.g., Java record, primitive wrappers, String, or immutable domain value objects).

2. The `TreeSet` Equality Inconsistency Trap: `compareTo()` vs. `equals()`

TreeSet operates under a unique architectural contract: it completely ignores hashCode() and equals()!

Element uniqueness and positioning in TreeSet are governed entirely by: $\text{comparator.compare}(a, b) == 0 \quad \text{or} \quad a\text{.compareTo}(b) == 0$

record Product(int id, String title) implements Comparable<Product> {
    // equals() compares both id AND title:
    // compareTo() mistakenly compares ONLY id:
    @Override
    public int compareTo(Product other) {
        return Integer.compare(this.id, other.id);
    }
}

Set<Product> treeSet = new TreeSet<>();
treeSet.add(new Product(1, "Mechanical Keyboard"));
boolean added = treeSet.add(new Product(1, "Gaming Mouse"));

System.out.println(added);          // FALSE! Rejected as duplicate because compareTo() == 0!
System.out.println(treeSet.size()); // 1!

If a class’s compareTo() logic is not consistent with equals() (meaning (a.compareTo(b) == 0) == a.equals(b)), TreeSet will violate the standard Set specification and discard logically distinct objects.

3. Java 21 `SequencedSet` Integration (JEP 431)

Java 21 introduced SequencedSet to standardize encounters for ordered sets:

LinkedHashSet and TreeSet implement SequencedSet, exposing addFirst(), addLast(), getFirst(), getLast(), and zero-copy reversed() views.
HashSet does NOT implement SequencedSet, because it possesses no well-defined encounter order.

SequencedSet<String> seqSet = new LinkedHashSet<>();
seqSet.addFirst("Z");
seqSet.addFirst("A"); // [A, Z]
SequencedSet<String> reversed = seqSet.reversed(); // [Z, A]

4 Tricky Questions

1. Why can full iteration over a `HashSet` be orders of magnitude slower than over a `LinkedHashSet`?

Answer: HashSet iteration has a time complexity of $O(\text{capacity} + \text{size})$. Its iterator must traverse every index of the internal Node<K,V>[] table array to locate non-null bucket heads. If a table was initialized with a large capacity (e.g., 1_000_000) or underwent expansion before elements were removed, the iterator checks all 1,000,000 array elements even if only 5 elements remain in the set. In contrast, LinkedHashSet links its entries via a global doubly-linked list (before and after pointers). Its iterator walks strictly along this linked list with a time complexity of $O(\text{size})$, ignoring empty table buckets entirely.

2. Why does `TreeSet` throw `NullPointerException` when inserting `null`, while `HashSet` permits it?

Answer: HashSet stores elements in a hash table. When e == null, HashMap bypasses calling e.hashCode() and explicitly routes the element to bucket index 0 with a synthetic hash of 0. In contrast, TreeSet maintains a self-balancing binary search tree (Red-Black Tree). To place any node into the tree, it must compare the candidate element against existing nodes via comparator.compare(e, node.key) or ((Comparable) e).compareTo(node.key). Invoking methods on or passing null to a standard comparator inevitably results in a NullPointerException. (Even with a null-friendly comparator, storing null in TreeSet is strongly discouraged and historically forbidden in modern JDKs).

3. What occurs if two objects with `equals() == false` but `compareTo() == 0` are inserted into `HashSet` vs. `TreeSet`?

Answer:

In HashSet: Both objects will be successfully stored. HashSet verifies identity by hashing, then walking collision buckets comparing hash and invoking equals(). Since equals() returns false, HashSet treats them as distinct and retains both in the bucket.
In TreeSet: The second object will be silently discarded (add() returns false). TreeSet does not invoke equals(); it checks uniqueness solely via compareTo() == 0. Because compareTo() returns 0, TreeSet considers the key already present and overwrites or ignores it.

4. What happens when an object’s fields are mutated after it has already been added to a `HashSet`?

Answer: If the mutated fields are factored into the object’s hashCode() calculation:

The object’s calculated hash code changes.
However, the object physically remains in the bucket determined by its original hash code at the moment of insertion.
Subsequent calls to contains(object) or remove(object) recalculate the hash code, looking in a different bucket slot. The method returns false, unable to locate the object.
Calling size() will still count the phantom object, but it can never be removed via remove(object), resulting in a silent, insidious memory leak.

🎯 Interview Cheat Sheet

30-Second Elevator Pitch

“HashSet, LinkedHashSet, and TreeSet are the three foundational implementations of Set. HashSet provides average $O(1)$ operations via a backing HashMap, but offers no ordering guarantees and suffers from $O(\text{capacity} + \text{size})$ iteration. LinkedHashSet layers a doubly-linked list over the hash table, preserving insertion order and speeding up iteration to $O(\text{size})$ at the expense of an extra 16 bytes per entry. TreeSet is backed by a Red-Black Tree (TreeMap), offering guaranteed $O(\log N)$ performance and sorted navigation (NavigableSet), but strictly prohibits null and enforces uniqueness using Comparable.compareTo() == 0 instead of equals(). Always use immutable objects as set elements.”

High-Impact Architectural Facts

Wrapper Paradigm: All three sets encapsulate their corresponding Map (HashMap, LinkedHashMap, TreeMap), using the set elements as map keys and a singleton dummy new Object() as the value.
TreeSet Uniqueness Law: TreeSet relies exclusively on compareTo() == 0 or Comparator.compare() == 0. It completely disregards equals() and hashCode().
Iteration Footprint: Iterating a sparse HashSet depends on the array capacity; iterating a LinkedHashSet depends strictly on the number of actual elements ($O(N)$).
SequencedSet (Java 21): LinkedHashSet and TreeSet implement SequencedSet (supporting reversed(), getFirst(), getLast()); HashSet does not.
Null Safety: HashSet and LinkedHashSet allow one null element (mapped to bucket 0); TreeSet throws NullPointerException.

Common Pitfalls & Red Flags

❌ Assuming TreeSet uses equals() for uniqueness: A classic senior interview trap. TreeSet uses compareTo().
❌ Mutating objects stored in a HashSet: Modifying hash-critical fields corrupts bucket mapping and causes permanent memory leaks.
❌ Using TreeSet when only sorting upon completion is needed: Inserting $N$ items into TreeSet takes $O(N \log N)$ with tree rebalancing; inserting into ArrayList and sorting once via Collections.sort() is significantly faster due to cache locality and Timsort optimizations.
❌ Expecting HashSet to preserve insertion order: HashSet ordering is non-deterministic and can shuffle across JVM runs or capacity rehashes.

How does HashSet work internally — HashMap backing and collision resolution
What is TreeSet and how does it work — Red-Black tree mechanics and balancing
What is the difference between HashMap, LinkedHashMap and TreeMap — Map hierarchy counterparts
What is Map and what implementations exist — Map architecture overview
What is the difference between List, Set and Queue — Collections taxonomy

🟢 Junior Level

🟡 Middle Level

1. Internal Architecture: Map Backing Mechanics

2. The Iteration Performance Paradox: HashSet vs. LinkedHashSet

3. Range Queries with TreeSet (NavigableSet)

🔴 Senior Level

1. The “Lost Object” Hazard with Mutable Elements

2. The TreeSet Equality Inconsistency Trap: compareTo() vs. equals()

3. Java 21 SequencedSet Integration (JEP 431)