Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Java HashSet vs LinkedHashSet: Ordering and Tradeoffs

Compare HashSet and LinkedHashSet in Java: ordering guarantees, internal structure, memory costs, iteration behavior, and when to choose each implementation.

~5 min readJava
#HashSet#LinkedHashSet#Java Collections#Set Interface
Illustration comparing HashSet's unordered bucket layout with LinkedHashSet's insertion-ordered linked structure.

When you need a Set in Java, the default choice is usually HashSet. But LinkedHashSet exists for a specific reason: it preserves insertion order while keeping the same uniqueness guarantees. The practical question is whether that ordering guarantee is worth the extra memory and the slightly different iteration behavior.

The Ordering Difference That Matters

HashSet stores elements based on their hash codes. The iteration order depends on the hash values and the internal bucket layout, which means it is effectively unpredictable and can change when the set is resized. LinkedHashSet extends HashSet and adds a doubly-linked list that connects the elements in the order they were inserted.

For normal Set operations, this is the only behavioral difference. Both implement Set, both reject duplicates, both allow at most one null element, and both have the same add, remove, and contains semantics. The ordering guarantee is the entire reason LinkedHashSet exists.

How Each Collection Is Built Internally

HashSet is backed by a HashMap instance. When you call add(element), the element is stored as a key in the backing map with a constant dummy value. LinkedHashSet extends HashSet and overrides the internal map creation so that a LinkedHashMap is used instead. The linked structure inside LinkedHashMap is what tracks insertion order.

This inheritance relationship also affects the constructors. LinkedHashSet exposes the same public constructors as HashSet:

  • LinkedHashSet()
  • LinkedHashSet(Collection<? extends E> c)
  • LinkedHashSet(int initialCapacity)
  • LinkedHashSet(int initialCapacity, float loadFactor)

The default initial capacity is 16 and the default load factor is 0.75, matching HashSet.

Iteration Behavior in Practice

Consider this example:

java
import java.util.HashSet; import java.util.LinkedHashSet; import java.util.Set; public class SetOrderDemo { public static void main(String[] args) { Set<String> hashSet = new HashSet<>(); Set<String> linkedHashSet = new LinkedHashSet<>(); String[] values = {"alpha", "beta", "gamma", "delta"}; for (String value : values) { hashSet.add(value); linkedHashSet.add(value); } System.out.println("HashSet: " + hashSet); System.out.println("LinkedHashSet: " + linkedHashSet); } }

The HashSet output is not guaranteed to match insertion order. It depends on the hash codes and the current internal table size, so the order is not part of the class contract and can change when the set is resized or in a different Java version. The LinkedHashSet output, by contrast, will always be this for the insertion order shown:

[alpha, beta, gamma, delta]

One subtle point: re-adding an element that is already present does not change its position in the LinkedHashSet. If you insert "alpha", then "beta", then "alpha" again, the set still contains only one "alpha" and the iteration order remains alpha, beta. The insertion order is the order of first insertion, not the order of the most recent add call.

Memory and Runtime Tradeoffs

The linked list inside LinkedHashSet adds a per-element cost. Each entry holds references to the previous and next entry, so memory usage is higher than HashSet for the same number of elements. For small sets this overhead is negligible, but for sets with hundreds of thousands of entries it can matter.

Iteration is a different story. HashSet iteration must walk every bucket and then walk the chain inside each bucket. LinkedHashSet iteration walks the linked list directly, visiting each element in constant time per element. Because it avoids bucket-by-bucket traversal, iterating a LinkedHashSet can be faster in practice, though the exact difference depends on the hash distribution and the load factor. The tradeoff is memory for predictable, direct iteration.

There is no meaningful difference in add, remove, or contains complexity. Both are O(1) on average. The linked-list maintenance in LinkedHashSet adds a small constant overhead per insertion, but it does not change the asymptotic behavior.

Choosing Between HashSet and LinkedHashSet

Use HashSet when the iteration order does not matter. This is the common case for membership checks, deduplication, and set algebra operations where you only care about what is in the set, not the order it comes back in.

Use LinkedHashSet when you need to preserve insertion order while keeping Set semantics. A typical example is a deduplication pass that must also retain the order in which elements first appeared, such as removing duplicate entries from a list while keeping the original sequence:

java
public static <T> List<T> dedupePreservingOrder(List<T> input) { Set<T> seen = new LinkedHashSet<>(input); return new ArrayList<>(seen); }

This pattern is common when processing user-facing lists where the order of first occurrence carries meaning.

If you need sorted order instead of insertion order, LinkedHashSet is the wrong tool. TreeSet provides natural ordering or a custom Comparator, at the cost of O(log n) operations. The decision is therefore: HashSet for unordered membership, LinkedHashSet for insertion order, TreeSet for sorted order.

Concurrency and Modification Behavior

Neither HashSet nor LinkedHashSet is thread-safe. If multiple threads modify the set concurrently, you must synchronize externally or wrap the instance with Collections.synchronizedSet. Both classes also use fail-fast iterators: if the set is structurally modified after the iterator is created, the iterator throws ConcurrentModificationException on the next access.

The fail-fast behavior applies equally to both classes. LinkedHashSet inherits the iterator() implementation from HashSet, but because the backing map is a LinkedHashMap, the returned iterator walks the linked list instead of the bucket chains. The structural modification detection works the same way.

Edge Cases and Compatibility Notes

Both classes allow one null element. Adding a second null is a no-op because the element already exists. The equals and hashCode contracts are identical because both inherit from AbstractSet.

Both classes are serializable, and the serialized form stores the set elements. For LinkedHashSet, the in-memory insertion-order guarantee is the important contract; if you need that order to survive a serialization round trip, verify it on your target runtime rather than assuming the same behavior.

One practical compatibility note: because LinkedHashSet extends HashSet, code that accepts a HashSet will also accept a LinkedHashSet. This can mask ordering assumptions. If a method signature declares HashSet and the caller passes a LinkedHashSet, the iteration order inside the method is insertion order, which may or may not be what the method expects. Prefer declaring the interface type (Set) and being explicit about ordering requirements in documentation.

Try matching browser tools

All tools

Small utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Java guides

More in Java

All Java guides

The guides filed next to this one in Java, in library order.