A Set<E> is a Collection with one extra rule: no duplicates. If you try to add a value that's already in there, the set refuses without raising an error. This lesson covers the Set contract, how equals and hashCode decide what counts as a duplicate, the API differences from List, the set algebra operations (union, intersection, difference), and a quick tour of the three main implementations.

java.util.Set<E> extends java.util.Collection<E>. It inherits the usual add, remove, contains, size, iterator, and friends, but it tightens the meaning of one operation: add is not allowed to insert a duplicate. If a set already contains an element equal to e, calling set.add(e) does nothing and returns false. On a list, add always succeeds and always returns true. That single difference reshapes how the whole interface behaves.

The contract in action. An online store wants to track the IDs of customers who placed at least one order today. The same customer can order twice, three times, ten times. Only the fact that they ordered at all matters.

Five add calls, but size() reports 3. The duplicate 101 and 204 were dropped. The set never grows beyond the count of distinct values, no matter how many times you push the same value in.

The API is also missing certain operations. There's no set.get(0), no set.indexOf(...), no positional insert. A set has no notion of "position", so the methods that depend on position aren't there. The only way to read elements is to iterate with a for-each loop, an iterator, or a stream.

The order looks arbitrary, and it is. HashSet makes no promise about iteration order. If you need insertion order or sorted order, use a different implementation.

A set doesn't compare elements with ==. It compares them by calling equals. For two elements to count as the same element, a.equals(b) must return true. For primitives wrapped in their boxed types (Integer, Long, etc.) and for String, this works because those classes have well-defined equals methods that compare values.

The story changes the moment you put your own class into a set. By default, a class inherits Object.equals, which only returns true when two references point to the exact same object in memory. Two Customer objects with the same ID but different references are not equal under the default equals, which means the set will store both of them as if they were separate customers.

Two customers with the exact same ID and name, yet the set holds both. The default equals says "different objects, different elements", and the set obediently stores both.

To fix it, the class needs to override both equals and hashCode. The two methods come as a pair: equals defines what "the same element" means, and hashCode lets hash-based sets find that element quickly. If two objects are equal, their hashCode values must be equal too. Override one without the other and hash-based collections start behaving in confusing ways.

Now the set treats two customers with the same id as the same element, regardless of the reference. The first two add calls produce one entry, the third adds a second. The equals/hashCode pair is the contract that makes a set behave correctly for your own types.

Forgetting to override hashCode while overriding equals is one of the classic Java bugs. Hash-based sets bucket elements by hashCode, so two "equal" objects with different hash codes land in different buckets and the set never notices the duplicate. Override them together.

The takeaway for sets: if the element type is a class you wrote, override both equals and hashCode, or accept that the set will be useless for deduplication.

One of the reasons to use a Set is that the API gives you the three standard set-algebra operations through methods inherited from Collection. They mutate the set in place rather than returning a new one.

Consider two sets of customer IDs: those who bought product A and those who bought product B.

The union is every customer who bought either A or B. The intersection is the customers who bought both. The difference A \ B is the customers who bought A but not B, which is the answer to a question like "who should we send a B promo to?".

The same idea in code. The store wants to find customers who bought both a wireless mouse and a wireless keyboard.

Two things matter in that snippet. First, boughtMouse is copied into boughtBoth before calling retainAll, because retainAll mutates the receiver. Calling boughtMouse.retainAll(boughtKeyboard) directly would have overwritten the original mouse set with the intersection. Second, the result is the customers present in both input sets, which is what cross-sell analysis wants.

The other two operations follow the same shape. Union with addAll:

204 appears in both input sets, but the union contains it once. That's the set contract again: addAll calls add internally, and add refuses duplicates.

Difference with removeAll:

The result is the customers in boughtMouse but not in boughtKeyboard. That's the list to target with a keyboard promo.

retainAll and removeAll look at every element in the receiver and ask the other collection whether it contains that element. If the "other" collection is a List, each contains check walks the list, making the whole operation O(n × m). When doing set algebra, pass a Set (or other O(1) contains collection) as the argument too.

A Set and a List look similar from the outside (both are collections, both have add, remove, contains, size) but the contracts are different. The decision is almost always about whether duplicates and order matter.

A few concrete examples from an e-commerce setting:

List for everything feels more general, but the price is slow contains lookups and unannounced acceptance of duplicates that bugs feed on. When the use case is "membership, not sequence", use Set.

Set is just an interface. To use one, you pick an implementation. The standard library gives you three, each with its own trade-off between speed and ordering.

A one-line summary of each, since each has its own chapter coming up:

The choice changes iteration order. Same three values, three different sets:

The HashSet order is whatever the hash buckets happen to produce. The LinkedHashSet shows the order the values were inserted. The TreeSet shows them sorted ascending. Which one to pick depends on what the code does with the iteration order.

One detail to learn now: Set<E> is the type to declare variables as. The implementation goes on the right side of =. Writing HashSet<Integer> ids = new HashSet<>() ties the variable to one implementation; writing Set<Integer> ids = new HashSet<>() lets you swap implementations later without changing the variable type. This is the same "program to the interface" guideline that applies to List.

A small program that uses every idea from the lesson. The store has two lists of customer IDs: those who bought a notebook today, and those who used a discount code today. The questions:

Walk through what happened. The raw notebookOrders list had six entries but only four distinct customer IDs. Passing the list into the HashSet constructor deduplicated it in one step, because the set's add rejects repeats. The intersection found the two customers present in both input collections. The difference found the two customers in the notebook-buyer set but not in the discount-user collection. Each operation mutated a copy of the buyer set, leaving the original untouched for the next question.

That pattern, deduplicate then do set algebra on copies, is common for customer-segmentation queries in any system that hasn't reached for a real database yet, and it scales to thousands of IDs in memory without trouble.