skip to content

When should you choose TreeMap over HashMap, and what alternatives exist for sorted or concurrent ordered access?

level: principalimportance: nice to knowfreq 38%

answer

  1. TreeMap only pays off if you use sortedness (order/range/nearest)
  2. HashMap wins for pure point lookups (average O(1))
  3. Concurrent sorted → ConcurrentSkipListMap (skip list, CAS)
  4. Static sorted data → sorted array + binarySearch
  5. Large/persistent ordered → B-tree / LSM (databases)

basics

~20 s

Use TreeMap when you need keys in sorted order or range/nearest-key queries. Otherwise prefer HashMap for speed. For thread-safe sorted access use ConcurrentSkipListMap; for fixed sorted data, a sorted array with binary search can be faster and lighter.

solid answer

~50 s

Reach for TreeMap when ordering or range/nearest queries are part of the access pattern: iterate keys in order, 'as-of' lookups (floorEntry on timestamps), range scans (subMap), or maintaining a running sorted index. If you only need point lookups, HashMap's average O(1) wins — TreeMap's O(log n) comparisons and pointer chasing cost real time at scale, even though per-entry memory is close. For ordered access under concurrency, TreeMap is not thread-safe; use ConcurrentSkipListMap, a scalable concurrent NavigableMap with the same navigation API, expected average O(log n) ops and no null keys or values. When the dataset is static or rarely mutated, a sorted array plus Arrays.binarySearch (or a specialized primitive map) is cheaper in memory and faster to scan. For very large or disk-resident ordered data, a B-tree/LSM index (as in databases) replaces an in-memory TreeMap. The decision is driven by access pattern, mutation rate, concurrency, and data size — not a default preference.

go deeper

for a junior

Knows to use TreeMap when sorting is needed and HashMap otherwise.

for a middle

Articulates the O(log n) vs average O(1) tradeoff and that TreeMap isn't thread-safe.

for a senior

Picks TreeMap for concrete range/nearest use cases, names ConcurrentSkipListMap for concurrency, and accounts for comparison and cache cost.

for a principal

Frames the choice across access pattern, mutation rate, concurrency and scale; composes structures (HashMap+index) and reaches for skip lists, sorted arrays, or B-tree/LSM indexes when warranted.

## The core question TreeMap and HashMap both implement `Map`, so the choice is about **what you do with the keys**, not about correctness. ## Choose TreeMap when ordering is part of the job TreeMap earns its O(log n) cost only if you use its sortedness: - **In-order iteration** of keys (reports, alphabetical listings). - **Range queries** via `subMap`/`headMap`/`tailMap` (events between two times, pagination of sorted keys). - **Nearest-key / as-of lookups** via `floorEntry`/`ceilingEntry` (most recent price at or before a timestamp; routing to the closest bucket). - **Min/max and ordered draining** via `firstEntry`/`lastEntry`/`pollFirstEntry`. If none of these apply, HashMap is the better default. ## The cost of TreeMap - **Time**: every key-based op is O(log n) vs HashMap's average O(1). - **Locality**: each entry is a separate tree node with left/right/parent pointers and a colour flag, so a lookup chases about log n pointers through the heap and risks a **cache miss** at each step. A HashMap lookup indexes an array and usually touches one node. - **Memory is closer than it looks**: on JDK 27 with default flags and compressed references, a `TreeMap.Entry` is 32 bytes and a `HashMap.Node` 24, but HashMap also pays for its bucket array, about 5 to 11 bytes per entry. On JDK 25 LTS, without compact object headers by default, they are 40 and 32. - **No null key under natural ordering**: `put(null, ...)` throws `NullPointerException`; null values are fine. ## Alternatives by scenario - **Thread-safe ordered access → ConcurrentSkipListMap.** TreeMap is **not** thread-safe. External synchronization or `Collections.synchronizedSortedMap` serializes the map's calls, and that wrapper's return type is `SortedMap`, so reaching `floorKey` takes `Collections.synchronizedNavigableMap` (since Java 8). `ConcurrentSkipListMap` is a concurrent **NavigableMap** (same floor/ceiling/subMap API) built on a **skip list** — a probabilistically balanced structure, updated with CAS rather than locks, with expected average O(log n) ops and good scalability under contention. Three differences from TreeMap matter: no null keys or values, weakly consistent iterators rather than fail-fast, and snapshot entries from every method. Prefer it over a synchronized TreeMap when contention is real. - **Static / read-mostly sorted data → sorted array + binary search.** If the data is built once and queried many times, a sorted `array`/`List` with `Arrays.binarySearch`/`Collections.binarySearch` gives O(log n) lookup with far less memory and excellent cache behaviour; build cost is one O(n log n) sort. - **Primitive keys at scale → specialized maps.** The JDK's maps box primitive keys; third-party primitive-collection libraries avoid that overhead. For sorted `int` keys, fastutil has `Int2ObjectRBTreeMap` and `Int2ObjectAVLTreeMap`. Eclipse Collections' primitive-keyed maps, such as `IntObjectHashMap`, are hash maps, and its `TreeSortedMap` takes object keys. - **Very large or persistent ordered data → B-tree / LSM-tree.** Databases use B-trees (or log-structured merge trees) because they minimize disk/page I/O; an in-memory TreeMap is the in-RAM analogue but does not scale past memory. - **Need both ordering *and* average O(1) point lookups** → sometimes maintain two structures (a HashMap for lookups + a TreeMap/ordered index for ranges), trading memory for time. ## Decision checklist 1. Do I ever need keys in order or range/nearest queries? No → HashMap. 2. Yes, and concurrent? → ConcurrentSkipListMap. 3. Yes, but data is static/read-mostly? → sorted array + binary search. 4. Yes, large or disk-resident? → B-tree/LSM index (database or specialized store). 5. Otherwise → TreeMap. The principal-level point: there is no default 'best' map. Match the structure to the **access pattern, mutation rate, concurrency model, and data size**, and be ready to compose two structures when one cannot serve both lookup and ordering cheaply.

  • What is the thread-safe equivalent of TreeMap and how is it implemented?
    ConcurrentSkipListMap — a concurrent NavigableMap with the same floor/ceiling/subMap API, implemented on a skip list updated with CAS rather than locks, giving expected average O(log n) operations that scale better under contention than a synchronized TreeMap. Unlike TreeMap it rejects null values, and its iterators are weakly consistent.
  • When would a plain sorted array beat a TreeMap?
    For static or read-mostly data: build it once, sort O(n log n), then query with binary search O(log n). It uses far less memory and has excellent cache locality, with no per-node pointer overhead.

  • Defaulting to TreeMap 'to be safe' when no ordering is needed
  • Assuming a synchronizedSortedMap wrapper exposes floorKey or scales under heavy contention
  • Ignoring the comparison and pointer-chasing cost of tree lookups at scale
  • Assuming TreeMap scales to disk-sized data like a database index

TreeMap
Java 1.2
ConcurrentSkipListMap
Java 1.6
Compact object headers on by default
Java 27

Assumes JDK 27. The entry and node sizes are JDK 27's, where compact object headers are on by default; JDK 25 LTS has them off by default, so both are 8 bytes larger there. ConcurrentSkipListMap.java is byte-identical at 25, and TreeMap.java differs only in a null check on an empty view's key-set spliterator.

context