PHASE 9Intermediate ~29 min· topic 5 of 13

Topic 9.5

HashSet, LinkedHashSet and TreeSet

In one line

A Set holds each element at most once. HashSet is a HashMap with only keys (O(1), no order), LinkedHashSet adds insertion order, and TreeSet keeps elements sorted in a red-black tree (O(log n)) with navigation methods like floor and ceiling.

Think of it like this

A guest list at the door of a party. Each name is written once; if someone tries to come in twice, the bouncer says "already here". Some bouncers just keep a messy pile of name cards (fast, no order), some keep them in the order people arrived, and some keep them in alphabetical order so they can answer "who's the first guest after M?". Those are HashSet, LinkedHashSet and TreeSet.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Set: A collection that never holds two equal elements.
Duplicate: An element equal to one already in the set. For hash sets that means equals; for tree sets it means comparing as 0.
Insertion order: The order in which elements were first added.
Sorted order: The order given by the elements' compareTo or by a Comparator.
Binary search tree: A tree where every node's left side holds smaller values and its right side larger ones, so searching halves the candidates at each step.
Balanced tree: A tree kept close to its minimum height, so no path from top to bottom is much longer than log n.
floor and ceiling: The nearest element at or below a value (floor) and at or above it (ceiling).
Union, intersection, difference: Everything in either set; only what's in both; what's in the first but not the second.

Step by step

01add returns whether the set changed

set.add("tea") returns true the first time and false afterwards. That boolean is the cheapest way to detect duplicates: if (!seen.add(x)) { /* x is a repeat */ } does one lookup instead of a contains followed by an add.

Main.javawhole filejava

Set<String> seen = new HashSet<>();
for (String email : signups) {
    if (!seen.add(email)) {
        System.out.println("duplicate sign-up: " + email);
    }
}

02HashSet: a HashMap with a dummy value

Open HashSet.java and you'll find private transient HashMap<E,Object> map; and private static final Object PRESENT = new Object();. Every method forwards to the map: add is map.put(e, PRESENT) == null, contains is map.containsKey(o), remove is map.remove(o) == PRESENT.

So a HashSet costs as much memory per element as a HashMap entry (a 32-byte node plus a table slot), and it has the same rules: hash-based, unordered, O(1) expected, element classes need equals and hashCode (Topic 4.8), and elements must not change while they're in the set.

HashSet.java (from the JDK, trimmed)whole filejava

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();

    public HashSet() { map = new HashMap<>(); }

    public boolean add(E e)          { return map.put(e, PRESENT) == null; }
    public boolean contains(Object o) { return map.containsKey(o); }
    public boolean remove(Object o)   { return map.remove(o) == PRESENT; }
}

03LinkedHashSet: the same plus a linked list

LinkedHashSet's constructors call a package-private HashSet constructor that creates a LinkedHashMap instead of a HashMap. Each entry gets before and after links, and the map keeps head and tail, so iteration follows the list rather than the buckets.

Iteration is therefore O(size) and predictable, while lookups stay O(1). Since Java 21 it's also a SequencedSet with getFirst, getLast, addFirst and reversed() (Topic 9.12).

04TreeSet: a red-black tree

A binary search tree puts smaller elements to the left and larger to the right, so contains follows one path from the root. If you insert 1, 2, 3, ... into a plain BST it becomes a straight line (O(n) per search). A red-black tree prevents that: every node is coloured red or black, and the rules (no red node has a red child; every path from a node down to its empty leaves has the same number of black nodes) force the longest path to be at most twice the shortest. Insertions and removals restore the rules with a few recolourings and rotations, O(log n).

TreeSet stores elements as keys of a TreeMap (again with a dummy value). A million elements means a tree only about 20 to 40 levels deep.

TreeSet: a red-black treediagram

Rendering diagram…

05Navigation: questions a HashSet can't answer

Because a TreeSet is sorted, it can answer "nearest" questions in O(log n): floor(25) is the largest element ≤ 25, ceiling(25) the smallest ≥ 25, higher and lower are the strict versions, and each returns null if no such element exists.

Range views (headSet(x) is everything < x, tailSet(x) everything ≥ x, subSet(a, b) everything in [a, b)) are live views backed by the original set, not copies: adding to the set inside the range shows up in the view.

06Comparison replaces equals in a TreeSet

A TreeSet never calls equals. If compare(a, b) == 0, a and b are the same element as far as the tree is concerned. With String.CASE_INSENSITIVE_ORDER, adding "tea" after "Tea" returns false.

