What Is an Ordered Map? The Data Structure Behind Range Queries

You reach for a hash map. Fast lookups, O(1) average, clean code. Then the requirements doc updates. "Find all keys between 100 and 200." Or: "What's the smallest key greater than X?" Your hash map stares back at you. It has never heard of order. It doesn't think about order. Order is not its problem.

Welcome to the moment every engineer eventually meets: the data structure you defaulted to cannot do the thing you now need.

An ordered map (also called a sorted map) is a key-value store where every key is always kept in sorted order. Insertions, deletions, lookups: every operation preserves the sorted invariant. You pay O(log n) instead of O(1), and in return you get a whole class of operations a hash map can never offer without a full scan.

Why Hash Maps Break Here

A hash map scatters keys across buckets based on a hash function. The physical location of key 5 has nothing to do with key 6. Order is meaningless to the implementation. So when you ask "give me everything between 100 and 200," the hash map has to look at every single entry.

An ordered map stores keys in a balanced binary search tree, typically a Red-Black tree, which keeps every operation at O(log n) because the height never exceeds that. The BST property guarantees that for any node, every key in the left subtree is smaller and every key in the right subtree is larger. Rotations keep the tree balanced after insertions and deletions.

If you want the rotation mechanics, this breakdown covers the Red-Black tree in detail. The short version: the color invariants keep the tree within a constant factor of minimum height.

The point is that structure means something. The BST knows where things live relative to each other. The hash map does not.

What You Trade

Operation	Hash Map	Ordered Map
Insert	O(1) avg	O(log n)
Delete	O(1) avg	O(log n)
Lookup	O(1) avg	O(log n)
Minimum key	O(n)	O(log n)
Maximum key	O(n)	O(log n)
Floor/ceiling	O(n)	O(log n)
Ordered iteration	O(n log n)	O(n)
Range query	O(n)	O(log n + k)

Space is O(n) for both. Each ordered map node stores a key, value, two child pointers, a parent pointer, and a color bit, so the constant factor is higher. Still linear.

The O(n log n) for "ordered iteration" from a hash map is not a typo. You dump all keys into a list and sort. An ordered map does an in-order traversal of the BST and produces keys in sorted order in O(n), free. If you find yourself writing Arrays.sort(map.keySet().toArray()) regularly, you have picked the wrong container.

In-order traversal visits keys in sorted order. A range query just stops when it exits the window.

The Operations That Make It Worth It

A hash map has get, put, and delete. An ordered map has all of those plus a small set of operations that make range problems feel trivial:

Floor and ceiling. floor(k) returns the largest key less than or equal to k. ceiling(k) returns the smallest key greater than or equal to k. Both are O(log n) walks down the BST to find a boundary. Absolutely nothing in a hash map does this without a full scan.

First and last key. Minimum and maximum in O(log n) by walking left or right to the leaf.

Range queries. All key-value pairs between lo and hi. The traversal starts at the first in-range key and walks in-order until it exits the range. Cost: O(log n) to find the start, then O(k) to collect k results.

Predecessor and successor. The previous and next key relative to any given key.

Here is the API in Java, where the class is TreeMap:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "ten");
map.put(30, "thirty");
map.put(20, "twenty");
map.put(5, "five");

map.firstKey();          // 5
map.lastKey();           // 30
map.floorKey(22);        // 20  (largest key <= 22)
map.ceilingKey(22);      // 30  (smallest key >= 22)
map.headMap(20);         // {5=five, 10=ten}  (keys strictly < 20)
map.tailMap(20);         // {20=twenty, 30=thirty}  (keys >= 20)
map.subMap(10, 30);      // {10=ten, 20=twenty}  (10 inclusive, 30 exclusive)

In C++, std::map is the ordered map. It uses lower_bound(k) (first key >= k) and upper_bound(k) (first key > k):

std::map<int, std::string> m;
m[10] = "ten"; m[30] = "thirty"; m[20] = "twenty"; m[5] = "five";

