TreeMap and HashMap both store key-value pairs, but they make different tradeoffs. One optimizes average lookup speed by hashing. The other keeps keys sorted and supports navigation by order.
Quick answer
Use HashMap when you need general-purpose key-value lookup and do not need sorted keys. Use TreeMap when sorted iteration, range queries, nearest keys, or ordered views are part of the requirement.
For most backend code, start with HashMap. Choose TreeMap when ordering is a real feature, not just a nice-to-have.
Main difference
HashMap stores entries in a hash table. It uses hashCode() and equals() to find keys.
TreeMap stores entries in a sorted tree. It uses natural key ordering or a Comparator.
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("zebra", 3);
hashMap.put("apple", 1);
hashMap.put("mango", 2);
System.out.println(hashMap.keySet()); // order is not guaranteedMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("zebra", 3);
treeMap.put("apple", 1);
treeMap.put("mango", 2);
System.out.println(treeMap.keySet()); // [apple, mango, zebra]If the order of keys is part of the API response, report, or business rule, the map type matters.
Complexity comparison
| Operation | HashMap | TreeMap |
|---|---|---|
get | Average O(1) | O(log n) |
put | Average O(1) | O(log n) |
remove | Average O(1) | O(log n) |
| Sorted key iteration | Not guaranteed | O(n) in key order |
| Range query | Not supported directly | Supported |
| Nearest lower or higher key | Not supported directly | Supported |
HashMap can have worse behavior under poor hash distribution, but it is still the usual default. TreeMap pays O(log n) so it can maintain sorted keys.
When HashMap fits
Use HashMap for ordinary lookup tables:
Map<Long, UserProfile> profilesById = new HashMap<>();
for (UserProfile profile : profiles) {
profilesById.put(profile.id(), profile);
}
UserProfile profile = profilesById.get(userId);This pattern appears in service methods, grouping logic, DTO assembly, caching inside a request, and joining data from multiple sources.
If you only need “find by exact key,” HashMap is usually simpler and faster.
When TreeMap fits
Use TreeMap when the code needs ordered navigation.
NavigableMap<LocalDate, BigDecimal> revenueByDay = new TreeMap<>();
revenueByDay.put(LocalDate.parse("2026-06-01"), BigDecimal.valueOf(1200));
revenueByDay.put(LocalDate.parse("2026-06-03"), BigDecimal.valueOf(900));
Map.Entry<LocalDate, BigDecimal> latestBefore =
revenueByDay.floorEntry(LocalDate.parse("2026-06-02"));TreeMap can answer questions such as:
- What is the first key?
- What is the last key?
- What is the nearest key less than this value?
- Which entries fall between two keys?
- How do I iterate keys in sorted order without sorting every time?
That makes it useful for time ranges, thresholds, ordered configuration rules, leaderboard cutoffs, and interval-style lookups.
Null handling
HashMap allows one null key and multiple null values.
TreeMap usually does not allow null keys with natural ordering because keys must be comparable. Values can be null, but using null values can make get ambiguous because the key may be missing or mapped to null.
In backend code, prefer explicit absence handling when possible. containsKey, Optional, validation, or a domain-specific default is usually clearer than storing nulls.
Comparator rules
TreeMap uniqueness depends on key comparison. If the comparator returns 0, the map treats two keys as the same key.
Map<String, Integer> counts = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
counts.put("API", 1);
counts.put("api", 2);
System.out.println(counts.size()); // 1
System.out.println(counts.get("API")); // 2This can be useful for case-insensitive keys, but it must be intentional. A comparator that ignores important fields can overwrite entries.
Memory and performance notes
HashMap stores an internal table and entries. It may resize when the load factor threshold is crossed. Read HashMap Load Factor Explained for capacity and resizing details.
TreeMap stores tree nodes with parent, left, right, and color metadata. It avoids hash distribution concerns but pays for ordering through comparisons and tree navigation.
For small maps, readability may matter more than raw complexity. For hot paths, benchmark with realistic data and key types.
Query pattern checklist
The deciding question is usually not “which map is better?” It is “what questions will the code ask the map?” If the code mostly asks for exact keys, HashMap keeps the implementation simple. If the code asks for nearest keys, sorted iteration, prefixes, ranges, or ordered windows, TreeMap may express the requirement directly.
For example, rate-limit buckets keyed by exact user ID usually fit HashMap. A scheduler that needs the next run time after now can fit TreeMap because ceilingKey and firstEntry are part of the structure’s natural API. Matching the data structure to the query shape makes the code easier to review.
Common mistakes
The first mistake is choosing TreeMap just because sorted output looks nicer in logs. If the code only needs lookup, sort a view when printing or returning output.
The second mistake is assuming HashMap iteration order is stable. It is not part of the contract.
The third mistake is using mutable keys. If a key changes after insertion, both hash-based and tree-based maps can behave incorrectly.
The fourth mistake is forgetting that comparator behavior defines key uniqueness in TreeMap.
Related reading
Read HashMap vs Hashtable in Java, Java equals and hashCode Explained, and HashMap Collision Handling Explained for hash map fundamentals. Read HashSet vs TreeSet in Java for the set version of the same ordering tradeoff. Use Time Complexity of Java Collections and the Big-O Cheat Sheet when reviewing map choices. For the full sequence, browse the Java Collections Learning Path and the Topics map.