BST vs Hash Map: O(log n) Beats O(1) More Often Than You Think

You reach for a hash map every time. So does everyone. O(1) lookup, O(1) insert, ship it, next problem. It's the comfort food of data structures. Then an interviewer asks "give me every key between 50 and 200" and your hash map just sits there like a golden retriever who heard a new word. You're stuck scanning every entry while the clock ticks.

Hash maps trade order for speed. BSTs keep keys sorted and pay O(log n) for it. The question is always whether you need that order.

Most interview prep treats this as an obvious choice. It isn't. Plenty of medium and hard problems actually need a sorted map, and reaching for a hash map first costs you the whole interview before you even notice what went wrong.

What Are You Actually Paying For?

A hash map stores key-value pairs in an array of buckets. A hash function converts each key into an array index. When two keys collide (land in the same bucket), the map either chains them in a linked list or probes forward to the next open slot. The load factor (ratio of entries to buckets) controls when the array doubles and every entry rehashes. Java's HashMap caps it at 0.75. Python's dict uses open addressing and rehashes at roughly 2/3 full.

A key goes in, a hash comes out, modular arithmetic picks a bucket. Collisions get chained.

A balanced BST (the sorted map in standard libraries, Java's TreeMap, C++'s std::map) stores key-value pairs in a binary tree where every node's left descendants are smaller and right descendants are larger. Self-balancing rules keep the height at O(log n), so the tree never degenerates into a linked list. Both TreeMap and std::map use red-black trees under the hood.

Walk left to right and the keys come out sorted. That's the whole trick.

Both store n key-value pairs. Both use O(n) space. The difference is what they're fast at.

The Complexity Table Nobody Shows You

Every "BST vs hash map" comparison online shows you three rows. Lookup, insert, delete. Hash map wins, end of article, thanks for reading. But the full table has eight rows, and the plot twist lives in the bottom five.

Operation	Hash Map (avg)	Hash Map (worst)	Balanced BST
Lookup by key	O(1)	O(n)	O(log n)
Insert	O(1) amortized	O(n)	O(log n)
Delete	O(1) amortized	O(n)	O(log n)
Min / Max	O(n)	O(n)	O(log n)
Floor / Ceiling	O(n)	O(n)	O(log n)
Range query [lo, hi]	O(n)	O(n)	O(log n + k)
Ordered iteration	O(n log n) sort	O(n log n) sort	O(n)
Rank (kth smallest)	O(n)	O(n)	O(log n)*

*With augmentation (order-statistics tree).

If you only need the top three rows, use a hash map. If you need anything in the bottom five, you need a BST. That's the entire decision. You can tattoo it on your forearm if you want. I won't judge.

Five Things a BST Can Do That a Hash Map Can't

Range queries: O(log n + k) vs scanning everything

"Give me every key between 50 and 200." A hash map has to scan all n entries because keys are scattered across buckets with no ordering. It's like asking everyone in a stadium to raise their hand if their birthday is in March. A BST walks to the first key >= 50 in O(log n), then follows the in-order successor chain until it passes 200, touching only the k keys in range.

Left: the BST walks straight to the range and stops. Right: the hash map checks every bucket and shrugs.

In Java, this is one method call:

SortedMap<Integer, String> range = treeMap.subMap(50, true, 200, true);

In C++:

auto lo = map.lower_bound(50);
auto hi = map.upper_bound(200);
// iterate [lo, hi) for all keys in [50, 200]

Calendar booking, interval scheduling, time-series queries. All range query territory.

Floor and ceiling find the nearest key

"What's the largest key less than or equal to 73?" That's a floor query. "What's the smallest key greater than or equal to 73?" That's a ceiling query. A BST answers both in O(log n) by walking the tree and tracking the best candidate. A hash map has no relationship between a key's hash and its value, so it has to check every entry. Asking a hash map for the nearest key is like asking a pile of laundry for the matching sock.

Java's TreeMap gives you floorKey(), ceilingKey(), lowerKey(), higherKey(). C++'s std::map gives lower_bound() and upper_bound(). Python has no built-in BST, but the sortedcontainers library provides bisect-based lookups.

Interview signal: any problem that says "find the nearest," "closest value," or "just smaller/larger than" is pointing you toward a BST.

Ordered iteration costs nothing extra

