You need the distinct SKUs in a basket, or the emails that already placed an order. open.contains(order) on an ArrayList of thousands of orders is a scan every time. It compiles. It is still a list.

Set is the uniqueness contract: at most one member that equals another, no index, add returns false when the element was already there. The class you new is how membership is found — hash, linked hash, or tree.

The Collections Roadmap owns Collection vs Map, optional operations, sequenced as a name, and “keys must honor equals / hashCode.” The full contract is equals and hashCode. This post is the Set API, why two sets compare by membership, and which JDK set to name until an implementation post owns the internals. Hash table layout lives in Sets (data structures); this series does not re-teach it.

A Set answers “is this already a member?” without walking every member.

The contract: membership, not position

Set extends Collection. It does not add get(i). There is no subList. Duplicates are not a second insert; they are a no-op that returns false.

Set<String> skus = new HashSet<>();
boolean inserted = skus.add("SKU-A"); // true
boolean again = skus.add("SKU-A");    // false — already a member
skus.contains("SKU-A");               // true
skus.remove("SKU-A");                 // true

That boolean is the whole point. List.add almost always returns true because a list is allowed a second copy. A set is not.

MethodJob on a Set
add(e)Insert if absent; false if equals an existing member
contains(o)Membership by equals (and hashCode on hash sets)
remove(o)Drop the member if present
addAll / removeAll / retainAllUnion, difference, intersection in place
iterator()Walk members — order depends on the implementation
equals / hashCodeSame members, any order

At most one null is allowed where the implementation allows null. HashSet and LinkedHashSet allow one. TreeSet with natural order does not. Set.of does not.

Set<String> emails = new HashSet<>();
for (Order order : orders) {
    emails.add(order.customerEmail());
}

After that loop, emails.size() is the number of distinct addresses. The same loop into an ArrayList keeps every duplicate and makes every later contains a scan.

List.contains is the wrong uniqueness type

The pain this post exists to name: a list that you probe with contains before add. It is a set you implemented with a scan.

List<String> seen = new ArrayList<>();
for (Order order : orders) {
    String email = order.customerEmail();
    if (!seen.contains(email)) {   // O(n) per order
        seen.add(email);
    }
}

The honest type is Set. add already answers “was it new?”

Set<String> seen = new HashSet<>();
for (Order order : orders) {
    seen.add(order.customerEmail()); // expected O(1); false if duplicate
}

List.contains is a scan. On a few line items it does not matter. On a day’s worth of order ids it is the hot path. If you later need both uniqueness and insertion order, that is LinkedHashSet, not “an ArrayList we de-dupe by hand.”

Bulk methods inherit the same decision. retainAll against a HashSet of in-stock SKUs is a hash lookup per basket line. Against another ArrayList, each lookup is a scan.

Set<String> inStock = Set.of("SKU-A", "SKU-C", "SKU-D");
List<String> basket = new ArrayList<>();
for (LineItem item : order.items()) {
    basket.add(item.sku());
}
basket.retainAll(inStock); // each contains is O(1) because inStock is a Set

Equals of two sets is membership

Set.equals is “same members,” not “same encounter order” and not “same class.”

Set<String> hashed = new HashSet<>(List.of("SKU-A", "SKU-B"));
Set<String> linked = new LinkedHashSet<>(List.of("SKU-B", "SKU-A"));
hashed.equals(linked); // true

Set.of("SKU-A", "SKU-B").equals(Set.of("SKU-B", "SKU-A")); // true
List.of("SKU-A", "SKU-B").equals(List.of("SKU-B", "SKU-A")); // false
hashed.equals(List.of("SKU-A", "SKU-B")); // false — Set vs List

Two sets with the same elements are equal even if they iterate differently. A set never equals a list with the same elements. Collection and Iterator showed that split; here it is the Set side of the contract.

There is still no get(i). If you wrote skus.get(0), you wanted a List — or you wanted iterator().next() for “any one member,” which is not an index.

How duplicates are detected

A hash set finds a member with hashCode then equals. A tree set finds a member with compareTo / Comparator. The roadmap already said keys must honor equals and hashCode; set elements are that same rule. Implement the pair in equals and hashCode.

Set<LineItem> uniqueItems = new HashSet<>();
uniqueItems.add(new LineItem("SKU-A", 1, new BigDecimal("10.00")));
uniqueItems.add(new LineItem("SKU-A", 1, new BigDecimal("10.00")));
// size == 1 — record equality

