Iterating LinkedHashSet
You'll learn: How LinkedHashSet's predictable iteration order differs from HashSet and TreeSet, and when that matters for performance.
The Iteration Order Guarantee
When you iterate over a LinkedHashSet, elements appear in exactly the order you inserted them—no exceptions. This is LinkedHashSet's defining feature. Compare this with:
- HashSet: Iteration order is unpredictable and may change over time (even between runs)
- TreeSet: Iteration order follows sorted order according to
compareToor a custom comparator - LinkedHashSet: Iteration order matches insertion order
Think of it like three different guest lists: HashSet scrambles names randomly, TreeSet alphabetizes them, but LinkedHashSet preserves the exact order guests signed up.
Iteration Performance
All three Set types iterate through their elements in O(n) time—you must visit each element once. However, the practical performance differs:
LinkedHashSet maintains explicit links between entries (like LinkedList nodes). The iterator simply follows these links from first-to-last, visiting only actual elements. Fast and efficient.
HashSet must walk through its entire backing array, checking each bucket for elements. Many buckets are empty, so the iterator wastes time skipping them. Slower than LinkedHashSet when the set is sparsely populated.
TreeSet traverses its red-black tree structure (in-order traversal). This involves more complex pointer-following than LinkedHashSet's simple linked list.
For iteration-heavy workloads where you need predictable order, LinkedHashSet offers the best of both worlds: HashSet-like add/contains/remove speed plus efficient, ordered iteration.
Key Takeaway: LinkedHashSet iterates in insertion order via efficient linked-list traversal, typically faster than HashSet (no empty bucket skipping) and simpler than TreeSet (no tree traversal), making it ideal when both order and iteration performance matter.