Java HashMap vs TreeMap: Ordering, Performance, and Null Handling

Choose HashMap for fast lookups when iteration order does not matter. Choose TreeMap when you need keys in sorted order or range queries. Both implement the Map interface, but their ordering, performance, and null handling differ enough that the choice matters.

Ordering Guarantees

HashMap makes no promises about iteration order. It stores entries in buckets based on the hash of the key, and the order in which keys appear when you iterate depends on the hash values, the table size, and the collision resolution strategy. Two HashMap instances with the same entries can iterate in different orders, and even the same instance may change order after a resize.

TreeMap maintains entries in sorted order. By default, it sorts keys according to their natural ordering, meaning the key type must implement Comparable. You can also supply a Comparator to define a custom order. Iteration always follows that order, so the first key is the smallest and the last is the largest.

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("banana", 2);
hashMap.put("apple", 1);
hashMap.put("cherry", 3);
System.out.println(hashMap.keySet()); // order not guaranteed

Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("banana", 2);
treeMap.put("apple", 1);
treeMap.put("cherry", 3);
System.out.println(treeMap.keySet()); // [apple, banana, cherry]

If your code relies on iteration order, TreeMap gives you a deterministic sequence. HashMap is the wrong choice unless you explicitly sort the keys before processing.

Performance Characteristics

The two maps use fundamentally different data structures. HashMap is backed by an array of buckets, each bucket holding a linked list or tree (since Java 8) when collisions occur. Lookup, insertion, and removal average O(1) time, assuming a good hash function and adequate capacity. Worst-case behavior degrades to O(log n) when many keys collide into a single tree bucket, but that is rare with a well-distributed hash.

TreeMap is a red-black tree, a self-balancing binary search tree. Every operation—put, get, remove, containsKey—runs in O(log n) time. That is significantly slower than O(1) for large maps, but the tree structure provides the sorted order and range queries.

// HashMap: average O(1) put/get
Map<Integer, String> hashMap = new HashMap<>();
for (int i = 0; i < 100000; i++) {
    hashMap.put(i, "value" + i);
}

// TreeMap: O(log n) put/get
Map<Integer, String> treeMap = new TreeMap<>();
for (int i = 0; i < 100000; i++) {
    treeMap.put(i, "value" + i);
}

For most lookup-heavy workloads, HashMap is the faster choice. The logarithmic cost of TreeMap only pays off when you need sorted iteration or range operations.

Null Keys and Values

HashMap allows exactly one null key and any number of null values. The null key is stored in a dedicated bucket, and get(null) works as expected.

TreeMap does not allow a null key by default. Because the tree must compare keys to maintain order, a null key throws a NullPointerException at insertion time, unless you provide a Comparator that explicitly handles null. Null values are allowed in both implementations.

Map<String, String> hashMap = new HashMap<>();
hashMap.put(null, "null key"); // OK
hashMap.put("key", null);     // OK

Map<String, String> treeMap = new TreeMap<>();
treeMap.put(null, "boom"); // throws NullPointerException

If your data may contain a null key, HashMap is the safer default. If you need a sorted map and must support null keys, you have to write a comparator that defines where null belongs in the ordering.

Custom Ordering with Comparator

TreeMap accepts a Comparator in its constructor, giving you control beyond natural ordering. This is useful when keys are not Comparable or when you want a different sort order, such as case-insensitive strings or reverse order.

Map<String, Integer> reverseMap = new TreeMap<>(Comparator.reverseOrder());
reverseMap.put("a", 1);
reverseMap.put("b", 2);
reverseMap.put("c", 3);
System.out.println(reverseMap.keySet()); // [c, b, a]

Map<String, Integer> lengthMap = new TreeMap<>(Comparator.comparingInt(String::length));
// Note: this comparator is not consistent with equals, use with care

When using a comparator, ensure it is consistent with equals to avoid violating the Map contract. An inconsistent comparator can make the map treat different keys as duplicates, or equal keys as separate entries, leading to unexpected containsKey results.

HashMap has no notion of ordering, so it cannot accept a comparator. If you need custom ordering, TreeMap is the standard sorted implementation for single-threaded code; ConcurrentSkipListMap provides the same capability when thread safety is also required.

Additional NavigableMap Operations

TreeMap implements NavigableMap, which provides methods for range queries and nearest-key lookups. These methods are not available on HashMap.

