Use a hash map by default: lookups, inserts and deletes are O(1) on average, with no order. Use a tree map when you need keys in sorted order, or questions like the first key at or above x: every operation is O(log n), and balanced tree maps have no linear worst case. The trade is speed against order.
Hash maps and tree maps compared
| Hash map | Tree map, balanced | |
|---|---|---|
| Lookup, insert, delete | O(1) on average | O(log n) |
| Worst case per operation | O(n), if keys collide | O(log n) |
| Keys in sorted order | No, sort them first: O(n log n) | Yes: O(n) to walk |
| First key at or above x | O(n) | O(log n) |
| What a key needs | A hash and equality | An ordering |
| Space | O(n) | O(n) |
Here is what each language documents, since you may be asked about yours:
| Language | Hash map | Tree map |
|---|---|---|
| Java | HashMap: constant-time get and put, assuming the hash disperses elements properly | TreeMap: guaranteed log(n) for containsKey, get, put and remove |
| C++ | unordered_map: average O(1), worst case O(size) | map: logarithmic find and insert |
| Python | dict: O(1) on average, O(n) in the worst case | None built in. A sorted list with bisect is the usual substitute. |
| JavaScript | Map: sublinear on average | None built in. |
A worked example where both apply
Keep a schedule of booked hours, and for any hour find the next booking at or after it. A hash map stores the bookings but has to scan to answer. A tree map answers directly.
Java
import java.util.*;
class NextBooking {
// HashMap: put is constant time, but finding the next hour scans every key.
static Integer nextWithHashMap(Map<Integer, String> bookings, int hour) {
Integer best = null;
for (int h : bookings.keySet()) {
if (h >= hour && (best == null || h < best)) best = h;
}
return best;
}
// TreeMap: ceilingKey finds it by walking down the tree.
static Integer nextWithTreeMap(TreeMap<Integer, String> bookings, int hour) {
return bookings.ceilingKey(hour);
}
}With n bookings and q queries, the hash map costs O(n · q) for the queries. The tree map's documented operations are log(n), and its navigation methods walk the same tree, though the Javadoc does not state a figure for ceilingKey. If queries are rare and lookups by exact hour are common, the hash map is still the better choice, and you can sort its keys on the rare occasion you need them.
Which to pick in an interview, and how to say why
- Exact lookups, counting, grouping, seen sets: a hash map, nearly always.
- Sorted output, once: a hash map, then sort the keys at the end.
- Sorted order or ranges while the data keeps changing: a tree map.
- A bound with no bad case: a tree map, and say why you need it.
I only need exact lookups, so I'll use a hash map, which is O(1) on average and O(n) if keys collide badly. If I needed the next key at or above a value while the data keeps changing, a hash map would have to scan, so I'd use a tree map and pay log n per operation in exchange for sorted keys. If I only needed sorted output once at the end, I'd stay with the hash map and sort, which is O(n log n) one time.