Java Collections
HashSet vs TreeSet
HashSet is usually used when you only need fast uniqueness. TreeSet is used when you need uniqueness plus sorted order.
The Short Answer
Both HashSet and TreeSet store unique elements.
TreeSet = uniqueness + sorted order
The tradeoff is that TreeSet must do extra work to keep elements sorted.
Mental Model
HashSet
Stored according to hash buckets.
No ordering guarantee.
TreeSet
Always maintained in sorted order.
Think of HashSet as caring only about uniqueness.
Think of TreeSet as caring about both uniqueness and ordering.
Implementation Under The Hood
HashSet
Internally backed by a HashMap.
TreeSet
Internally backed by a TreeMap (Red-Black Tree).
TreeSet gets its ordering from a balanced tree.
Time Complexity
| Operation | HashSet | TreeSet |
|---|---|---|
| add() | O(1) average | O(log n) |
| contains() | O(1) average | O(log n) |
| remove() | O(1) average | O(log n) |
| Iteration Order | Not guaranteed | Sorted |
HashSet Example
Set<String> fruits = new HashSet<>();
fruits.add("banana");
fruits.add("apple");
fruits.add("orange");
System.out.println(fruits);Possible output:
[banana, orange, apple]The order is not guaranteed.
TreeSet Example
Set<String> fruits = new TreeSet<>();
fruits.add("banana");
fruits.add("apple");
fruits.add("orange");
System.out.println(fruits);Output:
[apple, banana, orange]TreeSet automatically sorts elements.
Duplicate Handling
Both collections enforce uniqueness.
Set<Integer> set = new HashSet<>();
set.add(10);
set.add(10);
set.add(10);
System.out.println(set);[10]TreeSet behaves the same way.
TreeSet With Comparator
Just like PriorityQueue, TreeSet can use a custom Comparator.
TreeSet<String> set =
new TreeSet<>(Comparator.reverseOrder());
set.add("banana");
set.add("apple");
set.add("orange");
System.out.println(set);[orange, banana, apple]The comparator defines the ordering.
When Would I Actually Use TreeSet?
- Leaderboard rankings
- Sorted user names
- Sorted timestamps
- Always retrieving smallest or largest values
- Maintaining sorted unique values
If you don't need sorted order, HashSet is usually the better choice.
HashSet vs TreeSet Decision
Use HashSet When
You only need uniqueness and want the fastest lookups.
Use TreeSet When
You need uniqueness plus automatic sorting.
HashSet vs LinkedHashSet vs TreeSet
Interviewers often ask about all three collections together because they represent different tradeoffs between performance and ordering.
| Collection | Ordering | Contains/Add/Remove |
|---|---|---|
| HashSet | No guaranteed order | O(1) average |
| LinkedHashSet | Insertion order | O(1) average |
| TreeSet | Sorted order | O(log n) |
HashSet
Output order is not guaranteed.
LinkedHashSet
Preserves insertion order.
TreeSet
Always sorted.
LinkedHashSet cares about uniqueness and insertion order.
TreeSet cares about uniqueness and sorted order.
If you do not need ordering, HashSet is usually the best choice. If you need insertion order, use LinkedHashSet. If you need sorted order, use TreeSet.
Common Interview Follow-Ups
Why is TreeSet slower?
Because elements are stored in a balanced tree and every insertion, removal, or lookup may require traversing the tree.
Why is HashSet faster?
HashSet uses hashing to locate elements directly in buckets, giving O(1) average-time operations.
Can TreeSet use a Comparator?
Yes. TreeSet can sort using either natural ordering or a supplied Comparator.
Can HashSet guarantee iteration order?
No. If you need insertion order, use LinkedHashSet. If you need sorted order, use TreeSet.
What data structure backs TreeSet?
A TreeMap, which is implemented as a Red-Black Tree.