Hash Map vs Tree Map: dict vs Sorted Structure

Hash map vs tree map in one line: a hash map finds a key in O(1) on average but knows nothing about order; a tree map keeps keys sorted, pays O(log n) for every operation, and in return answers "what is the next key after x?" without a scan. Pick by the questions you will ask. If every question is "what is stored under this exact key?", the hash map wins. If any question mentions smallest, largest, before, after or between, it does not.

Operation	Hash map (dict)	Tree map (ordered map)
get, put, delete by key	O(1) average	O(log n)
min, max, floor, ceiling	O(n) scan	O(log n)
count or list keys in a range	O(n) scan	O(log n) to count, plus k to list
iterate in key order	O(n log n), sort first	O(n)

The problem it solves

Both structures map keys to values; the difference is what else they can tell you. A leaderboard, a booking calendar or a rate limiter's timestamps need "the closest key below this one" or "every key between these two". On a hash map those questions turn into a loop over every key. On a tree map they are a walk down one branch.

How a hash map gets its speed is covered in how hash tables work, and why it can slow to O(n) under collisions in hash collisions explained. This article is about the other trade: order.

The intuition

A hash map turns the key into an address. The hash table lesson does it with numbered bins: hash(key) % buckets names the bin, and lookup jumps straight there. That jump is the whole trick, and it is also why order is gone. Key 118 and key 119 land in unrelated bins, so "the key just below 500" has no bin to jump to.

A tree map keeps keys in a balanced binary search tree: smaller keys to the left, larger to the right, height kept at about log₂ n. Every lookup walks one root-to-leaf path, so it costs O(log n) comparisons instead of one jump. But the same walk answers ordered questions:

• floor(x): the largest key ≤ x. Walk down, remember the last key that was not too big.
• ceiling(x): the smallest key ≥ x, the mirror image.
• min and max: the leftmost and rightmost nodes.
• range [lo, hi]: find lo, then walk in order until you pass hi.

Language support differs, and interviewers notice when you know it:

• Java: HashMap and TreeMap, which has floorKey, ceilingKey and subMap.
• C++: unordered_map and map, with lower_bound and upper_bound.
• Python: dict, and no tree map in the standard library. The usual answer is a sorted list with bisect: O(log n) search, but O(n) insert because the list shifts. A third-party sorted container fixes the insert cost when you are allowed to use one.

One more trap: a Python dict remembers insertion order (guaranteed since 3.7). That is not sorted order. Iterating a dict gives keys in the order you added them, not smallest first.

Watch it run

The lesson's animation shows six numbered bins and a pharmacy rule for picking one: the last two digits of the order number, modulo 6. Writing SKU-118 computes 18 % 6 = 0 and drops the pair into bin 0; SKU-903 gives 3 and goes to bin 3. Reading SKU-118 back repeats the arithmetic and lands on bin 0 in one jump. Asking for SKU-000 also lands on bin 0, finds 118 there instead, and returns the default. The closing frame names what the bins cost: lookup is the same price for five bags or two hundred, but the order of the keys is never recoverable from where they sit.

The code

The lesson's bin model as a small chained hash map that counts the keys it looks at. Insertion order, bin order and sorted order are three different things:

class ChainedMap:
    """The lesson's model: hash the key to a bucket number, keep a chain per bucket."""
    def __init__(self, size=6):
        self.buckets = [[] for _ in range(size)]
        self.n = 0
        self.examined = 0                  # keys looked at, across all calls

    def _chain(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, value):
        chain = self._chain(key)
        for i, (k, _) in enumerate(chain):
            self.examined += 1
            if k == key:
                chain[i] = (key, value)
                return
        chain.append((key, value))
        self.n += 1
        if self.n > len(self.buckets):     # keep chains short: double and rehash
            pairs = [p for c in self.buckets for p in c]
            self.buckets = [[] for _ in range(2 * len(self.buckets))]
            for k, v in pairs:
                self._chain(k).append((k, v))

    def get(self, key, default=None):
        for k, v in self._chain(key):
            self.examined += 1
            if k == key:
                return v
        return default

    def delete(self, key):
        chain = self._chain(key)
        for i, (k, _) in enumerate(chain):
            if k == key:
                chain.pop(i)
                self.n -= 1
                return

    def keys(self):                        # bucket order: whatever the hash says
        return [k for chain in self.buckets for k, _ in chain]

    def floor(self, x):                    # no order to use: look at every key
        self.examined += self.n
        return max((k for k in self.keys() if k <= x), default=None)

    def range_count(self, lo, hi):
        self.examined += self.n
        return sum(lo <= k <= hi for k in self.keys())

    def first(self, k):
        self.examined += self.n
        return sorted(self.keys())[:k]


