How LinkedHashSet Maintains Insertion Order in Java

When you iterate over a LinkedHashSet, elements appear in the order they were added. That is the core behavior behind the java linkedhashset order guarantee, and it is the main reason developers choose this implementation over a plain HashSet. A HashSet makes no promise about iteration order, so the same set of strings can surface in a different sequence across runs or after rehashing. LinkedHashSet fixes that by keeping a doubly linked list of its entries alongside the hash table.

What LinkedHashSet Order Actually Guarantees

The contract is simple: iteration order matches the order in which elements were first inserted. If you add "alpha", then "beta", then "gamma", iterating the set produces those three strings in exactly that sequence. The guarantee applies to the iterator returned by iterator(), as well as to forEach and the enhanced for loop.

This is different from sorting. LinkedHashSet does not sort elements; it only remembers the sequence of first insertion. If you need elements in natural or custom sorted order, TreeSet is the implementation you want.

How LinkedHashSet Maintains the Order

LinkedHashSet extends HashSet and delegates its storage to a LinkedHashMap. The map keeps the same hash-based lookup as HashMap, but each entry also carries before and after references that form a doubly linked list. When a new element is inserted, the map appends it to the tail of that list. Iteration then walks the list from head to tail, which is why the order comes out as insertion order.

The important detail is that the linked list is independent of the hash buckets. Rehashing, which moves entries between buckets when the table grows, does not disturb the linked list. So even after the set resizes, iteration order remains stable.

Demonstrating Insertion Order with Code

A small example makes the behavior concrete:

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetOrderDemo {
    public static void main(String[] args) {
        Set<String> visitedRoutes = new LinkedHashSet<>();
        visitedRoutes.add("/home");
        visitedRoutes.add("/products");
        visitedRoutes.add("/cart");
        visitedRoutes.add("/checkout");

        for (String route : visitedRoutes) {
            System.out.println(route);
        }
    }
}

The output is:

/home
/products
/cart
/checkout

If you replace LinkedHashSet with HashSet, the same code may print the routes in a different order, and that order can change when the set grows past a threshold and rehashes. LinkedHashSet removes that unpredictability for cases where the sequence of first appearance matters.

Re-inserting an Existing Element Does Not Move It

A common mistake is assuming that adding an element a second time moves it to the end. It does not. Set.add returns false when the element is already present, and LinkedHashSet leaves the existing entry untouched. The linked list keeps the element at its original position.

Set<String> colors = new LinkedHashSet<>();
colors.add("red");
colors.add("green");
colors.add("blue");
colors.add("red"); // already present, ignored

System.out.println(colors); // [red, green, blue]

The duplicate "red" is not appended to the tail. This behavior comes from LinkedHashMap, which defaults to insertion-order mode (accessOrder is false). If you need a set that moves re-accessed elements to the end, you would have to build a custom LinkedHashMap with accessOrder set to true and use it as a key set, which is not what the standard LinkedHashSet does.

Performance Characteristics

LinkedHashSet has the same asymptotic cost as HashSet for the core operations: add, remove, and contains all run in constant time on average when the hash function distributes elements reasonably. The difference is memory. Each entry in the linked list carries two extra references (the before and after pointers), so LinkedHashSet uses more memory per element than a plain HashSet.

The practical impact is modest for most applications, but it is worth knowing when you are storing millions of elements. If the extra memory is unacceptable and order is not needed, HashSet is the lighter choice. If order is required, LinkedHashSet is usually the right tradeoff because it avoids the cost of sorting on every iteration.

Choosing Between HashSet, LinkedHashSet, and TreeSet

The three Set implementations differ in order guarantees, operation cost, and memory footprint:

Use HashSet when order does not matter and memory is a concern. Use LinkedHashSet when you need deterministic iteration matching first insertion, such as deduplicating a list while preserving the original sequence. Use TreeSet when you need elements in sorted order, not insertion order.

A typical use case for LinkedHashSet is removing duplicates from a collection while keeping the order of first occurrence:

List<String> raw = List.of("apple", "banana", "apple", "cherry", "banana");
Set<String> unique = new LinkedHashSet<>(raw);
System.out.println(unique); // [apple, banana, cherry]

The same operation with HashSet would produce an arbitrary order, which is often not what callers expect when the original sequence carries meaning.

Thread Safety and Concurrent Modification

LinkedHashSet is not thread-safe. If multiple threads read and write the same instance without external synchronization, the internal linked list and hash table can be corrupted, and iteration can throw ConcurrentModificationException when the set is modified during traversal. The same rules apply as for HashSet: either synchronize externally on the set, wrap it with Collections.synchronizedSet, or use a concurrent collection when concurrent access is expected. Note that Collections.synchronizedSet does not prevent ConcurrentModificationException during iteration; you still need to synchronize on the returned set while iterating.

For a thread-safe set that preserves insertion order, no standard concurrent implementation in the JDK offers that guarantee directly. You would need to synchronize access to a LinkedHashSet or use a ConcurrentSkipListSet if sorted order is acceptable, since it does not preserve insertion order.