Skip to content
  • Set: HashSet, LinkedHashSet & TreeSet · Java

Set: HashSet, LinkedHashSet & TreeSet

LearnViaNotes @learnvianotes· 3 min read

A Set stores each element at most once. The three implementations differ only in ordering and speed: hash (no order), linked hash (insertion order), tree (sorted).

Comparison

HashSetLinkedHashSetTreeSet
Backed bya HashMap (elements are keys)a LinkedHashMapa TreeMap (red-black tree)
Iteration orderUnspecifiedInsertion orderSorted (natural or Comparator)
add / remove / containsO(1) averageO(1) averageO(log n)
null elementOne allowedOne allowedNo (NullPointerException)
Needsequals + hashCodeequals + hashCodeComparable or a Comparator
Extra API—reversed(), getFirst() (Java 21)first, floor, ceiling, headSet, subSet…

Same input, three orders

Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> input = List.of(42, 7, 19, 7, 3, 42);
        System.out.println("HashSet       " + new HashSet<>(input));
        System.out.println("LinkedHashSet " + new LinkedHashSet<>(input));
        System.out.println("TreeSet       " + new TreeSet<>(input));

        Set<String> seen = new HashSet<>();
        System.out.println(seen.add("x") + " " + seen.add("x"));   // second add is rejected
    }
}
Output
HashSet       [19, 3, 7, 42]
LinkedHashSet [42, 7, 19, 3]
TreeSet       [3, 7, 19, 42]
true false

TreeSet as a NavigableSet

Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> ts = new TreeSet<>(List.of(10, 20, 30, 40, 50));
        System.out.println(ts.first() + " " + ts.last());
        System.out.println(ts.floor(25) + " " + ts.ceiling(25));   // <= 25, >= 25
        System.out.println(ts.lower(20) + " " + ts.higher(20));    // < 20, > 20
        System.out.println(ts.floor(5));                           // none -> null
        System.out.println(ts.headSet(30) + " " + ts.tailSet(30)); // [..30) and [30..]
        System.out.println(ts.subSet(20, true, 40, true));
        System.out.println(ts.descendingSet());
        System.out.println(ts.pollFirst() + " -> " + ts);
    }
}
Output
10 50
20 30
10 30
null
[10, 20] [30, 40, 50]
[20, 30, 40]
[50, 40, 30, 20, 10]
10 -> [20, 30, 40, 50]

Trap: forgetting equals/hashCode

Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Set<Point> raw = new HashSet<>();
        raw.add(new Point(1, 2));
        raw.add(new Point(1, 2));
        System.out.println("class without equals/hashCode: " + raw.size());

        Set<PointRec> rec = new HashSet<>();
        rec.add(new PointRec(1, 2));
        rec.add(new PointRec(1, 2));
        System.out.println("record: " + rec.size());
    }
}

class Point {                        // uses Object's identity equals/hashCode
    final int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }
}

record PointRec(int x, int y) {}     // records generate equals/hashCode from the fields
Output
class without equals/hashCode: 2
record: 1
Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Set<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length));
        byLength.addAll(List.of("dog", "cat", "horse"));
        System.out.println(byLength);       // "cat" looked like a duplicate of "dog"
    }
}
Output
[dog, horse]

How does HashSet guarantee uniqueness?

HashSet vs TreeSet — which and why?

Can you add null to a TreeSet?

Free for students and teachers

Write notes like this one

Cards for every idea, quizzes and flashcards, read aloud — on the web and your phone.

Something wrong with this note? Open it to report