What is the difference between HashSet and LinkedHashSet?

• HashSet: backed by HashMap, no ordering guarantee, O(1) operations, iteration scans bucket array (may visit empty buckets)
• LinkedHashSet: extends HashSet using LinkedHashMap, maintains a doubly-linked list across all entries for insertion order
• Performance: both O(1) for add/contains/remove; LinkedHashSet iteration is slightly faster because it follows the linked list directly
• Memory: LinkedHashSet uses ~8 extra bytes per entry for the before/after linked-list pointers
• Null: both allow one null element

What is the difference between HashSet and LinkedHashSet?

Both reject duplicates using hashCode() and equals(). The only difference is iteration order.

package com.bank.demo;

import java.util.*;

public class HashSetVsLinkedHashSetDemo {
    public static void main(String[] args) {
        // HashSet: iteration order is unpredictable
        Set<String> hashSet = new HashSet<>();
        hashSet.add("SAV2001");
        hashSet.add("CUR3001");
        hashSet.add("FD4001");
        hashSet.add("LON5001");
        System.out.println("HashSet:       " + hashSet);

        // LinkedHashSet: iteration order = insertion order
        Set<String> linkedSet = new LinkedHashSet<>();
        linkedSet.add("SAV2001");
        linkedSet.add("CUR3001");
        linkedSet.add("FD4001");
        linkedSet.add("LON5001");
        System.out.println("LinkedHashSet: " + linkedSet);

        // Adding and removing does not change order for LinkedHashSet
        linkedSet.remove("CUR3001");
        linkedSet.add("CUR3001"); // re-added at the END
        System.out.println("After re-add:  " + linkedSet);
    }
}

HashSet:       [FD4001, LON5001, CUR3001, SAV2001]
LinkedHashSet: [SAV2001, CUR3001, FD4001, LON5001]
After re-add:  [SAV2001, FD4001, LON5001, CUR3001]

Why does ordering matter?

Deterministic iteration order is important for:

• Audit logs: statements must list accounts in a consistent, reproducible order.
• Test assertions: unit tests that compare set contents fail intermittently with HashSet because iteration order varies between JVM runs.
• API responses: JSON serialization of a set produces different output each time with HashSet.
• Deduplication: when removing duplicates from a feed, LinkedHashSet preserves the first occurrence.

package com.bank.service;

import java.util.*;

public class OrderingMattersDemo {
    public static void main(String[] args) {
        // Test assertion with HashSet: FRAGILE
        Set<String> hashResult = new HashSet<>(List.of("A", "B", "C"));
        // hashResult.toString() varies between runs!
        // assertEquals("[A, B, C]", hashResult.toString()); // may fail!

        // Test assertion with LinkedHashSet: DETERMINISTIC
        Set<String> linkedResult = new LinkedHashSet<>(List.of("A", "B", "C"));
        System.out.println(linkedResult.toString()); // always [A, B, C]

        // JSON output
        // {"accounts": ["SAV2001", "CUR3001"]} – always this order with LinkedHashSet
        // {"accounts": ["CUR3001", "SAV2001"]} – random with HashSet
    }
}

[A, B, C]

What about iteration performance?

LinkedHashSet iterates faster than HashSet for sparse maps. HashSet's iterator scans the entire bucket array, skipping empty buckets. If the map has capacity 10,000 but only 100 entries, the iterator visits 10,000 slots. LinkedHashSet's iterator follows the linked list and visits exactly 100 entries.

For dense maps (many entries relative to capacity), the difference is negligible.

When should you use each?

| Scenario | Best choice |
|---|---|
| Fast membership testing, order irrelevant | HashSet |
| Membership testing + deterministic iteration | LinkedHashSet |
| Dedup preserving first occurrence | LinkedHashSet |
| Unit test assertions on set contents | LinkedHashSet |
| JSON serialization with consistent field order | LinkedHashSet |
| Memory-sensitive with many elements | HashSet |

What should a senior engineer know?

- LinkedHashSet does not support access-order mode. LinkedHashMap has an access-order mode (move-to-end on get), but LinkedHashSet does not expose it. For LRU cache behavior, use LinkedHashMap directly.

- Re-adding a removed element. If you remove and re-add an element in LinkedHashSet, it goes to the end of the insertion order (not back to its original position).

- Set.of() is unordered. Set.of("A", "B", "C") returns an immutable set with no ordering guarantee. It is not a LinkedHashSet.

What are common interview follow-up questions?

• "Which Set preserves insertion order?" – LinkedHashSet.
• "What is the memory overhead of LinkedHashSet vs HashSet?" – ~8 extra bytes per entry for the linked-list pointers.
• "Is LinkedHashSet slower than HashSet?" – No, both are O(1); LinkedHashSet iteration is actually faster for sparse sets.