LinkedHashSet is a Set that remembers the order in which its elements were inserted. It provides the same uniqueness guarantee and the same average O(1) add, remove, and contains as HashSet, but iterating over it walks elements in the order they were first added rather than in some scrambled hash order. This lesson covers what changes underneath when insertion order is preserved, the cost of that extra bookkeeping, the common e-commerce use cases (recently viewed unique products, unique browsed categories, applied coupon codes in the order they were entered), and how LinkedHashSet compares to HashSet and TreeSet.

The defining behavior of LinkedHashSet is also its only behavioral difference from HashSet: iteration returns the elements in the order they were first inserted. Re-inserting an element that's already there doesn't change its position, because the second add is a no-op for a Set.

A small program to see this directly. A storefront shows the customer the unique products viewed today. Each click adds a product to a tracker, duplicates should be ignored, and the display should list the products in the order the customer first viewed them.

Two observations. The second add("Pen") was ignored, because "Pen" was already in the set. And the order in the output matches the order of the first time each product was added, not the order of all five calls and not some hash-driven order.

The same five calls against a HashSet produce a very different result:

The output order isn't random in a true sense, it's determined by hash codes and bucket positions, but from the caller's point of view it's unpredictable. For code that doesn't care about iteration order, that's fine. For code that does, LinkedHashSet is the right type.

The performance picture stays attractive. add, remove, and contains all run in average O(1), the same as HashSet. The class is a thin extension over HashSet, and the underlying storage is a LinkedHashMap.

Iteration over a LinkedHashSet is proportional to the number of elements, not to the capacity of the underlying table. Iterating a HashSet with the same elements can be slower in practice when the table is sparse, because the iterator has to walk over empty buckets.

LinkedHashSet extends HashSet, and its backing store is a LinkedHashMap instead of a plain HashMap. The buckets-and-chains structure is still there, so lookups by hash code work the same way. The extra piece is a doubly-linked list that threads through every entry in the order they were inserted.

Each entry in the underlying map has the usual hash and bucket pointers, plus two extra fields: a reference to the entry that was inserted just before it and a reference to the entry that was inserted just after. The set as a whole keeps a head pointer (the first inserted entry) and a tail pointer (the most recent insertion). An add of a new element appends the new entry to the tail of this linked list. A remove unlinks the entry from its neighbors before the bucket chain is updated.

The solid lines show the hash buckets. Each unique product lives in whichever bucket its hash code maps to, the same as in a HashSet. The dotted arrows show the insertion-order linked list overlaid on top. Iteration walks this list, head to tail, which is why the iterator produces Notebook, Pen, Eraser, Backpack even though the buckets put those elements in a different order.

The dual structure has two notable consequences. First, the per-element memory cost is higher than HashSet, because each entry carries two extra reference fields (the prev and next pointers in the linked list). On a 64-bit JVM with compressed object pointers, that's roughly 16 extra bytes per element, which usually doesn't matter unless the set is very large. Second, iteration is faster and more predictable. The iterator follows the linked list and doesn't have to scan empty buckets, which makes LinkedHashSet iteration consistently linear in the number of elements.

A program that demonstrates the iteration behavior, with both successful lookups and a remove:

Removing "Stationery" unlinked it from between "Books" and "Bags". Re-adding it afterward put it back at the tail of the linked list, because that re-insertion was a new addition (the entry didn't exist when add was called). The iteration walks the current list, which now ends with "Stationery".

One detail: re-adding a value that's already present does not move it to the tail. The earlier Notebook -> Pen -> Eraser -> Backpack example showed this. The behavior is different from a queue or a list, where the second occurrence would always end up at the end. With LinkedHashSet, position is set the first time the element is inserted and only changes if the element is removed and added again.

For a Set where presentation order also matters, LinkedHashSet is the default choice. A few concrete e-commerce patterns:

Recently viewed unique products. A customer clicks around the store, and the UI shows a strip of products viewed, with duplicates collapsed but the order preserved. HashSet provides the dedup but loses the order. A List provides the order but lets duplicates in. LinkedHashSet provides both in one call per click.

Four unique products, in the order they were first viewed. The duplicate clicks on "Notebook" and "Pen" are absorbed silently, and the order matches the customer's actual browsing pattern.

Unique browsed categories in click order. Same shape as the previous example, with categories instead of products. The output strip on the homepage might read "You browsed: Books, Bags, Electronics", and a LinkedHashSet is the simplest way to build the underlying data.

Applied coupon codes in the order they were entered. Consider a checkout where the customer types in coupon codes one by one. Each new code that hasn't been entered before should be applied, duplicates should be ignored with no error, and the receipt should list the codes in the order the customer entered them.

add returns true when the element was new and false when it was already present. That return value alone is enough to drive both the "applied" and "already applied" messages without an extra contains call.

Building a deterministic test fixture. For a test that uses a Set and needs stable output across runs and JVM versions, LinkedHashSet is a safer choice than HashSet. The order is determined by code, not by the hash codes of the chosen elements.

When not to use it. Without iteration, or with iteration order that doesn't matter, plain HashSet is slightly cheaper in memory and is the right default. For elements in a sorted order (alphabetical, numerical, by some comparator), LinkedHashSet is the wrong tool, because it preserves insertion order, not sorted order. TreeSet covers that case.

The constructors look exactly like HashSet's, because LinkedHashSet extends HashSet and inherits the same set of overloads.

The copy constructor comes up most often. It takes an existing collection (such as a List of viewed products with duplicates) and produces a LinkedHashSet that dedups while preserving the original order.

The constructor walks clicks in order, calling add for each element. The first time it sees each unique product, the entry goes into the linked list. Later duplicates are silently dropped. The result is the input list, deduplicated, in the order each unique value first appeared.

The capacity hint matters when the approximate size is known up front. Loading 10,000 unique tags without a capacity hint starts the underlying table at 16 and resizes (doubling each time) until it can hold them. Each resize rehashes every entry and rewires the linked list. Pre-sizing the table avoids this churn.

The set behaves the same as one created with new LinkedHashSet<>(), without the resizes that would happen growing from the default capacity of 16 to a thousand elements.

Sizing a LinkedHashSet too small causes repeated rehashes, each one O(n) in the current size. Sizing it too large wastes memory on empty buckets but doesn't change iteration cost, because iteration walks the linked list, not the bucket array.

Three implementations of Set, three different stories about order and cost. The differences are easier to keep straight in a table.

A small program that puts the three side by side:

The HashSet output is determined by hash codes. The LinkedHashSet output mirrors the input order, with the duplicate "books" collapsed. The TreeSet output is alphabetical. Three reasonable choices, depending on what you need from the iteration.

A guideline: if "does order matter?" is no, use HashSet. If the answer is "yes, insertion order", use LinkedHashSet. If the answer is "yes, sorted by some natural ordering", use TreeSet.