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:
- The element becomes a key in the internal
LinkedHashMap - It's placed in the appropriate hash bucket (via
hashCode) - It's also linked to the end of the doubly-linked chain (via
before/afterpointers)
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).