firstKey() and lastKey() return the smallest and largest keys.
subMap(fromKey, toKey) returns a view from fromKey (inclusive) to toKey (exclusive) by default.
headMap(toKey) returns a view below toKey (exclusive), and tailMap(fromKey) returns a view from fromKey (inclusive).
floorKey(key), ceilingKey(key), lowerKey(key), and higherKey(key) find the nearest keys.

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(1, "one");
treeMap.put(3, "three");
treeMap.put(5, "five");
treeMap.put(7, "seven");

System.out.println(treeMap.ceilingKey(4)); // 5
System.out.println(treeMap.floorKey(4));   // 3
System.out.println(treeMap.subMap(2, 6));  // {3=three, 5=five}

firstKey(), lastKey(), and the nearest-key lookups are O(log n) operations. The range-view methods (subMap, headMap, tailMap) let you work with only the selected span rather than scanning the whole map. These capabilities are the main reason to choose TreeMap when you need to answer questions like "what is the next key greater than X" or "give me all entries between two bounds." HashMap cannot do this without scanning the entire map.

Concurrency and Thread Safety

Neither HashMap nor TreeMap is thread-safe. If multiple threads access the same map concurrently and at least one modifies it, you must synchronize externally or use a concurrent implementation.

For HashMap, the standard concurrent replacement is ConcurrentHashMap, which offers better scalability than synchronizing the whole map. For TreeMap, there is no concurrent drop-in replacement, but ConcurrentSkipListMap gives you a sorted concurrent map. You can also wrap TreeMap with Collections.synchronizedSortedMap, but that serializes all access and does not support concurrent reads well.

// Thread-safe sorted map
Map<Integer, String> concurrentSortedMap = new ConcurrentSkipListMap<>();

If your application is single-threaded, the thread-safety difference is irrelevant. In a multi-threaded environment, decide whether you need sorted order; if not, ConcurrentHashMap is usually the better choice.

Memory and Overhead

HashMap uses an array of buckets plus per-entry objects. Its memory footprint depends on the load factor and capacity. TreeMap uses a red-black tree with nodes that store color, parent, left, and right pointers, so each entry carries more overhead than a HashMap entry. For very large maps, this difference can be significant, but it is rarely the deciding factor unless memory is extremely constrained.

HashMap also resizes when the number of entries exceeds the load factor threshold, which can cause temporary memory spikes. TreeMap grows incrementally without resizing, so its memory usage is more predictable.

When to Use Each Map

Choose HashMap when you need fast lookups and do not care about iteration order. It is the default choice for most key-value storage, caching, and indexing scenarios. The O(1) average performance and null-key support make it the most flexible general-purpose map.

Choose TreeMap when you need sorted iteration, range queries, or nearest-key operations. If you are building a leaderboard, a calendar of events, or any structure where keys must be processed in order, TreeMap provides that behavior directly. The O(log n) cost is acceptable when the map size is moderate or when the sorted order is a hard requirement.

A hybrid approach is also common: use a HashMap for fast access and maintain a separate sorted structure if you occasionally need ordered views. That adds complexity but can give you the best of both worlds when the sorted operations are rare.

Handling Custom Keys Correctly

When using custom objects as keys, HashMap relies on hashCode() and equals(), while TreeMap relies on Comparable or a Comparator. If your key class does not implement Comparable, TreeMap will throw a ClassCastException at insertion time unless you provide a comparator.

class Person {
    String name;
    int age;
    // equals and hashCode implemented
}

// TreeMap requires Comparable or Comparator
Map<Person, String> people = new TreeMap<>((p1, p2) -> p1.name.compareTo(p2.name));
people.put(new Person("Alice", 30), "engineer");

For HashMap, ensure that hashCode() is stable and consistent with equals(). A mutable key that changes its hash after insertion will be lost in the map. This is a common bug that affects both maps, but TreeMap is more forgiving if the comparator is based on immutable fields.

Compatibility with Java Versions

Both HashMap and TreeMap have been part of the Java Collections Framework since Java 1.2. No version-specific behavior affects the core differences described here. Java 8 introduced tree bins in HashMap to improve worst-case collision handling, but that does not change the practical ordering or performance characteristics for typical usage.

When you upgrade to newer Java versions, the behavior of these maps remains stable. The NavigableMap methods in TreeMap have been available since Java 6, so code written today works across modern JDKs without modification.