JAVA / COLLECTIONS
LinkedHashSet and insertion-order iteration
Use LinkedHashSet to deduplicate while iterating in first-insertion order, and predict exactly when an element's position can change.
What you will learn
- Build order-preserving unique collections with new LinkedHashSet<>(collection).
- Explain why re-adding an existing element leaves its position unchanged.
- Move an element to the end by removing it first, then adding it back.
- Collect streams with toCollection(LinkedHashSet::new) instead of toSet().
Understanding LinkedHashSet and insertion-order iteration
A LinkedHashSet is a hash table with a doubly-linked list threaded through its entries. Membership tests and inserts still go through the element's hash, exactly as in HashSet, so add and contains stay constant time on average; the list exists only to remember what came before what. Every element therefore carries two extra references, before and after, and that is the memory you pay for order.
The order recorded is first-insertion order, and the word first is the whole story. add begins by hashing the element and looking for an existing entry; when it finds one it returns false and stops there, so the before and after links are never touched and the element keeps the position it earned the first time it went in. The only way to move something is remove followed by add, which unlinks the old node and appends a fresh one at the tail. LinkedHashMap can be constructed in access-order mode where a read relinks an entry, but LinkedHashSet exposes no such constructor, so reads and repeated adds are always order-neutral.
Order survives growth because a resize only rebuilds the bucket array; rehashing does not touch the before and after links, so iteration order never depends on capacity or on hash values. That same independence makes iteration cost proportional to the number of elements rather than to the table size: over 20 elements in a set created with capacity 10000, a LinkedHashSet iterator visits 20 nodes while a HashSet iterator has to scan 10000 slots looking for occupants.
import java.util.LinkedHashSet;
import java.util.Set;
public class OrderedSetDemo {
public static void main(String[] args) {
Set<String> stops = new LinkedHashSet<>();
stops.add("Kings Cross");
stops.add("Farringdon");
stops.add("Moorgate");
stops.add("Farringdon");
System.out.println(stops);
System.out.println("add returned: " + stops.add("Moorgate"));
stops.remove("Kings Cross");
stops.add("Kings Cross");
System.out.println(stops);
System.out.println("size = " + stops.size());
}
}Insertion order in a LinkedHashSet is held by a separate linked list that only a successful first add ever appends to, which is why re-adding an existing element never reorders it.
Worked examples
Deduplicating without losing order
Shows the same input collected into a LinkedHashSet and a HashSet, and why only one of the two results is something you can rely on.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
public class Dedupe {
public static void main(String[] args) {
List<Integer> codes = Arrays.asList(9, 3, 9, 12, 3, 7);
System.out.println(new LinkedHashSet<>(codes));
System.out.println(new HashSet<>(codes));
List<Integer> unique = new ArrayList<>(new LinkedHashSet<>(codes));
System.out.println("first code seen: " + unique.get(0));
}
}Example explained
Line 1The LinkedHashSet constructor inserts left to right, so the repeated 9 and 3 are rejected and the survivors keep their first-appearance positions.
Line 2The HashSet line happens to print in ascending order because these small Integer hashes map straight onto bucket index hash & 15 and the iterator scans buckets by index; nothing in the API promises that.
Line 3new ArrayList<>(set) copies in iteration order, which is why unique.get(0) is 9, the first code seen, and not the smallest code.
Order is not part of set identity
Two LinkedHashSets built in opposite orders compare equal even though they iterate differently.
import java.util.LinkedHashSet;
import java.util.Set;
public class SetEquality {
public static void main(String[] args) {
Set<String> a = new LinkedHashSet<>();
a.add("red");
a.add("green");
a.add("blue");
Set<String> b = new LinkedHashSet<>();
b.add("blue");
b.add("green");
b.add("red");
System.out.println(a);
System.out.println(b);
System.out.println("equals: " + a.equals(b));
System.out.println("same hashCode: " + (a.hashCode() == b.hashCode()));
System.out.println(a.iterator().next() + " vs " + b.iterator().next());
}
}Example explained
Line 1a.equals(b) is true because set equality is defined as equal size plus mutual containment, and it never consults iteration order.
Line 2The hash codes match because a Set's hashCode is the sum of its elements' hash codes, and addition ignores order.
Line 3The two iterators still hand back different first elements, which is the point: order is a property of traversal here, not of the set's value.
Line 4Consequence for tests: assertEquals on two sets will not catch an ordering bug, so assert on a List copy instead.
Important notes
Set.of(...) and Collectors.toSet() leave iteration order unspecified, and Set.of deliberately varies its order between JVM runs, so a test that passes locally can fail on another machine; copy into a LinkedHashSet when order is part of the contract.
The iterator is fail-fast, so adding or removing through the set inside a for-each throws ConcurrentModificationException; the class is also unsynchronized, so shared instances need Collections.synchronizedSet or external locking.
Common mistakes
Expecting add on an element that is already present to move it to the end, as LinkedHashMap in access-order mode would. The set silently keeps the old position and returns false, so a hand-rolled most-recently-used list never actually updates.
Reading insertion order as sorted order. Inserting 30, 10, 20 iterates 30, 10, 20, so treating the first element as the minimum gives 30; sorted uniqueness needs TreeSet.
Mutating a field used by an element's hashCode after inserting it. The element still appears during iteration because the linked list holds it, but contains and remove hash to the wrong bucket and report it as absent, so the set can never be cleaned up.
Try it yourself
Change, predict, then run
Starting from Arrays.asList("delta", "alpha", "delta", "beta", "alpha"), print the unique words in first-appearance order, then make "alpha" the last element without disturbing the relative order of the others. Print the set before and after to confirm that a plain add on "alpha" would not have done it.
Open the Java workspaceCheck your understanding
A LinkedHashSet holds "a", "b", "c", inserted in that order. You call set.add("a") and then iterate. What happens?
- Iteration gives a, b, c; add returned false and never touched the links, so "a" keeps its original position
- Iteration gives b, c, a; add returned false but the entry was relinked at the tail as the most recent one
- Iteration gives b, c, a; add returned true because touching an element counts as a structural modification
- Iteration gives a, b, c on this JVM, but the order is unspecified so another JVM may print something else
Show answer
add hashes the element, finds the existing entry, and returns false immediately; the before and after pointers are only written when a genuinely new node is appended, so the position is untouched. Option 2 describes LinkedHashMap built with accessOrder true, a mode LinkedHashSet has no constructor for. Option 4 confuses LinkedHashSet with HashSet or Set.of, whose orders really are unspecified, whereas insertion-order iteration here is part of the documented behaviour.