Internal Working of LinkedHashSet in Java

Introduction

A LinkedHashSet in Java is a part of the java.util package and is used to store unique elements while maintaining insertion order. It extends HashSet and uses a linked list to maintain order. Unlike HashSet, which does not guarantee the order of elements, LinkedHashSet ensures elements are returned in the same order they were inserted.

---

1. Data Structure Used

LinkedHashSet is implemented using a combination of HashMap and a doubly linked list. It ensures:

• Unique elements (via HashMap for fast lookups)
• Preserved insertion order (via a doubly linked list that maintains the order of elements)

Implementation in Java:

public class LinkedHashSet<E> extends HashSet<E> {
    private transient LinkedHashMap<E,Object> map;
}

• The map is an instance of LinkedHashMap, which maintains insertion order.
• Elements are stored as keys, and a dummy object (PRESENT) is stored as values.

Internally, LinkedHashMap maintains a doubly linked list, ensuring elements retain their insertion order while benefiting from fast lookups using hashing.

---

2. How Elements are Stored and Accessed

Adding an Element

When add() is called:

1. The element is stored as a key in LinkedHashMap.
2. The key’s insertion order is recorded using a doubly linked list.
3. If the element already exists, it is not inserted again.

Example:

LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Cherry");
System.out.println(set); // Output: [Apple, Banana, Cherry]

Retrieving an Element

Elements are accessed using iteration, preserving insertion order:

for (String item : set) {
    System.out.println(item);
}

Output:

Apple
Banana
Cherry

Unlike HashSet, where elements are returned in an unpredictable order, LinkedHashSet preserves insertion order.

Removing an Element

When remove() is called:

1. The key is removed from the HashMap.
2. The corresponding node in the doubly linked list is also removed.
3. The links between the previous and next elements are updated to maintain order.

Example:

set.remove("Banana");
System.out.println(set); // Output: [Apple, Cherry]

---

3. Internal Working of LinkedHashMap (Behind LinkedHashSet)

How the LinkedHashSet Uses LinkedHashMap

• The LinkedHashMap contains a table (hash array) for quick lookups.
• Each entry in the LinkedHashMap has pointers (before and after) to maintain insertion order.
• When elements are added, they are stored in both the hash table and the linked list.

Node Structure in LinkedHashMap

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
}

• before and after keep track of element order.
• Ensures iteration order is maintained efficiently.

---

4. Performance Analysis

Operation	Time Complexity
Add Element	O(1)
Get Element	O(1)
Remove Element	O(1)
Iteration	O(n)

Comparison with HashSet

Feature	LinkedHashSet (Ordered)	HashSet (Unordered)
Maintains Insertion Order	✅ Yes	❌ No
Performance	⏳ Slightly Slower	⚡ Faster
Best Use Case	Ordered Unique Elements	Fastest Unique Lookup

---

5. Use Cases of LinkedHashSet

1. Maintaining Order in Caching Mechanisms: Since LinkedHashSet maintains order, it is useful in LRU Cache implementations.
2. Eliminating Duplicates While Maintaining Order: When processing a list and needing unique values while keeping order, LinkedHashSet is ideal.
3. Efficient Iteration with Predictable Ordering: Unlike HashSet, it allows predictable iteration, making it useful in ordered datasets.

---

6. Key Takeaways

✔ LinkedHashSet is a HashSet with ordering, keeping insertion order.

✔ Uses a doubly linked list for maintaining order.

✔ Fast lookups (O(1)) but slightly slower than HashSet due to additional ordering overhead.

✔ Internally backed by LinkedHashMap, which maintains order using before-after pointers.

✔ Ideal when both uniqueness and ordering are required.

Understanding the internal working of LinkedHashSet helps in selecting the right data structure based on performance and ordering needs.