A BST's in-order traversal visits keys in sorted order in O(n). No sorting step, no extra allocation, just walk the tree. A hash map has to copy all keys into a list and sort them: O(n log n). That's the data structure equivalent of dumping your entire bookshelf on the floor and then alphabetizing.

If the problem says "return results in sorted order" and you're inserting dynamically, a BST saves you the final sort.

Min and max live at the edges

The minimum key in a BST is the leftmost node. The maximum is the rightmost. Both O(log n) to reach. Java's TreeMap exposes them as firstKey() and lastKey(). C++'s std::map uses begin() and rbegin(). Easy.

A hash map doesn't know where its smallest or largest key lives without checking every single entry. The sliding window median (LC 480) and stock price fluctuation (LC 2034) both exploit this: you need to insert, delete, and find min/max efficiently, all at once. Try that with a hash map and you'll be writing a second data structure by minute three anyway.

Rank queries with one extra integer per node

"How many keys are smaller than 73?" An order-statistics tree, which is a BST augmented with subtree sizes, answers this in O(log n). Each node stores size = 1 + left.size + right.size. Walking the tree and summing left-subtree sizes gives the rank.

C++ provides this via __gnu_pbds::tree with order_of_key() and find_by_order(). In other languages you'd augment a BST yourself or use a Fenwick tree for the same effect.

When Hash Maps Win Decisively

Look, I've been roasting hash maps for five sections. Time to be fair. For pure key-value lookup, hash maps win and the gap is embarrassingly wide. O(1) average vs O(log n). At a million keys, that's roughly 1 operation vs 20. At a billion, 1 vs 30. The constant factor favors hash maps too: one hash computation plus one or two memory accesses, versus pointer-chasing through O(log n) tree nodes that are probably scattered across three different cache lines.

Use a hash map when:

• You only need contains, get, put, delete
• You're counting frequencies (counter[x] += 1)
• You're testing membership (deduplication, "have I seen this?")
• The problem is Two Sum shaped: "does a complement exist?"
• You never need keys in sorted order or range queries

Most coding interview problems land here. Two Sum, group anagrams, subarray sum equals k, word frequency. All hash map territory. The hash map earned its reputation honestly.

The Tradeoffs the Table Hides

The worst case that actually happens

Hash maps promise O(1) on average. But "average" assumes the hash function distributes keys uniformly (the SUHA assumption). In 2011, Alexander Klink and Julian Wälde demonstrated at the Chaos Communication Congress (28C3) that an attacker who controls the keys can force all entries into a single bucket, degrading every operation to O(n). Sending 65,536 crafted POST parameters froze a PHP 5 server for 30 seconds on a single core. One POST request. Thirty seconds. Ouch.

A balanced BST guarantees O(log n) per operation regardless of input. No adversarial keys, no degenerate cases. For security-sensitive code paths, this guarantee matters.

Java's HashMap actually hedges this bet in a way that's almost funny. Since Java 8, when a single bucket accumulates 8 or more entries (the TREEIFY_THRESHOLD), the bucket's linked list converts into a red-black tree. So Java's worst-case lookup per bucket is O(log n), not O(n). The hash map literally borrowed from the BST to patch its own weakness.

When a bucket gets too crowded, Java's HashMap quietly upgrades it to a BST. If you can't beat them, embed them.

Memory: different flavors of waste

Both structures are O(n) space, but they waste it in different ways. Like two people with the same grocery budget who somehow end up with completely different pantries.

A Java HashMap.Entry holds a key reference (8 bytes), value reference (8 bytes), cached hash (4 bytes), next pointer (8 bytes), plus object header (~16 bytes). Roughly 44 bytes overhead per entry. Then the bucket array itself keeps roughly 25% of its slots empty at load factor 0.75.

A Java TreeMap.Entry holds a key reference (8 bytes), value reference (8 bytes), left/right/parent pointers (24 bytes), and a color flag (1 byte plus alignment padding). Roughly 48 bytes per entry. No wasted array capacity.

In practice, the memory difference is small. Hash maps waste space on empty buckets. BSTs waste it on structural pointers. Pick your poison.

Cache locality favors hash maps

