The java.util.LinkedHashSet is a hash table and linked list implementation of the Set interface. It differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order).
A LinkedHashSet isn't just one data structure; it's two working in perfect harmony. It uses a Hash Table to ensure uniqueness and fast lookups, and a Doubly-Linked List to preserve the sequence of elements.
Like a HashSet, it calculates the hash code of an element to find a bucket. This keeps the contains() and add() methods running at O(1).
Every element in a LinkedHashSet has a pointer to the element added before it and the element added after it. This makes iteration predictable.
Imagine you are building a "Recent Searches" feature. You want to store unique search terms, but you want to display them to the user in the exact order they were searched. A HashSet would scramble the order, and a TreeSet would sort them alphabetically. Only LinkedHashSet preserves the timeline.
There is no such thing as a free lunch in computer science. To get predictable ordering, you pay a small price in memory and a tiny bit of speed.
| Metric | HashSet | LinkedHashSet |
|---|---|---|
| Time Complexity | $O(1)$ | $O(1)$ (slightly slower constant factor) |
| Space Complexity | Lower | Higher (needs space for previous/next pointers) |
| Iteration Speed | Depends on capacity | Depends on size (often faster) |
Note: Iterating over a LinkedHashSet is actually faster than a HashSet if the initial capacity is much larger than the number of elements, because the linked list allows it to skip empty buckets.
Just like its cousin the HashSet, the LinkedHashSet relies on hashCode() to place items in buckets and equals() to check for duplicates. If you forget to override these in your custom objects, the LinkedHashSet will fail to enforce uniqueness, resulting in duplicate entries that break your application's logic.
In this example, we simulate a system that tracks the order of unique user logins. Notice how the order is preserved even though we are using a Set.
A critical detail about LinkedHashSet: if you attempt to re-insert an element that is already present, the insertion order is not affected. The element stays in its original position. To move it to the end, you must remove it first and then re-add it.
If memory is extremely scarce (like in small embedded systems or Android apps with massive lists), the overhead of two extra pointers per element can be a problem. In such cases, if you don't care about the order, stick with HashSet. If you need sorting, go for TreeSet.
Q: Is LinkedHashSet synchronized?
A: No. If multiple threads access it, you must wrap it: Collections.synchronizedSet(new LinkedHashSet(...)).
Q: What is the underlying data structure of LinkedHashSet?
A: It is a LinkedHashMap. Just as HashSet uses a HashMap, the LinkedHashSet uses the keys of a LinkedHashMap to function.
Q: Can LinkedHashSet contain multiple nulls?
A: No, only one null is allowed because it is a Set, and uniqueness must be maintained.
The LinkedHashSet is the professional choice for datasets where uniqueness and chronological order are equally important. It provides the elite speed of hashing while removing the "chaos" of random iteration. Use it for caches, history tracking, and any UI element where the order of appearance matters to the user.
Next: Exploring the Map Interface →