Sets: HashSet & TreeSet

Unique elements with HashSet, LinkedHashSet and TreeSet, set algebra and navigation.

A set is a collection with no duplicates. Ask it "do you contain this?" and a hash-based set answers almost instantly, however large it is. Use sets for unique visitors, tags, permissions, already-seen IDs, and any time you would otherwise write if (!list.contains(x)) list.add(x).

`HashSet` basics#

SetBasics.java

import java.util.HashSet;
import java.util.Set;

public class SetBasics {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        System.out.println(tags.add("java"));     // true: added
        System.out.println(tags.add("spring"));
        System.out.println(tags.add("java"));     // false: already present

        System.out.println(tags.size());
        System.out.println(tags.contains("spring"));
        tags.remove("spring");
        System.out.println(tags.contains("spring"));

        for (String t : tags) {
            System.out.println("tag: " + t);
        }
    }
}

Output

true
true
false
2
true
false
tag: java

add, remove and contains are all O(1) on average for a HashSet. A List needs O(n) for contains.

A HashSet has no defined order. Elements may come out in any order, and that order can change as the set grows. Never rely on it.

Removing duplicates#

Dedupe.java

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class Dedupe {
    public static void main(String[] args) {
        List<String> emails = List.of("a@x.com", "b@x.com", "a@x.com", "c@x.com", "b@x.com");

        Set<String> unique = new LinkedHashSet<>(emails);   // keeps first-seen order
        System.out.println(unique);

        List<String> backToList = new ArrayList<>(unique);
        System.out.println(backToList.size());

        Set<String> seen = new LinkedHashSet<>();
        Set<String> duplicates = new LinkedHashSet<>();
        for (String e : emails) {
            if (!seen.add(e)) duplicates.add(e);           // add() returns false for repeats
        }
        System.out.println("Duplicates: " + duplicates);
    }
}

Output

[a@x.com, b@x.com, c@x.com]
3
Duplicates: [a@x.com, b@x.com]

The three main implementations#

	`HashSet`	`LinkedHashSet`	`TreeSet`
Order	none	insertion order	sorted
`add`/`contains`/`remove`	O(1)	O(1)	O(log n)
`null` allowed	one	one	no (with natural ordering)
Needs	`equals` + `hashCode`	`equals` + `hashCode`	`Comparable` or a `Comparator`
Use when	you just need uniqueness and speed	you also want predictable order	you need sorted data or range queries

ThreeSets.java

import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class ThreeSets {
    public static void main(String[] args) {
        List<String> input = List.of("pear", "apple", "fig", "apple", "banana");
        System.out.println(new LinkedHashSet<>(input));   // as inserted
        System.out.println(new TreeSet<>(input));         // alphabetical
    }
}

Output

[pear, apple, fig, banana]
[apple, banana, fig, pear]

Set algebra: union, intersection, difference#

The bulk methods mutate the set they are called on, so copy first if you want to keep the original:

SetAlgebra.java

import java.util.Set;
import java.util.TreeSet;

public class SetAlgebra {
    public static void main(String[] args) {
        Set<String> javaDevs = Set.of("Asha", "Ben", "Chen", "Dev");
        Set<String> pythonDevs = Set.of("Chen", "Dev", "Esha");

        Set<String> union = new TreeSet<>(javaDevs);
        union.addAll(pythonDevs);
        System.out.println("Either: " + union);

        Set<String> both = new TreeSet<>(javaDevs);
        both.retainAll(pythonDevs);
        System.out.println("Both: " + both);

        Set<String> onlyJava = new TreeSet<>(javaDevs);
        onlyJava.removeAll(pythonDevs);
        System.out.println("Only Java: " + onlyJava);

        System.out.println(javaDevs.containsAll(Set.of("Asha", "Ben")));
    }
}

Output

Either: [Asha, Ben, Chen, Dev, Esha]
Both: [Chen, Dev]
Only Java: [Asha, Ben]
true

Set.of(...) creates an unmodifiable set (and throws if you pass duplicates or null).

`TreeSet`: sorted and navigable#

TreeSet is backed by a red-black tree. Besides keeping order, it implements NavigableSet, which answers "nearest" and "range" questions:

Navigable.java

import java.util.TreeSet;

