Definition
- HashMap: backed by hash table, O(1) average get/put, no ordering, allows one null key, uses hashCode+equals
- TreeMap: backed by Red-Black tree, O(log n) get/put, sorted key order, no null keys, uses compareTo or Comparator
- NavigableMap: TreeMap provides firstKey, lastKey, floorKey, ceilingKey, subMap, headMap, tailMap
- Use HashMap for fast lookups; use TreeMap when you need sorted keys or range queries
HashMap is a phone book where entries are stored by hash – finding a name is instant but they are in no particular order. TreeMap is a phone book where entries are alphabetically sorted – finding a name takes a few more steps (binary search through the tree), but you can easily ask "who comes after Rajesh?" or "list everyone between M and P."
Understanding the Concepts
What is the difference between TreeMap and HashMap?
| Feature | HashMap | TreeMap |
|---|---|---|
| Internal structure | Hash table (Node[]) | Red-Black tree |
| get/put | O(1) average | O(log n) |
| Ordering | None | Sorted by key |
| Null key | 1 allowed | Not allowed (NPE) |
| Null values | Yes | Yes |
| Equality | hashCode + equals | compareTo or Comparator |
| NavigableMap | No | Yes |
| Memory per entry | ~32 bytes | ~48 bytes |
| Thread-safe | No | No |
| Concurrent equivalent | ConcurrentHashMap | ConcurrentSkipListMap |
package com.bank.demo;
import java.math.BigDecimal;
import java.util.*;
public class TreeMapVsHashMapDemo {
public static void main(String[] args) {
// HashMap: fast, unordered
Map<String, BigDecimal> hashMap = new HashMap<>();
hashMap.put("SAV2001", new BigDecimal("150000"));
hashMap.put("CUR3001", new BigDecimal("75000"));
hashMap.put("FD4001", new BigDecimal("500000"));
System.out.println("HashMap: " + hashMap.keySet());
// TreeMap: sorted by key
TreeMap<String, BigDecimal> treeMap = new TreeMap<>(hashMap);
System.out.println("TreeMap: " + treeMap.keySet());
// TreeMap range query
System.out.println("Range [CUR..SAV): " + treeMap.subMap("CUR3001", "SAV2001"));
System.out.println("Floor of 'G': " + treeMap.floorKey("G"));
}
}
HashMap: [FD4001, CUR3001, SAV2001]
TreeMap: [CUR3001, FD4001, SAV2001]
Range [CUR..SAV): {CUR3001=75000, FD4001=500000}
Floor of 'G': FD4001
When should you use TreeMap?
- Use TreeMap when:
- You need keys in sorted order for reports or display.
- You need range queries: "all accounts between CUR and SAV."
- You need first/last key without scanning all entries.
- You need floor/ceiling/lower/higher lookups.
- Use HashMap when:
- You only need fast key-value lookup.
- Order does not matter.
- You want the best possible performance.
package com.bank.service;
import java.math.BigDecimal;
import java.time.LocalDate;
import java.util.*;
public class TreeMapUseCaseDemo {
public static void main(String[] args) {
// Sorted map of transactions by date
TreeMap<LocalDate, BigDecimal> dailyTotals = new TreeMap<>();
dailyTotals.put(LocalDate.of(2024, 1, 15), new BigDecimal("5000000"));
dailyTotals.put(LocalDate.of(2024, 1, 16), new BigDecimal("3500000"));
dailyTotals.put(LocalDate.of(2024, 1, 17), new BigDecimal("7200000"));
dailyTotals.put(LocalDate.of(2024, 1, 18), new BigDecimal("4100000"));
dailyTotals.put(LocalDate.of(2024, 1, 19), new BigDecimal("6800000"));
// Range query: transactions from Jan 16 to Jan 18 (inclusive)
var range = dailyTotals.subMap(
LocalDate.of(2024, 1, 16), true,
LocalDate.of(2024, 1, 18), true
);
System.out.println("Jan 16-18: " + range);
// Most recent day
System.out.println("Latest: " + dailyTotals.lastEntry());
}
}
Jan 16-18: {2024-01-16=3500000, 2024-01-17=7200000, 2024-01-18=4100000}
Latest: 2024-01-19=6800000
What are common mistakes?
Mistake: Using TreeMap for fast lookups when order is not needed
// WRONG: O(log n) per lookup when O(1) is available
Map<String, String> lookup = new TreeMap<>(); // unnecessary sorting overhead
// CORRECT: use HashMap when order is irrelevant
Map<String, String> lookup = new HashMap<>(); // O(1) lookups
Mistake: TreeMap with keys that have inconsistent compareTo and equals
// TreeMap uses compareTo for equality, not equals!
// If compareTo returns 0 but equals returns false:
// TreeMap considers them the SAME key (overwrites)
// HashMap considers them DIFFERENT keys
What should a senior engineer know?
- TreeMap is a NavigableMap. Always declare as NavigableMap or SortedMap when using TreeMap-specific methods, to make the API contract clear.
- Performance gap. For 1 million entries, HashMap.get is about 5-10x faster than TreeMap.get. This difference matters in high-throughput banking systems.
- ConcurrentSkipListMap. The thread-safe sorted map. Uses a skip list (probabilistic balanced structure) instead of a Red-Black tree. Supports NavigableMap.
What are common interview follow-up questions?
- "When would you use TreeMap over HashMap?" – When you need sorted keys or range queries.
- "What is the internal structure of TreeMap?" – Red-Black tree (self-balancing BST).
- "Why can't TreeMap have null keys?" – compareTo throws NPE on null.
- "What is the time complexity of TreeMap.get?" – O(log n).
Visual Overview
HashMap vs TreeMap
HashMap (hash table):
Bucket 0: null
Bucket 1: [SAV2001→150000]
Bucket 5: [CUR3001→75000]
Bucket 9: [FD4001→500000]
get("SAV2001") → hash → bucket 1 → O(1)
TreeMap (Red-Black tree):
FD4001
/ \
CUR3001 SAV2001
get("SAV2001") → root → right → O(log n)
subMap("CUR","SAV") → traverse left subtree → O(log n + k)
Key Takeaway
HashMap and TreeMap serve different purposes. HashMap is the fastest map with O(1) lookups and no ordering. TreeMap provides sorted keys and NavigableMap range queries at the cost of O(log n) operations.
In the National Bank of India's reporting system, Rajesh uses HashMap for the real-time balance cache (100K lookups per second, order irrelevant) and TreeMap for the daily transaction totals sorted by date (range queries like "totals from January 16 to 18"). He never uses TreeMap when a HashMap would suffice because the O(log n) vs O(1) difference multiplied by millions of operations adds up.
Remember one sentence: HashMap for fast unordered access, TreeMap for sorted keys and range queries – never pay the O(log n) cost when you do not need sorting.
---