LinkedHashSet

Overview

In Java’s collection framework, LinkedHashSet offers a blend of two desirable properties: uniqueness and insertion order preservation. It implements the Set interface and extends HashSet, but its backing store is a LinkedHashMap. This design gives it the constant‑time performance of a hash table while maintaining a predictable iteration order that matches the sequence in which elements were added.

Core Characteristics

• Uniqueness – Elements are considered duplicates if equals() returns true and their hashCode() values match. Only the first occurrence is kept.
• Insertion Order – Iteration follows the order in which elements were inserted, unless an element is removed and re‑added.
• Null Support – One null value is allowed, just like HashSet.
• Performance – add, remove, and contains run in average O(1) time, slightly slower than a plain HashSet due to the extra linkage maintenance.
• Thread Safety – Not synchronized. Concurrent modifications require external synchronization.
• Fail‑Fast Iteration – Modifying the set while iterating (except via the iterator’s own remove) throws ConcurrentModificationException.

Internal Mechanics

LinkedHashSet inherits almost all behavior from HashSet. Internally, it holds a single LinkedHashMap instance:

private transient HashMap<E,Object> map;

Each element added to the set becomes a key in this map; the value is a constant dummy object. LinkedHashMap augments the standard hash table with a doubly‑linked list that records the order of insertion. Consequently, operations that rely on the map’s hash table (like lookup) remain fast, while the list guarantees order.

Because LinkedHashSet extends HashSet, most methods simply delegate to the underlying map. The only difference is the constructor, which creates a LinkedHashMap instead of a plain HashMap.

Constructors

These constructors let you tune memory usage and performance for large or predictable workloads.

Practical Example

import java.util.LinkedHashSet;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        LinkedHashSet<String> set = new LinkedHashSet<>();
        set.add("Java");
        set.add("Python");
        set.add("Java");   // duplicate – ignored
        set.add("C++");
        set.add(null);

        System.out.println(set);                    // [Java, Python, C++, null]
        System.out.println(set.contains("Python")); // true
        System.out.println(set.size());             // 4

        set.remove("C++");
        for (String item : set) {
            System.out.println(item);
        }
    }
}

Output:

[Java, Python, C++, null]
true
4
Java
Python
null

Notice that the duplicate "Java" is discarded and the iteration order matches the insertion sequence.

Comparison with Other Set Implementations

• When to use HashSet – If you only need fast uniqueness checks and don’t care about order.
• When to use TreeSet – If you require elements to be sorted automatically.
• When to use LinkedHashSet – When you need both uniqueness and a stable iteration order that reflects insertion.

Typical Use Cases

1. Removing Duplicates While Preserving Order
   Convert a List to a LinkedHashSet to drop duplicates but keep the first occurrence’s position.

2. Configuration and Menu Items
   Store options or UI elements that must appear in the order they were defined.

3. Path Tracking
   Record unique nodes visited by a user or algorithm, maintaining the sequence of visits.

4. Deterministic Serialization
   Ensure that the order of elements in a serialized form is predictable for testing or caching.

Important Considerations

• Thread Safety – Wrap the set with Collections.synchronizedSet(new LinkedHashSet<>()) for concurrent access, but remember to synchronize manually during iteration.
• Fail‑Fast Behavior – Use the iterator’s remove() method if you need to delete elements while looping.
• Correct equals()/hashCode() – The set’s ability to detect duplicates depends entirely on these methods.
• Access Order vs. Insertion Order – LinkedHashSet preserves insertion order. To maintain access order, use a LinkedHashMap with access‑order enabled and build a set from it.
• Memory Footprint – The linked list adds overhead; if order is unnecessary, prefer HashSet.

Takeaway

LinkedHashSet is a practical choice when you need a unique collection that also respects the order of insertion. Its implementation via LinkedHashMap gives it near‑hash‑table speed while delivering predictable iteration. Understanding its trade‑offs—slightly higher memory usage, lack of built‑in thread safety, and the need for proper equals/hashCode—helps you decide when it’s the right tool for the job.