Hash maps using open addressing (Python's dict, Go's map, Rust's HashMap) store entries in a contiguous array. Sequential probes hit adjacent memory, which hardware prefetchers love. L1 cache access takes about 2 nanoseconds. Main memory (DRAM) takes 80 to 100 nanoseconds. When probes stay in cache, O(1) translates directly to wall-clock speed.

BST lookups chase pointers. Each parent-to-child jump is a dependent load: the CPU can't issue load N+1 until load N reveals the child's address. For a tree with a million nodes scattered across the heap, most of those loads miss L1 and hit L2 or L3. Bjarne Stroustrup demonstrated (Going Native 2012) that even a sorted vector with binary search often outperforms a std::map in practice, because contiguous memory wins on modern hardware.

This gap narrows with small data sets (where the whole tree fits in L1/L2) and widens with large ones.

Amortized O(1) has spikes

Hash map insert is amortized O(1) because of occasional O(n) rehashing. When the load factor exceeds the threshold, the map allocates a new, larger array and re-inserts every entry. For n = 1 million, that's a million copies in a single insert call. 999,999 inserts are instant, and then one of them takes a coffee break.

In most applications, this is fine. Amortized analysis (Tarjan 1985) proves the average cost per operation is still O(1). But in latency-sensitive systems (game loops, trading engines, audio processing), a single O(n) spike can miss a deadline. A balanced BST's O(log n) is steady. Every insert takes the same bounded time. No surprises, no excuses.

A Problem That Needs Both

Here's where things get fun. LeetCode 2034 (Stock Price Fluctuation) is the cleanest example of why "BST or hash map?" is sometimes the wrong question. The right question is "BST AND hash map?" You receive timestamped price updates and need to support four operations: update a price, get the latest price, get the current maximum, and get the current minimum.

from sortedcontainers import SortedList

class StockPrice:
    def __init__(self):
        self.latest_time = 0
        self.prices = {}              # hash map: timestamp -> price
        self.sorted = SortedList()    # BST-like: sorted prices

    def update(self, timestamp: int, price: int) -> None:
        if timestamp in self.prices:
            self.sorted.remove(self.prices[timestamp])  # O(log n)
        self.prices[timestamp] = price                  # O(1)
        self.sorted.add(price)                          # O(log n)
        self.latest_time = max(self.latest_time, timestamp)

    def current(self) -> int:
        return self.prices[self.latest_time]  # O(1) hash lookup

    def maximum(self) -> int:
        return self.sorted[-1]                # O(log n) max

    def minimum(self) -> int:
        return self.sorted[0]                 # O(log n) min

The hash map gives O(1) lookup by timestamp. The sorted structure gives O(log n) min and max. Neither alone solves the problem. Recognizing when you need both is the real interview skill.

How to Decide in 30 Seconds

Three questions. Ask them in order. You can do this while the interviewer is still finishing the problem statement.

1. Do I need keys in sorted order? Range queries, floor/ceiling, ordered iteration, min/max while inserting and deleting. If yes: BST.
2. Do I need guaranteed worst-case bounds? Adversarial inputs, real-time constraints, no tolerance for rehash spikes. If yes: BST.
3. Neither? Hash map. It's faster for point operations by a wide margin.

Two questions. That's it. The flowchart fits on a sticky note.

The signals that point toward a BST in an interview: "in sorted order," "closest to," "between X and Y," "kth smallest," and "track the min/max while values change." If none of those appear, the hash map is almost certainly right.

The Short Version

• Hash maps give O(1) average for point operations. They don't maintain order. They don't care about order. Order is not their problem.
• Balanced BSTs give O(log n) for everything, plus range queries, floor/ceiling, min/max, ordered iteration, and rank.
• The honest complexity table has eight rows. Hash maps win the top three. BSTs win the bottom five.
• Use a hash map when you only need point operations. That's most problems.
• Use a BST when you need ordering, nearest-neighbor queries, or guaranteed worst-case bounds.
• Some problems need both structures working together. Recognizing that split is the skill that separates "strong hire" from "no hire."

If the hash map vs BST decision has tripped you up before, practicing under realistic conditions helps it stick. SpaceComplexity runs voice-based mock interviews where an AI interviewer will absolutely ask you why you picked a hash map when the problem screams sorted map.

Further Reading

• Hash Table - Wikipedia
• Self-Balancing Binary Search Tree - Wikipedia
• TreeMap (Java SE 8) - Oracle Docs
• std::map - cppreference.com
• Binary Search Tree vs Hash Table - GeeksforGeeks