When would you choose a TreeSet over a HashSet or a PriorityQueue, and what are the costs?
answer
- TreeSet O(log n) sorted; HashSet O(1) unordered
- PriorityQueue = heap: O(1) peek, no dedup, O(n) contains
- Tree nodes: poor cache locality; memory near HashSet's
- Sort once at the end can beat a maintained TreeSet
- Concurrent sorted = ConcurrentSkipListSet
basics
~20 sUse a TreeSet when you need elements kept sorted and need to query ranges or nearest values. It is slower (O(log n)) than a HashSet, and unlike a PriorityQueue it has no duplicates and lets you search and iterate in full order.
solid answer
~50 sPick 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 each descent chases pointers through scattered tree nodes with worse cache locality, so for pure membership testing HashSet wins. Memory per element is close to HashSet's, since a node's extra links roughly offset the bucket array. 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
Knows TreeSet is for sorted data and HashSet is faster for plain lookups.
Compares O(log n) vs O(1) and knows a PriorityQueue only gives easy access to the min/max.
Weighs memory, cache locality, dedup and search capabilities across HashSet/TreeSet/PriorityQueue and picks by access pattern; knows ConcurrentSkipListSet.
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.** Fastest 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 — neither of the other two 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 descends from the root → **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 flag. That is **close to a `HashSet`**, whose smaller node also pays for a slot in the bucket array, and **far above a heap's flat array**. Measured at about a million `Integer` elements with compressed references, not counting the elements: on JDK 27 about 32 bytes each for `TreeSet`, 29 to 35 for `HashSet` and 4 to 6 for `PriorityQueue`; on JDK 25 LTS, where compact object headers are off by default, about 40, 37 to 43 and 4 to 6. - **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 (`add(null)` throws `NullPointerException`). - **Comparator correctness:** an ordering inconsistent with equals can silently drop elements (see the comparator topic). ## Concurrency note TreeSet is **not** thread-safe. For concurrent sorted-set needs use `ConcurrentSkipListSet`, which also implements NavigableSet with expected average 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 expected average O(log n) operations with lock-free concurrent access, unlike the non-thread-safe TreeSet.
- 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
- Assuming memory is TreeSet's main cost against HashSet: per-element size is close, while lookups are log n and cache-unfriendly
Assumes JDK 27, where compact object headers are on by default; with compressed references that makes each tree or hash node 8 bytes smaller than on 25 LTS, where they are off by default. TreeSet and HashSet stay close to each other on both.
context
- TreeSet (Java SE 27 & JDK 27)docs.oracle.com
- PriorityQueue (Java SE 27 & JDK 27)docs.oracle.com
- JEP 534: Compact Object Headers by Defaultopenjdk.org