Java HashSet vs TreeSet: Choosing the Right Set
Compare Java's HashSet and TreeSet by ordering, performance, null handling, and use cases to choose the right Set implementation.

Choosing between HashSet and TreeSet starts with understanding what each implementation guarantees and what those guarantees cost. When you need to store unique elements in Java, both are common Set implementations, but they make different trade-offs. HashSet offers constant-time average lookup with no ordering guarantee, while TreeSet maintains elements in sorted order at the cost of logarithmic operations. This article compares their behavior and gives you criteria for making the decision.
What Each Set Guarantees
HashSet is backed by a hash table. It uses the hashCode() and equals() methods of its elements to store and retrieve them. The iteration order is not guaranteed and can change when the set is resized. TreeSet, on the other hand, is backed by a red-black tree. It stores elements in their natural order, or according to a Comparator you supply at construction time. This means iteration always produces elements in sorted order.
The Set interface itself only promises uniqueness. Neither implementation allows duplicate elements. But the way they enforce uniqueness differs: HashSet relies on hash codes and equality checks, while TreeSet relies on the comparator or natural ordering to determine both ordering and equality. Two elements are considered equal in a TreeSet if the comparator returns zero, even if their equals() method would say they are different.
Ordering Behavior and Its Cost
The most visible difference is ordering. If you add the strings banana, apple, and cherry to a HashSet, you might get them back in any order. A TreeSet will always iterate as apple, banana, cherry if using natural string ordering.
This ordering has a cost. Maintaining a balanced tree requires comparisons on every insertion and lookup. That is an O(log n) operation. HashSet insertion and lookup are O(1) on average, assuming a good hash function and adequate capacity. For small collections the difference is negligible, but as the set grows, the logarithmic behavior of TreeSet becomes noticeable.
Consider a scenario where you need to frequently retrieve the smallest or largest element. TreeSet provides first() and last() in O(log n) time. A HashSet has no such method; you would have to iterate the entire set, which is O(n). So if your algorithm depends on ordered access, TreeSet is the natural fit.
Performance Characteristics
It's important to understand the underlying mechanics rather than rely on vague claims about speed. HashSet uses a hash table with an array of buckets. The average case is constant time, but the worst case can degrade to O(n) if many elements collide. In practice, a well-distributed hash function keeps collisions rare. TreeSet always operates in O(log n) because it is a balanced binary search tree. This makes TreeSet predictable but slower for large datasets.
Memory usage also differs. A HashSet allocates an array of buckets, which may be larger than the number of elements to reduce collisions. A TreeSet allocates a node for each element, with pointers to left and right children. For large sets, the tree's overhead per node might be higher than the hash table's overhead, but the hash table may waste space if the load factor is low. Neither is universally more memory-efficient; it depends on the size and the hash function.
If you need to iterate in sorted order repeatedly, TreeSet avoids the cost of sorting a separate list. But if you only need uniqueness and do not care about order, HashSet gives you better average performance.
Null and Duplicate Handling
HashSet and TreeSet have different null-handling rules. HashSet allows a single null element because HashMap maps null to a fixed hash bucket. TreeSet does not allow null by default. When you insert null, the set needs to compare it, and the default natural ordering throws NullPointerException. You can work around this by providing a custom Comparator that handles null, but that is an extra design decision.
Duplicates are rejected by both, but the definition of duplicate differs. In HashSet, two elements are duplicates if equals() returns true and their hash codes are equal. In TreeSet, two elements are duplicates if the comparator returns 0. This can lead to surprising behavior if you have objects that are not equal according to equals() but compare as equal according to the comparator. For example, a TreeSet with a case-insensitive comparator would treat Apple and apple as the same element, even though equals() would say they are different.
When to Use HashSet
Use HashSet when:
- You need to test membership frequently and order is irrelevant.
- You want the best average performance for add, remove, and contains.
- You need to allow
nullwithout extra handling. - You do not need to iterate in a specific order.
Typical use cases include deduplicating a list of IDs, tracking visited nodes in a graph, or storing a set of configuration keys where order does not matter.
When to Use TreeSet
Use TreeSet when:
- You need elements to remain sorted at all times.
- You need to perform range queries like
subSet(from, to)orheadSet(to). - You need to find the closest element to a given value using
ceiling()orfloor(). - You want to avoid the cost of sorting a collection after each insertion.
TreeSet is a good fit for maintaining a leaderboard, a sorted list of events by timestamp, or any data that must be presented in order without a separate sort step.
Decision Criteria: A Practical Comparison
The following table summarizes the key differences:
| Feature | HashSet | TreeSet |
|---|---|---|
| Ordering | None | Sorted (natural or custom) |
| Time complexity | O(1) average | O(log n) |
| Null handling | Allows one null | Throws NPE by default |
| Iteration order | Unpredictable | Sorted |
| Range queries | Not supported | Supported |
| Comparator | Not used | Required for custom order |
Your choice should be driven by the operations you perform most. If you only need add, remove, and contains, HashSet is almost always the right choice. If you need to iterate in order or perform range operations, TreeSet saves you from manually sorting.
A Practical Example: Using Both in One Workflow
Suppose you have a list of user IDs and you want to find unique IDs and then process them in ascending order. You could use a HashSet to deduplicate, then sort a list. Or you could use a TreeSet directly.
List<Integer> ids = List.of(5, 3, 8, 3, 1, 5);
// Using HashSet then sorting
Set<Integer> unique = new HashSet<>(ids);
List<Integer> sortedIds = new ArrayList<>(unique);
Collections.sort(sortedIds);
// Using TreeSet directly
Set<Integer> sortedUnique = new TreeSet<>(ids);Both approaches produce the same result, but the TreeSet version keeps the data sorted from the start. If you need to add more IDs later and keep the order, TreeSet is cleaner. If you only need the sorted list once, the HashSet plus sort might be preferable because you avoid the overhead of maintaining a tree for every insertion.
Concurrency and Thread Safety Considerations
Neither HashSet nor TreeSet is thread-safe. If multiple threads access the same set concurrently, you must synchronize externally or use a concurrent collection. Java provides ConcurrentSkipListSet as a thread-safe sorted set, which is similar to TreeSet in ordering but uses a skip list. For a concurrent unordered set, you might use ConcurrentHashMap.newKeySet().
If you need a sorted set in a concurrent environment, ConcurrentSkipListSet is a better choice than wrapping a TreeSet with synchronization, because it allows concurrent reads and writes without blocking the entire collection. For a HashSet, the concurrent equivalent is ConcurrentHashMap.newKeySet(), which provides thread-safe membership operations.
When you do use Collections.synchronizedSet() on a HashSet or TreeSet, you must synchronize on the returned set when iterating, or you may get inconsistent results. This is a common source of bugs.
The Role of Hash Code Quality
One detail that often gets overlooked is the quality of the hashCode() implementation for objects stored in a HashSet. If you use mutable objects as keys, their hash code can change after insertion, causing the set to lose track of them. TreeSet has a similar issue if the comparator depends on mutable state. In both cases, you should use immutable objects as set elements, or ensure that the fields used for equality and ordering do not change.
If you are storing custom objects, make sure equals() and hashCode() are consistent. In a TreeSet, the comparator must be consistent with equals() to avoid violating the Set contract. The Java documentation states that a TreeSet's behavior is well-defined only if the comparator is consistent with equals(). If it is not, the set may treat distinct objects as duplicates or otherwise behave inconsistently with the Set contract.
This is a subtle but important point when you are deciding between HashSet and TreeSet for domain objects. If your objects have a natural ordering that matches equality, TreeSet is safe. If not, you need to be careful.
Try matching browser tools
All toolsSmall utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.
Related Java guides
All Java guidesJava Final Keyword: Usage and Behavior
How Java's final keyword works for variables, methods, and classes, with practical examples and decision guidance for using it.
Java Final Variable: Syntax, Behavior, and Use Cases
Understand what a final variable in Java means, how initialization works, and when to use it for constants, immutability, and clearer code.
Java Duration vs Period: When to Use Each
java duration vs period: Compare Java Duration and Period to handle time-based and date-based calculations correctly. Learn syntax, conversion, and pitfalls.
Instance vs Static Variables in Java: Key Differences
Understand the difference between instance and static variables in Java, including memory, lifecycle, and when to use each.
More in Java
All Java guidesThe guides filed next to this one in Java, in library order.