Two LineItem records with the same components are one member. Two records that differ in quantity are two members — uniqueness is the whole value, not “the SKU field” unless you put SKUs in the set.

Note: If you need unique SKUs, store String sku, not the whole LineItem. A set of line items treats (SKU-A, 1) and (SKU-A, 2) as different members.

Mutating an object after it is in a HashSet breaks lookup. The element sits in the bucket of its old hash. contains uses the new hash and misses.

Set<StringBuilder> broken = new HashSet<>();
StringBuilder sku = new StringBuilder("SKU-A");
broken.add(sku);
sku.append("-X");
broken.contains(sku);     // false — hash changed
broken.contains(new StringBuilder("SKU-A")); // also false

Use immutable members. record, String, and enum are the usual honest elements. The HashSet post owns the table; do not mutate what you already inserted.

HashSet vs LinkedHashSet vs TreeSet

Three deliveries of the same contract. Implementation posts own the internals — HashSet, Navigable collections, Enum collections. This table is enough to pick a name today.

TypeNullsEncounter orderadd / containsWhen
HashSetone nullnoneexpected O(1)Default uniqueness
LinkedHashSetone nullinsertionexpected O(1)Uniqueness and stable encounter order
TreeSetno (natural order)sortedO(log n)Uniqueness and sorted / ceiling / floor
EnumSetnoenum declarationtiny universeClosed enum of flags

Default in application code: HashSet. Reach for LinkedHashSet when a later loop must see first-inserted first, TreeSet when you need sorted or navigable methods, EnumSet when the members are a small enum.

Set<String> distinct = new HashSet<>();
Set<String> inArrivalOrder = new LinkedHashSet<>();
Set<String> alphabetical = new TreeSet<>();

for (LineItem item : order.items()) {
    distinct.add(item.sku());
    inArrivalOrder.add(item.sku());
    alphabetical.add(item.sku());
}

HashSet iteration order is unspecified and must not be a feature. HashSet is not a SequencedCollection.

SequencedSet<String> arrival = new LinkedHashSet<>();
arrival.add("SKU-A");
arrival.add("SKU-B");
arrival.getFirst(); // SKU-A — legal; LinkedHashSet is sequenced

Set<String> hashed = new HashSet<>(arrival);
// hashed.getFirst(); // does not compile — HashSet is not sequenced

Sequenced Collections is the name for types that have a first and a last. LinkedHashSet and TreeSet are sequenced; HashSet is not. Iteration that looks stable on one JVM can shuffle after a resize.

Re-adding a member does not move it in a LinkedHashSet. Insertion order is the first insert. That is different from access-order LinkedHashMap.

LinkedHashSet<String> skus = new LinkedHashSet<>();
skus.add("SKU-A");
skus.add("SKU-B");
skus.add("SKU-A"); // false — still [SKU-A, SKU-B], A does not jump to last

Set.of, only as far as Set needs

Set.of and Set.copyOf are unmodifiable. They reject null. They reject duplicate arguments at construction with IllegalArgumentException — they do not return false. The factories post owns the catalog.

Set<String> frozen = Set.of("SKU-A", "SKU-B");
frozen.add("SKU-C");                 // UnsupportedOperationException
Set.of("SKU-A", "SKU-A");            // IllegalArgumentException
Set.of("SKU-A", null);               // NullPointerException
Set.copyOf(skus);                    // unmodifiable copy, still no nulls

Set.of iteration order is unspecified. It is not LinkedHashSet. If the factory set must be a sequence, you wanted new LinkedHashSet<>(Set.of(...)) or a sequenced type the factories post will name.

Internals that change a decision

HashSet is a HashMap that only cares about keys (a dummy value per member). Expected O(1) contains is why you stop scanning a list. The layout — buckets, tree bins — is the hash-set ADT post, not this one. What you need here: if equals and hashCode disagree, membership is wrong; if you mutate a member, the bucket is wrong.

LinkedHashSet is that hash table plus a linked list of insertion order. You pay a little extra per element to iterate in a defined sequence. If you never iterate in that order, HashSet is enough.

retainAll / removeAll against a HashSet of in-stock ids is a hash lookup per element. Against another list, it is a scan per element.

TreeSet is a TreeMap of keys. Comparison, not hashing. Inconsistent compareTo vs equals means you can fail to find what you put.

Nulls are not allowed with natural order because compareTo cannot accept them. Sorted uniqueness is O(log n) — cheaper than sorting a list on every insert only if you actually need the order as you go.

