Java HashSet and TreeSet

A Set is a collection that stores unique elements — no duplicates allowed. Java’s two most common set implementations, HashSet and TreeSet, both enforce this uniqueness but organize their elements very differently under the hood: HashSet uses a hash table for fast, unordered storage, while TreeSet uses a self-balancing binary search tree to keep elements sorted at all times. Picking between them is really a tradeoff between raw speed and guaranteed ordering.

Overview / How Sets Work

The Set interface extends Collection and adds exactly one rule: no two elements may be “equal” to each other. What counts as “equal” depends on the implementation. HashSet is backed internally by a HashMap — every element you add is stored as a key in that map (with a dummy constant value), so uniqueness is decided by hashCode() and equals(). TreeSet is backed internally by a TreeMap, which is a red-black tree, so uniqueness and ordering are both decided by compareTo() (or a Comparator you supply) rather than equals().

This leads to very different performance characteristics. A HashSet offers average O(1) time for add, remove, and contains, but gives you no ordering guarantee at all — the iteration order can change between runs, between JDK versions, or even after a resize. A TreeSet offers O(log n) time for the same operations, but always iterates in sorted order and supports powerful range queries like “give me everything between X and Y.”

Another subtle but important difference: HashSet permits a single null element, because HashMap reserves a special bucket for a null key. A TreeSet using natural ordering does not permit null — trying to insert one throws a NullPointerException, because the tree has to call null.compareTo(...) to figure out where it belongs.

Syntax

Set<Type> setName = new HashSet<>();
Set<Type> setName = new TreeSet<>();
TreeSet<Type> setName = new TreeSet<>(comparator);

Method	Available on	Description
add(e)	both	Inserts e; returns false if it was already present
remove(e)	both	Removes e if present
contains(e)	both	Checks membership
size() / isEmpty()	both	Count of elements / whether it’s empty
first() / last()	TreeSet	Smallest / largest element
higher(e) / lower(e)	TreeSet	Strictly greater / lesser neighbor of e
ceiling(e) / floor(e)	TreeSet	Smallest element >= e / largest element <= e
headSet(e) / tailSet(e)	TreeSet	View of elements before / from e

Examples

1. A basic HashSet

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

public class Main {
    public static void main(String[] args) {
        Set<Integer> numbers = new HashSet<>();
        numbers.add(5);
        numbers.add(3);
        numbers.add(9);
        numbers.add(3);
        numbers.add(1);

        System.out.println("Set contents: " + numbers);
        System.out.println("Size: " + numbers.size());
        System.out.println("Contains 9? " + numbers.contains(9));
    }
}

Output:

Set contents: [1, 3, 5, 9]
Size: 4
Contains 9? true

Notice the duplicate 3 was silently ignored — add() returns false for it instead of throwing. For small, non-negative Integer values like these, HashSet happens to iterate in ascending order because an Integer‘s hash code is its own value, which maps directly to a bucket index in the default 16-bucket table. This is an implementation detail, not a guarantee — don’t rely on it for anything but strings and larger/negative numbers, where the order looks essentially random.

2. TreeSet keeps things sorted

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> scores = new TreeSet<>();
        scores.add(72);
        scores.add(95);
        scores.add(48);
        scores.add(88);
        scores.add(60);

        System.out.println("Sorted scores: " + scores);
        System.out.println("Lowest: " + scores.first());
        System.out.println("Highest: " + scores.last());
        System.out.println("Smallest score >= 60: " + scores.ceiling(60));
        System.out.println("Largest score < 88: " + scores.lower(88));
    }
}

Output:

Sorted scores: [48, 60, 72, 88, 95]
Lowest: 48
Highest: 95
Smallest score >= 60: 60
Largest score < 88: 72

Unlike HashSet, this ordering is guaranteed by the contract of TreeSet — every insertion walks the red-black tree to find the correct sorted position. Methods like ceiling and lower take advantage of that structure to answer “nearest value” questions in O(log n) time instead of scanning the whole set.

3. A realistic example: sorting custom objects

import java.util.TreeSet;

class Employee implements Comparable<Employee> {
    String name;
    double salary;

    Employee(String name, double salary) {
        this.name = name;
        this.salary = salary;
    }

    @Override
    public int compareTo(Employee other) {
        return Double.compare(this.salary, other.salary);
    }

    @Override
    public String toString() {
        return name + " ($" + salary + ")";
    }
}

public class Main {
    public static void main(String[] args) {
        TreeSet<Employee> employees = new TreeSet<>();
        employees.add(new Employee("Dana", 72000));
        employees.add(new Employee("Sam", 58000));
        employees.add(new Employee("Priya", 91000));

        System.out.println("Employees sorted by salary:");
        for (Employee e : employees) {
            System.out.println(e);
        }
        System.out.println("Highest paid: " + employees.last());
    }
}

Output:

Employees sorted by salary:
Sam ($58000.0)
Dana ($72000.0)
Priya ($91000.0)
Highest paid: Priya ($91000.0)

Because Employee implements Comparable<Employee>, the TreeSet knows exactly how to order every insertion — no manual sorting step needed. If you wanted a different order (say, alphabetical by name) without changing the class, you’d pass a Comparator<Employee> to the TreeSet constructor instead of relying on compareTo.

Under the Hood

