HashSet & TreeSet

HashSet and TreeSet are the two workhorse implementations of the Set interface, and they sit at opposite ends of a classic trade-off: raw speed versus guaranteed ordering.

HashSet — Fast, Unordered

HashSet is backed by a hash table (internally, a HashMap whose values are all a shared dummy object). Adding, removing, and checking membership are all O(1) on average, because the element's hash code determines almost directly where it lives in the underlying table — no scanning required.

HashSet basics

Java

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

Set<String> cities = new HashSet<>();
cities.add("Tokyo");
cities.add("Cairo");
cities.add("Lima");

System.out.println(cities.contains("Cairo")); // O(1) average
System.out.println(cities);

true
[Cairo, Lima, Tokyo]

Never rely on HashSet's iteration order

HashSet gives absolutely no ordering guarantee. The order you see when printing or iterating depends on internal hash bucket placement, which can change between different runs of the same program, different JVM versions, or even after resizing the internal table as more elements are added. Code that depends on a particular HashSet order is fragile and will eventually break.

TreeSet — Sorted, Slower

TreeSet is backed by a red-black tree, a self-balancing binary search tree. Instead of scattering elements based on a hash code, TreeSet keeps them arranged in sorted order at all times — every add, remove, and contains operation runs in O(log n) time, which is slower than HashSet's O(1) average but comes with a real benefit: iterating a TreeSet always produces elements in ascending order.

TreeSet keeps elements sorted automatically

Java

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

Set<Integer> scores = new TreeSet<>();
scores.add(42);
scores.add(7);
scores.add(15);
scores.add(99);

System.out.println(scores); // always sorted ascending

[7, 15, 42, 99]

TreeSet also implements NavigableSet, which adds useful methods for working with ordered data, such as first(), last(), higher(e), and lower(e). By default it uses the elements' natural ordering (they must implement Comparable), but you can supply a custom Comparator instead — the same mechanism covered on the Comparable & Comparator page.

TreeSet with a custom Comparator

Java

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

TreeSet<String> byLength =
    new TreeSet<>(Comparator.comparingInt(String::length));

byLength.add("kiwi");
byLength.add("fig");
byLength.add("watermelon");

System.out.println(byLength);

[fig, kiwi, watermelon]

LinkedHashSet — The Middle Ground

LinkedHashSet is worth a quick mention alongside these two. It's a HashSet under the hood, but it additionally maintains a linked list running through all its entries, so iteration always follows insertion order — while keeping HashSet-like O(1) average performance for add, remove, and contains. It costs a bit more memory than a plain HashSet for that extra bookkeeping.

Comparison

Implementation	Backing structure	Ordering	Performance	Best for
HashSet	Hash table	None — unpredictable	O(1) average	Fastest general-purpose set when order doesn't matter
LinkedHashSet	Hash table + linked list	Insertion order	O(1) average	Predictable iteration without the cost of sorting
TreeSet	Red-black tree	Sorted order	O(log n)	When you need elements sorted, or range queries

Tip

Default to HashSet unless you specifically need sorted iteration order (reach for TreeSet) or insertion-order iteration (reach for LinkedHashSet). Picking TreeSet by habit when you never actually need the ordering just pays an unnecessary O(log n) tax on every operation.

HashSet: fastest, no ordering guarantee whatsoever
TreeSet: sorted order, O(log n) operations, supports NavigableSet methods
LinkedHashSet: HashSet speed with predictable insertion-order iteration

Note

All three still enforce the core Set contract — no duplicates — they simply differ in how they store elements internally and what iteration order (if any) that storage produces.