Stage 5: Collections compared, lesson 2 of 8

HashSet vs TreeSet (and LinkedHashSet)

Intermediate3 min read@since 8Code runs on your Java 25
Explain it forThe essentials plus production detail and pitfalls.

All three store unique elements. They differ in order, speed and how they decide what "the same" means:

  • HashSet: backed by a HashMap. add, contains and remove are O(1) on average. No order. Uniqueness uses hashCode() and equals(). One null is allowed.
  • LinkedHashSet: a HashSet that also remembers insertion order. Nearly as fast; a little more memory.
  • TreeSet: backed by a TreeMap (a red-black tree). Operations are O(log n). Always sorted, by natural order or a Comparator, with navigation methods such as first, last, floor, ceiling, headSet and tailSet. Uniqueness uses compareTo() (or the comparator), not equals(). No null with natural ordering.

Choose HashSet for fast "have I seen this?" checks, LinkedHashSet to remove duplicates but keep order, and TreeSet when you need sorted output or range queries.

Side by side

HashSetTreeSet
Backed byHashMapTreeMap (red-black tree)
OrderNoneSorted (natural or Comparator)
add / contains / removeO(1) on averageO(log n)
Duplicates decided byhashCode() + equals()compareTo() or the Comparator
nullOne allowedNot with natural ordering (NullPointerException)
Extra methodsNonefirst, last, floor, ceiling, headSet, tailSet, descendingSet
Elements mustHave good equals()/hashCode()Be Comparable, or you supply a Comparator
Use it forFast membership checksSorted output, ranges, "next higher"

Example

Java
List<String> tags = List.of("java", "spring", "sql", "java", "docker", "kafka");

new HashSet<>(tags);         // [spring, java, kafka, sql, docker]   order comes from the hash codes
new LinkedHashSet<>(tags);   // [java, spring, sql, docker, kafka]   insertion order, duplicates removed
TreeSet<String> sorted = new TreeSet<>(tags);   // [docker, java, kafka, spring, sql]

sorted.first();              // docker
sorted.ceiling("k");         // kafka   the smallest element >= "k"
sorted.headSet("spring");    // [docker, java, kafka]
The TreeSet surprise: the comparator decides what's a duplicate
Set<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length));
byLength.addAll(List.of("cat", "dog", "lion"));
System.out.println(byLength);    // [cat, lion]   "dog" was dropped: same length as "cat" = "equal"

Common mistake

Using a TreeSet comparator that compares only one field. Elements with the same value in that field are treated as duplicates and silently dropped.

Under the hood

A TreeSet with a comparator that's inconsistent with equals() breaks the Set contract in surprising ways, as above. Break ties with thenComparing (for example by length, then alphabetically). Since Java 21, TreeSet and LinkedHashSet also implement SequencedSet (getFirst(), getLast(), reversed()).

Check yourself

Which set keeps elements in insertion order?

How this connects

Where this leads

You've reached the end of this thread. Try a learning path for what's next.

Part of Java 8 and collections, practically.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.