Difference Between HashMap and TreeMap in Java

In Java, we have HashMap and TreeMap classes to store and organize data (key-value pairs). Both do similar jobs but in different ways. In this post, we will learn the differences between HashMap and TreeMap in Java with examples.

Difference Between HashMap and TreeMap in Java - Key Points

Underlying Data Structure: 

HashMap: Uses Hash table to store key-value pairs. 

TreeMap: Uses a red-black tree (a balanced binary search tree). 

Ordering: 

HashMap: This does not guarantee any specific order of its key-value pairs. 

TreeMap: Stores its key-value pairs in a sorted order based on their keys. 

Performance: 

HashMap: get and put operations are generally O(1), assuming good hash distribution. However, in the worst case (e.g., many hash collisions), it can degrade to O(n). 

TreeMap: get, put, and other operations like remove are O(log n) due to the tree-based structure. 

Null Keys and Values: 

HashMap: Allows one null key and multiple null values. 

TreeMap: Does not allow null keys (throws NullPointerException). However, it does allow multiple null values. 

Concurrency: 

HashMap: Not synchronized, meaning it's not thread-safe by default. 

TreeMap: Also not synchronized by default. 

Fail-fast Iterators: 

Both HashMap and TreeMap provide fail-fast iterators, meaning any structural modification (addition or removal of mappings) after the iterator is created, except through the iterator's own remove method, will throw a ConcurrentModificationException. 

Complexity and Memory: 

HashMap: Typically offers constant-time performance and is usually faster but might use more memory due to its hash table structure. 

TreeMap: Due to its red-black tree structure, it generally uses less memory for fewer elements but might be slower for certain operations compared to HashMap.

Difference Between HashMap and TreeMap in Java - Summary in Table

Criteria	HashMap	TreeMap
Underlying Data Structure	Hash table	Red-black tree (a type of balanced binary search tree)
Ordering of Keys	No guaranteed order	Keys are sorted according to their natural ordering or by a comparator provided at map creation time
Null Keys and Values	Allows one null key and multiple null values	Doesn't allow any null key (if natural ordering is used or any custom comparator does not permit nulls) but allows multiple null values
Performance	Generally faster for common operations like `get` and `put`	Logarithmic time cost for `get`, `put`, and `containsKey` operations
Duplicates	Does not allow duplicate keys; allows duplicate values	Does not allow duplicate keys; allows duplicate values
Thread Safety	Not synchronized	Not synchronized
Use-case	When the ordering of keys is not important and operations need to be faster	When the sorted or natural order of keys is crucial

Difference Between HashMap and TreeMap in Java - Simple Example

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class HashMapVsTreeMapDemo {

    public static void main(String[] args) {

        // Create a HashMap and add some key-value pairs
        Map<String, String> hashMap = new HashMap<>();
        hashMap.put("three", "cherry");
        hashMap.put("one", "banana");
        hashMap.put("two", "apple");
        hashMap.put("four", "date");

        System.out.println("HashMap:");
        hashMap.forEach((key, value) -> System.out.println(key + " -> " + value));

        // Create a TreeMap and add some key-value pairs
        Map<String, String> treeMap = new TreeMap<>();
        treeMap.put("c", "elephant");
        treeMap.put("a", "grape");
        treeMap.put("b", "fox");
        treeMap.put("d", "honeydew");

        System.out.println("\nTreeMap:");
        treeMap.forEach((key, value) -> System.out.println(key + " -> " + value));
    }
}

Output:

HashMap:
three -> cherry
one -> banana
two -> apple
four -> date

TreeMap:
a -> grape
b -> fox
c -> elephant
d -> honeydew

Explanation:

1. HashMap: A HashMap is an implementation of the Map interface, which stores key-value pairs. It uses a hash table to store the data and therefore does not guarantee any specific order of the keys or values. Its primary advantage is that it allows constant-time performance for the basic operations (get and put) under ideal conditions.

2. TreeMap: A TreeMap is a Red-Black tree-based NavigableMap implementation. It stores its key-value pairs in a sorted order (by the keys). This sorting is based on the natural order of its keys or by a comparator provided at the map's creation time. Its performance is generally log(n) for most operations.

3. In the given example, the hashMap does not maintain any order for its keys, while the treeMap automatically arranges the keys in their natural order (alphabetically). This distinction becomes evident in the output where the TreeMap key-value pairs are printed in a sorted manner (by keys), whereas the HashMap key-value pairs are in a seemingly random order.