[Advanced Java] Set Implementations in Java: HashSet, LinkedHashSet and TreeSet

A List answers "what is at index 3". A Map answers "what is stored under this key". A Set answers exactly one question — is this element already in here — and every difference between the three JDK implementations falls out of how each one answers it.

The interface itself promises one thing and nothing more: no duplicates. Order, sorting, null tolerance and the cost of contains are all left to the implementation, and each of the three makes a different bargain. This article works through those bargains, and spends most of its length on the part that surprises people: HashSet and TreeSet do not agree on what a duplicate even is.

Every listing, javap dump, exception and count below was produced by compiling and running the code on OpenJDK 21.0.6 (arm64). Cost is always expressed as instrumented counts of hashCode(), equals() and compareTo() calls, never as elapsed time — a counter returns the same number on every machine and a stopwatch does not. The hashCode/equals contract itself is assumed here; it is the subject of the HashMap article in the Java Basics series.

What a Set guarantees, and what it does not

Set<E> extends Collection<E> and declares no method of its own. What it adds is a stricter reading of methods that already existed: add returns false instead of storing a second copy, and size() counts distinct elements.

The detail people miss is what happens to the object on a rejected add. The set keeps the one it already had and throws your new one away:

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

class Id {
    final String v;
    final int serial;

    Id(String v, int serial) { this.v = v; this.serial = serial; }

    @Override public boolean equals(Object o) { return o instanceof Id i && v.equals(i.v); }
    @Override public int hashCode() { return v.hashCode(); }
    @Override public String toString() { return v + "#" + serial; }
}

public class KeepsFirst {
    public static void main(String[] args) {
        Id first = new Id("a", 1);
        Id second = new Id("a", 2);

        Set<Id> s = new HashSet<>();
        System.out.println("add first  = " + s.add(first));
        System.out.println("add second = " + s.add(second));
        System.out.println("set        = " + s);
        System.out.println("kept is the first object = " + (s.iterator().next() == first));
    }
}

