HashMap vs TreeMap
HashMap unless you need the keys in order. TreeMap costs you a log factor on every operation and buys ordering, range queries, and the floor and ceiling lookups that a hash table cannot do at all.
The complexity difference is real but small: O(1) against O(log n) means about twenty comparisons on a million keys. The difference that actually decides it is capability. A hash table can tell you whether a key is present. A tree can tell you the nearest key below it, the next one above, and every key in a range, none of which a hash table can answer without scanning everything.
Side by side
| Dimension | HashMap | TreeMap |
|---|---|---|
| Get, put, remove | O(1) average | O(log n) guaranteed |
| Worst case get | O(log n) since Java 8 treeifies buckets | O(log n) |
| Iteration order | Unspecified and may change | Sorted by key |
| Range queries | Not supported | subMap, headMap, tailMap |
| Nearest key | Not supported | floorKey, ceilingKey, higherKey |
| Null keys | One permitted | None, it must compare keys |
| Requires | equals and hashCode | Comparable or a Comparator |
When to pick each
HashMap
- Plain lookup by key, which is the overwhelming majority of cases.
- Counting and grouping, where merge and computeIfAbsent do the work.
- Keys have no meaningful order, such as UUIDs or usernames.
TreeMap
- You need the entries sorted without a separate sort step.
- You need everything in a range, such as all events between two timestamps.
- You need the nearest key below or above a value, which is how consistent hashing finds the next server on the ring.
Mutating an object after using it as a key. A HashMap files the entry under the hash it had at insertion time, so changing a field that hashCode reads makes the entry unreachable while it still occupies the map, and the same key will not find it. TreeMap has the equivalent problem through its comparator. Keys should be immutable, which is most of why String is such a common key type.
Questions people ask
Is a HashMap really O(1)?
On average, with a decent hash. Colliding keys share a bucket, and before Java 8 that made lookups linear in the bucket size, which was exploitable as a denial of service. Java 8 converts a bucket to a balanced tree past eight entries, so the worst case is now O(log n).
What about LinkedHashMap?
It is a HashMap that also keeps a linked list through the entries, giving O(1) operations with predictable iteration order, either insertion order or access order. The access-order mode is an LRU cache in about five lines.
Which for an interview answer about ordering?
Say what kind of order you need. Insertion order is LinkedHashMap, sorted order is TreeMap, and no order is HashMap. Answering with just TreeMap when insertion order was wanted is a common miss.