skip to content

What is the difference between HashSet and LinkedHashSet, and when would you choose one over the other?

level: middleimportance: must knowfreq 70%

answer

  1. LinkedHashSet extends HashSet + a doubly-linked list
  2. HashSet: no order; LinkedHashSet: insertion order
  3. Same average O(1) ops, same equals/hashCode uniqueness
  4. LinkedHashSet costs 2 extra pointers per entry
  5. Re-adding an element does not change its position

basics

~10 s

Both store unique elements. HashSet has no defined iteration order, while LinkedHashSet remembers the order you added items and iterates them in that insertion order. Choose LinkedHashSet when order matters.

solid answer

~40 s

HashSet and LinkedHashSet both implement Set and both reject duplicates using equals()/hashCode(), with average O(1) add, remove, and contains. The difference is iteration order. HashSet gives none — order is an artefact of hashing and may change on rehash. LinkedHashSet extends HashSet and additionally threads a doubly-linked list through all entries, so iteration follows insertion order (predictable and reproducible). The cost is slightly higher memory (two extra pointers per entry) and marginally slower mutation. Choose HashSet when you only need fast membership and de-duplication and order is irrelevant — it is the lightest. Choose LinkedHashSet when you need deterministic, insertion-ordered iteration: building stable output, deterministic tests, or removing duplicates from a list while preserving original order. For sorted rather than insertion order you would use TreeSet instead.

code

java · 8 lines
java
Set<String> hash = new HashSet<>();
Set<String> linked = new LinkedHashSet<>();
for (String s : List.of("c", "a", "b", "a")) { hash.add(s); linked.add(s); }

// linked is guaranteed to iterate: c, a, b  (insertion order, dup 'a' ignored)
System.out.println(linked); // [c, a, b]
// hash order is unspecified — could be [a, b, c] or anything
System.out.println(hash);

go deeper

for a junior

Knows LinkedHashSet keeps insertion order and HashSet does not, and that both hold unique elements.

for a middle

Explains the inheritance relationship and the doubly-linked-list mechanism, plus the memory/speed trade-off and when each fits.

for a senior

Discusses determinism benefits (reproducible tests/output), rehash effects on HashSet order, and contrasts with TreeSet's sorted O(log n) semantics.

for a principal

Weighs footprint and predictability at scale, sets team conventions for when deterministic iteration is required (e.g. serialized/logged collections), and knows the LinkedHashMap access-order capability behind it.

## Start with what they share Both `HashSet` and `LinkedHashSet` are implementations of the `Set` interface — collections of **unique** elements. Both: - decide uniqueness via `equals()` and `hashCode()`, - give **average O(1)** `add`, `remove`, and `contains`, - allow a single `null`, - are **not thread-safe**. In fact `LinkedHashSet extends HashSet` — it is the same machine with one feature bolted on. ## The single difference: iteration order **Iteration order** is the sequence in which a for-each loop or iterator visits the elements. - **HashSet**: order is **undefined**. It comes from where elements land in the internal hash buckets, which depends on their hash codes. When the set grows past its load-factor threshold it **rehashes** (rebuilds the bucket array), and the visible order can change entirely. So you must treat HashSet order as arbitrary. - **LinkedHashSet**: order is **insertion order** — the order in which elements were first added. Re-adding an existing element does **not** move it. ## How LinkedHashSet achieves order LinkedHashSet reuses HashSet's bucket storage for fast lookup, and **additionally** maintains a **doubly-linked list** that runs through every entry in insertion order. Each entry stores two extra pointers (`before` and `after`). Iteration simply walks this linked list head-to-tail, which is why the order is stable and independent of bucket layout. (Internally it sets a flag on the underlying `LinkedHashMap` to keep this list.) ## The cost of ordering - **Memory**: each LinkedHashSet entry carries two extra references, so it uses more memory per element than HashSet. - **Speed**: mutations are marginally slower because the linked list must be maintained, but the big-O is the same (O(1) average). - **Iteration**: LinkedHashSet iteration can actually be slightly *faster* and more cache-friendly than HashSet's, because it walks a list rather than skipping over empty buckets. ## How to choose | Need | Pick | |---|---| | Fast membership / de-dup, order irrelevant, lightest footprint | **HashSet** | | Same, but iteration must follow insertion order (stable output, deterministic tests, de-dup a list preserving order) | **LinkedHashSet** | | Elements must come out **sorted** | **TreeSet** (different — O(log n), no null) | ## A concrete reason LinkedHashSet matters Deterministic iteration makes tests reproducible and output stable across JVM runs and versions. If you log or serialize a HashSet you may get a different order on another machine; LinkedHashSet won't surprise you.

  • Does re-adding an element that's already in a LinkedHashSet move it to the end?
    No. LinkedHashSet preserves first-insertion order; add() on an existing element returns false and leaves its position untouched. (Access-order reordering exists for LinkedHashMap via a constructor flag, but LinkedHashSet does not expose it.)
  • If both are O(1), why not always use LinkedHashSet?
    It carries two extra pointers per element (more memory) and slightly slower mutation. When order genuinely doesn't matter, HashSet is the leaner choice; paying for ordering you don't use is waste.

HashSet is a bag of marbles — pull them out in whatever order they tumble. LinkedHashSet is the same bag but with a string tied through the marbles in the order you dropped them in, so you can always retrace that order.

saying these in an interview costs you the question

  • Saying LinkedHashSet sorts elements (it preserves insertion order, not sorted order)
  • Claiming LinkedHashSet is a fundamentally different data structure rather than HashSet + a linked list
  • Thinking re-adding an existing element re-orders it
  • Assuming LinkedHashSet is much slower in big-O terms

context

resolving links…