Performance Trade-offs: TreeSet vs HashSet
You'll learn when TreeSet's sorted ordering is worth the performance cost compared to HashSet's speed.
The Big-O Difference
HashSet and TreeSet solve the same problem—storing unique elements—but with dramatically different performance characteristics:
- HashSet:
O(1)average time foradd,remove, andcontains - TreeSet:
O(log n)time for the same operations
HashSet uses hashing to jump directly to an element's location (constant time). TreeSet uses a red-black tree, navigating branches to find the right position (logarithmic time).
What Does O(log n) Really Mean?
Think of TreeSet like a phone book: to find a name among 1,000 entries, you only need about 10 comparisons (halving your search space each time). With 1,000,000 entries? Only about 20 comparisons. That's logarithmic growth—very efficient, but not instant.
HashSet is like having numbered lockers: you calculate the locker number and go straight there. One step, regardless of how many lockers exist.
When to Choose TreeSet
Choose TreeSet when:
- You need sorted iteration (alphabetical names, chronological events)
- You need range queries (elements between two values)
- The ordering itself provides business value
Choose HashSet when:
- You only care about membership testing (is this user ID in the set?)
- Maximum speed is critical
- Order doesn't matter
The Real Cost
With 10 elements, TreeSet's O(log n) ≈ 3-4 operations vs HashSet's 1. Barely noticeable. With 1,000,000 elements, TreeSet needs ~20 operations vs HashSet's 1. Still fast, but the gap widens significantly under heavy load.
Key Takeaway: Use HashSet for raw speed (O(1)), choose TreeSet only when you need sorted order and can accept the O(log n) performance cost—it's still efficient, just not instant.