Set, and removing duplicates properly

A Set holds each element once and answers one question fast: have I seen this before? That is a narrower job than List or Map, and it is the reason Set is the collection most often not used when it should be.

The commonest symptom is a List with contains called on it inside a loop. This lesson shows what that costs.

Uniqueness

List<String> areas = List.of("Wagholi", "Kharadi", "Wagholi", "Bavdhan", "Kharadi");
Set<String> unique = new HashSet<>(areas);

System.out.println(unique + " size " + unique.size());
System.out.println("add returns: " + unique.add("Wagholi"));

[Wagholi, Bavdhan, Kharadi] size 3
add returns: false

Deduplicating a collection is one constructor call. And add returns a boolean: false means it was already there. That return value is genuinely useful:

if (!seen.add(pincode)) {
    System.out.println("duplicate row for pincode " + pincode);
}

One call that both records and tests. Writing if (seen.contains(x)) ... else seen.add(x) does the same work twice.

The three implementations

Set<String> hash = new HashSet<>(areas);
Set<String> linked = new LinkedHashSet<>(areas);
Set<String> tree = new TreeSet<>(areas);

HashSet       : [Wagholi, Bavdhan, Kharadi]
LinkedHashSet : [Wagholi, Kharadi, Bavdhan]
TreeSet       : [Bavdhan, Kharadi, Wagholi]

HashSet is a HashMap with a constant as every value — that is literally how it is implemented, which is why it has exactly the same requirements and the same key-mutation trap.

Use LinkedHashSet whenever the output is shown to a person. HashSet's order is arbitrary, and a report whose rows shuffle between runs looks broken even when it is correct. The cost is a few bytes per element.

TreeSet needs its elements to be orderable:

Set<Object> t = new TreeSet<>();
t.add(new Object());
t.add(new Object());

ClassCastException: class java.lang.Object cannot be cast to class java.lang.Comparable

Note it succeeded on the first add — with one element there is nothing to compare against. The failure arrives on the second, which makes a test with a single element pass.

Set operations

The three you want, done with bulk methods on a copy:

Set<String> monday = new LinkedHashSet<>(List.of("Priya", "Arjun", "Kavita"));
Set<String> tuesday = new LinkedHashSet<>(List.of("Arjun", "Kavita", "Amit"));

Set<String> both = new LinkedHashSet<>(monday);
both.retainAll(tuesday);              // intersection

Set<String> either = new LinkedHashSet<>(monday);
either.addAll(tuesday);               // union

Set<String> mondayOnly = new LinkedHashSet<>(monday);
mondayOnly.removeAll(tuesday);        // difference

both days     : [Arjun, Kavita]
either day    : [Priya, Arjun, Kavita, Amit]
monday only   : [Priya]

Copy first. retainAll and removeAll modify the set they are called on, so monday.retainAll(tuesday) destroys monday. The copy line is not optional ceremony.

These three cover a surprising amount of real work: who ordered on both days, who has lapsed, which pincodes are newly serviceable.

Why this matters: contains

List<Integer> list = new ArrayList<>();
Set<Integer> set = new HashSet<>();
for (int i = 0; i < 200_000; i++) { list.add(i); set.add(i); }

// 2,000 lookups of the last element

List.contains x2000 : 192 ms
Set.contains  x2000 : 0 ms

A list scans, comparing with equals until it finds a match. A hash set computes one hash and looks in one bucket. The gap grows with the size of the collection: double the list and the scan doubles, while the set lookup does not change.

Whenever contains appears inside a loop, you want a Set. This is the single most valuable performance instinct in this module, and it costs one word at the declaration.

A common shape:

Set<String> serviceable = new HashSet<>(loadServiceablePincodes());
for (Order order : orders) {
    if (!serviceable.contains(order.pincode())) {
        reject(order);
    }
}

Building the set costs one pass. Every lookup afterwards is free.

Set.of

Set.of("Wagholi", "Wagholi");

IllegalArgumentException: duplicate element: Wagholi

Unlike new HashSet<>(...), which silently drops duplicates, Set.of rejects them. It is immutable, rejects nulls, and its iteration order is deliberately randomised between JVM runs so that nobody can accidentally depend on it.

That randomisation is a kindness. It turns "works on my machine" into "fails immediately".

What a Set cannot do

• Hold duplicates. Obvious, and still the reason people reach for it wrongly: counting how many times each area appears is a Map, not a Set.
• Keep a position. There is no get(i). If you need "the third one", you want a List.
• Protect you from a broken equals. A HashSet of objects without a correct equals and hashCode will happily hold two identical-looking elements. That is the next lesson, and it is the most important one in this module.

Check your work

What does set.add(x) return? false if the element was already present. One call both tests and records.

Which set implementation should a report use? LinkedHashSet. HashSet's order is arbitrary and makes output look unstable between runs.

What does TreeSet require, and when does it fail? Elements must be Comparable or you must supply a Comparator. It throws ClassCastException on the second add, because the first has nothing to compare against.

How do you compute an intersection? Copy one set, then retainAll the other. Copying matters — the bulk methods modify the receiver.

Why is contains on a HashSet so much faster than on a List? A list scans every element with equals; a hash set computes one hash and checks one bucket. The difference grows with size.

How does Set.of differ from new HashSet<>(List.of(...))? Set.of throws IllegalArgumentException: duplicate element rather than silently deduplicating, is immutable, rejects nulls, and randomises its iteration order between runs.

When is a Set the wrong choice? When you need counts, duplicates or positions.

Practice 3, the set operations. Intersection [Arjun, Kavita], union [Priya, Arjun, Kavita, Amit], difference [Priya]. If your monday set is empty afterwards, you called retainAll on it directly instead of on a copy.

Practice 5, the lapsed customers. Customers who ordered in August but not in September is a difference:

Set<String> lapsed = new LinkedHashSet<>(august);
lapsed.removeAll(september);

New customers is the same operation the other way round. Loyal customers is retainAll. Three business questions, one method each — and doing any of them with nested loops over lists is both slower and easier to get wrong.

Practice

1. Deduplicate. Turn a list with repeats into a set in one line. Then print the same data through HashSet, LinkedHashSet and TreeSet and compare the orders.

2. Use the return value. Read a list of pincodes and report each duplicate as you find it, using only add.

3. Do the three set operations. Intersection, union and difference of two sets of names. Then deliberately call retainAll without copying and confirm you have destroyed the original.

4. Measure it. Build a 200,000-element ArrayList and HashSet of the same numbers and time 2,000 contains calls on each. Then try it with 400,000 and see which time doubles.

5. Answer three business questions. Given August and September customer sets: who lapsed, who is new, who is loyal. One set operation each.

6. Harder — serviceable pincodes. Load 50,000 pincodes from a list and check 100,000 orders against them. Do it once with a List and once with a HashSet, timing both. Then make the pincodes a TreeSet and use headSet to answer "which serviceable pincodes are below 411100" — and notice you have just done something neither of the other two could.

Next: equals and hashCode — the contract that makes all of this work, and what breaks when you get it wrong.