HashMap vs TreeMap: When O(1) Loses to O(log n)
- HashMap gives O(1) average for get/put/remove but has zero ordering guarantees
- TreeMap gives O(log n) worst-case for everything plus floor, ceiling, and range queries
- The decision question: do you ever need the nearest key or a range of keys? If yes, TreeMap
- LinkedHashMap is the middle ground when you need O(1) lookups with insertion-order iteration
- In coding interviews, TreeMap signals hide in calendar scheduling, sliding window median, and sweep-line problems
- Python has no built-in tree map. Use
sortedcontainers.SortedDictor maintain a sorted list alongside your dict
You reach for a HashMap by default. You should. O(1) lookup, O(1) insertion, O(1) deletion. But somewhere around your third coding interview, you hit a problem where the HashMap does absolutely nothing useful. "Find the closest timestamp." "Get everything between key A and key B." You stare at your beautiful O(1) map and realize it has no idea what "closest" means. It is a goldfish. It remembers keys. It does not rank them.
The mental model is simple: a hash map is an unsorted bucket of key-value pairs optimized for point lookups. A tree map is a sorted structure optimized for range operations and ordered access. Everything else follows from that one distinction.
How Does a HashMap Actually Work?
A hash map stores entries in an array of buckets. Feed a key through a hash function, take the result modulo the array length, land in a bucket. If two keys collide, the entries chain together as a linked list (or, in Java 8+, as a red-black tree once a bucket grows past 8 entries). Even hash maps need trees eventually.
A key's journey: hash it, mod it, land in a bucket. Collisions chain off the side like uninvited guests at a party.
The load factor controls when the array doubles. Java's default is 0.75, Python's dict uses 2/3, C++ std::unordered_map defaults to 1.0. The math behind rehashing is amortized O(1): doubling costs O(n) once, but spread across the n insertions that triggered it, each insertion is still constant.
The catch: none of this machinery preserves any ordering. Iterate over a Java HashMap and you get entries in whatever order the hash function scattered them. Rehash, and the order changes. There is no "first key" or "next key above x." Asking a hash map for the nearest key is like asking a pile of laundry which shirt is closest to blue.
How Does a TreeMap Actually Work?
A tree map stores entries in a self-balancing BST. Java's TreeMap and C++'s std::map use a red-black tree. Rust's BTreeMap uses a B-tree for cache locality. The common thread: every node sits in sorted position by key.
A TreeMap's internals: a balanced BST where every in-order walk produces sorted output. No exceptions, no surprises.
Because the tree stays balanced, the path from root to any leaf is at most O(log n). Every get, put, and delete walks that path. No amortization, no average-case caveats. O(log n) worst-case, every single time. Boring, but reliable.
The price you pay is per-node overhead. Each red-black tree node carries the key, the value, child and parent pointers, and a color bit. In Java, roughly 40 bytes of overhead per entry vs. about 32 for a HashMap entry. TreeMap nodes eat more memory the way a golden retriever eats treats. Enthusiastically and without restraint.
How Does HashMap vs TreeMap Compare?
| Operation | HashMap | TreeMap |
|---|---|---|
get(key) | O(1) average | O(log n) |
put(key, val) | O(1) amortized | O(log n) |
remove(key) | O(1) average | O(log n) |
containsKey | O(1) average | O(log n) |
| Iterate all entries | O(n + capacity) | O(n) |
| Find min/max key | O(n) | O(log n) |
| Find floor/ceiling | O(n) | O(log n) |
| Range query [lo, hi] | O(n) | O(log n + k) |
| Worst-case lookup | O(n) | O(log n) |
The first four rows are the HashMap's victory lap. The last four rows are where it falls on its face. A hash map can do floor/ceiling by scanning every key. That is O(n). A tree map walks one root-to-leaf path. For a million keys, that is roughly 20 comparisons vs. a million. Not a close race.
At a million keys, HashMap scans a million entries to find the nearest key. TreeMap walks about 20 nodes. That is a 999,980x difference.
What Can Only a TreeMap Do?
The NavigableMap interface in Java (and lower_bound/upper_bound in C++) gives you a toolkit hash maps cannot replicate.
Floor and ceiling. Given a key, find the greatest key less than or equal to it (floorKey), or the smallest key greater than or equal (ceilingKey). O(log n) on a tree map. On a hash map, they do not exist. You would have to write your own, and it would be O(n) and sad.
TreeMap<Integer, String> map = new TreeMap<>(); map.put(10, "a"); map.put(20, "b"); map.put(30, "c"); map.floorKey(25); // 20, greatest key <= 25 map.ceilingKey(25); // 30, smallest key >= 25 map.lowerKey(20); // 10, greatest key strictly < 20 map.higherKey(20); // 30, smallest key strictly > 20
Range views. subMap, headMap, and tailMap return live views of a slice. No copying, no extra memory. Modifications to the view reflect in the original map and vice versa.
// All entries with keys in [15, 25] NavigableMap<Integer, String> slice = map.subMap(15, true, 25, true); // slice contains {20="b"} // All entries with keys < 25 SortedMap<Integer, String> head = map.headMap(25); // head contains {10="a", 20="b"}
First and last. firstKey() and lastKey() return the min and max in O(log n). A hash map would need to scan all keys.
Sorted iteration. Iterating a tree map gives you keys in ascending order. Always. descendingMap() gives you descending order. A hash map gives you chaos.
When Should You Use a TreeMap Instead of a HashMap?
Ask yourself: do I ever need my keys in sorted order, or do I need to find the nearest key to some value?
If the answer is no, use a hash map. It is faster. End of story.
If the answer is yes, use a tree map. The O(log n) per operation buys you navigation that O(1) lookup cannot provide at any price. You cannot tip your way to better service at a hash map. It genuinely does not know.
There is a third option. If you need O(1) lookup and insertion-order iteration (not sorted order), Java gives you LinkedHashMap. Python's dict preserves insertion order since 3.7. JavaScript's Map does too. These are hash maps with a doubly-linked list threaded through the entries. O(1) operations and predictable iteration, but no floor/ceiling and no range queries.
The decision tree. Most of the time you end up at HashMap. That is fine. The point is knowing when not to.
| Need | Use |
|---|---|
| Fast point lookups, order irrelevant | HashMap |
| Fast lookups + insertion-order iteration | LinkedHashMap |
| Sorted keys, range queries, floor/ceiling | TreeMap |
Which Languages Have a Built-In Tree Map?
The names change. The tradeoff does not.
| Language | Hash Map | Tree Map |
|---|---|---|
| Java | HashMap | TreeMap (red-black) |
| C++ | std::unordered_map | std::map (red-black) |
| Python | dict | sortedcontainers.SortedDict (third-party) |
| Rust | HashMap | BTreeMap (B-tree) |
| Go | map | No stdlib equivalent |
| JavaScript | Map / Object | No built-in (use a library) |
| C# | Dictionary | SortedDictionary (red-black) |
| Kotlin | HashMap | TreeMap (via Java stdlib) |
| Swift | Dictionary | No stdlib equivalent |
Python is notable here. No built-in tree map. You reach for the third-party sortedcontainers library or maintain a sorted list alongside your dict. In competitive programming, this gap matters. It is the Python equivalent of showing up to a potluck empty-handed.
Rust chose a B-tree over a red-black tree for BTreeMap. B-trees store multiple keys per node, fewer pointer dereferences, better cache locality. For most workloads under a few thousand keys, Rust's BTreeMap is competitive with its HashMap purely because of cache effects.
TreeMap in Coding Interviews: The Signal You Should Recognize
In coding interviews, the tree map signal hides in a few specific patterns.
"Maintain a sorted collection that changes over time." If elements are being added and removed and you need the min, max, or nearest neighbor at each step, that is a tree map. A sorted array costs O(n) per insertion. A heap gives you min or max but not both. A tree map gives you everything.
Calendar and interval scheduling. My Calendar I (LC 729) asks whether a new event overlaps any existing one. With a TreeMap keyed by start time, floorKey and ceilingKey find the two candidates in O(log n). Two checks instead of scanning every event.
from sortedcontainers import SortedDict class MyCalendar: def __init__(self): self.bookings = SortedDict() def book(self, start: int, end: int) -> bool: idx = self.bookings.bisect_right(start) - 1 # Check overlap with the event that starts at or before 'start' if idx >= 0: prev_start = self.bookings.keys()[idx] if self.bookings[prev_start] > start: return False # Check overlap with the event that starts just after 'start' if idx + 1 < len(self.bookings): next_start = self.bookings.keys()[idx + 1] if end > next_start: return False self.bookings[start] = end return True
Sliding window with sorted access. Sliding Window Median (LC 480) needs the median of a window that shifts by one element each step. Two tree maps maintain the sorted window in O(log k) per step vs. O(k log k) brute-force.
Sweep line problems. My Calendar III (LC 732) uses a tree map to track start and end timestamps. Increment at each start, decrement at each end, walk keys in sorted order to find peak overlap.
The general rule: if the problem says "find the nearest", "find all in range", or requires sorted order that updates dynamically, reach for a tree map. A hash map with a post-hoc sort is O(n log n) per query. A tree map is O(log n) per update and O(n) for a full sorted traversal.
The Part People Get Wrong
The most common mistake is thinking TreeMap is "just a slower HashMap." It is not a slower anything. It is a different data structure solving a different problem. You do not compare a screwdriver to a hammer by measuring how well each one drives nails. (The screwdriver loses. The screwdriver was never trying.)
The second mistake is reaching for a tree map when a hash map plus a single sort would suffice. If you insert a million entries and need them sorted exactly once, sort the hash map's key set. Both cost O(n log n) total, but tree rebalancing and pointer chasing add higher constant factors. Tree maps win when you need sorted access interleaved with mutations, not as a one-time bulk operation.
The third mistake is ignoring LinkedHashMap when insertion order is all you need. In Java, setting accessOrder = true in the constructor turns it into an LRU cache for free. Free as in "it is in your standard library and you are importing a third-party cache."
When to Reach for Each
- HashMap: O(1) average. No ordering. Default choice.
- TreeMap: O(log n) worst-case, plus floor/ceiling, range queries, sorted iteration. Choose it when you need keys in order.
- LinkedHashMap: O(1) with insertion-order iteration. The middle ground.
- The decision question: "Do I ever need the nearest key or a range of keys?" If yes, tree map. If no, hash map.
If you want to practice problems where the HashMap-vs-TreeMap decision changes everything, SpaceComplexity runs voice-based mock interviews that test whether you reach for the right structure before you start coding.