public class Navigable {
    public static void main(String[] args) {
        TreeSet<Integer> slots = new TreeSet<>(java.util.List.of(900, 1030, 1200, 1400, 1630));

        System.out.println(slots.first() + " " + slots.last());
        System.out.println(slots.ceiling(1100));   // smallest >= 1100
        System.out.println(slots.floor(1100));     // largest <= 1100
        System.out.println(slots.higher(1200));    // strictly greater
        System.out.println(slots.lower(900));      // strictly smaller: none
        System.out.println(slots.headSet(1200));   // < 1200
        System.out.println(slots.tailSet(1200));   // >= 1200
        System.out.println(slots.subSet(1000, 1500));
        System.out.println(slots.descendingSet());
        System.out.println(slots.pollFirst() + " removed, now " + slots);
    }
}

Output

900 1630
1200
1030
1400
null
[900, 1030]
[1200, 1400, 1630]
[1030, 1200, 1400]
[1630, 1400, 1200, 1030, 900]
900 removed, now [1030, 1200, 1400, 1630]

You can also give a TreeSet a custom order:

CustomOrder.java

import java.util.Comparator;
import java.util.TreeSet;

public class CustomOrder {
    public static void main(String[] args) {
        TreeSet<String> byLength = new TreeSet<>(
            Comparator.comparing(String::length).thenComparing(Comparator.naturalOrder()));
        byLength.addAll(java.util.List.of("kiwi", "fig", "banana", "plum", "apple"));
        System.out.println(byLength);

        TreeSet<String> ignoreCase = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
        ignoreCase.add("Java");
        ignoreCase.add("JAVA");      // considered equal by the comparator: not added
        System.out.println(ignoreCase);
    }
}

Output

[fig, kiwi, plum, apple, banana]
[Java]

Important: a TreeSet decides equality using compareTo/the comparator, not equals. If the comparator says two elements are equal (returns 0), the second one is treated as a duplicate.

Sets of your own objects#

HashSet relies on hashCode() and equals() to detect duplicates. If your class doesn't override them, two objects with identical data are considered different:

CustomObjects.java

import java.util.HashSet;
import java.util.Set;

public class CustomObjects {
    static class PointClass {           // no equals/hashCode
        final int x, y;
        PointClass(int x, int y) { this.x = x; this.y = y; }
    }

    record Point(int x, int y) { }      // records generate equals/hashCode

    public static void main(String[] args) {
        Set<PointClass> a = new HashSet<>();
        a.add(new PointClass(1, 2));
        a.add(new PointClass(1, 2));
        System.out.println(a.size());   // 2: duplicates not detected!

        Set<Point> b = new HashSet<>();
        b.add(new Point(1, 2));
        b.add(new Point(1, 2));
        System.out.println(b.size());   // 1
        System.out.println(b.contains(new Point(1, 2)));
    }
}

Output

2
1
true

The fix is to implement equals and hashCode, or use a record. This is covered in depth in the equals() & hashCode() lesson. Also, never mutate an object while it is inside a HashSet in a way that changes its hash code; the set will no longer find it.

Performance: List vs Set lookups#

LookupSpeed.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LookupSpeed {
    public static void main(String[] args) {
        int n = 50_000;
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) { list.add(i); set.add(i); }

        long t0 = System.nanoTime();
        int hits = 0;
        for (int i = 0; i < n; i++) if (list.contains(i)) hits++;
        long listMs = (System.nanoTime() - t0) / 1_000_000;

        t0 = System.nanoTime();
        for (int i = 0; i < n; i++) if (set.contains(i)) hits++;
        long setMs = (System.nanoTime() - t0) / 1_000_000;

        System.out.println("hits " + hits);
        System.out.println("List: " + listMs + " ms, Set: " + setMs + " ms");
    }
}

Typical output (exact numbers depend on your machine):

Output

hits 100000
List: 520 ms, Set: 3 ms

50,000 lookups in a list of 50,000 is about 1.25 billion comparisons; the set does about 50,000 hash lookups.

Common mistakes#

Relying on HashSet iteration order.
Putting objects without equals/hashCode into a HashSet.
Mutating elements after adding them to a hash-based set.
Expecting TreeSet to use equals; it uses the comparator.
Adding null to a TreeSet or to Set.of(...), which throws NullPointerException.

What's next#

Sets store unique values. Often you need to associate values with keys instead: a phone book, word counts, a cache. That's the job of maps, up next.

HashSet basics#

Removing duplicates#

The three main implementations#

Set algebra: union, intersection, difference#

TreeSet: sorted and navigable#

Sets of your own objects#

Performance: List vs Set lookups#

Common mistakes#

What's next#

Quick quiz

`HashSet` basics#

`TreeSet`: sorted and navigable#