The Set contract is defined in terms of equals, so a comparator that disagrees with equals makes the set behave strangely when mixed with other sets. The JDK calls this being "inconsistent with equals". The famous case: new BigDecimal("1.0") and new BigDecimal("1.00") are not equals (different scale) but compareTo says 0, so a HashSet holds both and a TreeSet holds one.

Try it yourself

1
Strings in a HashSet
In the first example, change the rolls to the strings "six", "two", "six", "three", "one". Predict which set's printed order you can be sure of before running (the LinkedHashSet and the TreeSet). The HashSet order follows the hash codes.
2
Find the nearest slot
In the navigation example, print slots.floor(800) and slots.ceiling(1700). Predict them first. Both are null: always handle that case before unboxing.
3
Make a case-insensitive HashSet
A HashSet can't take a comparator. How would you get case-insensitive uniqueness while keeping O(1) lookups? Try storing s.toLowerCase() and predict how "Tea" would print afterwards.

Code & diagrams

Three sets, same input New tab

Integer's hashCode is its value, so small numbers land in buckets 1, 2, 3, 5, 6 in that order. With strings the HashSet order would look random.

Expected output

repeat roll: 6
repeat roll: 2
HashSet:       [1, 2, 3, 5, 6]  (small Integers happen to look sorted)
LinkedHashSet: [6, 2, 3, 1, 5]
TreeSet:       [1, 2, 3, 5, 6]
contains 4? false, size 5

Set algebra: union, intersection, difference New tab

Set.of has an unspecified iteration order, so we copy into a TreeSet before printing.

Expected output

either: [chess, coding, cooking, cricket, music]
both:   [coding, cricket]
only Asha: [chess, music]
Asha has all of both? true
originals unchanged: [chess, coding, cricket, music] [coding, cooking, cricket]

TreeSet navigation New tab

Expected output

first 900, last 1600
floor(1100)   = 1030
ceiling(1100) = 1200
ceiling(1200) = 1200, higher(1200) = 1430
lower(900)    = null
before noon:  [900, 1030]
10:00-15:00:  [1030, 1200, 1430]
descending:   [1600, 1430, 1200, 1030, 900]
afternoon view now: [1200, 1300, 1430, 1600]
pollFirst: 900, left [1030, 1200, 1300, 1430, 1600]

When compareTo and equals disagree New tab

HashSet asks equals (scale matters); TreeSet asks compareTo (only the value matters).

Expected output

add Tea: true
add tea: false
drinks: [Tea], contains TEA? true
equals: false, compareTo: 0
HashSet size 2, TreeSet size 1 [1.0]

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Put non-comparable elements in a TreeSet

Declare record Point(int x, int y) { } and run Set<Point> pts = new TreeSet<>(); pts.add(new Point(1, 2));.

terminal

$ java Main

── what you'll see ──

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.TreeMap.put(TreeMap.java:569)

at java.base/java.util.TreeSet.add(TreeSet.java:259)

at Main.main(Main.java:6)

Break #2

Add null to a TreeSet

Call names.add(null) on a TreeSet<String> that already holds "asha".

terminal

$ java Main

── what you'll see ──

Exception in thread "main" java.lang.NullPointerException

at java.base/java.util.Objects.requireNonNull(Objects.java:233)

at java.base/java.util.TreeMap.put(TreeMap.java:844)

at java.base/java.util.TreeMap.put(TreeMap.java:569)

at java.base/java.util.TreeSet.add(TreeSet.java:259)

at Main.main(Main.java:7)

Myth vs fact

Myth

A HashSet is a different data structure from a HashMap.

Fact

It's a wrapper around a HashMap whose values are all one dummy object. Same buckets, same rules, same memory per entry.

Myth

TreeSet uses equals to find duplicates.

Fact

It uses only compareTo or the comparator. A comparison of 0 means "duplicate", whatever equals says.

Myth

LinkedHashSet is slow because it's linked.

Fact

Lookups are still O(1) hash lookups; the links only add two references per element and make iteration O(size) and ordered.

Myth

headSet and subSet return copies.

Fact

They're live views of the original set. Changes show through in both directions, and adding an element outside the view's range throws IllegalArgumentException.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
HashSet(Collection c) sizes its map from c.size() / 0.75 (at least 16), so copying a collection into a set never resizes. Java 19 added HashSet.newHashSet(int) and LinkedHashSet.newLinkedHashSet(int) for the same arithmetic on empty sets.
▸
TreeMap itself is a hand-written red-black tree (from the CLR algorithms textbook, as its Javadoc notes). Each entry holds key, value, left, right, parent and a colour flag: about 40 bytes, more than a HashMap node.
▸
EnumSet stores membership as bits in a long (RegularEnumSet, up to 64 constants) or a long[] (JumboEnumSet). contains is a bit test and addAll a bitwise OR, so for enum elements it beats every general-purpose set.
▸
Set.of(...) (Java 9) returns an immutable set whose iteration order is deliberately randomised per JVM run (a salt is mixed into the probe position), precisely so nobody comes to depend on an order (Topic 9.11).

