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. add() on an existing element keeps 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

~50 s

HashSet and LinkedHashSet both implement Set and both reject duplicates using equals()/hashCode(), with average O(1) add, remove, and contains. The core 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). Since JDK 21 its addFirst and addLast move an element already present.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 core 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. So you must treat HashSet order as arbitrary. - **LinkedHashSet**: order is **insertion order** — the order in which elements were first added. Calling `add` on an existing element does **not** move it; removing it and adding it again does, and since JDK 21 so do `addFirst` and `addLast`. ## 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, its constructors call a package-private `HashSet` constructor that makes the backing map a `LinkedHashMap`; that constructor's boolean argument is ignored and only distinguishes the overload.) ## 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 takes time proportional to its **size**, regardless of capacity, while HashSet's is proportional to size plus capacity, because it must also pass over empty buckets. ## Since JDK 21: a sequenced set Since JDK 21, so on 25 LTS and 27 alike, `LinkedHashSet` implements `SequencedSet`. `addFirst(e)` and `addLast(e)` **relocate** an element already present, without a remove first, and it also has `getFirst()`, `getLast()`, `removeFirst()`, `removeLast()` and `reversed()`. `HashSet` has none of these. ## 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); `null` only with a comparator that permits it) | ## A concrete reason LinkedHashSet matters Insertion-ordered iteration makes tests reproducible and output stable across JVM runs and versions, provided the elements go in in the same order. 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. add() on an existing element returns false and leaves its position untouched. To move it, call addFirst or addLast (JDK 21+), or remove it and add it again. (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 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 add() on an existing element moves it to the end
  • Assuming LinkedHashSet is much slower in big-O terms

LinkedHashSet addFirst and addLast
Java 21

Assumes JDK 27. LinkedHashSet became a SequencedSet in JDK 21, gaining addFirst, addLast, getFirst, getLast, removeFirst, removeLast and reversed, so they work the same on 25 LTS; before 21 it had no repositioning methods.

context