SyntaxPilot
Courses/Java/Lesson 31

Java · Lesson 31 of 51 · 11 min

Collections 2: HashSet, LinkedHashSet, TreeSet

queued

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), then a.hashCode() == b.hashCode(). The reverse isn't required: different objects may share a hash code (a collision); equals sorts 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]
  • add returns 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

  1. Count the unique words in "the cat and the dog and the bird".
  2. Print the first repeated character in "programming".
  3. Bus times 900, 930, 1000, 1045 in a TreeSet: the next bus after 9:40 (940)?
  4. Make a Book class 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

  1. How does HashSet work internally? It's backed by a HashMap: each element is a key; hashCode() picks the bucket and equals() finds the match inside it.
  2. What is the equals/hashCode contract? Equal objects must have equal hash codes; unequal objects may collide. Override both together, using the same fields.
  3. What happens if you override only equals? Equal objects may land in different buckets, so the set keeps duplicates.
  4. HashSet vs LinkedHashSet vs TreeSet? No order, O(1) / insertion order, O(1) / sorted, O(log n), needs comparison.
  5. 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).
  6. Does TreeSet use equals? No, it uses compareTo/compare; a result of 0 counts as a duplicate.
  7. Can a set contain null? HashSet and LinkedHashSet allow one null; TreeSet doesn't (it can't compare null); Set.of doesn't.
  8. Why shouldn't you change an object's hash fields while it's in a HashSet? It stays in the old bucket, so contains and remove can'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.contains is O(n).
  • Hashing: hashCode() picks a bucket, equals() checks inside it, so HashSet operations are about O(1).
  • HashSet.add returns false for 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 equals and hashCode together; 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).