LinkedHashSet

#Introduction

LinkedHashSet is essentially a HashSet + predictable insertion-order iteration. Since the HashSet chapter already covered hashing, collisions, equals(), hashCode(), load factor and resizing, we'll focus here on what is new.

#What is LinkedHashSet?

LinkedHashSet is a Set implementation that:

• Does not allow duplicates
• Maintains insertion order
• Allows one null
• Provides average O(1) add(), remove() and contains()
• Is not thread-safe

Package:

java.util.LinkedHashSet

Declaration:

public class LinkedHashSet<E>
        extends HashSet<E>
        implements Set<E>, Cloneable, Serializable

#The Key Difference

The easiest way to remember it:

Set<String> set = new LinkedHashSet<>();

set.add("Java");
set.add("Python");
set.add("Spring");
set.add("Java");

Java
Python
Spring

The duplicate "Java" is ignored, but its original position is retained.

#How Does LinkedHashSet Preserve Order?

This is the main interview question. LinkedHashSet uses a LinkedHashMap internally.

• The hash table provides efficient lookup.
• The linked list maintains insertion order.

Internal Architecture

So each entry participates in two structures: the hash table structure and a doubly linked list.

Simplified Internal Representation

set.add("A");
set.add("B");
set.add("C");

before and after References

This is an important internal detail. LinkedHashMap entries maintain links conceptually like:

Why Can't HashSet Simply Preserve Order?

HashSet's iteration order is determined by its hash-table structure. If elements are placed into different buckets (A → Bucket 5, B → Bucket 1, C → Bucket 7), there is no separate structure remembering A → B → C. LinkedHashSet adds that structure.

#What Happens During add()?

set.add("Java");

So a successful insertion:

1. Places the entry in the hash table.
2. Links the entry into the insertion-order chain.

What Happens with a Duplicate?

set.add("Java");
set.add("Java");

First: Java → inserted. Second: Java → already exists → rejected. No second linked-list node is created. Therefore the order is Java → Python → Spring, not Java → Python → Spring → Java.

Does remove() Preserve the Remaining Order?

Yes. Suppose A → B → C → D and you remove B. The links are adjusted to A → C → D, so iteration produces A, C, D. The relative order of the remaining elements is preserved.

Re-Adding an Existing Element

Important interview trap:

Set<String> set = new LinkedHashSet<>();

set.add("A");
set.add("B");
set.add("C");
set.add("A");

[A, B, C]

It does not move A to the end. Why? Because the second add("A") is a duplicate and does not create a new insertion.

#LinkedHashSet vs HashSet

The key trade-off: more memory + slightly more bookkeeping → predictable iteration order.

#LinkedHashSet vs TreeSet

Don't confuse these: LinkedHashSet keeps insertion order, TreeSet keeps sorted order.

Example input 40, 10, 30, 20:

• LinkedHashSet → 40, 10, 30, 20
• TreeSet → 10, 20, 30, 40

Choose based on the required ordering semantics.

#Null Handling

LinkedHashSet allows one null.

Set<String> set = new LinkedHashSet<>();

set.add(null);
set.add(null);
set.add("Java");

null
Java

Only one null exists because duplicates aren't allowed.

#Performance and Memory

Why Can LinkedHashSet Iteration Be Better Than HashSet?

Suppose Size = 100 but Capacity = 1,000,000. HashSet iteration can involve scanning the underlying table structure. LinkedHashSet maintains a linked chain containing only actual entries.

So LinkedHashSet iteration is proportional to the number of elements rather than the hash-table capacity. This is an important performance detail.

Memory Overhead

LinkedHashSet requires additional links to maintain order. Conceptually, each entry needs:

• Hash information
• Key
• Value / dummy value
• Next link
• Previous link

Therefore LinkedHashSet > HashSet in memory usage. The exact footprint depends on the JVM implementation and object layout.

#When to Use LinkedHashSet

Use it when you need unique elements + original insertion order.

Remove duplicates while preserving order

List<String> names = Arrays.asList("A", "B", "A", "C", "B");

Set<String> unique = new LinkedHashSet<>(names);

[A, B, C]

API response

Suppose an API must return unique values while preserving the order in which they were encountered:

Set<String> result = new LinkedHashSet<>();

Ordered permissions

Set<String> permissions = new LinkedHashSet<>();

Useful when permissions must be unique but displayed in configuration order.

When NOT to use LinkedHashSet

#Thread Safety and Fail-Fast Behaviour

Is LinkedHashSet Thread-Safe?

No. Just like HashSet, LinkedHashSet is not synchronized. For synchronized access:

Set<String> set = Collections.synchronizedSet(new LinkedHashSet<>());

For concurrent workloads, choose a collection designed for the required concurrency semantics rather than automatically wrapping everything.

Fail-Fast Behaviour

Its iterator is generally fail-fast:

for (String value : set) {
    if (value.equals("B")) {
        set.remove(value);
    }
}

ConcurrentModificationException

Use the iterator's own remove() when removing during iteration:

Iterator<String> iterator = set.iterator();

while (iterator.hasNext()) {
    String value = iterator.next();
    if (value.equals("B")) {
        iterator.remove();
    }
}

As discussed earlier, fail-fast behaviour is best effort, not a synchronization mechanism.

#LinkedHashSet Does NOT Mean Sorted

This is one of the easiest interview traps. Input 50, 10, 30, 20 → LinkedHashSet gives 50, 10, 30, 20. It preserves insertion order; it does not sort. If you need 10, 20, 30, 50, use TreeSet.

#Decision Table

Final Mental Model

HashSet answers "Is this element present?" LinkedHashSet answers "Is this element present, and in what insertion order should I iterate?"