The navigable post owns Comparator contracts. Do not use a TreeSet as a “smarter HashSet”; use it when sorted order or ceiling/floor is the job.

Set<String> domains = new TreeSet<>();
for (Order order : orders) {
    String email = order.customerEmail();
    domains.add(email.substring(email.indexOf('@') + 1));
}
// iterates alphabetically — that is the reason to pick TreeSet

When Set is the wrong type

  • You need get(i), a page, or “the third item” → List.
  • You need first / last on a hash set → that set is not sequenced. Use LinkedHashSet or a list.
  • You need a count of how many times a SKU appeared → Map<String, Long>, not a Set.
  • You need lookup by order id → Map<String, Order>. A Set<Order> still requires you to hold the whole Order to find it.
  • You need a queue of work → Queue / Deque. Membership is not a hand-off.
  • TreeSet because “sets should be sorted” → they should not, unless sorting is the job. HashSet is the default.

Do not keep an ArrayList “and we call contains before add.” That is a hand-rolled set with O(n) inserts. Do not rely on HashSet iteration as a sequence.

Interview lens

Interviewers want why List.contains is the wrong uniqueness type, how duplicates are detected, and that HashSet is not insertion-ordered. Draw Collection → Set, three boxes: HashSet / LinkedHashSet / TreeSet. No index on the interface.

Whiteboard one-liner. A Set is unique membership via equals (hash or compare). add returns false on a duplicate. HashSet has no iteration order; Set.of rejects null.

OperationHashSetLinkedHashSetTreeSet
add / contains / removeexpected O(1)expected O(1)O(log n)
iteration orderunspecifiedinsertionsorted
null elementoneoneno (natural order)
sequenced (Java 21)noyesyes
QuestionHonest answer
How does a Set detect duplicates?HashSet: hashCode then equals. TreeSet: compareTo / Comparator. Same member → add returns false.
HashSet vs TreeSet order?HashSet: none you may rely on. TreeSet: sorted. Insertion order is LinkedHashSet.
Can Set.of contain null?No. NullPointerException. Duplicates in the argument list throw IllegalArgumentException.
List vs Set for uniqueness?List.contains is a scan. Set is the uniqueness type. Use a list when position or duplicates are the job.
What if you mutate an element already in a HashSet?Lookup uses the new hashCode and misses the old bucket. The member is lost until you rebuild. Use immutable elements.
Why is there no get(i)?A set has members, not positions. HashSet would have to pick an arbitrary member and pretend it was an index.
Does re-adding move a LinkedHashSet member?No. Insertion order is the first successful add. add of a duplicate returns false and leaves position alone.

Wrong answer: “HashSet iterates in insertion order.” That is LinkedHashSet. HashSet iteration is unspecified and may change when the table resizes.

Cheat sheet

Set            unique members; no get(i); add → false on duplicate
equals         same members, any order; never equals a List
null           HashSet/LinkedHashSet: one; TreeSet natural: none; Set.of: none
HashSet        default; expected O(1); not sequenced
LinkedHashSet  uniqueness + insertion order
TreeSet        uniqueness + sorted / navigable
EnumSet        closed enum universe — enum-collections post
Set.of         unmodifiable; NPE on null; IAE on duplicate args
elements       immutable; honor equals/hashCode (or compareTo)

Do             HashSet for distinct SKUs / emails
               LinkedHashSet when encounter order is part of the job
Don't          ArrayList.contains as uniqueness
               HashSet order as a sequence
               mutate a member already in a HashSet

Do:

  • Put uniqueness in a Set. Put SKUs and emails in it, not “the whole order, and we scan.”
  • Pick HashSet until insertion order or sorting is a real requirement.
  • Keep set elements immutable.

Don’t:

  • Treat HashSet iteration as insertion order.
  • Call Set.of(a, a) or Set.of(..., null) and expect add-style false.
  • Use a Set<Order> when the lookup key is Order.id — that is a Map.

Wrap-up

Set is uniqueness: no duplicates, no indexes, add returns false when the member is already there, and two sets are equal when they contain the same members. HashSet is the default. LinkedHashSet adds encounter order. TreeSet adds sorted order. Set.of is unmodifiable and rejects null. List.contains is not a set.

When the job is “take from this end, insert at that end,” you are no longer asking about membership. That job is Queue and Deque.

Next optional step in the series Insert and take from the ends — offer versus add, and why ArrayDeque beats LinkedList. Queue and Deque: Ends, Not Indexes