HashSet, LinkedHashSet and TreeSet

Three ways to guarantee uniqueness, differing only in ordering, cost and null handling.

Intermediate10 min read

Read these first

Why this matters

A Set is the clearest way to express "membership matters, duplicates do not", and using a List with contains instead is a common and avoidable O(n) mistake.
Which set you pick determines whether iteration order is arbitrary, insertion-based or sorted, and that silently affects test reliability.
Uniqueness depends entirely on equals and hashCode, so a broken contract shows up here first.

Three implementations

HashSetNo order · O(1) · one null

LinkedHashSetInsertion order · O(1) · one null

TreeSetSorted · O(log n) · no null

All three reject duplicates. They differ only in the order you get back when iterating and in what that ordering costs.

Aspect	Implementation	Properties
HashSet	No order guarantee	O(1) add, remove, contains
LinkedHashSet	Insertion order preserved	O(1), slightly more memory for the links
TreeSet	Sorted order	O(log n), plus navigation and range queries

HashSet
ImplementationNo order guarantee
PropertiesO(1) add, remove, contains
LinkedHashSet
ImplementationInsertion order preserved
PropertiesO(1), slightly more memory for the links
TreeSet
ImplementationSorted order
PropertiesO(log n), plus navigation and range queries

Each wraps a map internally: HashSet over HashMap, LinkedHashSet over LinkedHashMap, TreeSet over TreeMap.

Java

List<String> input = List.of("carl", "ana", "bob", "ana");

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

System.out.println(hash);     // [bob, ana, carl]  — arbitrary, may differ between runs
System.out.println(linked);   // [carl, ana, bob]  — first-seen order
System.out.println(tree);     // [ana, bob, carl]  — sorted

Each dropped the duplicate "ana". Only the ordering differs.

Uniqueness depends on your contract

A HashSet decides whether an element is already present by hashing it and then comparing with equals. A broken contract breaks the set.

Java

class Tag {
    final String name;
    Tag(String name) { this.name = name; }
    // equals and hashCode deliberately not overridden
}

Set<Tag> tags = new HashSet<>();
tags.add(new Tag("java"));
tags.add(new Tag("java"));
System.out.println(tags.size());        // 2 — identity comparison, so both are "unique"

Java

record Tag(String name) { }              // equals and hashCode generated from the component

Set<Tag> tags = new HashSet<>();
tags.add(new Tag("java"));
tags.add(new Tag("java"));
System.out.println(tags.size());        // 1 — as expected

TreeSet uses compareTo or a supplied Comparator instead, so it has the same dependency on a different method. Two elements comparing as 0 are considered duplicates even if equals disagrees.

TreeSet navigation

Sorted order unlocks operations the other two cannot offer, defined by the NavigableSet interface.

Java

NavigableSet<Integer> scores = new TreeSet<>(List.of(10, 20, 30, 40, 50));

scores.first();                  // 10
scores.last();                   // 50

scores.floor(35);                // 30 — greatest element ≤ 35
scores.ceiling(35);              // 40 — least element ≥ 35
scores.lower(30);                // 20 — strictly less than
scores.higher(30);               // 40 — strictly greater than

scores.headSet(30);              // [10, 20]       — exclusive by default
scores.tailSet(30);              // [30, 40, 50]   — inclusive by default
scores.subSet(20, 45);           // [20, 30, 40]

scores.descendingSet();          // [50, 40, 30, 20, 10] — a view, not a copy

scores.pollFirst();              // removes and returns 10
scores.pollLast();               // removes and returns 50

These are the reason to choose TreeSet despite its O(log n) cost. "The nearest value at or below this" is not expressible with a hash set at all.

Java

// A custom ordering, longest first then alphabetical
Set<String> byLength = new TreeSet<>(
        Comparator.comparingInt(String::length).reversed()
                  .thenComparing(Comparator.naturalOrder()));

byLength.addAll(List.of("java", "go", "kotlin", "rust"));
System.out.println(byLength);    // [kotlin, java, rust, go]

Set algebra

The bulk operations give you union, intersection and difference directly.

Java

Set<String> backend = new HashSet<>(Set.of("java", "go", "sql"));
Set<String> frontend = new HashSet<>(Set.of("js", "css", "sql"));

Set<String> union = new HashSet<>(backend);
union.addAll(frontend);                       // [java, go, sql, js, css]

Set<String> intersection = new HashSet<>(backend);
intersection.retainAll(frontend);             // [sql]

Set<String> difference = new HashSet<>(backend);
difference.removeAll(frontend);               // [java, go]

boolean subset = backend.containsAll(Set.of("java", "sql"));   // true

Each of these mutates the receiver, which is why the copy comes first. Forgetting the copy destroys the original set — an easy mistake in a method that was only supposed to compute something.

EnumSet for enum keys

When the elements are enum constants, there is a specialised implementation that is dramatically more efficient.

Java

enum Day { MON, TUE, WED, THU, FRI, SAT, SUN }

Set<Day> weekend = EnumSet.of(Day.SAT, Day.SUN);
Set<Day> weekdays = EnumSet.complementOf(EnumSet.copyOf(weekend));
Set<Day> midweek = EnumSet.range(Day.TUE, Day.THU);

System.out.println(weekdays);     // [MON, TUE, WED, THU, FRI] — declaration order

EnumSet represents membership as bits in a single long when the enum has 64 or fewer constants. Every operation becomes a bitwise instruction, and the whole set occupies a handful of bytes. It iterates in declaration order, which is usually the order you want.

Choosing

HashSet — the default. Fastest, least memory, no ordering promise.
LinkedHashSet — when iteration order must match insertion order, including in tests.
TreeSet — when you need sorted iteration or navigation. Note that it rejects null.
EnumSet — always, for enum elements.
CopyOnWriteArraySet — read-heavy concurrent use. It is backed by an array, so contains is O(n).
ConcurrentHashMap.newKeySet() — the concurrent set to reach for when writes are frequent.

Common misreadings

"HashSet keeps insertion order." It does not. The order you observe is an accident of hashing.
"A Set cannot contain null." HashSet and LinkedHashSet accept one. TreeSet rejects it, because comparing requires a non-null value.
"TreeSet uses equals." It uses compareTo or a Comparator. Elements comparing as 0 are duplicates regardless of equals.
"retainAll returns the intersection." It modifies the receiver and returns a boolean. Copy first.
"Set has get(index)." It has no positional access. Iterate, or use a List if position matters.
"HashSet adds no memory over a list." It is backed by a HashMap, so each element carries an entry object.

Quick recall

Everything you need if you only revisit this box.

All three sets guarantee uniqueness; they differ in ordering and cost.
HashSet O(1) and unordered, LinkedHashSet O(1) and insertion-ordered, TreeSet O(log n) and sorted.
Each wraps the matching map internally.
Uniqueness relies on equals/hashCode — or on compareTo/Comparator for TreeSet, where comparing to 0 means duplicate.
Never assert on HashSet iteration order; use LinkedHashSet or sort.
TreeSet adds floor, ceiling, headSet, tailSet, subSet, descendingSet, pollFirst/Last.
addAll, retainAll and removeAll give union, intersection and difference — but they mutate the receiver, so copy first.
Use EnumSet for enum elements: bitwise operations, tiny footprint, declaration order.

Test yourself

Answer these before moving on — recall is what makes it stick.