When should you choose TreeMap over HashMap, and what alternatives exist for sorted or concurrent ordered access?
answer
- TreeMap only pays off if you use sortedness (order/range/nearest)
- HashMap wins for pure point lookups (average O(1))
- Concurrent sorted → ConcurrentSkipListMap (skip list, CAS)
- Static sorted data → sorted array + binarySearch
- Large/persistent ordered → B-tree / LSM (databases)
basics
~20 sUse 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 sReach 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
Knows to use TreeMap when sorting is needed and HashMap otherwise.
Articulates the O(log n) vs average O(1) tradeoff and that TreeMap isn't thread-safe.
Picks TreeMap for concrete range/nearest use cases, names ConcurrentSkipListMap for concurrency, and accounts for comparison and cache cost.
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
- ConcurrentSkipListMap (Java SE 27 & JDK 27)docs.oracle.com
- Collections (Java SE 27 & JDK 27)docs.oracle.com
- JEP 534: Compact Object Headers by Defaultopenjdk.org