Course contentsShow
← Java
Lesson 981 of 2,87023. Collections Framework OverviewFree lesson

HashSet vs TreeSet: Performance vs Ordering Trade-offs

Using HashSet for fast O(1) operations, TreeSet when you need sorted elements or range queries.

HashSet vs TreeSet: Performance vs Ordering Trade-offs

What you'll learn: How to choose between HashSet for speed and TreeSet for sorted order.


Both HashSet and TreeSet implement the Set interface—they store unique elements without duplicates. The crucial difference lies in performance versus ordering guarantees.

HashSet: Speed First

HashSet uses a hash table internally. When you add, remove, or check for an element, it computes a hash code to find the right "bucket" almost instantly. This gives you O(1) average-time complexity for basic operations—blazingly fast.

Trade-off: Elements have no guaranteed order. When you iterate through a HashSet, the sequence is unpredictable and may even change between runs.

HashSet<String> cities = new HashSet<>();
cities.add("Paris");
cities.add("London");
cities.add("Berlin");

// Fast contains check: O(1)
boolean hasLondon = cities.contains("London"); // true

// Iteration order is unpredictable
for (String city : cities) {
    System.out.println(city); // Could print in any order
}

TreeSet: Sorted Order

TreeSet uses a red-black tree internally. It keeps elements sorted at all times (using natural ordering or a custom comparator). This enables sorted iteration and efficient range queries (finding elements within a range).

Trade-off: Operations are O(log n) because the tree must be rebalanced on insertions and deletions—slower than HashSet, but still efficient.

TreeSet<Integer> scores = new TreeSet<>();
scores.add(85);
scores.add(92);
scores.add(78);

// Elements are always sorted
for (Integer score : scores) {
    System.out.println(score); // Prints: 78, 85, 92
}

When to Use Which

  • HashSet: Default choice when you need fast lookups and don't care about order
  • TreeSet: When you need sorted elements or range-based queries

Key Takeaway: Choose HashSet for O(1) performance when order doesn't matter; choose TreeSet when you need sorted elements or range operations, accepting O(log n) cost.