You need to know whether this request ID has already been processed. The method is alreadySeen.contains(id). The name is honest. If alreadySeen is an ArrayList of a hundred thousand IDs, every check walks the list. The hot path is a scan.

A set hashes once and looks in a bucket. Same verb. Different layout. Different bill.

From the series hub: a set is an ADT — unique membership — and a hash table is one layout that delivers it. This post is that contract, why List.contains is the expensive stand-in, HashSet as a HashMap that only cares about keys, and when a tree (or a list) is the honest choice. Glossary terms live on the hub; they are not re-taught here.

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

The set ADT

Three verbs. One invariant: each value is in the set at most once.

OperationMeaning
add(x)Insert x if it is absent. If it is already a member, the set does not grow.
contains(x)True if and only if x is a member.
remove(x)Drop x if it is present. If it was absent, the set does not change.

There is no index i. There is no second copy of x. There is no promised encounter order unless a particular implementation adds one.

That last sentence is the ADT vs implementation split the hub named. “Set” is the contract. HashSet is a hash table that implements it. TreeSet is a tree that implements it. An ArrayList you call contains on is still a list.

Membership uses equality, not identity. Two strings that print the same are one member. Two distinct objects that compare equal under equals are one member. If equals and hashCode disagree, the set cannot keep that promise — more on that below.

A tiny session of the contract:

Set<String> seen = new HashSet<>();

seen.add("req-17");           // true  — inserted
seen.add("req-17");           // false — already a member
seen.contains("req-17");      // true
seen.remove("req-17");        // true  — was present
seen.contains("req-17");      // false

add and remove returning boolean is the ADT talking: did the membership change?

List.contains is the expensive layout

List.contains has the same method name. It does not have the same job. It walks from index 0 until it finds an equal element or runs out of the list.

boolean alreadyProcessed(List<String> seen, String id) {
    return seen.contains(id); // scan
}

boolean alreadyProcessed(Set<String> seen, String id) {
    return seen.contains(id); // hash, then a bucket
}

Both compile. Both pass a unit test with five IDs. Only the second stays cheap when seen grows.

The bill is worse if you also try to keep the list unique:

void markProcessed(List<String> seen, String id) {
    if (!seen.contains(id)) { // walk n
        seen.add(id);         // append is cheap; the check was not
    }
}

Every insert that might be a duplicate pays a scan. At a hundred thousand members, you are doing uniqueness the hard way: List.contains as a set. The hub’s JDK map already flags this. The fix is not a faster loop. The fix is a layout whose hot operation is membership.

Note: ArrayList.get(i) is cheap. That is a different job. If the hot path is “the element at index i,” you wanted a list. If the hot path is “have I seen this value,” you wanted a set.

HashSet is a HashMap with dummy values

A map’s keys are already unique. A set is that idea with the values thrown away.

Java’s HashSet is literally a HashMap. Each member is a key. The value is a shared dummy object the set never lets you see. add, contains, and remove are put, containsKey, and remove on that map.

A sketch of the idea (not a class you should copy into production):

final class TinyHashSet<E> {
    private static final Object PRESENT = new Object();
    private final HashMap<E, Object> map = new HashMap<>();

    boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

    boolean contains(Object e) {
        return map.containsKey(e);
    }

    boolean remove(Object e) {
        return map.remove(e) == PRESENT;
    }
}

add returns true when put had no previous mapping — the set grew. remove returns true when the dummy was there to take out.

That is why a HashSet has no order you can depend on. Hash buckets are not a sequence. Iteration walks the table, not “the order you inserted.” You also cannot ask for index i. Those are not missing methods. They are the cost of making membership the cheap operation.

Expected cost, with a decent hashCode and a load factor you respect:

HashSet
add          expected O(1)
contains     expected O(1)
remove       expected O(1)
iterate      O(n) — no promised order

Expected is not a guarantee on the next call. A bad hash, or a load factor you ignored, turns a bucket into a walk. The hub already defined amortized vs worst-case; treat Javadoc “constant time” the same way it told you to treat HashMap.

Java HashSet

Program to Set. Construct a HashSet when you want the hash-table layout:

Set<String> active = new HashSet<>();
active.add("token-a");
active.add("token-b");

if (active.contains(incoming)) {
    return; // already in
}
active.add(incoming);

Or build from a collection. Duplicate members collapse to one:

Set<String> tags = new HashSet<>(List.of("java", "java", "hashing"));
System.out.println(tags.size()); // 2

A few JDK facts that bite if you skip them:

  • HashSet is the default unique-membership type in Java. Reach for it unless you have a reason the next sections name.
  • At most one null. HashSet allows it; many other set types do not.
  • Not thread-safe. Concurrent writers need a concurrent set (ConcurrentHashMap.newKeySet(), or a lock you already own).
  • Set.of(...) and Set.copyOf(...) are unmodifiable and reject duplicates and null. They are not a HashSet.
  • Iteration order is an implementation detail. Do not sort in your head from a debugger screenshot.