add first  = true
add second = false
set        = [a#1]
kept is the first object = true

add is not put. Two objects can be equal and still carry different data — a different serial, a different timestamp, a different cached field — and a Set silently keeps whichever arrived first. If you need last-write-wins, remove then add, or use a Map.

Here is the full list of what you are and are not promised:

Three implementations, three iteration orders

Same five elements, same insertion sequence, three different results:

import java.util.*;

public class Ordering {
    public static void main(String[] args) {
        List<String> input = List.of("delta", "alpha", "charlie", "bravo", "echo");

        Set<String> hash = new HashSet<>(input);
        Set<String> linked = new LinkedHashSet<>(input);
        Set<String> tree = new TreeSet<>(input);

        System.out.println("inserted      = " + input);
        System.out.println("HashSet       = " + hash);
        System.out.println("LinkedHashSet = " + linked);
        System.out.println("TreeSet       = " + tree);
    }
}

inserted      = [delta, alpha, charlie, bravo, echo]
HashSet       = [bravo, alpha, delta, echo, charlie]
LinkedHashSet = [delta, alpha, charlie, bravo, echo]
TreeSet       = [alpha, bravo, charlie, delta, echo]

LinkedHashSet and TreeSet are making a promise there. HashSet is not.

Why the HashSet order looks stable and still must not be relied on

That HashSet line is a real run, and it comes out the same on every run of this JDK. It does not even depend on the order the elements went in:

import java.util.*;

public class OrderIndep {
    public static void main(String[] args) {
        String[] a = {"delta", "alpha", "charlie", "bravo", "echo"};
        String[] b = {"echo", "bravo", "charlie", "alpha", "delta"};
        System.out.println("inserted A = " + new HashSet<>(Arrays.asList(a)));
        System.out.println("inserted B = " + new HashSet<>(Arrays.asList(b)));
    }
}

inserted A = [bravo, alpha, delta, echo, charlie]
inserted B = [bravo, alpha, delta, echo, charlie]

Both lines are identical because the position of a String in the table is a function of its hashCode() and the table size, and neither of those knows anything about insertion order. That determinism is what makes the trap dangerous: the order is reproducible enough to pass every test you write, and it is not a guarantee. Change the table size by adding one more element, run on a different JDK, or switch to a key type whose hashCode is not stable across JVMs, and it changes.

Set.of makes the point unmistakably. It is deliberately salted, so its iteration order changes between JVM runs of the same program:

import java.util.Set;

public class Immutable {
    public static void main(String[] args) {
        Set<String> s = Set.of("delta", "alpha", "charlie", "bravo", "echo");
        System.out.println("Set.of = " + s);
    }
}

Set.of = [echo, charlie, delta, bravo, alpha]
Set.of = [echo, alpha, bravo, delta, charlie]
Set.of = [alpha, echo, charlie, delta, bravo]
Set.of = [alpha, bravo, delta, charlie, echo]

Four runs of the same class file, four orders, no code change. That is the JDK actively defending the "unspecified" in the specification. If you need an order, name it: LinkedHashSet for insertion order, TreeSet for sorted order.

Two more things about Set.of worth knowing, since it is the shortest way to build a set: it rejects a duplicate at construction rather than collapsing it, and it rejects null.

add  -> java.lang.UnsupportedOperationException
dup  -> java.lang.IllegalArgumentException: duplicate element: a
null -> java.lang.NullPointerException

Set.copyOf, by contrast, does collapse duplicates — Set.copyOf(List.of("a", "b", "a")) gives a two-element set.

A HashSet is a HashMap with the values thrown away

This is not a metaphor. It is the implementation, and knowing it explains the whole cost profile of HashSet in one stroke. javap -p prints the private members of any class on the JDK's own class path:

javap -p java.util.HashSet

Compiled from "HashSet.java"
public class java.util.HashSet<E> extends java.util.AbstractSet<E> implements java.util.Set<E>, java.lang.Cloneable, java.io.Serializable {
  static final long serialVersionUID;
  transient java.util.HashMap<E, java.lang.Object> map;
  static final java.lang.Object PRESENT;
  public java.util.HashSet();
  ...
}

Two fields, and that is the entire state: a HashMap whose values are Object, and a single static final Object called PRESENT. Disassembling the methods shows how they are used:

javap -p -c java.util.HashSet

  public boolean add(E);
    Code:
       0: aload_0
       1: getfield      #10                 // Field map:Ljava/util/HashMap;
       4: aload_1
       5: getstatic     #64                 // Field PRESENT:Ljava/lang/Object;
       8: invokevirtual #68                 // Method java/util/HashMap.put:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
      11: ifnonnull     18
      14: iconst_1
      15: goto          19
      18: iconst_0
      19: ireturn

  public boolean contains(java.lang.Object);
    Code:
       0: aload_0
       1: getfield      #10                 // Field map:Ljava/util/HashMap;
       4: aload_1
       5: invokevirtual #60                 // Method java/util/HashMap.containsKey:(Ljava/lang/Object;)Z
       8: ireturn

  static {};
    Code:
       0: new           #80                 // class java/lang/Object
       3: dup
       4: invokespecial #225                // Method java/lang/Object."<init>":()V
       7: putstatic     #64                 // Field PRESENT:Ljava/lang/Object;
      10: return

Read straight off the bytecode: add(e) is map.put(e, PRESENT) and returns true exactly when put returned null, which is the map's way of saying the key was new. contains(o) is map.containsKey(o). The static initialiser allocates one bare Object for the whole class — one instance for every HashSet in the JVM, ever.

Confirming it with reflection

The bytecode is the proof, but the runtime picture is worth seeing. In Java 21 the module system blocks the obvious attempt:

Field f = HashSet.class.getDeclaredField("map");
f.setAccessible(true);

Exception in thread "main" java.lang.reflect.InaccessibleObjectException: Unable to make field transient java.util.HashMap java.util.HashSet.map accessible: module java.base does not "opens java.util" to unnamed module @15db9742
	at java.base/java.lang.reflect.AccessibleObject.throwInaccessibleObjectException(AccessibleObject.java:391)
	at java.base/java.lang.reflect.Field.setAccessible(Field.java:177)
	at Reflect.main(Reflect.java:8)

Run it with java --add-opens java.base/java.util=ALL-UNNAMED Reflect and you get:

HashSet.map class = java.util.HashMap
HashSet.map       = {a=java.lang.Object@3af49f1c, b=java.lang.Object@3af49f1c}
PRESENT class     = java.lang.Object
all values same object = true
value == PRESENT       = true
LinkedHashSet.map class = java.util.LinkedHashMap

Both entries print the same identity hash because both values are literally the same object. (The hex digits differ between runs; the important part is that the two are identical.) Everything you know about HashMap now transfers without modification:

The last row is the one that bites. Iteration walks the whole table, empty slots included, so a HashSet that once held a million elements and now holds three still takes a million-slot walk to iterate — the table does not shrink on remove.

LinkedHashSet: what the extra linked list buys

LinkedHashSet extends HashSet and adds no instance field of its own:

Compiled from "LinkedHashSet.java"
public class java.util.LinkedHashSet<E> extends java.util.HashSet<E> implements java.util.SequencedSet<E>, java.lang.Cloneable, java.io.Serializable {
  private static final long serialVersionUID;
  public java.util.LinkedHashSet(int, float);
  ...
  java.util.LinkedHashMap<E, java.lang.Object> map();
  public void addFirst(E);
  public void addLast(E);
  public E getFirst();
  public E getLast();
  public E removeFirst();
  public E removeLast();
  public java.util.SequencedSet<E> reversed();
}

It inherits HashSet's map field and fills it with a LinkedHashMap instead — which the reflection dump above already confirmed. The cost of the ordering guarantee is therefore exactly the cost of a LinkedHashMap entry over a HashMap one, and javap prices it:

class java.util.LinkedHashMap$Entry<K, V> extends java.util.HashMap$Node<K, V> {
  java.util.LinkedHashMap$Entry<K, V> before;
  java.util.LinkedHashMap$Entry<K, V> after;
}

Two extra reference fields per element, on top of the four a HashMap$Node already carries. In exchange, iteration follows the linked list rather than the table, so it is O(size) instead of O(capacity + size) — a LinkedHashSet can actually iterate faster than a HashSet of the same contents when the table is sparse.

Re-adding an element does not move it; removing and re-adding does

The obvious question about insertion order is what happens on a repeat add. Do not guess — run it:

import java.util.*;

public class Reinsert {
    public static void main(String[] args) {
        LinkedHashSet<String> s = new LinkedHashSet<>(List.of("a", "b", "c", "d"));
        System.out.println("start          = " + s);

        System.out.println("add(\"b\") again = " + s.add("b"));
        System.out.println("after re-add   = " + s);

        s.remove("b");
        System.out.println("after remove b = " + s);
        s.add("b");
        System.out.println("after re-insert= " + s);

        LinkedHashSet<String> t = new LinkedHashSet<>(List.of("a", "b", "c"));
        t.addFirst("z");
        System.out.println("addFirst z     = " + t);
        t.addLast("a");
        System.out.println("addLast a      = " + t);
        System.out.println("reversed       = " + t.reversed());
    }
}

start          = [a, b, c, d]
add("b") again = false
after re-add   = [a, b, c, d]
after remove b = [a, c, d]
after re-insert= [a, c, d, b]
addFirst z     = [z, a, b, c]
addLast a      = [z, b, c, a]
reversed       = [a, c, b, z]

Three separate behaviours in that output, and they are easy to conflate:

• add on an element already present does nothing at all. It returns false and the position is untouched. "Insertion order" means order of first insertion.
• remove then add moves the element to the end. As far as the linked list is concerned this is a brand new element.
• addLast on an element already present does move it. Look at the second-to-last line: t was [z, a, b, c], addLast("a") produced [z, b, c, a]. addFirst and addLast arrived with SequencedCollection in Java 21 and are explicitly documented to reposition an existing element, which makes them the odd ones out next to add.

That last asymmetry is a real source of bugs in code that mixes the two APIs on the same set.

TreeSet and the NavigableSet methods

TreeSet throws the hash table away entirely. javap -p java.util.TreeSet shows exactly one instance field, private transient java.util.NavigableMap<E, java.lang.Object> m, alongside the same PRESENT trick; the map is a TreeMap, which is a red-black tree. Elements are kept in sorted order — by their compareTo if they are Comparable, or by a Comparator handed to the constructor.

Sorted order is not the reason to reach for TreeSet, though. You can sort a HashSet into a list any time you like. The reason is NavigableSet: the tree can answer questions about nearby elements that no hash table can answer at all.

The navigation methods

import java.util.*;

public class Navigate {
    public static void main(String[] args) {
        TreeSet<Integer> t = new TreeSet<>(List.of(10, 20, 30, 40, 50));
        System.out.println("set          = " + t);
        System.out.println("first        = " + t.first());
        System.out.println("last         = " + t.last());
        System.out.println("floor(35)    = " + t.floor(35));
        System.out.println("floor(30)    = " + t.floor(30));
        System.out.println("ceiling(35)  = " + t.ceiling(35));
        System.out.println("ceiling(30)  = " + t.ceiling(30));
        System.out.println("lower(30)    = " + t.lower(30));
        System.out.println("higher(30)   = " + t.higher(30));
        System.out.println("floor(5)     = " + t.floor(5));
        System.out.println("ceiling(99)  = " + t.ceiling(99));
        System.out.println("headSet(30)  = " + t.headSet(30));
        System.out.println("headSet(30,t)= " + t.headSet(30, true));
        System.out.println("tailSet(30)  = " + t.tailSet(30));
        System.out.println("subSet(20,50)= " + t.subSet(20, 50));
        System.out.println("subSet incl  = " + t.subSet(20, true, 50, true));
        System.out.println("descendingSet= " + t.descendingSet());
    }
}

set          = [10, 20, 30, 40, 50]
first        = 10
last         = 50
floor(35)    = 30
floor(30)    = 30
ceiling(35)  = 40
ceiling(30)  = 30
lower(30)    = 20
higher(30)   = 40
floor(5)     = null
ceiling(99)  = null
headSet(30)  = [10, 20]
headSet(30,t)= [10, 20, 30]
tailSet(30)  = [30, 40, 50]
subSet(20,50)= [20, 30, 40]
subSet incl  = [20, 30, 40, 50]
descendingSet= [50, 40, 30, 20, 10]

The whole family reduces to two independent choices — which direction, and whether an exact match counts:

All four return null when nothing qualifies, which is why floor(5) and ceiling(99) are null above. The default headSet/tailSet/subSet forms follow the usual Java convention of inclusive lower bound and exclusive upper bound; the three-argument and four-argument overloads let you say otherwise.

Every one of these costs a walk down the tree, not a scan. A counting Comparator shows how short that walk is:

contains(30) comparisons = 3
contains(35) comparisons = 3
floor(35)    comparisons = 3
first()      comparisons = 0

Three comparisons in a five-element set, and first() needs none at all — it just follows left pointers to the end. That is the shape of the whole class: O(log n) for anything keyed on a value, O(1) for the ends.

Range views are live views

headSet, tailSet, subSet and descendingSet do not copy. They return a view backed by the same tree, and it works in both directions:

NavigableSet<Integer> view = t.tailSet(30, true);
t.add(45);
System.out.println("view is live = " + view);
view.remove(45);
System.out.println("backing set  = " + t);

System.out.println("pollFirst    = " + t.pollFirst() + " -> " + t);
System.out.println("pollLast     = " + t.pollLast() + " -> " + t);

view is live = [30, 40, 45, 50]
backing set  = [10, 20, 30, 40, 50]
pollFirst    = 10 -> [20, 30, 40, 50]
pollLast     = 50 -> [20, 30, 40]

Adding 45 to the backing set makes it appear in a view created before it existed, and removing it through the view removes it from the backing set. That is usually what you want and occasionally a nasty surprise: holding a subSet alive holds the entire original set alive too. Wrap it in new TreeSet<>(view) when you want a snapshot.

pollFirst and pollLast remove and return the ends, which makes a TreeSet a serviceable sorted work queue when you also need contains and de-duplication.

Two different rules for deciding a duplicate

Here is the section that matters. HashSet and TreeSet do not use the same definition of "already present", and neither the compiler nor the runtime will tell you when the two definitions disagree.

Instrument an element class to count every call it receives, then add the same seven values to each implementation:

import java.util.*;

class Probe implements Comparable<Probe> {
    static int hash = 0, eq = 0, cmp = 0;
    static void reset() { hash = eq = cmp = 0; }
    static String counts() { return "hashCode=" + hash + "  equals=" + eq + "  compareTo=" + cmp; }

    final int id;
    Probe(int id) { this.id = id; }

    @Override public int hashCode() { hash++; return Integer.hashCode(id); }
    @Override public boolean equals(Object o) { eq++; return o instanceof Probe p && id == p.id; }
    @Override public int compareTo(Probe o) { cmp++; return Integer.compare(id, o.id); }
}

public class WhoIsCalled {
    public static void main(String[] args) {
        int[] ids = {5, 3, 8, 1, 9, 3, 8};

        Probe.reset();
        Set<Probe> h = new HashSet<>();
        for (int i : ids) h.add(new Probe(i));
        System.out.println("HashSet  after 7 adds -> size " + h.size() + "   " + Probe.counts());

        Probe.reset();
        Set<Probe> t = new TreeSet<>();
        for (int i : ids) t.add(new Probe(i));
        System.out.println("TreeSet  after 7 adds -> size " + t.size() + "   " + Probe.counts());

        Probe.reset();
        h.contains(new Probe(9));
        System.out.println("HashSet  contains(#9)                    " + Probe.counts());

        Probe.reset();
        t.contains(new Probe(9));
        System.out.println("TreeSet  contains(#9)                    " + Probe.counts());
    }
}

HashSet  after 7 adds -> size 5   hashCode=7  equals=2  compareTo=0
TreeSet  after 7 adds -> size 5   hashCode=0  equals=0  compareTo=11
HashSet  contains(#9)             hashCode=1  equals=1  compareTo=0
TreeSet  contains(#9)             hashCode=0  equals=0  compareTo=3

Both sets end up with five elements, and they got there by consulting entirely disjoint methods. The TreeSet called equals() zero times. Not "rarely" — never. Its notion of duplicate is compare(a, b) == 0, full stop, and hashCode() is equally irrelevant to it.

Note also the two equals calls on the HashSet side: exactly the two repeated ids. equals is only consulted when a hash collision puts two elements in the same bucket, which is what makes a good hashCode worth having.

When compareTo disagrees with equals

Comparable's documentation calls a comparison "consistent with equals" when a.compareTo(b) == 0 agrees with a.equals(b), and says outright that it is strongly recommended but not required. Sorted collections are where "not required" turns into lost data.

Here is a version number whose compareTo deliberately ignores the build suffix:

import java.util.*;

class Version implements Comparable<Version> {
    final int major, minor;
    final String build;

    Version(int major, int minor, String build) {
        this.major = major; this.minor = minor; this.build = build;
    }

    @Override public boolean equals(Object o) {
        return o instanceof Version v && major == v.major && minor == v.minor && build.equals(v.build);
    }

    @Override public int hashCode() { return Objects.hash(major, minor, build); }

    // ignores build, so this is NOT consistent with equals
    @Override public int compareTo(Version o) {
        int c = Integer.compare(major, o.major);
        return c != 0 ? c : Integer.compare(minor, o.minor);
    }

    @Override public String toString() { return major + "." + minor + "+" + build; }
}

public class Conflict {
    public static void main(String[] args) {
        List<Version> versions = List.of(
                new Version(2, 1, "a1b2"),
                new Version(2, 1, "c3d4"),
                new Version(3, 0, "e5f6"));

        Set<Version> hash = new HashSet<>(versions);
        Set<Version> tree = new TreeSet<>(versions);

        System.out.println("added         = " + versions);
        System.out.println("HashSet size  = " + hash.size() + "  " + hash);
        System.out.println("TreeSet size  = " + tree.size() + "  " + tree);

        Version probe = new Version(2, 1, "zzzz");
        System.out.println("equals any?   = " + versions.stream().anyMatch(v -> v.equals(probe)));
        System.out.println("hash.contains = " + hash.contains(probe));
        System.out.println("tree.contains = " + tree.contains(probe));
    }
}

added         = [2.1+a1b2, 2.1+c3d4, 3.0+e5f6]
HashSet size  = 3  [2.1+a1b2, 3.0+e5f6, 2.1+c3d4]
TreeSet size  = 2  [2.1+a1b2, 3.0+e5f6]
equals any?   = false
hash.contains = false
tree.contains = true

The same three objects, added to two sets in the same program: one holds three, the other holds two. Nothing threw, nothing warned, and 2.1+c3d4 is simply gone from the TreeSet.

The last three lines are worse. probe is equal to nothing in the collection — the stream check says so, and HashSet agrees. TreeSet reports that it contains it, because 2.1+zzzz compares equal to 2.1+a1b2. A TreeSet will happily tell you it contains an element that is not in it by any definition of equality your class defines.

The disagreement runs the other way too. Give a class an equals that is broader than its compareTo and the same two objects that a HashSet merges stay separate in a TreeSet:

class Coord implements Comparable<Coord> {
    final int x, y;
    Coord(int x, int y) { this.x = x; this.y = y; }

    @Override public boolean equals(Object o) { return o instanceof Coord c && x == c.x; }   // x only
    @Override public int hashCode() { return Integer.hashCode(x); }
    @Override public int compareTo(Coord o) {                                                // x then y
        int c = Integer.compare(x, o.x);
        return c != 0 ? c : Integer.compare(y, o.y);
    }
    @Override public String toString() { return "(" + x + "," + y + ")"; }
}

a.equals(b)     = true
a.compareTo(b)  = -1
HashSet         = [(1,1)]  size 1
TreeSet         = [(1,1), (1,2)]  size 2

Two objects that report themselves equal, in a set that holds them both. The rule to take away is short: if a class implements Comparable and might ever meet a sorted collection, make compareTo return 0 for exactly the pairs equals returns true for. When you cannot, do not put it in a TreeSet.

A comparator makes "duplicate" mean whatever it says

The same rule applies to a Comparator passed to the constructor, and it is easier to trip over because the comparator is usually written for sorting, not for identity:

Set<String> ci = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
ci.addAll(List.of("Java", "java", "JAVA", "Kotlin"));

Set<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length));
byLength.addAll(List.of("aa", "bb", "ccc"));

input                    = [Java, java, JAVA, Kotlin]
TreeSet natural          = [JAVA, Java, Kotlin, java]
TreeSet CASE_INSENSITIVE = [Java, Kotlin]
ci.contains("jAvA")      = true
plain.contains("jAvA")   = false
TreeSet by length        = [aa, ccc]   size 2

The case-insensitive set is defensible: three spellings of one word collapsing to one entry is often the point, and it is why case-insensitive lookups get built this way. The length comparator is a disaster — "bb" vanished because it is the same length as "aa". A comparator used with a sorted set is not a sort order, it is an identity function, and any comparator that returns 0 for genuinely different values will silently delete data.

⚠️ Comparator.comparing(...) on a non-unique field is the single most common way to lose elements in a TreeSet. Chain a tie-breaker with thenComparing on something unique.

An element mutated after it was added

Both implementations place an element based on what it looked like at add time. Change it afterwards and it is in the wrong place — but the two failures look different.

class Tag implements Comparable<Tag> {
    String name;   // mutable on purpose
    Tag(String name) { this.name = name; }

    @Override public boolean equals(Object o) { return o instanceof Tag t && name.equals(t.name); }
    @Override public int hashCode() { return name.hashCode(); }
    @Override public int compareTo(Tag o) { return name.compareTo(o.name); }
    @Override public String toString() { return name; }
}

Add aaa to each set alongside some neighbours, then rename it to zzz while it is inside:

HashSet  = [zzz, ccc, bbb, ddd]
  size            = 4
  contains(same)  = false
  remove(same)    = false
  size after      = 4
TreeSet  = [zzz, bbb, ccc, ddd, eee, fff, ggg]
  size            = 7
  contains(same)  = false
  remove(same)    = false
  size after      = 7
  first()         = zzz
  iteration sees it = true

In the HashSet the element is filed under the old hashCode, so a lookup hashes "zzz", goes to a different bucket and finds nothing. contains says no, remove says no, size says four and toString prints it. The element is unreachable and undeletable, and only iteration can still see it.

In the TreeSet it is unreachable for the same reason and by a different mechanism: the search compares "zzz" against the root and walks right, while the node is sitting off to the left where "aaa" belonged. The tree is now structurally invalid — look at that first() result. It returns zzz, because first() does not compare anything, it just follows left pointers, and the leftmost node is the corrupted one. A TreeSet whose elements have been mutated does not merely lose an element; its ordering invariant is broken and subsequent inserts can land anywhere.

Mutable elements do not belong in either set. If a field participates in equals, hashCode or compareTo, make it final.

What a TreeSet refuses: non-Comparable elements and null

ClassCastException, and exactly when it fires

A TreeSet with no Comparator requires its elements to be Comparable, and the compiler does not enforce it — new TreeSet<Point>() compiles happily for a Point that implements nothing. The failure is at runtime:

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

Set<Point> s = new TreeSet<>();
System.out.println("add first  = " + s.add(new Point(1, 1)));

Exception in thread "main" java.lang.ClassCastException: class Point cannot be cast to class java.lang.Comparable (Point 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.TreeMap.addEntryToEmptyMap(TreeMap.java:811)
	at java.base/java.util.TreeMap.put(TreeMap.java:820)
	at java.base/java.util.TreeSet.add(TreeSet.java:259)
	at NoCompare.main(NoCompare.java:12)

Note where that came from. The println never ran, and the frame is addEntryToEmptyMap — on this JDK the first add throws, because inserting into an empty tree calls compare(key, key) purely as a type check. Older tutorials say the exception comes on the second add, on the grounds that the first insert has nothing to compare against; that was true of much older JDKs and it is not true here. Check the frame name before believing either claim.

There is still a case that fails on the second add, and it is a different bug. When the elements are individually Comparable but not comparable to each other, the first insert type-checks fine and the second one blows up inside your own compareTo:

add "a"  = true
size     = 1
now adding an Integer to a TreeSet that already holds a String
Exception in thread "main" java.lang.ClassCastException: class java.lang.String cannot be cast to class java.lang.Integer (java.lang.String and java.lang.Integer are in module java.base of loader 'bootstrap')
	at java.base/java.lang.Integer.compareTo(Integer.java:73)
	at java.base/java.util.TreeMap.put(TreeMap.java:849)
	at java.base/java.util.TreeSet.add(TreeSet.java:259)
	at MixedType.main(MixedType.java:9)

The stack frame is Integer.compareTo, not TreeMap.compare. A raw or Object-typed TreeSet is the usual way to get here.

null

HashSet and LinkedHashSet accept exactly one null; TreeSet accepts none.

HashSet add(null)   = true
HashSet add(null)#2 = false
HashSet             = [null]  size=1
HashSet contains    = true
LinkedHashSet       = [a, null, b]
TreeSet empty add(null) -> java.lang.NullPointerException: Cannot invoke "java.lang.Comparable.compareTo(Object)" because "k1" is null
TreeSet non-empty add(null) -> java.lang.NullPointerException
TreeSet contains(null) -> java.lang.NullPointerException
TreeSet w/ nullsFirst comparator = [null, a, b]

null is a legal element in a hash-based set — it hashes to bucket zero by special case — and a second null is rejected as a duplicate like anything else.

The TreeSet lines answer a question worth asking: does it matter whether the set is empty? The outcome does not — both throw — but the exception does, and the difference tells you which code path you hit:

The helpful message on the empty set is a helpful-NullPointerException produced from the bytecode; on a non-empty set the explicit null check fires first and you get nothing. contains(null) throws too, which makes TreeSet awkward in any code path that might legitimately hold a null.

The last line is the escape hatch: null rejection comes from natural ordering, not from TreeSet itself. Hand it Comparator.nullsFirst(Comparator.naturalOrder()) and null becomes an ordinary element.

EnumSet: the right Set for enum elements

When the element type is an enum, none of the three above is the right answer. EnumSet is an abstract class with no public constructor and a set of factories, and it stores membership as bits rather than as objects:

enum Perm { READ, WRITE, EXECUTE, DELETE }

EnumSet<Perm> e = EnumSet.noneOf(Perm.class);
e.add(Perm.DELETE); e.add(Perm.READ); e.add(Perm.EXECUTE);

EnumSet inserted DELETE,READ,EXECUTE -> [READ, EXECUTE, DELETE]
class          = java.util.RegularEnumSet
complementOf   = [WRITE]
range(R,E)     = [READ, WRITE, EXECUTE]
HashSet same   = [READ, DELETE, EXECUTE]
add(null)      -> java.lang.NullPointerException: Cannot invoke "Object.getClass()" because "e" is null
f retain e     = [READ]

Three things in that output are the reason to use it. Iteration is in declaration order regardless of insertion order, which is a real guarantee and not an accident — compare it against the HashSet line built from the same three constants. complementOf and range are operations that only make sense when the universe of possible elements is known in advance. And null is rejected outright, because there is no bit position for a constant with no ordinal.

Which implementation you get depends on how many constants the enum declares, and the boundary is exact:

63 constants -> java.util.RegularEnumSet
64 constants -> java.util.RegularEnumSet
65 constants -> java.util.JumboEnumSet

RegularEnumSet keeps the entire set in one long, one bit per constant, so 64 is the last size that fits; at 65 the factory switches to JumboEnumSet and an array of long. A Set of 64 enum constants therefore costs eight bytes of payload where a HashSet would cost a table plus 64 node objects.

Set algebra: union, intersection and difference

The three bulk methods on Collection are set algebra under other names, and all three mutate the receiver:

Set<String> a = new LinkedHashSet<>(List.of("red", "green", "blue", "cyan"));
Set<String> b = new LinkedHashSet<>(List.of("blue", "cyan", "magenta"));

Set<String> union = new LinkedHashSet<>(a);        union.addAll(b);
Set<String> intersection = new LinkedHashSet<>(a); intersection.retainAll(b);
Set<String> difference = new LinkedHashSet<>(a);   difference.removeAll(b);

A                    = [red, green, blue, cyan]
B                    = [blue, cyan, magenta]
A union B            = [red, green, blue, cyan, magenta]
A intersect B        = [blue, cyan]
A minus B            = [red, green]
symmetric difference = [red, green, magenta]
A unchanged          = [red, green, blue, cyan]
containsAll(subset)  = true

Copy first, as above. Every one of these writes into the set you call it on, and a removeAll on the wrong object is a data-loss bug that reads like a query.

Why removeAll can go quadratic

AbstractSet.removeAll picks between two completely different algorithms based on which collection is bigger. The bytecode says so plainly:

  public boolean removeAll(java.util.Collection<?>);
    Code:
       7: aload_0
       8: invokevirtual #15                 // Method size:()I
      11: aload_1
      12: invokeinterface #11,  1           // InterfaceMethod java/util/Collection.size:()I
      17: if_icmple     59
      ...
      48: invokevirtual #52                 // Method remove:(Ljava/lang/Object;)Z
      ...
      80: invokeinterface #56,  2           // InterfaceMethod java/util/Collection.contains:(Ljava/lang/Object;)Z

this.size() against c.size(), and then a branch. If the set is bigger, it iterates the argument and calls its own remove — a hash lookup each time. If the set is not bigger, it iterates itself and calls c.contains on every element. When c is a List, that is a linear scan per element.

Instrument the element class and the difference is not subtle. Each row is one removeAll call, counting equals() invocations:

set 1000, arg ArrayList 2000  (set <= arg)     set=1000  arg=2000  equals calls=500500
set 1000, arg HashSet   2000  (set <= arg)     set=1000  arg=2000  equals calls=1000
set 3000, arg ArrayList 2000  (set >  arg)     set=3000  arg=2000  equals calls=2000
set 2000, arg ArrayList 2000  (set == arg)     set=2000  arg=2000  equals calls=2001000
set 2001, arg ArrayList 2000  (set >  arg by 1) set=2001  arg=2000  equals calls=2000

Read the last two rows together. Same argument, same data, one extra element in the set — 2,001,000 equals calls versus 2,000. A thousandfold change in work from adding one element, because that element flipped size() > c.size() from false to true and switched the algorithm.

Row two is the fix: passing a HashSet instead of an ArrayList for the argument turns c.contains into a constant-time call and the count drops from 500,500 to 1,000 — one equals per element, which is the floor.

The rule is a one-liner: removeAll and retainAll call contains on their argument, so the argument should be a hash-based collection. set.removeAll(someList) is the shape to look for in a review.

Choosing an implementation

Default to HashSet. Move to LinkedHashSet when output order matters or must be reproducible, which is more often than people expect — deterministic logs and stable test fixtures both want it, and it is cheap. Move to TreeSet only when you need sorted iteration on every read, or the NavigableSet neighbour queries. Use EnumSet whenever the elements are enum constants.

FAQ

What is the difference between HashSet, LinkedHashSet and TreeSet in Java?

All three reject duplicates; they differ in ordering and cost. HashSet gives no ordering guarantee and O(1) average operations. LinkedHashSet adds a doubly-linked list through the entries to give insertion order, costing two extra references per element. TreeSet keeps elements sorted in a red-black tree with O(log n) operations, and is the only one that supports neighbour and range queries.

Is HashSet ordered?

No. The iteration order is unspecified and may change when the table resizes, when the JDK changes, or with a different element type. It often looks stable across runs of one program on one JDK, which is exactly what makes depending on it dangerous. Set.of deliberately varies its order between JVM runs to stop that habit forming.

Why did my TreeSet drop elements that are not equal?

Because a TreeSet decides duplicates with compareTo or a Comparator, and never calls equals. Any two elements whose comparison returns 0 are one element to a TreeSet, however different equals says they are. Most often the cause is a Comparator.comparing on a non-unique field; add a thenComparing tie-breaker on something unique.

Can a TreeSet contain null?

Not with natural ordering — add(null) throws NullPointerException, and so does contains(null). It works if you supply a null-tolerant comparator such as Comparator.nullsFirst(Comparator.naturalOrder()). HashSet and LinkedHashSet accept a single null element without any special setup.

Why does TreeSet throw ClassCastException?

Because the element type does not implement Comparable and no Comparator was supplied. On OpenJDK 21 that throws on the very first add, in TreeMap.addEntryToEmptyMap, which calls compare(key, key) as a type check. A different ClassCastException on the second add means the elements are Comparable but not to each other, such as a String and an Integer in the same set.

Which Set should I use for enum values?

EnumSet. It iterates in declaration order, stores membership as bits — one long up to 64 constants, an array of long from 65 — and offers complementOf, range, allOf and noneOf, which a general-purpose set cannot provide. It rejects null.

How do I do a union or an intersection of two sets in Java?

Copy one set and call the bulk method on the copy: addAll for union, retainAll for intersection, removeAll for difference. There is no symmetric-difference method; do addAll then removeAll of the intersection. Make the argument a HashSet rather than a List, because removeAll and retainAll call contains on it.

Is HashSet thread-safe?

No, and neither is LinkedHashSet or TreeSet. Wrap one in Collections.synchronizedSet(...), which gives a java.util.Collections$SynchronizedSet, or use ConcurrentHashMap.newKeySet(), which returns a ConcurrentHashMap$KeySetView and is the concurrent set the JDK actually intends you to use.

Conclusion

A Set guarantees one thing — no duplicates — and every implementation difference is a different answer to "what counts as a duplicate, and what order do I get". HashSet is a HashMap with one shared dummy value in every slot, which the bytecode of add shows in five instructions and which explains its whole cost profile. LinkedHashSet buys insertion order for two references per element. TreeSet is a red-black tree, and it is worth its O(log n) not for sorted iteration but for floor, ceiling, headSet and the rest of NavigableSet.

The one thing to carry away is the split in the equality rules. HashSet asks hashCode and equals; TreeSet asks compareTo and never calls equals at all — the instrumented count is zero, not small. A compareTo inconsistent with equals produces two different set sizes from the same three objects, silently. Add the same discipline about mutation: an element modified after insertion is unreachable in a HashSet and leaves a TreeSet structurally invalid.

The next article stays inside the collections framework and takes the maps: TreeMap, LinkedHashMap, the legacy Hashtable and ConcurrentHashMap — including how a TreeMap gives you the same navigation methods you just met on TreeSet, and why ConcurrentHashMap is not simply a synchronized HashMap.