What is the difference between TreeMap and HashMap in Java?

1. Short Answer

HashMap and TreeMap both implement the Map interface, but they differ fundamentally in their internal data structure and guarantees:

• HashMap — backed by a hash table; O(1) average get/put; no ordering of keys; allows one null key.
• TreeMap — backed by a Red-Black tree; O(log n) get/put; keys always in sorted order; does not allow null keys.

2. Detailed Explanation

2.1 HashMap Internals

HashMap uses an array of buckets (initial capacity 16, load factor 0.75). Each bucket holds a linked list of entries (or a red-black tree if the bucket length exceeds 8, since Java 8). When you call put(key, value):

1. The key's hashCode() is computed and mixed (spread) to reduce collisions.
2. The bucket index is derived from the mixed hash.
3. The key-value pair is stored in that bucket (chained if collisions exist).

This gives O(1) average time with a good hash function, but O(n) worst case if all keys collide.

2.2 TreeMap Internals

TreeMap uses a Red-Black tree — a self-balancing binary search tree. Every node stores a key-value pair. The tree is always sorted by key using the natural ordering (Comparable) or a supplied Comparator. Because the tree must stay balanced, every operation (get, put, remove) traverses O(log n) nodes.

TreeMap implements NavigableMap, which extends SortedMap, providing rich navigation methods not available in HashMap.

2.3 Key Differences at a Glance

2.4 NavigableMap Features of TreeMap

TreeMap's NavigableMap interface provides powerful range and navigation methods:

• firstKey() / lastKey() — smallest / largest key in the map.
• floorKey(k) — greatest key less than or equal to k.
• ceilingKey(k) — smallest key greater than or equal to k.
• lowerKey(k) — greatest key strictly less than k.
• higherKey(k) — smallest key strictly greater than k.
• subMap(from, fromInclusive, to, toInclusive) — view of entries between two keys.
• headMap(to) — view of entries with keys less than to.
• tailMap(from) — view of entries with keys greater than or equal to from.
• descendingMap() — reverse-order view of the map.
• pollFirstEntry() / pollLastEntry() — retrieve and remove the first/last entry.

3. Code Example

import java.util.*;

public class TreeMapVsHashMap {
    public static void main(String[] args) {

        // ---- HashMap ----
        Map<String, Integer> hashMap = new HashMap<>();
        hashMap.put("Banana", 3);
        hashMap.put("Apple",  5);
        hashMap.put("Cherry", 1);
        hashMap.put(null, 0);     // null key allowed
        System.out.println("HashMap (no order): " + hashMap);
        // Output order is unpredictable

        // ---- TreeMap ----
        Map<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("Banana", 3);
        treeMap.put("Apple",  5);
        treeMap.put("Cherry", 1);
        // treeMap.put(null, 0); // throws NullPointerException
        System.out.println("TreeMap (sorted):   " + treeMap);
        // Output: {Apple=5, Banana=3, Cherry=1}

        // ---- NavigableMap methods ----
        NavigableMap<String, Integer> nav = new TreeMap<>(treeMap);
        System.out.println("First key: " + nav.firstKey());           // Apple
        System.out.println("Last key:  " + nav.lastKey());            // Cherry
        System.out.println("Floor of 'Bz': " + nav.floorKey("Bz"));  // Banana
        System.out.println("Ceiling of 'B': " + nav.ceilingKey("B"));// Banana
        System.out.println("Higher than 'Banana': " + nav.higherKey("Banana")); // Cherry
        System.out.println("Lower than 'Banana':  " + nav.lowerKey("Banana"));  // Apple

        // subMap: keys from "Apple" (inclusive) to "Cherry" (exclusive)
        System.out.println("subMap [Apple, Cherry): " + nav.subMap("Apple", "Cherry"));
        // {Apple=5, Banana=3}

        // headMap: keys strictly less than "Cherry"
        System.out.println("headMap(Cherry): " + nav.headMap("Cherry"));
        // {Apple=5, Banana=3}

        // tailMap: keys >= "Banana"
        System.out.println("tailMap(Banana): " + nav.tailMap("Banana"));
        // {Banana=3, Cherry=1}

        // Descending iteration
        System.out.print("Descending: ");
        nav.descendingMap().forEach((k, v) -> System.out.print(k + " "));
        // Cherry Banana Apple

        // ---- Custom Comparator ----
        // Sort by reverse alphabetical order
        TreeMap<String, Integer> reverseMap = new TreeMap<>(Comparator.reverseOrder());
        reverseMap.putAll(treeMap);
        System.out.println("\nReverse order: " + reverseMap);
        // {Cherry=1, Banana=3, Apple=5}

        // ---- Common use-case: range query ----
        TreeMap<Integer, String> schedule = new TreeMap<>();
        schedule.put(900,  "Team standup");
        schedule.put(1030, "Design review");
        schedule.put(1400, "Sprint planning");
        schedule.put(1600, "1-on-1");

        // Find the next meeting at or after 10:00 AM (1000)
        Map.Entry<Integer, String> next = schedule.ceilingEntry(1000);
        System.out.println("Next meeting: " + next); // 1030=Design review
    }
}