Equality is the membership test. If you put your own type in a HashSet, equals and hashCode must agree: equal objects, same hash. Records get that for free; a hand-written class that overrides only equals will look unique under contains and vanish into the wrong bucket. The language contract is equals and hashCode.

record UserId(String value) {}

Set<UserId> ids = new HashSet<>();
ids.add(new UserId("u-1"));
ids.contains(new UserId("u-1")); // true — same components, same hash

Note: Do not mutate a field that participates in equals / hashCode after the object is in the set. The bucket it landed in will not move. The member is still in the table and contains will not find it. Prefer immutable members — records, strings, enums.

If you need uniqueness and insertion order, that is LinkedHashSet, not a promise you invent on HashSet. On Java 21, LinkedHashSet is a sequenced set; HashSet is not. That API is Sequenced Collections: First, Last, and Reversed Without the Ceremony. If every member is an enum, EnumSet is the specialized layout — still a set ADT, packed as bits.

TreeSet when uniqueness must be sorted

HashSet makes membership cheap and throws order away. Sometimes order is the job: unique timestamps you must walk oldest-first, unique names you must print alphabetically, a range query over members.

That is a different layout. TreeSet is a NavigableSet backed by a tree (TreeMap underneath). add, contains, and remove are O(log n). Iteration is sorted. You need a Comparator, or members that are Comparable. A natural-order TreeSet does not allow null.

Set<String> names = new TreeSet<>();
names.add("zeta");
names.add("alpha");
names.add("alpha"); // no-op — still unique
System.out.println(names); // [alpha, zeta]

Use TreeSet when sorted uniqueness is the hot path. Do not sort a HashSet on every read and call it ordered. Do not pick TreeSet “to be safe” when you never iterate in order — you are paying O(log n) for a guarantee you do not use.

This is a pointer, not a tree tutorial. Rotations, TreeMap internals, and why sorted input can unbalance a naive BST live in later posts in this series. Here the only decision is: unique, unordered, expected O(1) → HashSet. Unique and sorted → TreeSet.

When not to use a set

A set is the wrong layout when uniqueness is not the job.

You need duplicates. Scores, log lines, timestamps, the items in a cart — multiplicity is data. A set will silently drop the second 3. Use a List (or a bag / multiset if you have one).

You need index i. set.get(i) is not a set operation. If the hot path is “the third row,” you wanted an array or ArrayList. Copying a set into a list so you can index it is a signal the set was the wrong first choice — or that you needed both a list and a set, not a set pretending to be a list.

You need a stable sequence as API. HashSet iteration is not first-to-last. If callers will ask for first, last, or reversed, pick LinkedHashSet or a sorted set and say so in the type. Do not document “order doesn’t matter” and then depend on it in a test.

The “set” is tiny and the scan is not the hot path. Five elements in a local method is not a reason to debate layouts. The expensive picture is a collection that grows while contains stays on the request path.

// Honest list: duplicates and index both matter
List<Integer> rolls = new ArrayList<>();
rolls.add(4);
rolls.add(4);
int second = rolls.get(1); // 4

// Honest set: membership is the only question
Set<Integer> uniqueFaces = new HashSet<>(rolls);
uniqueFaces.contains(4); // true

Cheat sheet

ADT:          unique membership — add / contains / remove
HashSet:      HashMap keys + dummy value; expected O(1)
You lose:     order, index, duplicates
List.contains: O(n) scan — not a set
TreeSet:      sorted uniqueness, O(log n); needs ordering
LinkedHashSet: uniqueness + insertion order
EnumSet:      set of one enum type
equals/hashCode must agree; do not mutate keys

Do:

  • Name membership as the hot operation, then reach for HashSet.
  • Program to Set; construct the layout you mean.
  • Use a record (or other immutable type) as the member when you own the class.
  • Pick TreeSet only when sorted iteration or range queries are real work.

Don’t:

  • Use List.contains as uniqueness on a collection that grows.
  • Treat HashSet iteration as a sequence.
  • Put a mutable object in a hash set and then change a field that feeds hashCode.
  • Choose TreeSet by default “because ordered is safer.”

Wrap-up

The set ADT is unique membership. HashSet delivers it by being a HashMap that only stores keys: add, contains, and remove are expected O(1), and you give up order, index, and duplicates to get that. List.contains is a scan with the same method name. TreeSet is the other common layout — sorted uniqueness at O(log n) — not a faster HashSet.

If the question is “have I seen this?”, the cheap layout is a set. If the question is “what is at index i?” or “how many times did this happen?”, it is not.

The glossary, JDK map, and living index for this series sit on the Data Structures Roadmap.

Next optional step in the series Hierarchy before search: left, right, and what balanced means. Binary Trees: Shape and Traversals