00:00

Help Us Improve

We're sorry this tutorial wasn't helpful. Please tell us what we can do better.

Difference Between HashMap and TreeMap in Java

Last updated: 4 min read

HashMap and TreeMap both implement Map and store unique keys mapped to values, but they are built very differently:

  • HashMap is a hash table: O(1) average operations and no ordering.
  • TreeMap is a red-black tree: keys are always sorted, operations take O(log n), and it supports range and nearest-key queries through NavigableMap.

1. Comparison Table

AspectHashMapTreeMap
OrderingNone guaranteedSorted by key (natural order or Comparator)
Data structureArray of buckets (lists/trees)Red-black tree
get / put / removeO(1) averageO(log n)
Key equalityhashCode() + equals()compareTo() or compare()
Null keysOne allowedNot allowed (natural ordering)
Null valuesAllowedAllowed
InterfacesMapNavigableMap, SortedMap, SequencedMap
Range / nearest queriesNofloorKey, ceilingEntry, headMap, subMap…
MemoryTable plus entriesTree nodes (parent, left, right, colour)
Thread-safe alternativeConcurrentHashMapConcurrentSkipListMap

2. Sorted Keys and Navigation

SortedKeys.java 
import java.util.*;

public class SortedKeys {
    public static void main(String[] args) {
        Map<String, Integer> hash = new HashMap<>();
        TreeMap<String, Integer> tree = new TreeMap<>();
        for (String w : "spring java kafka docker java aws spring java".split(" ")) {
            hash.merge(w, 1, Integer::sum);
            tree.merge(w, 1, Integer::sum);
        }
        System.out.println("HashMap : " + hash + "  <- no order");
        System.out.println("TreeMap : " + tree + "  <- keys sorted");

        // NavigableMap methods: only TreeMap
        System.out.println("firstKey / lastKey : " + tree.firstKey() + " / " + tree.lastKey());
        System.out.println("ceilingKey(\"b\")    : " + tree.ceilingKey("b"));
        System.out.println("headMap(\"java\")    : " + tree.headMap("java"));
        System.out.println("descendingMap      : " + tree.descendingMap());

        TreeMap<String, Integer> byLength = new TreeMap<>(Comparator.comparing(String::length).thenComparing(Comparator.reverseOrder()));
        byLength.putAll(hash);
        System.out.println("custom comparator  : " + byLength);
    }
}
Output
HashMap : {spring=2, java=3, kafka=1, aws=1, docker=1}  <- no order
TreeMap : {aws=1, docker=1, java=3, kafka=1, spring=2}  <- keys sorted
firstKey / lastKey : aws / spring
ceilingKey("b")    : docker
headMap("java")    : {aws=1, docker=1}
descendingMap      : {spring=2, kafka=1, java=3, docker=1, aws=1}
custom comparator  : {aws=1, java=3, kafka=1, spring=2, docker=1}

3. Range Lookups and Null Keys

floorEntry finds the greatest key less than or equal to a value, perfect for slabs, price bands and time-based lookups:

RangeQueries.java 
import java.util.*;

public class RangeQueries {
    public static void main(String[] args) {
        // Illustrative tax slabs: lower bound -> rate
        TreeMap<Integer, Integer> slabs = new TreeMap<>(Map.of(0, 0, 300_000, 5, 700_000, 10, 1_000_000, 15, 1_200_000, 20));
        for (int income : new int[] {250_000, 850_000, 1_500_000})
            System.out.println("income " + income + " -> rate " + slabs.floorEntry(income).getValue() + "%");

        try {
            new TreeMap<String, Integer>().put(null, 1);
        } catch (NullPointerException e) {
            System.out.println("TreeMap null key -> NullPointerException");
        }
        Map<String, Integer> hash = new HashMap<>();
        hash.put(null, 1);
        System.out.println("HashMap null key ok: " + hash.containsKey(null));
    }
}
Output
income 250000 -> rate 0%
income 850000 -> rate 10%
income 1500000 -> rate 20%
TreeMap null key -> NullPointerException
HashMap null key ok: true

4. When to Use Which

  • HashMap: fast lookups by key when order does not matter. This is the default choice.
  • TreeMap: when you need keys sorted, ranges (between two keys), or the nearest key below or above a value.
  • LinkedHashMap: when you need insertion order with hash-map speed.

If you only need sorted output once, filling a HashMap and sorting its entries at the end can be faster than maintaining a TreeMap.

5. Summary

  • HashMap: O(1), unordered, one null key allowed.
  • TreeMap: O(log n), sorted keys, no null keys, rich navigation API.
  • TreeMap compares keys with compareTo/comparator; HashMap uses hashCode/equals.
  • Neither is thread-safe; use ConcurrentHashMap or ConcurrentSkipListMap.

Related Tutorials