You are collecting SKUs from today’s orders. The question is not “the third line in the cart.” It is “have I already seen WB-40?” If that bag is an ArrayList, every check walks. The set ADT post already priced that scan. This post is the JDK types that implement the contract: HashSet when uniqueness is the only job, LinkedHashSet when uniqueness still has to come back in insertion order.
Both are HashMap wrappers. Neither is a sorted set. Hashing, buckets, and why “constant time” is expected live in Hash Tables. Fail-fast iterators, optional operations, sequenced as a name, and “do not mutate a key after insert” live on the collections hub. This post does not re-teach them.
HashSet: uniqueness without a sequence
Checkout already has the domain the hub named. Uniqueness here is on the identifier you put in the set — usually LineItem.sku(), not the whole line:
record LineItem(String sku, int quantity, BigDecimal unitPrice) {}
record Order(
String id,
String customerEmail,
List<LineItem> items,
BigDecimal total,
boolean active) {}
LineItem wb = new LineItem("WB-40", 2, new BigDecimal("8.50"));
LineItem nut = new LineItem("NUT-M8", 12, new BigDecimal("0.20"));
LineItem wbAgain = new LineItem("WB-40", 1, new BigDecimal("8.50"));
Order o1 = new Order("o-1", "ada@ex.com", List.of(wb, nut),
new BigDecimal("19.40"), true);
Order o2 = new Order("o-2", "grace@ex.com", List.of(wbAgain),
new BigDecimal("8.50"), true);
List<Order> orders = List.of(o1, o2);Two orders, three lines, two SKUs. A list of lines still has three members. A set of SKUs has two.
Set<String> skus = new HashSet<>();
for (Order order : orders) {
for (LineItem item : order.items()) {
skus.add(item.sku());
}
}
skus.contains("WB-40"); // true
skus.size(); // 2
skus.add("WB-40"); // false — already a memberadd returns whether membership changed. That is the set contract talking, not a leftover boolean. The same unique SKUs as a stream:
Set<String> skus = orders.stream()
.flatMap(order -> order.items().stream())
.map(LineItem::sku)
.collect(Collectors.toSet());Collectors.toSet() does not promise a class. In the JDK it is a HashSet. When you need a specific type, say so: Collectors.toCollection(LinkedHashSet::new).
If you put the LineItem in the set instead of the SKU, uniqueness is the whole record — quantity and price included:
Set<LineItem> lines = new HashSet<>();
lines.add(wb);
lines.add(wbAgain);
lines.size(); // 2 — same sku, different quantity, different memberHashSet uniques the element you inserted, not the field you meant. SKU identity belongs in Set<String> (or a small Sku record that is that identity).
It is a HashMap that threw the values away
Java’s HashSet is not a second hash-table implementation. It is a HashMap whose keys are the members and whose value is a shared dummy the set never shows you. add is put; contains is containsKey; remove is remove on that map. A sketch of the real relationship:
class HashSet<E> {
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
}That is why there is no index and no promised encounter order. Iteration walks the table, not “the order you inserted.” The hash-set ADT post named that layout; the hash table post is why membership is expected O(1) rather than a law.
HashSet is the default unique-membership type in application code. Program to Set. Construct a HashSet unless a later section names a reason not to.
The API you actually call
| Method / factory | Job |
|---|---|
add(e) | Insert if absent; true if the set grew |
contains(o) | Membership (hashCode, then equals, on the backing map) |
remove(o) | Drop if present; true if it was there |
iterator() | Fail-fast walk; no encounter order |
size() / isEmpty() | Count |
addAll / retainAll / removeAll / removeIf | Bulk; Collection contract |
new HashSet<>() | Capacity 16, load factor 0.75 |
new HashSet<>(n) | Capacity hint for the backing map (buckets, not “n slots forever”) |
HashSet.newHashSet(n) | Java 19+; sized so n adds should not resize at 0.75 |
Expected cost, with a decent hashCode and a load you respect: add / contains / remove expected O(1); iteration O(n) with no sequence. A bad hash, or a table you never sized, turns a bucket into a walk — that bill is Hash Tables, not a faster contains.
One null, load factor 0.75, fail-fast, then stop mutating
HashSet allows at most one null. add(null) once succeeds; the second call returns false. Many other sets do not allow that — do not take “sets accept null” as a Set rule.
Set<String> skus = new HashSet<>();
skus.add(null); // true
skus.add(null); // false — still one null
skus.contains(null); // trueThe default load factor is 0.75. The backing HashMap resizes when size > capacity × loadFactor. You almost never change 0.75. You do pass an expected size so the table does not double on the way in. new HashSet<>(16) is bucket count, not “I will add 16 SKUs and never resize” — threshold is 12, so the 13th add already grows the table. On Java 19+, HashSet.newHashSet(1_000) is the honest “I am about to add a thousand SKUs” constructor.
Iterators are fail-fast: a structural add / remove during a for-each throws ConcurrentModificationException, except Iterator.remove. That contract, and how it is not a memory barrier, is on the hub. HashSet is not thread-safe. Concurrent writers want ConcurrentHashMap.newKeySet(), not a hope.
Do not mutate a member after insert. The hub already said keys must honor equals / hashCode and stay stable. The equals and hashCode lecture is that contract. A record does. A mutable stand-in does not:
class CartSku {
String sku;
CartSku(String sku) { this.sku = sku; }
@Override public boolean equals(Object o) {
return o instanceof CartSku other && sku.equals(other.sku);
}
@Override public int hashCode() { return sku.hashCode(); }
}
Set<CartSku> seen = new HashSet<>();
CartSku item = new CartSku("WB-40");
seen.add(item);
item.sku = "NUT-M8";
seen.contains(item); // false — different bucket
seen.contains(new CartSku("WB-40")); // false — the table still has the old hashThe member is still in the table and contains will not find it. Prefer strings, enums, and records as HashSet elements.
HashSet is not sequenced. instanceof SequencedSet is false. Iteration order on Java 8+ is repeatable for a given table and a given JDK, and still not insertion order. A test that asserts HashSet iteration order is wrong even if it is green on your laptop.
LinkedHashSet: uniqueness that still iterates in insert order
Same SKUs, different question: uniqueness and first-seen order, because the packing slip prints SKUs in the order they appeared on the orders, not alphabetically and not in hash-bucket order.
Set<String> uniqueSkus = new LinkedHashSet<>();
for (Order order : orders) {
for (LineItem item : order.items()) {
uniqueSkus.add(item.sku());
}
}
System.out.println(uniqueSkus);[WB-40, NUT-M8]WB-40 arrived first on o-1. The second WB-40 on o-2 is a no-op — the member stays where it was. That is insertion order, not access order. (LinkedHashMap can be access-order; LinkedHashSet is not.)
LinkedHashSet extends HashSet. The package-private HashSet constructor the subclass uses installs a LinkedHashMap as the backing map instead of a HashMap. Membership is still expected O(1). Iteration walks a doubly linked list through the entries, so you get encounter order. The extra pointers are the memory you pay: two more references per member than a plain HashSet.
Use LinkedHashSet when uniqueness still has to be a sequence — first-seen SKUs, stable de-duplication of a log, “unique and still printable in the order we met them.” If you never iterate in that order, the linked list is waste. Stay on HashSet.
SequencedSet on Java 21
On Java 21, LinkedHashSet implements SequencedSet. HashSet does not. Ends and a reversed view are real methods on the type you already constructed:
LinkedHashSet<String> uniqueSkus = new LinkedHashSet<>();
uniqueSkus.add("WB-40");
uniqueSkus.add("NUT-M8");
uniqueSkus.add("BOLT-M6");
uniqueSkus.getFirst(); // WB-40
uniqueSkus.getLast(); // BOLT-M6getFirst, getLast, and reversed are the Sequenced Collections contract (JEP 431). This post does not re-teach that interface: reversed() is a live view, empty ends throw NoSuchElementException, and addFirst / addLast on a LinkedHashSet relocate an existing member to that end rather than ignoring it the way add does. Read that post when the ends are the API you are designing. Here the only decision is: uniqueness with encounter order → LinkedHashSet; uniqueness without a sequence → HashSet.
A LinkedHashSet still allows one null, is fail-fast, and is not thread-safe. Same load-factor story as HashSet (LinkedHashSet.newLinkedHashSet(n) exists on Java 19+). Same rule about mutating a member after insert.
Delta vs HashSet | LinkedHashSet |
|---|---|
| Backing map | LinkedHashMap (insertion-order list through entries) |
| Iteration | Insertion order |
| Java 21 | SequencedSet — getFirst / getLast / reversed |
| Memory | Slightly more (before/after pointers per member) |
add of an existing member | No-op; position unchanged |
| Hot operations | Still expected O(1) add / contains / remove |
When not: TreeSet, EnumSet, Set.of
HashSet and LinkedHashSet are the hash-table deliveries of Set. They are the wrong delivery when the job is a different contract.
You need sorted uniqueness. Packing slip in SKU order, a range of timestamps, ceiling/floor. That is TreeSet: O(log n), iteration in comparator order, no null with natural ordering. It is not a HashSet you sorted later. Details stay in Navigable Collections.
Set<String> sorted = new TreeSet<>(uniqueSkus);
System.out.println(sorted);[NUT-M8, WB-40]The universe is one enum. Status flags, days of week, a closed set of warehouse bins. EnumSet is a bit vector, not a hash table — denser, faster, iteration in declaration order. That type is EnumSet and EnumMap. Do not put OrderStatus in a HashSet because “set of enums” sounded like HashSet.
The set is frozen and known at the call site. Set.of("WB-40", "NUT-M8") is unmodifiable, rejects null, and rejects duplicate arguments. It is not a HashSet. Set.copyOf(skus) copies. Factories, copyOf, and why they are not a wrapper on a live set live in Collection Factories.
You need index i, or duplicates. That is a List. Copying a HashSet into an ArrayList so you can get(0) is a signal the set was the wrong first type — or that you needed both.
Another thread mutates while you iterate. Fail-fast will throw. A synchronized wrapper still needs the iterator locked by you. The concurrent set is ConcurrentHashMap.newKeySet(), not HashSet.
Do not use HashSet iteration as a sequence. If callers will ask for first, last, or “in the order we inserted,” the type is LinkedHashSet (or a sorted set). If they will ask for sort order, the type is TreeSet.
Interview lens
Interviewers want the backing map, why order is not insertion order, and which sibling to name. They do not want you to invent a second hash table.
Complexity they expect without a lookup: HashSet.add / contains / remove expected O(1); iteration O(n) with no sequence; LinkedHashSet the same times plus extra memory per member; TreeSet O(log n) and sorted; EnumSet O(1) bit ops on a closed universe.
What to draw. An array of buckets. Each occupied slot holds a key and the dummy PRESENT. add("WB-40") hashes, lands in a bucket. Iteration walks bucket 0..length-1, not an insert list. Then draw LinkedHashSet as the same table plus before / after arrows: WB-40 → NUT-M8 → BOLT-M6. Label HashSet: not a SequencedSet. Label LinkedHashSet: insertion-order SequencedSet on Java 21.
Typical questions:
| Question | Honest answer |
|---|---|
What is HashSet internally? | A HashMap of members → dummy PRESENT. add is put returning whether the key was new. |
| Why isn’t iteration order insertion order? | The iterator walks hash buckets. Buckets are not a sequence. Java 8+ order is repeatable and still unspecified. |
LinkedHashSet vs HashSet? | Same expected O(1) membership. LinkedHashSet keeps a linked list through entries so iteration is insertion order. Slightly more memory. SequencedSet on Java 21. |
| What is the load factor? | Default 0.75. Resize when size > capacity × loadFactor. Rarely change it; size the table (newHashSet(n)) instead. |
Does HashSet allow null? | One null. TreeSet with natural order does not. EnumSet does not. Set.of does not. |
HashSet vs TreeSet? | Hash: expected O(1), no order. Tree: O(log n), sorted, comparator / Comparable, no null with natural order. |
| What if you mutate an element after insert? | The bucket it hashed into does not move. contains misses. Use an immutable member. |
Set.of vs HashSet? | Factory set is unmodifiable and rejects nulls and duplicate arguments. Not a HashSet, not a wrapper on a live set. |
Wrong answer: “HashSet preserves insertion order.” It does not. If a screenshot looks sorted or insertion-ordered, that is a coincidence of buckets. Name LinkedHashSet for insertion order and TreeSet for sorted order.
Cheat sheet
HashSet HashMap keys + dummy PRESENT; expected O(1)
one null; fail-fast; NOT sequenced
LinkedHashSet HashSet + LinkedHashMap; insertion-order iteration
SequencedSet on Java 21; slightly more memory
Load factor 0.75 default; size with newHashSet(n) (Java 19+)
Mutate after add lost member — records / strings / enums
vs TreeSet sorted, O(log n), no null (natural order)
vs EnumSet closed enum universe — bit vector, not a hash
vs Set.of unmodifiable factory; no null; not a HashSet
Do Set<String> skus from LineItem.sku()
Don't HashSet order as a sequence
List.contains as uniqueness that growsDo:
- Program to
Set.new HashSet<>()for uniqueness;new LinkedHashSet<>()when first-seen order is part of the contract. - Unique the identifier (
sku), not a larger record, unless equality of the whole line is really the member. - Size the table when you know
n. Leave the load factor at0.75.
Don’t:
- Treat
HashSetiteration as insertion order. - Put
OrderStatusin aHashSetwhen EnumSet exists. - Mutate a field that feeds
equals/hashCodeafter the object is in the set.
Wrap-up
HashSet is uniqueness with expected O(1) membership because it is a HashMap that only stores keys. You get one null, fail-fast iterators, a 0.75 load factor, and no encounter order — it is not a sequenced type. LinkedHashSet is the same uniqueness with a linked list through the entries so iteration is insertion order, at a small memory cost, and on Java 21 it is a SequencedSet. Sorted uniqueness is TreeSet. A closed enum universe is EnumSet. A frozen set of known SKUs is Set.of.
The type that compiles as Set is not always the type whose iteration you can publish. Pick HashSet until order, sort, or a tiny enum universe says otherwise.