stock = ChainedMap()
for order in (118, 903, 245, 10, 777):
    stock.put(order, f"bag-{order}")
plain = {order: f"bag-{order}" for order in (118, 903, 245, 10, 777)}

print(list(plain))                         # [118, 903, 245, 10, 777]  insertion order
print(stock.keys())                        # [903, 777, 118, 10, 245]  bucket order
print(sorted(plain))                       # [10, 118, 245, 777, 903]  sorted order
print(stock.get(245), stock.floor(500))    # bag-245 245

Now the Python stand-in for a tree map: a sorted key list searched with the same loop bisect.bisect_left runs. Both structures load the same 10,000 keys and answer the same four questions; the counters show how many keys each one looked at:

import random

class SortedMap:
    """A sorted key list plus binary search: the stdlib stand-in for a tree map."""
    def __init__(self):
        self.keys_, self.vals = [], []
        self.examined = 0                  # keys compared, across all calls
        self.shifted = 0                   # slots moved by inserts and deletes

    def _lower(self, x):                   # first index with key >= x (bisect_left)
        lo, hi = 0, len(self.keys_)
        while lo < hi:
            mid = (lo + hi) // 2
            self.examined += 1
            if self.keys_[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def put(self, key, value):
        i = self._lower(key)
        if i < len(self.keys_) and self.keys_[i] == key:
            self.vals[i] = value
            return
        self.shifted += len(self.keys_) - i  # the O(n) half of a sorted list
        self.keys_.insert(i, key)
        self.vals.insert(i, value)

    def get(self, key, default=None):
        i = self._lower(key)
        if i < len(self.keys_) and self.keys_[i] == key:
            return self.vals[i]
        return default

    def delete(self, key):
        i = self._lower(key)
        if i < len(self.keys_) and self.keys_[i] == key:
            self.shifted += len(self.keys_) - i - 1
            del self.keys_[i], self.vals[i]

    def floor(self, x):                    # largest key <= x
        i = self._lower(x)
        if i < len(self.keys_) and self.keys_[i] == x:
            return x
        return self.keys_[i - 1] if i else None

    def range_count(self, lo, hi):         # keys in [lo, hi]: two searches, no scan
        return self._lower(hi + 1) - self._lower(lo)

    def first(self, k):
        return self.keys_[:k]              # already in order


random.seed(22)
keys = random.sample(range(1_000_000), 10_000)
h, t = ChainedMap(), SortedMap()
for key in keys:
    h.put(key, key * 2)
    t.put(key, key * 2)
print(h.examined, t.examined, t.shifted)   # cost of building both
# 7247 119028 24962979

queries = [
    ("get", lambda m: m.get(keys[1234])),
    ("floor", lambda m: m.floor(500_000)),
    ("range_count", lambda m: m.range_count(250_000, 750_000)),
    ("first 3", lambda m: m.first(3)),
]
print("query        hash   sorted answer")
for name, q in queries:
    h.examined = t.examined = 0
    a, b = q(h), q(t)
    print(f"{name:<12} {h.examined:<6} {t.examined:<6} {a if a == b else 'MISMATCH'}")
# query        hash   sorted answer
# get          1      14     792332
# floor        10000  13     499910
# range_count  10000  28     4996
# first 3      10000  0      [32, 132, 514]

Building: the hash map looked at 7,247 keys for 10,000 inserts, about one each. The sorted list did 119,028 comparisons, close to n log₂ n, but also moved almost 25 million slots, because each insert shifts the tail. A balanced tree avoids that cost; a bisect list does not. Querying: the hash map wins get, one key to fourteen, then looks at all 10,000 keys for every ordered question the sorted side answers in a few dozen comparisons at most.

A brute-force check: 2,000 random puts, deletes and queries on small keys, so collisions and repeated keys are common. Both toys must agree with a plain dict answering every ordered question by scanning, and the hand-written binary search must match the standard library's bisect_left:

from bisect import bisect_left

random.seed(2200)
h, t, truth = ChainedMap(), SortedMap(), {}  # truth: a plain dict, answers by brute force
agree = True
for _ in range(2_000):
    op, x = random.choice(["put", "put", "delete", "get", "floor", "range", "first"]), random.randint(0, 300)
    if op == "put":
        for m in (h, t):
            m.put(x, -x)
        truth[x] = -x
    elif op == "delete":
        h.delete(x)
        t.delete(x)
        truth.pop(x, None)
    elif op == "get":
        agree &= h.get(x) == t.get(x) == truth.get(x)
    elif op == "floor":
        want = max((k for k in truth if k <= x), default=None)
        agree &= h.floor(x) == t.floor(x) == want
    elif op == "range":
        want = sum(x <= k <= x + 50 for k in truth)
        agree &= h.range_count(x, x + 50) == t.range_count(x, x + 50) == want
    else:
        agree &= h.first(5) == t.first(5) == sorted(truth)[:5]
    agree &= t._lower(x) == bisect_left(t.keys_, x)   # same loop as the stdlib's bisect
print(len(truth), agree)                   # 190 True

The complexity

• Hash map: O(1) average for get, put and delete; O(n) worst case under heavy collisions. Every ordered query is an O(n) scan, and sorted iteration is O(n log n).
• Balanced tree map: O(log n) worst case for get, put, delete, floor, ceiling, min and max; a range query is O(log n + k) for k results; in-order iteration is O(n).
• Sorted list with bisect: O(log n) search and ordered queries, O(n) insert and delete. Fine when reads dominate or the data is built once.

Where it goes wrong

• Treating dict order as sorted order. It is insertion order. Code that "works" on sorted input breaks the day the input arrives shuffled.
• Calling sorted(d) inside a loop. An O(n log n) sort per query turns a fast program slow. If you need order repeatedly, keep the keys sorted.
• Building a big sorted list one insort at a time. Each insert shifts the tail: O(n²) total. Sort once at the end if you can.
• Using a tree map for pure key lookups. You pay log n comparisons for an order you never use.
• Off-by-one in floor and ceiling. bisect_left and bisect_right differ exactly on equal keys; test the case where x is present.

When it shows up in interviews

Anywhere "nearest" or "between" appears: a time-based key-value store that returns the latest value at or before a timestamp, booking systems that reject overlapping intervals, a leaderboard asked for ranks, a stock price tracker that needs the max. In Python the expected answer is usually dict plus bisect on a sorted list, with the insert cost named out loud.

How to say it in an interview

"A hash map gives me O(1) average lookups but no order, so floor, ceiling, min or range queries are O(n) scans. A tree map keeps keys sorted in a balanced BST: every operation is O(log n), and ordered queries come almost free. Java has TreeMap and C++ has map; Python has no tree map in the standard library, so I would keep a sorted list with bisect, which searches in O(log n) but inserts in O(n), or use a sorted container if allowed."

Frequently asked questions

What is the difference between a hash map and a tree map?

A hash map stores keys by hash, giving O(1) average lookup and no order. A tree map stores keys in a balanced binary search tree, giving O(log n) operations and sorted order, so it can answer floor, ceiling, min, max and range queries without scanning every key.

Does Python have a TreeMap?

Not in the standard library. A dict keeps insertion order, not sorted order. The usual substitute is a sorted list searched with bisect, which gives O(log n) lookups but O(n) inserts, or a third-party sorted container when dependencies are allowed.

When should I use a tree map instead of a hash map?

When you need keys in order or need questions about neighbours: the largest key below x, everything in a range, the minimum or the maximum. If you only ever look up exact keys, a hash map is faster and simpler.