skip to content

When would you choose a TreeSet over a HashSet or a PriorityQueue, and what are the costs?

level: seniorimportance: should knowfreq 55%

answer

  1. TreeSet O(log n) sorted; HashSet O(1) unordered
  2. PriorityQueue = heap: O(1) peek-min, no dedup, no sorted iteration, O(n) contains
  3. Tree nodes cost more memory + worse cache locality
  4. Sort once at the end can beat a maintained TreeSet
  5. Concurrent sorted = ConcurrentSkipListSet

basics

~20 s

Use a TreeSet when you need elements kept sorted and need to query ranges or nearest values. It is slower (O(log n)) and uses more memory than a HashSet, and unlike a PriorityQueue it has no duplicates and lets you search and iterate in full order.

solid answer

~50 s

Pick a TreeSet when your access pattern needs ordering: sorted iteration, first/last, floor/ceiling, or range views. Its add/contains/remove are O(log n) versus HashSet's O(1) average, and it carries higher per-element memory (tree nodes with child/parent pointers and color bits) plus worse cache locality, so for pure membership testing HashSet wins. Versus a PriorityQueue (a binary heap): a heap gives O(1) peek and O(log n) poll of just the min (or max), but it does not deduplicate, cannot do O(log n) contains/remove of arbitrary elements, and cannot iterate in sorted order. So choose TreeSet when you need a *fully ordered, duplicate-free, searchable* structure; choose PriorityQueue when you only repeatedly need the extreme element and want lower overhead. If you need ordering only once, sorting a list or HashSet at the end is often cheaper than maintaining a TreeSet throughout.

go deeper

for a junior

Knows TreeSet is for sorted data and HashSet is faster for plain lookups.

for a middle

Compares O(log n) vs O(1) and knows a PriorityQueue only gives easy access to the min/max.

for a senior

Weighs memory, cache locality, dedup and search capabilities across HashSet/TreeSet/PriorityQueue and picks by access pattern; knows ConcurrentSkipListSet.

for a principal

Frames the choice as a systems trade-off (insertion-time cost vs one-time sort, GC/memory pressure of node-based structures, concurrency model) and validates against measured workloads.

## The three candidates - **HashSet** — hash table. **O(1)** average add/contains/remove. **No order.** Lowest overhead for membership. - **TreeSet** — red-black tree (a balanced binary search tree). **O(log n)** add/contains/remove. **Fully sorted**, duplicate-free, supports NavigableSet (floor/ceiling, ranges, first/last). - **PriorityQueue** — binary **heap** (an array-based tree where the root is the min). **O(1)** peek of the min, **O(log n)** add and poll-min. **Not** a set (allows duplicates), **O(n)** arbitrary contains/remove, and **no sorted iteration** (iteration order is heap order, which is not sorted). ## Decision guide Ask what you actually do with the data: 1. **Only membership tests, order irrelevant** → **HashSet**. Don't pay log(n) for ordering you never use. 2. **Need sorted iteration, min AND max, nearest-neighbour, or range queries, and no duplicates** → **TreeSet**. This is its sweet spot — nothing else does all of it. 3. **Repeatedly pull the smallest (or largest) element and that's basically it** → **PriorityQueue**. A heap is leaner than a tree and peek is O(1). But it can't dedupe or search. 4. **Need order produced just once at the end** → keep a HashSet/List and **sort once** (`O(n log n)` total), which is usually cheaper than the per-insert log(n) overhead of maintaining a TreeSet the whole time. ## The costs of a TreeSet - **Time:** every add/contains/remove is a root-to-leaf descent → **O(log n)**, not O(1). For millions of lookups this matters. - **Memory:** each element lives in a tree **node** carrying references to two children and a parent plus a color bit — markedly more per-element overhead than a hash bucket entry, and more than a heap's flat array. - **Cache locality:** tree nodes are scattered across the heap (pointer chasing), so traversal is less cache-friendly than the contiguous array a PriorityQueue or an ArrayList uses. - **null:** disallowed under natural ordering (would NPE on compareTo). - **Comparator correctness:** an ordering inconsistent with equals silently drops elements (see the comparator topic). ## Concurrency note TreeSet is **not** thread-safe. For concurrent sorted-set needs use `ConcurrentSkipListSet`, which also implements NavigableSet with O(log n) operations but allows lock-free concurrent access; it is the concurrent analogue of TreeSet. ## Summary table | Need | Best choice | |---|---| | Fast membership, no order | HashSet | | Sorted, dedup, range/nearest queries | TreeSet | | Repeatedly take the extreme element | PriorityQueue | | Concurrent sorted set | ConcurrentSkipListSet | | Order needed once at the end | Sort a list/HashSet once |

  • You need to repeatedly find and remove the smallest element of a changing collection. Heap or TreeSet?
    If you only ever touch the smallest and allow duplicates, a PriorityQueue (heap) is leaner with O(1) peek. If you also need dedup, arbitrary contains/remove, or both ends, use a TreeSet (pollFirst/pollLast).
  • What's the thread-safe equivalent of a TreeSet?
    ConcurrentSkipListSet — a NavigableSet backed by a skip list giving O(log n) operations with lock-free concurrent access, unlike the non-thread-safe TreeSet.

saying these in an interview costs you the question

  • Defaulting to TreeSet when order is never used (pay log n for nothing)
  • Thinking a PriorityQueue iterates in sorted order
  • Believing PriorityQueue deduplicates or supports O(log n) arbitrary contains
  • Using TreeSet from multiple threads without external synchronization
  • Ignoring memory/cache cost of tree nodes at large scale

context

resolving links…