TreeMap keeps its keys sorted in a red-black tree and needs O(log n) time per operation, whereas HashMap keeps no order and finds a key in O(1) average time through hashing. Both implement the Map interface, so in most code we can swap one for the other by changing the constructor.
We pick HashMap for fast lookups by exact key, such as caches, indexes and counters, and TreeMap when we need the keys in order or need range and nearest-key queries. The following example puts the same entries into both maps.
HashMap<String, Integer> hashMap = new HashMap<>(Map.of("pear", 3, "apple", 5, "fig", 7));
TreeMap<String, Integer> treeMap = new TreeMap<>(hashMap);
Integer fromHash = hashMap.get("fig"); // 7
Integer fromTree = treeMap.get("fig"); // 7
Set<String> hashKeys = hashMap.keySet(); // order depends on hash codes
Set<String> treeKeys = treeMap.keySet(); // [apple, fig, pear]
String smallest = treeMap.firstKey(); // "apple"
Integer nullKey = treeMap.put(null, 0); // NullPointerExceptionBoth maps return the same values, but only the TreeMap gives a sorted key set and a first key, and only the HashMap accepts a null key. We go through each difference, and the last sections tell when to use which map, including LinkedHashMap as a third option.
1. Differences between HashMap and TreeMap
The two classes differ in how they store entries, and every other difference follows from that. The summary table answers the common questions, and the subsections explain each row with code.
| Feature | HashMap | TreeMap |
|---|---|---|
| Data structure | Array of buckets (hash table) | Red-black tree |
| Iteration order | None guaranteed | Sorted by key (natural order or Comparator) |
| get(), put(), remove() | O(1) on average | O(log n) |
| Null key | One allowed | NullPointerException with natural ordering |
| Null values | Allowed | Allowed |
| Key equality | hashCode() and equals() | compareTo() or compare() |
| Extra methods | None beyond Map | NavigableMap methods (floor, ceiling, ranges) |
| Tuning | Initial capacity and load factor | None |
| Thread-safe | No | No |
1.1. Class Hierarchy
Both classes extend AbstractMap. HashMap implements only Map, whereas TreeMap implements NavigableMap, which extends SortedMap and, since Java 21, SequencedMap.
// does not compile: declaration lines from the JDK source, bodies left out
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable
public class TreeMap<K, V> extends AbstractMap<K, V> implements NavigableMap<K, V>, Cloneable, SerializableBecause of the interface, we can declare a TreeMap as NavigableMap or SortedMap and still call the ordering methods, while a HashMap is always used as a plain Map.
1.2. Internal Implementation
A HashMap keeps an array of buckets. It computes the bucket from the key’s hash code, and keys in the same bucket form a short linked list. Since Java 8, a bucket with more than 8 entries turns into a small red-black tree, but only when the table already has at least 64 buckets; a smaller table is resized instead. The article on how HashMap works covers these steps in detail.
A TreeMap has no array at all. Every entry is a node of one red-black tree, a binary search tree that rebalances itself after each change, so its height stays at about log n.
Note that HashMap does not use the legacy Hashtable class internally. Both classes use the hash table technique, but they are separate implementations.
1.3. Null Keys and Values
A HashMap allows one null key, and a second put(null, …) replaces the value of the first. A TreeMap with natural ordering calls compareTo() on every new key, so a null key throws NullPointerException. Both maps accept any number of null values.
HashMap<String, String> settings = new HashMap<>();
settings.put(null, "default");
settings.put(null, "fallback");
String nullEntry = settings.get(null); // "fallback"
TreeMap<String, String> sorted = new TreeMap<>();
sorted.put("theme", null);
boolean nullValueOk = sorted.containsKey("theme"); // true
String failed = sorted.put(null, "default"); // NullPointerExceptionA TreeMap accepts one null key only when we give it a comparator that handles null, such as Comparator.nullsFirst(Comparator.naturalOrder()).
1.4. Functionality
TreeMap has more methods than HashMap. Along with the Map methods, it offers the NavigableMap methods for the first and last keys, the nearest key and key ranges.
TreeMap<String, Integer> prices = new TreeMap<>(Map.of("apple", 5, "fig", 7, "pear", 3, "plum", 4));
String first = prices.firstKey(); // "apple"
String last = prices.lastKey(); // "plum"
Map.Entry<String, Integer> firstEntry = prices.firstEntry(); // apple=5
String beforePear = prices.lowerKey("pear"); // "fig"
SortedMap<String, Integer> fromP = prices.tailMap("p"); // {pear=3, plum=4}
Map.Entry<String, Integer> polled = prices.pollLastEntry(); // plum=4
String remaining = prices.toString(); // "{apple=5, fig=7, pear=3}"With a HashMap, each of these lines needs a loop over all entries or a sort, which costs O(n) or O(n log n) per call.
1.5. Element Ordering
A HashMap makes no promise about iteration order. The order follows the bucket positions, so it depends on the hash codes and the table size, and it can change when the map resizes or when a key’s hashCode() implementation changes. Tests that compare the printed HashMap with a fixed string break for that reason.
A TreeMap always returns its keys in ascending order, either by natural order or by the Comparator passed to the constructor.
Map<Integer, String> source = Map.of(10, "ten", 2, "two", 13, "thirteen", 5, "five");
TreeMap<Integer, String> ascending = new TreeMap<>(source);
String up = ascending.toString(); // "{2=two, 5=five, 10=ten, 13=thirteen}"
TreeMap<Integer, String> descending = new TreeMap<>(Comparator.reverseOrder());
descending.putAll(source);
String down = descending.toString(); // "{13=thirteen, 10=ten, 5=five, 2=two}"When we only need the insertion order and not a sorted order, LinkedHashMap gives it with HashMap speed.
1.6. Performance Comparison
HashMap is faster for single-key operations. Its get(), put(), containsKey() and remove() run in O(1) time on average, because one hash computation leads to the right bucket.
- When many keys share a bucket, a linked bucket costs O(k) for its k entries. A treeified bucket costs O(log k), and the tree is ordered by compareTo() when the keys are Comparable.
- A resize rehashes all entries, which costs O(n) once, but the average cost per put() stays O(1).
- A TreeMap takes O(log n) for every basic operation and for every navigation method, with no bad case, because the tree stays balanced.
The constant factors matter too. A TreeMap lookup calls compareTo() about log n times, for example around 20 times in a map of one million keys, while a HashMap lookup computes one hash and, with a good hash function, calls equals() about once. For exact-key lookups in large maps, HashMap is the faster choice; for sorted iteration or range queries, TreeMap avoids a separate sort.
1.7. Memory Usage
The memory use of the two maps is close, and neither one is the clear winner. A TreeMap node holds the key, the value, three references (left, right, parent) and a color flag, whereas a HashMap node holds the key, the value, the cached hash and one next reference. So each TreeMap node is bigger, but a HashMap also keeps its bucket array, which has empty slots because the table resizes at 75% load.
On a 64-bit JVM with compressed references, a HashMap node takes 32 bytes and a TreeMap node takes 40 bytes, not counting the key and value objects. With one million entries, the HashMap table has 2,097,152 slots of 4 bytes each, which adds about 8 bytes per entry, so both maps end up at about 40 bytes per entry. The HashMap figure moves up and down with the fill level of its table, so the difference between the two is too small to drive the choice of map.
Pick between the two maps by ordering and speed, not by memory. If we know how many entries a HashMap will hold, we create it with HashMap.newHashMap(expectedSize) (Java 19), which sizes the table once for that number and avoids repeated resizing.
1.8. Key Searches
HashMap decides whether two keys are the same with hashCode() and equals(), whereas TreeMap uses only compareTo() or the comparator. For most key types, both give the same answer, and putting an existing key replaces the value in both maps while the original key object stays.
HashMap<Integer, String> hashMap = new HashMap<>();
hashMap.put(10, "value1");
hashMap.put(10, "value2");
String inHashMap = hashMap.toString(); // "{10=value2}"
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(10, "value1");
treeMap.put(10, "value2");
String inTreeMap = treeMap.toString(); // "{10=value2}"The answers differ when compareTo() is not consistent with equals(). BigDecimal is the classic case, because new BigDecimal(“1.0”) and new BigDecimal(“1.00”) are not equal (different scale), but compareTo() returns 0 for them.
HashMap<BigDecimal, String> hashPrices = new HashMap<>();
hashPrices.put(new BigDecimal("1.0"), "first");
hashPrices.put(new BigDecimal("1.00"), "second");
int hashSize = hashPrices.size(); // 2
TreeMap<BigDecimal, String> treePrices = new TreeMap<>();
treePrices.put(new BigDecimal("1.0"), "first");
treePrices.put(new BigDecimal("1.00"), "second");
String treeContent = treePrices.toString(); // "{1.0=second}"A billing app that groups invoice lines by price would show two groups with a HashMap and one group with a TreeMap. We normalize such keys first, for example with stripTrailingZeros(), so both maps agree.
2. When to Use HashMap and TreeMap
The choice comes down to whether the code needs the keys in order. If it does not, HashMap is faster and simpler; if it does, TreeMap keeps them sorted at all times without a separate sort step.
| Situation | Pick |
|---|---|
| Lookups by exact key, caches, counters, indexes | HashMap |
| Keys printed or processed in sorted order | TreeMap |
| Nearest key, ranges, first or last key | TreeMap |
| Keys in insertion order, such as JSON fields | LinkedHashMap |
| A null key is needed | HashMap or LinkedHashMap |
| Sorted map shared by threads | ConcurrentSkipListMap |
| Unsorted map shared by threads | ConcurrentHashMap |
Say a dictionary app shows the definition of a word and an alphabetical word list with “previous” and “next” buttons. A HashMap serves the definition lookup fastest, but the word list and the buttons need sorted keys. A TreeMap serves all three, because lowerKey() and higherKey() return the neighbors of the current word in O(log n).
TreeMap<String, String> dictionary = new TreeMap<>(Map.of("apple", "a fruit", "banana", "a long fruit", "cherry", "a small fruit"));
String definition = dictionary.get("banana"); // "a long fruit"
String previous = dictionary.lowerKey("banana"); // "apple"
String next = dictionary.higherKey("banana"); // "cherry"Many apps use both maps. They keep a HashMap as the main store and copy it into a TreeMap with new TreeMap<>(map) only when a sorted report is needed, which costs O(n log n) once per report. The Java Collections guide lists the other Map types for less common needs.
3. TreeMap vs HashMap FAQs
Speed and memory are the two topics most questions about the two maps cover.
3.1. Which is faster, HashMap or TreeMap?
HashMap, for get(), put() and remove(), which take O(1) average time against O(log n) for TreeMap. TreeMap is faster only for order-based work such as sorted iteration or range queries, which a HashMap cannot do without sorting first.
3.2. Does TreeMap use equals() to compare keys?
No. TreeMap uses only compareTo() or the comparator, and treats keys as equal when the result is 0. The BigDecimal example in section 1.8 shows the effect.
3.3. Which uses more memory, HashMap or TreeMap?
About the same. Each TreeMap node is larger, but a HashMap adds a bucket array with empty slots, and with one million entries both need about 40 bytes per entry, as described in section 1.7.
3.4. Can we sort a HashMap?
Not in place. We either copy it into a TreeMap to sort by key, or stream the entries, sort them and collect them into a LinkedHashMap, as shown in sorting a map by keys.
3.5. What is the difference between HashMap, LinkedHashMap and TreeMap?
All three implement Map. HashMap keeps no order, LinkedHashMap keeps insertion order or access order at nearly the same speed, and TreeMap keeps the keys sorted at O(log n) per operation.
4. Conclusion
HashMap and TreeMap answer different questions. HashMap finds a key fast and allows a null key, but its order is unpredictable; TreeMap keeps the keys sorted and offers navigation and range methods at O(log n) per operation.
Two details often surprise developers. A TreeMap compares keys with compareTo(), so keys that are equal by comparison but not by equals() merge. And neither map saves meaningful memory over the other, so memory is not a reason to pick TreeMap.
5. References
- HashMap Javadoc (Java 25)
- TreeMap Javadoc (Java 25)
- Comparable Javadoc (Java 25)
- OpenJDK 25 source, HashMap.java
- JEP 180: Handle Frequent HashMap Collisions with Balanced Trees
Happy Learning !!
