What is the difference between HashSet and TreeSet?
HashSet and TreeSet are both implementations of the Set interface in Java, but they differ fundamentally in their underlying data structures, performance characteristics, and ordering guarantees.
HashSet is backed by a HashMap internally. When you add an element, it computes the hash code, determines the bucket, and stores the element as a key in the underlying map. This gives HashSet O(1) average-case time complexity for add, remove, and contains operations. However, HashSet provides no ordering guarantees — iterating over a HashSet may return elements in any order. HashSet allows one null element and requires that elements properly implement hashCode() and equals().
TreeSet is backed by a TreeMap, which uses a red-black tree — a self-balancing binary search tree. This gives TreeSet O(log n) time complexity for add, remove, and contains operations. The key advantage is that TreeSet maintains elements in sorted order, either by natural ordering (Comparable) or by a custom Comparator. TreeSet does not allow null elements because it needs to compare every element.
Because TreeSet implements NavigableSet, it exposes powerful methods: first(), last(), headSet(), tailSet(), subSet(), ceiling(), floor(), higher(), and lower(). These allow efficient range queries that would require sorting the entire collection with a HashSet.
When choosing between them, use HashSet when you need fast lookups and do not care about ordering. Use TreeSet when you need sorted order or range queries. One subtle point: TreeSet's ordering must be consistent with equals. If a Comparator considers two distinct objects as equal (returns 0), TreeSet will reject the second one, even if equals() returns false.
| Aspect | HashSet | TreeSet |
|---|---|---|
| Underlying structure | HashMap (hash table) | TreeMap (red-black tree) |
| Time complexity | O(1) average | O(log n) guaranteed |
| Ordering | No ordering guarantee | Sorted (natural or Comparator) |
| Null elements | Allows one null | Does not allow null |
| Interface | Set | Set, SortedSet, NavigableSet |
| Range queries | Not supported | headSet, tailSet, subSet, ceiling, floor |
| Key requirement | hashCode() and equals() | Comparable or Comparator |
Identifies that HashSet is O(1) and unordered while TreeSet is O(log n) and sorted. Mentions underlying data structures. May not discuss NavigableSet methods.
Explains both data structures, contrasts time complexities, covers ordering guarantees, mentions NavigableSet methods like ceiling/floor/subSet, discusses null handling, and provides practical guidance on when to use each.
Reading the answer is step one. Explaining it unprompted — under interview pressure — is what actually matters. Get AI-graded feedback on your answer with follow-up probes on your weak points.
Get Graded — Free Assessment