HashSet: internally it’s a HashMap<E, Object> where your elements are keys and every value points to a shared dummy constant. When you call add(e), Java computes e.hashCode(), “spreads” the bits to reduce collisions, and uses hash & (capacity - 1) to pick a bucket index (capacity is always a power of two, default 16). If that bucket already holds elements, Java compares your new element to each one with equals() to check for a real duplicate; if none match, it’s appended to that bucket’s list (or a small tree, once a bucket gets crowded with 8+ entries). Once the number of elements exceeds capacity * loadFactor (0.75 by default), the whole table doubles in size and everything is rehashed — which is why iteration order can shift as a set grows.

TreeSet: internally it’s a TreeMap<E, Object>, a self-balancing red-black tree. Every add(e) walks down from the root, comparing e against existing nodes with compareTo() (or your Comparator) until it finds the right spot, then rebalances the tree if needed to keep operations at O(log n). Critically, TreeSet decides duplicates using compareTo, not equals. If compareTo returns 0 for two objects that are otherwise different, the second one is silently rejected as a “duplicate” — even though equals() would say they’re not the same object at all. This is a frequent source of subtle bugs when a Comparator only looks at one field.

Common Mistakes

Mistake 1: Forgetting to override equals() and hashCode()

Wrong — two objects that “look” identical are treated as distinct because the default Object.equals() compares memory references:

import java.util.HashSet;

class Point {
    int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }
}

public class Main {
    public static void main(String[] args) {
        HashSet<Point> points = new HashSet<>();
        points.add(new Point(1, 2));
        points.add(new Point(1, 2));

        System.out.println("Size: " + points.size());
    }
}

Output:

Size: 2

Both points have the same coordinates, but the set still stores two entries because Point never told Java what “equal” means for it. Fixed version:

import java.util.HashSet;
import java.util.Objects;

class Point {
    int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Point)) return false;
        Point other = (Point) obj;
        return x == other.x && y == other.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

public class Main {
    public static void main(String[] args) {
        HashSet<Point> points = new HashSet<>();
        points.add(new Point(1, 2));
        points.add(new Point(1, 2));

        System.out.println("Size: " + points.size());
    }
}

Output:

Size: 1

Always override equals() and hashCode() together — if two objects are equal, their hash codes must match too, or a HashSet may never even look in the right bucket to find the duplicate.

Mistake 2: Removing from a set while looping over it with for-each

Wrong — modifying a set during iteration corrupts the iterator’s internal bookkeeping:

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

public class Main {
    public static void main(String[] args) {
        Set<Integer> numbers = new HashSet<>();
        numbers.add(2);
        numbers.add(4);
        numbers.add(6);
        numbers.add(8);

        for (int n : numbers) {
            if (n == 2) {
                numbers.remove(n);
            }
        }

        System.out.println(numbers);
    }
}

Output:

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java)
    at java.base/java.util.HashMap$KeyIterator.next(HashMap.java)
    at Main.main(Main.java:12)

A for-each loop uses an Iterator behind the scenes, and every set method that structurally changes the collection (like remove called directly on the set) invalidates it, tripping a safety check the next time next() is called. Fixed version — remove through the iterator itself:

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

public class Main {
    public static void main(String[] args) {
        Set<Integer> numbers = new HashSet<>();
        numbers.add(2);
        numbers.add(4);
        numbers.add(6);
        numbers.add(8);

        Iterator<Integer> it = numbers.iterator();
        while (it.hasNext()) {
            int n = it.next();
            if (n == 2) {
                it.remove();
            }
        }

        System.out.println(numbers);
    }
}

Output:

[4, 6, 8]

Best Practices

• Always override equals() and hashCode() together for any class you plan to store in a HashSet.
• For TreeSet, make sure your compareTo/Comparator is consistent with equals — otherwise two “different” objects can silently vanish as duplicates.
• Use TreeSet when you need sorted iteration or range queries (headSet, tailSet, ceiling, floor).
• Use HashSet when you only need fast uniqueness checks and don’t care about order — it’s faster and uses less memory per operation.
• Never mutate a set directly while iterating with for-each; use Iterator.remove() instead.
• If you want insertion-order iteration with HashSet-like speed, use LinkedHashSet instead of either of these.
• Don’t hard-code assumptions about HashSet iteration order into your program logic — it’s an implementation detail that can change.
• If you know roughly how many elements you’ll store, construct the HashSet with an initial capacity to avoid repeated resizing.

Practice Exercises

Exercise 1: Write a program that reads a list of words from an array and prints only the unique ones (in any order), using a HashSet.

Exercise 2: Given an array of int values with duplicates, use a TreeSet to print them in sorted order with duplicates removed, then print the second-highest value using TreeSet methods (no manual loops for the second-highest part).

Exercise 3: Define a Book class with title and isbn fields. Override equals() and hashCode() based only on isbn, then add several Book objects (including two with the same isbn but different titles) to a HashSet and print the resulting size to confirm the duplicate was rejected.

Summary

• HashSet stores unique elements using a hash table; it offers average O(1) operations but no ordering guarantee.
• TreeSet stores unique elements in a sorted red-black tree; it offers O(log n) operations plus guaranteed sorted order and range queries.
• HashSet uniqueness is decided by equals()/hashCode(); TreeSet uniqueness is decided by compareTo() or a supplied Comparator.
• Objects placed in a HashSet must override equals() and hashCode() together to behave correctly.
• TreeSet with natural ordering rejects null; HashSet allows exactly one null.
• Never remove from a set directly inside a for-each loop — use Iterator.remove() to avoid ConcurrentModificationException.
• Reach for LinkedHashSet when you want predictable insertion-order iteration.