4. Time Complexity Table

5. When to Use Each

5.1 Use HashMap When

• You need the fastest possible get/put — O(1) average.
• The order of keys does not matter.
• You may have a null key.
• Your map is used as a simple cache, counter, or lookup table.

5.2 Use TreeMap When

• You need keys sorted in natural or custom order when iterating.
• You need range queries: "give me all entries between key A and key B".
• You use navigation methods like floorKey(), ceilingKey(), firstKey(), lastKey().
• You are building a scheduling system, leaderboard, or time-series store where ordering is critical.
• You need a consistent (reproducible) iteration order.

6. Interview Context

Interviewers ask this question to test knowledge of data-structure trade-offs. Common follow-up questions:

• "What happens if you insert a null key into a TreeMap?" → NullPointerException because the comparator calls compareTo(null).
• "How do you iterate a TreeMap in reverse order?" → Use descendingMap() or descendingKeySet().
• "Can two keys in a TreeMap be considered equal by the Comparator but unequal by equals()?" → Yes, and this breaks the Map contract — the tree treats them as the same key, so the second put() silently overwrites the first. Always keep Comparator consistent with equals().
• "Which is better for a phone book — HashMap or TreeMap?" → TreeMap, because you want names sorted alphabetically and may need range queries (find all names starting with 'S').

7. Common Pitfalls

7.1 Null Key in TreeMap

TreeMap<String, Integer> map = new TreeMap<>();
map.put(null, 1); // throws NullPointerException at runtime!

// Fix: use HashMap or ensure no null keys are inserted
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put(null, 1); // perfectly fine

7.2 Comparator Not Consistent with equals()

// Comparator that ignores case — "apple" and "Apple" seen as the same key
TreeMap<String, Integer> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
map.put("apple", 1);
map.put("Apple", 2); // overwrites! Only one entry remains
System.out.println(map.size());       // 1
System.out.println(map.get("APPLE")); // 2
// This is correct for case-insensitive maps, but can surprise you if unexpected.

7.3 Forgetting NavigableMap Cast

// If you declare as Map you lose NavigableMap methods
Map<String, Integer> map = new TreeMap<>();
// map.floorKey("B"); // compile error — Map has no floorKey()

// Fix: declare as NavigableMap or TreeMap
NavigableMap<String, Integer> nav = new TreeMap<>();
nav.put("Apple", 1);
nav.put("Banana", 2);
System.out.println(nav.floorKey("Avocado")); // Apple

8. Conclusion

The choice between TreeMap and HashMap comes down to one question: do you need sorted keys or range navigation?

• If yes → TreeMap with O(log n) and full NavigableMap API.
• If no → HashMap with O(1) average and lower memory overhead.

Remember: TreeMap does not allow null keys, while HashMap allows exactly one. For insertion-order guarantees without sorting overhead, consider LinkedHashMap as a middle ground.