Remember this

1
A Set is a Collection that rejects duplicates. add(e) returns true if the element was added and false if an equal element was already there; the set is unchanged in that case. "Equal" means equals for HashSet and LinkedHashSet, and compareTo (or the comparator) returning 0 for TreeSet.
2
**HashSet is a HashMap in disguise.** Its only field is a HashMap<E, Object>; add(e) calls map.put(e, PRESENT), where PRESENT is one shared dummy object, and returns whether the old value was null. So everything from Topic 9.4 applies: O(1) expected add, remove and contains, bucket iteration order, one null allowed, and the element class must have consistent equals and hashCode.
3
**LinkedHashSet** extends HashSet but is backed by a LinkedHashMap, which threads a doubly linked list through the entries. Same O(1) operations, plus iteration in insertion order (re-adding an existing element doesn't move it). It costs two extra references per element. It's the go-to for "remove duplicates but keep the original order".
4
**TreeSet** is backed by a TreeMap: a red-black tree, a binary search tree that keeps itself balanced so its height stays at most about 2·log₂(n). add, remove and contains are O(log n). It iterates in sorted order and implements NavigableSet: first(), last(), floor(x) (largest ≤ x), ceiling(x) (smallest ≥ x), lower, higher, headSet, tailSet, subSet, pollFirst and descendingSet().
5
TreeSet needs an ordering: either the elements implement Comparable (Topic 9.10) or you pass a Comparator. Without one, the first add throws ClassCastException. It rejects null (there's nothing to compare it with). And it uses the comparison instead of equals: if the comparator says two elements are 0 apart, the second is a duplicate even if equals disagrees, so a case-insensitive TreeSet keeps only one of "Tea" and "tea".
6
Set algebra is built in: a.addAll(b) is the union, a.retainAll(b) the intersection, a.removeAll(b) the difference, and a.containsAll(b) tests for a subset. Each modifies a, so copy first if you need the original. For enum elements, EnumSet is a bit vector: tiny and faster than any of the three.

Explain it without notes

How is HashSet implemented, and what does that imply for its element classes?

Compare HashSet, LinkedHashSet and TreeSet on order, complexity, nulls and requirements on elements.

What does it mean for a comparator to be inconsistent with equals, and why does it matter?

What is a red-black tree and why does TreeSet use one instead of a plain binary search tree?

Practice

Remove duplicates from ["b", "a", "b", "c", "a"] keeping first-seen order, then print the distinct elements in sorted order too.

Given a sorted set of exam cut-off marks {40, 55, 70, 85} and grades D, C, B, A for each cut-off, print the grade for marks 39, 40, 69 and 99 using floor (below 40 is F). Use a TreeMap for the mapping.

Find the first repeated character in "programming" using a HashSet and the boolean returned by add.

Trade-offs

↔
HashSet is the fastest for membership tests but has no order. LinkedHashSet costs a little more memory for a predictable order. TreeSet costs O(log n) per operation but gives sorted order and nearest-element queries.
↔
A comparator lets a TreeSet define uniqueness however you like (case-insensitive, by ID), but if it disagrees with equals the set stops behaving like other sets. Document it, or normalise the data instead.
↔
Sets of boxed numbers are memory-hungry: a HashSet<Integer> with a million entries uses tens of megabytes. A sorted int[] with binary search, or a BitSet, can be far smaller.

Done when you can

Done when you can explain that HashSet is a HashMap with a dummy value.
Done when you can choose between hash, linked and tree sets for a given need.
Done when you can use floor, ceiling, headSet, subSet and descendingSet.
Done when you can do union, intersection and difference without destroying the inputs.
Done when you can explain why TreeSet ignores equals and what goes wrong when the comparator disagrees with it.

Command Palette

Words you'll meet

Step by step

01add returns whether the set changed

02HashSet: a HashMap with a dummy value

03LinkedHashSet: the same plus a linked list

04TreeSet: a red-black tree

05Navigation: questions a HashSet can't answer

06Comparison replaces equals in a TreeSet

Try it yourself

Strings in a HashSet

Find the nearest slot

Make a case-insensitive HashSet

Code & diagrams

Break it on purpose

Put non-comparable elements in a TreeSet

Add null to a TreeSet

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can