auto it = m.lower_bound(22);   // iterator to 30
--it;                           // iterator to 20 (floor of 22)
m.begin()->first;               // 5 (minimum)

Python has no built-in ordered map. dict preserves insertion order since 3.7, but insertion order is not sorted order. For a true sorted map you need sortedcontainers.SortedDict from a third-party library, or you can approximate using the bisect module on a sorted key list alongside a regular dict. Java and C++ candidates get the native implementation for free; Python candidates often need to build it or explain why they're reaching for a third-party dep. Know this going in.

Hash Map or Ordered Map?

The decision is not complicated once you see the shape. Use an ordered map when the problem cares about the relative order of keys, not just whether a key exists. A few patterns that come up constantly:

• Range queries. "How many bookings overlap this time window?" Store start times as keys. A subMap call extracts the relevant entries without scanning everything.
• Nearest-neighbor lookup. "What is the closest temperature reading to 72°F?" Floor and ceiling give you the answer in O(log n). A hash map requires a full scan.
• Sliding window with ordered invariant. A TreeMap holding window elements with counts lets you track the minimum as the first key and the maximum as the last key, updating in O(log n) per element.
• Scheduling problems. Calendars, event timelines, and interval stores all need O(log n) neighbor lookups that a hash map cannot provide.

If your problem only needs exact lookups, use the hash map. If it needs any concept of "nearby" or "in range," use the ordered map. BST vs Hash Map covers the full decision tree. For the Java-specific tradeoff, HashMap vs TreeMap walks through the cases where O(log n) beats amortized O(1) in practice.

Where This Shows Up in Interviews

Ordered maps show up in a handful of problem shapes often enough that recognizing them is the whole game.

My Calendar problems. Store existing bookings in a TreeMap. For each new booking, check whether the floor entry overlaps and whether the ceiling entry overlaps. Two O(log n) lookups replace a full scan. Interviewers love these because they separate candidates who know the library from candidates who iterate.

Sliding window median. Maintain two ordered maps as a lower half and upper half. The median lives at the boundary. Insertions and deletions are O(log n) each.

Count of smaller numbers after self. A TreeMap with a headMap size call is a readable alternative to coordinate compression plus a Fenwick tree. This one surprises a lot of candidates.

Interval merge and insert. Store intervals keyed by start time. Find neighbors in O(log n) per insertion, then merge as needed.

The pattern to recognize: whenever a problem involves finding the nearest key, querying a range, or iterating in sorted order, an ordered map will produce a cleaner solution than the hash map alternative. If you find yourself sorting a hash map's keys inside a loop, something has gone wrong upstream.

What the Interview Actually Tests

Interviewers asking ordered-map problems are checking two things. First: do you know this data structure exists? A lot of candidates reach for a hash map plus a sort, which technically works but burns O(n log n) for operations that should be O(log n). Calling out TreeMap.floorKey or std::map::lower_bound signals that you know the library.

Second: do you understand why it costs O(log n)? "It's backed by a Red-Black tree, and walking a path to the leaf is O(log n)" answers the follow-up before it's asked. That one sentence turns a solved problem into a strong hire signal.

One misconception worth killing: an ordered map is not a sorted array. A sorted array gives you O(log n) binary search for lookups, yes. But insertions cost O(n) because you have to shift elements. An ordered map handles insertions in O(log n) because the BST absorbs elements by walking down one path and rebalancing locally. No shifting. No O(n) cost hiding in your analysis.

If you want to practice problems that use ordered maps under real time pressure, SpaceComplexity runs voice-based mock interviews with rubric feedback on exactly this kind of data structure decision. The pressure is the point.

Further Reading

• Java TreeMap documentation (Oracle)
• cppreference: std::map
• Red-Black tree (Wikipedia)
• sortedcontainers documentation (Python)
• Binary search tree (GeeksforGeeks)