These are the notes for Java episode 31. Fest registrations get duplicates when students click Register twice. A List keeps them, and checking contains before every add is correct but painfully slow at scale. Today we invent hashing (a number from each item picks a bucket, equals checks inside it) and meet the three sets: HashSet (fast, no order), LinkedHashSet (arrival order) and TreeSet (sorted). We also see why your own classes need equals and hashCode, why a TreeSet needs items that can be compared, and set maths. Every example was run with javac 21.
The problem: a List keeps duplicates
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> fest = new ArrayList<>();
fest.add("asha@mail.in");
fest.add("ravi@mail.in");
fest.add("asha@mail.in"); // clicked Register twice
fest.add("meena@mail.in");
System.out.println("Registrations: " + fest.size());
System.out.println(fest);
}
}
Registrations: 4
[asha@mail.in, ravi@mail.in, asha@mail.in, meena@mail.in]
Four lunches for three people. A List (episode 30) is a sequence: it keeps everything you add.
Obvious fix: check before adding (slow)
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> fest = new ArrayList<>();
long t = System.nanoTime();
for (int i = 0; i < 100_000; i++) {
int id = i % 50_000; // everyone registers twice
if (!fest.contains(id)) fest.add(id);
}
long ms = (System.nanoTime() - t) / 1_000_000;
System.out.println(fest.size() + " people, " + ms + " ms");
}
}
One run on our machine (times vary):
50000 people, 3615 ms
Correct, but contains on a list checks every item from the start: O(n) per check, so O(n²) overall, billions of comparisons.
The fix: hashing
| At a post office | In Java |
|---|---|
| A letter carries a PIN code | hashCode(): a number computed from the object |
| The PIN code picks one pigeonhole | the hash code picks a bucket |
| Look only inside that pigeonhole | equals() compares only the few items there |
| Found in seconds, however many letters | HashSet: about constant time, O(1) |
public class Main {
public static void main(String[] args) {
String a = "asha@mail.in";
String b = new String("asha@mail.in");
System.out.println(a.hashCode() + " " + b.hashCode());
System.out.println("ravi@mail.in".hashCode());
System.out.println(Math.abs(a.hashCode()) % 16);
System.out.println(Math.abs("ravi@mail.in".hashCode()) % 16);
}
}
1654781479 1654781479
1803618206
7
14
- Equal strings have the same hash code, even as different objects.
- The last line is a simplified way to pick one of 16 buckets (Java's real formula also mixes the high bits,
h ^ (h >>> 16), and uses& (n - 1)). - The contract: if
a.equals(b), thena.hashCode() == b.hashCode(). The reverse isn't required: different objects may share a hash code (a collision);equalssorts them out inside the bucket.
HashSet
A Set is a collection with no duplicates. HashSet builds it with buckets (internally, it's a HashMap, episode 32).
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Set<String> fest = new HashSet<>();
System.out.println(fest.add("asha@mail.in"));
System.out.println(fest.add("ravi@mail.in"));
System.out.println(fest.add("asha@mail.in")); // duplicate
fest.add("meena@mail.in");
System.out.println("Registrations: " + fest.size());
System.out.println(fest.contains("ravi@mail.in") + " " + fest);
}
}
true
true
false
Registrations: 3
true [meena@mail.in, asha@mail.in, ravi@mail.in]
addreturns false when the item is already there.- The printed order is bucket order, not insertion order. Never rely on a HashSet's order.
Same fest test, no contains check:
Set<Integer> fest = new HashSet<>();
for (int i = 0; i < 100_000; i++) {
int id = i % 50_000; // everyone registers twice
fest.add(id);
}
50000 people, 51 ms
From seconds to milliseconds by changing the collection.
LinkedHashSet and TreeSet: choosing an order
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
String[] arrivals = { "Ravi", "Zoya", "Asha", "Meena", "Kabir", "Asha" };
Set<String> h = new HashSet<>();
Set<String> l = new LinkedHashSet<>();
Set<String> t = new TreeSet<>();
for (String s : arrivals) { h.add(s); l.add(s); t.add(s); }
System.out.println("HashSet: " + h);
System.out.println("LinkedHashSet: " + l);
System.out.println("TreeSet: " + t);
}
}
HashSet: [Ravi, Asha, Zoya, Kabir, Meena]
LinkedHashSet: [Ravi, Zoya, Asha, Meena, Kabir]
TreeSet: [Asha, Kabir, Meena, Ravi, Zoya]
- LinkedHashSet = a HashSet plus a linked list through its items: insertion order, nearly as fast.
- TreeSet = a red-black tree (a self-balancing binary search tree): always sorted, O(log n) per operation.
| A dictionary | In Java |
|---|---|
| Words always in A to Z order | TreeSet is always sorted |
| Open in the middle, before or after, halve again | the tree compares and goes left or right |
| The next word after "mango" | ceiling, higher, floor, lower |
TreeSet tools
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
TreeSet<Integer> slots = new TreeSet<>();
slots.add(1300); slots.add(800); slots.add(1800);
slots.add(1030); slots.add(800);
System.out.println(slots);
System.out.println(slots.first() + " " + slots.last());
System.out.println(slots.ceiling(1000) + " " + slots.floor(1000));
System.out.println(slots.headSet(1300) + " " + slots.tailSet(1300));
}
}
[800, 1030, 1300, 1800]
800 1800
1030 800
[800, 1030] [1300, 1800]
| Method | Returns |
|---|---|
first() / last() |
smallest / largest |
ceiling(x) / floor(x) |
smallest ≥ x / largest ≤ x (or null) |
higher(x) / lower(x) |
smallest > x / largest < x |
headSet(x) / tailSet(x) |
items < x / items ≥ x |
pollFirst() / pollLast() |
remove and return the smallest / largest |
descendingSet() |
the set in reverse order |
Trap 1: your own class without equals and hashCode
import java.util.HashSet;
import java.util.Set;
class Student {
String roll;
String name;
Student(String roll, String name) { this.roll = roll; this.name = name; }
}
public class Main {
public static void main(String[] args) {
Set<Student> fest = new HashSet<>();
fest.add(new Student("21CS07", "Asha"));
fest.add(new Student("21CS07", "Asha"));
System.out.println("Registrations: " + fest.size());
}
}
Registrations: 2
Without overrides, Student uses Object's equals and hashCode (episode 22), which compare identity: two new objects are always different. Fix: define equality, and the hash code from the same fields:
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
class Student {
String roll;
String name;
Student(String roll, String name) { this.roll = roll; this.name = name; }
@Override
public boolean equals(Object o) {
if (!(o instanceof Student)) return false;
return roll.equals(((Student) o).roll);
}
@Override
public int hashCode() { return Objects.hash(roll); }
}
public class Main {
public static void main(String[] args) {
Set<Student> fest = new HashSet<>();
fest.add(new Student("21CS07", "Asha"));
fest.add(new Student("21CS07", "Asha"));
System.out.println("Registrations: " + fest.size());
}
}
Registrations: 1
Override both. With only equals, the two copies get different identity hash codes, land in different buckets, and are never compared. A record (episode 24) generates both for you. Also: don't change a field used in hashCode while the object is inside a set; it would sit in the wrong bucket.
Trap 2: your own class in a TreeSet
import java.util.Set;
import java.util.TreeSet;
class Student {
String roll;
Student(String roll) { this.roll = roll; }
}
public class Main {
public static void main(String[] args) {
Set<Student> fest = new TreeSet<>();
fest.add(new Student("21CS07"));
System.out.println(fest.size());
}
}
Exception in thread "main" java.lang.ClassCastException: class Student cannot be cast to class java.lang.Comparable (Student is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
at java.base/java.util.TreeMap.compare(TreeMap.java:1604)
...
at java.base/java.util.TreeSet.add(TreeSet.java:259)
at Main.main(Main.java:12)
A TreeSet must compare items. String and Integer implement Comparable; Student doesn't. Fix: implement Comparable<Student> or pass a Comparator (episode 34). A TreeSet uses compareTo (not equals) to detect duplicates, and doesn't allow null.
Set maths
import java.util.Set;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
Set<String> dance = Set.of("Asha", "Ravi", "Meena");
Set<String> music = Set.of("Ravi", "Kabir", "Meena");
Set<String> both = new TreeSet<>(dance);
both.retainAll(music); // in both
Set<String> any = new TreeSet<>(dance);
any.addAll(music); // in either
Set<String> onlyDance = new TreeSet<>(dance);
onlyDance.removeAll(music); // dance, not music
System.out.println(both + " " + any + " " + onlyDance);
}
}
[Meena, Ravi] [Asha, Kabir, Meena, Ravi] [Asha]
| Maths | Method | Result |
|---|---|---|
| Intersection A ∩ B | a.retainAll(b) |
in both |
| Union A ∪ B | a.addAll(b) |
in either |
| Difference A − B | a.removeAll(b) |
in A, not B |
| Subset A ⊆ B | b.containsAll(a) |
true/false |
Set.of is read-only (like List.of), so copy it before changing.
Which set?
| HashSet | LinkedHashSet | TreeSet | |
|---|---|---|---|
| Order | none (bucket order) | insertion order | sorted |
| add / contains / remove | O(1) average | O(1) average | O(log n) |
| Needs | equals + hashCode |
equals + hashCode |
Comparable or a Comparator |
| null | one allowed | one allowed | not allowed |
| Extras | first, last, ceiling, floor, ranges |
||
| Use it when | default | arrival order matters | sorted order or nearest-value queries |
Common mistakes (and the real error messages)
| Mistake | Real message | Why | Fix |
|---|---|---|---|
if (!list.contains(x)) list.add(x) at scale |
no error: seconds instead of milliseconds | contains checks every item |
HashSet |
| own class in a HashSet, no overrides | no error: Registrations: 2 |
Object compares identity |
override equals and hashCode |
overriding only equals |
no error: duplicates still kept | different buckets | override hashCode too |
| own class in a TreeSet | ClassCastException: class Student cannot be cast to class java.lang.Comparable |
TreeSet must compare | implements Comparable or a Comparator |
| expecting HashSet to keep add order | no error: jumbled order | buckets decide the order | LinkedHashSet / TreeSet |
Set.of(...).add(x) |
java.lang.UnsupportedOperationException |
immutable | new HashSet<>(Set.of(...)) |
set.get(0) |
error: cannot find symbol / symbol: method get(int) |
sets have no index | iterate, or use a List |
Mini project: fest registration desk
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
String[] clicks = { "ravi@mail.in", "asha@mail.in", "ravi@mail.in", "zoya@mail.in", "asha@mail.in", "kabir@mail.in" };
Set<String> seen = new HashSet<>();
Set<String> repeated = new TreeSet<>();
Set<String> firstCome = new LinkedHashSet<>();
for (String c : clicks) {
if (!seen.add(c)) repeated.add(c); // add() is false for a duplicate
firstCome.add(c);
}
System.out.println("Unique people: " + seen.size());
System.out.println("Clicked twice: " + repeated);
System.out.println("Arrival order: " + firstCome);
System.out.println("Certificates: " + new TreeSet<>(seen));
}
}
Unique people: 4
Clicked twice: [asha@mail.in, ravi@mail.in]
Arrival order: [ravi@mail.in, asha@mail.in, zoya@mail.in, kabir@mail.in]
Certificates: [asha@mail.in, kabir@mail.in, ravi@mail.in, zoya@mail.in]
Practice
- Count the unique words in
"the cat and the dog and the bird". - Print the first repeated character in
"programming". - Bus times 900, 930, 1000, 1045 in a TreeSet: the next bus after 9:40 (940)?
- Make a
Bookclass work in a HashSet by ISBN.
Solutions
import java.util.*;
public class Main {
public static void main(String[] args) {
String s = "the cat and the dog and the bird";
System.out.println(new HashSet<>(Arrays.asList(s.split(" "))).size()); // 5
Set<Character> seen = new HashSet<>();
for (char c : "programming".toCharArray()) if (!seen.add(c)) { System.out.println(c); break; } // r
TreeSet<Integer> bus = new TreeSet<>(List.of(900, 930, 1000, 1045));
System.out.println(bus.ceiling(940)); // 1000
}
}
5
r
1000
4. Override equals to compare isbn, and hashCode as Objects.hash(isbn), or write record Book(String isbn, String title) and compare on all fields.
Quick quiz
Set<Integer> a = new LinkedHashSet<>();
Set<Integer> b = new TreeSet<>();
for (int x : new int[] { 30, 10, 30, 20 }) {
a.add(x); b.add(x);
}
System.out.println(a + " " + b + " " + a.add(10));
A) [30, 10, 30, 20] [10, 20, 30] true B) [30, 10, 20] [10, 20, 30] false C) [10, 20, 30] [10, 20, 30] false D) [30, 10, 20] [30, 20, 10] true
Answer
B. The LinkedHashSet keeps arrival order and drops the second 30. The TreeSet sorts. 10 is already in a, so add(10) returns false.
[30, 10, 20] [10, 20, 30] false
Interview questions
- How does HashSet work internally? It's backed by a
HashMap: each element is a key;hashCode()picks the bucket andequals()finds the match inside it. - What is the equals/hashCode contract? Equal objects must have equal hash codes; unequal objects may collide. Override both together, using the same fields.
- What happens if you override only equals? Equal objects may land in different buckets, so the set keeps duplicates.
- HashSet vs LinkedHashSet vs TreeSet? No order, O(1) / insertion order, O(1) / sorted, O(log n), needs comparison.
- What is a hash collision? Two different objects in the same bucket; Java keeps a small list in the bucket (a tree if it gets long, from Java 8).
- Does TreeSet use equals? No, it uses
compareTo/compare; a result of 0 counts as a duplicate. - Can a set contain null? HashSet and LinkedHashSet allow one
null; TreeSet doesn't (it can't comparenull);Set.ofdoesn't. - Why shouldn't you change an object's hash fields while it's in a HashSet? It stays in the old bucket, so
containsandremovecan't find it.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Set | A collection with no duplicates | Set<String> |
| Duplicate | An item equal to one already present | asha@mail.in twice |
| Hashing | Turning an item into a number to find its place fast | post-office PIN codes |
| hashCode() | The number an object computes from its contents | "asha@mail.in".hashCode() |
| Bucket | One slot of a hash table, chosen by the hash code | 16 buckets by default |
| equals() | Decides whether two objects mean the same thing | same roll number |
| Hash collision | Different objects in the same bucket | resolved by equals |
| equals/hashCode contract | Equal objects must have equal hash codes | override both |
| HashSet | A set built on buckets; fast, no order | new HashSet<>() |
| LinkedHashSet | A HashSet that remembers insertion order | arrival list |
| TreeSet | A sorted set built on a balanced tree | new TreeSet<>() |
| Red-black tree | A self-balancing binary search tree | inside TreeSet / TreeMap |
| Comparable | An interface for objects that can compare themselves | String, Integer |
| ceiling / floor | Smallest ≥ x / largest ≤ x in a sorted set | next show after 10:00 |
| Intersection / union / difference | In both / in either / in A but not B | retainAll, addAll, removeAll |
| O(log n) | Time that grows slowly, by halving | TreeSet operations |
| Objects.hash | Builds a hash code from several fields | Objects.hash(roll) |
Summary
- A List keeps duplicates, and
list.containsis O(n). - Hashing:
hashCode()picks a bucket,equals()checks inside it, soHashSetoperations are about O(1). HashSet.addreturnsfalsefor a duplicate; its order is not guaranteed.- LinkedHashSet keeps arrival order; TreeSet keeps sorted order and answers
first,last,ceiling,floor. - Your own classes: override
equalsandhashCodetogether; for a TreeSet, make them Comparable (episode 34). - Set maths:
retainAll,addAll,removeAll. - Next: given a key, find a whole value: HashMap internals and TreeMap (episode 32).