Course contentsShow
← Java
Lesson 1078 of 2,87025. Set ImplementationsFree lesson

Internal Structure: HashMap with Linked List

Exploring how LinkedHashSet uses a LinkedHashMap internally to maintain doubly-linked entry chains.

Internal Structure: HashMap with Linked List

What you'll learn: How LinkedHashSet uses a LinkedHashMap under the hood to maintain insertion order through doubly-linked entries.

The Two-Layer Structure

Just as HashSet wraps HashMap (as you've learned), LinkedHashSet wraps a special variant called LinkedHashMap. This internal map does double duty: it provides fast hash-based lookup and maintains a doubly-linked list threading through all entries.

HashMap + Doubly-Linked Chain

Think of LinkedHashMap as a regular hash table where each bucket entry has been upgraded with two extra pointers: before and after. These create a separate linked list that runs through all entries in insertion order, completely independent of their bucket positions.

Analogy: Imagine a library where books are organized on shelves by category (the hash buckets), but there's also a numbered chain connecting every book in the exact order they were purchased—regardless of which shelf they're on.

How It Maintains Order

When you add an element to LinkedHashSet:

  1. The element becomes a key in the internal LinkedHashMap
  2. It's placed in the appropriate hash bucket (via hashCode)
  3. It's also linked to the end of the doubly-linked chain (via before/after pointers)

When you iterate, LinkedHashSet doesn't traverse buckets randomly—it follows the linked chain from head to tail, giving you insertion order.

Why This Design Works

This dual structure keeps both guarantees intact:

  • O(1) operations through hashing
  • Predictable iteration order through the linked list

The extra memory cost (two pointers per entry) is the price paid for maintaining order.

Key Takeaway: LinkedHashSet uses LinkedHashMap internally, where each entry participates in both a hash table (for fast lookups) and a doubly-linked list (for insertion-order iteration).