Course contentsShow
← Java
Lesson 1075 of 2,87025. Set ImplementationsFree lesson

Performance Trade-offs: TreeSet vs HashSet

Compare TreeSet's O(log n) operations with HashSet's O(1) and when to choose sorted sets over hash sets.

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 for add, remove, and contains
  • 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.