ByteScrollGet the app
☰ Topics
set-implementations3 / 200‹›
JAVA / COLLECTIONS2 minute read

HashSet vs TreeSet vs LinkedHashSet

Medium

HashSet: O(1) average, no order, uses hashCode/equals. LinkedHashSet: same speed plus insertion order. TreeSet: O(log n), kept sorted by compareTo or a Comparator, and that comparison (not equals) decides what counts as a duplicate.

How it works

  1. Each set wraps a map. The elements are the map's keys and a shared dummy object is the value.
    • HashSet → HashMap
    • LinkedHashSet → LinkedHashMap
    • TreeSet → TreeMap (a red-black tree)
  2. HashSet finds a bucket from hashCode() and checks equals(). add, remove, contains are O(1) on average. Iteration order is unspecified and can change after a resize.
  3. LinkedHashSet adds a doubly linked list through the entries, so iteration follows insertion order. Re-adding an existing element doesn't move it.
  4. TreeSet keeps elements sorted. Operations are O(log n). Two elements are duplicates when compare(a, b) == 0, whatever equals says.
  5. Extra API. TreeSet is a NavigableSet: floor, ceiling, headSet, tailSet, descendingSet. From Java 21, LinkedHashSet and TreeSet are both SequencedSets with getFirst(), getLast() and reversed().
TreeSetLinkedHashSetHashSethash → bucketequals() inbuckethash → bucketplus linkedlist ininsertionordercompare() fromrootwalk left /right, O(logn)
TreeSetLinkedHashSetHashSethash → bucketequals() inbuckethash → bucketplus linkedlist ininsertionordercompare() fromrootwalk left /right, O(logn)

Example

Example.javaJava
List<String> names = List.of("mira", "Zed", "ann", "mira", "Bo");

new HashSet<>(names);       // e.g. [ann, Bo, mira, Zed] (order not guaranteed)
new LinkedHashSet<>(names); // [mira, Zed, ann, Bo]
new TreeSet<>(names);       // [Bo, Zed, ann, mira] (uppercase sorts first)

// Comparator decides duplicates in a TreeSet
Set<String> tags = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
tags.addAll(List.of("Java", "java", "JAVA"));
tags.size(); // 1

// NavigableSet queries
TreeSet<Integer> slots = new TreeSet<>(List.of(9, 11, 14, 16));
slots.ceiling(12);  // 14: next free slot at or after 12
slots.headSet(14);  // [9, 11]

Edge cases

  • HashSet and LinkedHashSet allow one null. TreeSet with natural ordering throws NullPointerException on null.
  • A TreeSet of a class that isn't Comparable and has no Comparator throws ClassCastException on the first add.
  • Mutating a field used by hashCode() or compareTo() after insertion makes the element unfindable.
  • TreeSet.addFirst() throws UnsupportedOperationException: sorted order is fixed, so you can't place an element.

Common mistakes

  • Picking TreeSet "to be safe" when you never need ordering. You pay O(log n) and a comparison per step.
  • Expecting HashSet to keep insertion order because it happened to in a small test.
  • Using a comparator that is inconsistent with equals and losing elements without noticing.

Likely follow-up

"How would you get a thread-safe sorted set?" Use ConcurrentSkipListSet. It's sorted, lock-free for reads, and its iterators are weakly consistent. Collections.synchronizedSortedSet works too but locks the whole set.

Get every deep dive in the app

Coming soon to the App StoreComing soon to Google Play