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 (O(1), better cache locality)
- Concurrent sorted → ConcurrentSkipListMap (skip list, lock-free)
- 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 O(1) and lower per-entry overhead win — TreeMap's O(log n), pointer-heavy nodes and worse cache locality cost real time at scale. For ordered access under concurrency, TreeMap is not thread-safe; use ConcurrentSkipListMap, a lock-free NavigableMap with the same API and O(log n) ops. 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 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 memory/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 op is O(log n) vs HashMap's average O(1). - **Memory & locality**: each entry is a tree node with left/right/parent pointers and a colour bit; nodes are scattered on the heap, so traversal causes **cache misses**. HashMap's array-of-buckets is more cache-friendly. - **No nulls**: TreeMap rejects null keys (under natural ordering). ## Alternatives by scenario - **Thread-safe ordered access → ConcurrentSkipListMap.** TreeMap is **not** thread-safe (external synchronization or `Collections.synchronizedSortedMap` serializes everything). `ConcurrentSkipListMap` is a concurrent **NavigableMap** (same floor/ceiling/subMap API) built on a **skip list** — a probabilistically balanced, lock-free structure with O(log n) ops and good scalability under contention. Prefer it over a synchronized TreeMap for concurrent sorted maps. - **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.** Libraries (Eclipse Collections, fastutil, Koloboke) offer primitive-keyed sorted maps avoiding boxing overhead. - **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* 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 lock-free skip list giving O(log n) operations that scale better under contention than a synchronized TreeMap.
- 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.
saying these in an interview costs you the question
- Defaulting to TreeMap 'to be safe' when no ordering is needed
- Wrapping TreeMap in synchronizedSortedMap instead of using ConcurrentSkipListMap for concurrency
- Ignoring cache-locality/memory overhead of tree nodes at scale
- Assuming TreeMap scales to disk-sized data like a database index