HashMap vs TreeMap vs LinkedHashMap in Java

HashMap vs TreeMap vs LinkedHashMap in Java

When working with key-value pairs in Java, the Map interface provides various implementations to store and manage data efficiently. The three most commonly used implementations are:

HashMap – Uses a hash table for storage and provides fast access.
TreeMap – Maintains a sorted order using a red-black tree.
LinkedHashMap – Maintains insertion order while using a hash table.

Each of these implementations has distinct characteristics affecting performance and behavior. In this blog post, we will explore the differences between HashMap, TreeMap, and LinkedHashMap and guide you on when to use each.

1. HashMap

A HashMap is a key-value pair collection that does not guarantee any order of elements. It is backed by a hash table, making it highly efficient for most operations.

Characteristics of HashMap:

Unordered collection (insertion order is not preserved).
Allows one null key and multiple null values.
Fast insertion, deletion, and lookup operations (O(1) on average).
Not synchronized (use Collections.synchronizedMap() for thread safety).

Example of HashMap Usage:

import java.util.*;

public class HashMapExample {
    public static void main(String[] args) {
        Map<Integer, String> hashMap = new HashMap<>();
        hashMap.put(3, "Banana");
        hashMap.put(1, "Apple");
        hashMap.put(2, "Cherry");
        
        System.out.println(hashMap); // Output: {1=Apple, 2=Cherry, 3=Banana} (order may vary)
    }
}

2. TreeMap

A TreeMap is a Map implementation that stores elements in sorted order based on the natural ordering of keys (or a custom comparator). It is backed by a red-black tree.

Characteristics of TreeMap:

Elements are stored in sorted order (ascending by default).
Does not allow null keys (throws NullPointerException).
Search, insertion, and deletion operations take O(log n) time.
Useful when keys need to be in a sorted sequence.

Example of TreeMap Usage:

import java.util.*;

public class TreeMapExample {
    public static void main(String[] args) {
        Map<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "Banana");
        treeMap.put(1, "Apple");
        treeMap.put(2, "Cherry");
        
        System.out.println(treeMap); // Output: {1=Apple, 2=Cherry, 3=Banana} (sorted order)
    }
}

3. LinkedHashMap

A LinkedHashMap maintains the insertion order of elements while providing fast lookup operations similar to HashMap. It internally uses a linked list with a hash table.

Characteristics of LinkedHashMap:

Maintains insertion order.
Allows one null key and multiple null values.
Faster than TreeMap but slightly slower than HashMap.
Useful when predictable iteration order is required.

Example of LinkedHashMap Usage:

import java.util.*;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put(3, "Banana");
        linkedHashMap.put(1, "Apple");
        linkedHashMap.put(2, "Cherry");
        
        System.out.println(linkedHashMap); // Output: {3=Banana, 1=Apple, 2=Cherry} (insertion order)
    }
}

Performance Comparison: HashMap vs TreeMap vs LinkedHashMap

Feature	HashMap	TreeMap	LinkedHashMap
Ordering	No order	Sorted order	Insertion order
Null keys	Allowed (one)	Not allowed	Allowed (one)
Insertion Time Complexity	O(1)	O(log n)	O(1)
Deletion Time Complexity	O(1)	O(log n)	O(1)
Search Time Complexity	O(1)	O(log n)	O(1)
Memory Usage	Least	Most	More than HashMap but less than TreeMap

When to Use HashMap, TreeMap, or LinkedHashMap?

Scenario	Recommended Collection
Need fast lookups and don't care about order	`HashMap`
Need sorted keys	`TreeMap`
Need to maintain insertion order	`LinkedHashMap`
Need high performance and key uniqueness	`HashMap`
Need a sorted map for navigation (e.g., first, last, submap)	`TreeMap`
Need both fast lookups and ordered elements	`LinkedHashMap`

Example: Performance Test

Let's compare the time taken for insertion into HashMap, TreeMap, and LinkedHashMap.

import java.util.*;

public class MapPerformanceTest {
    public static void main(String[] args) {
        int size = 100000;
        Map<Integer, Integer> hashMap = new HashMap<>();
        Map<Integer, Integer> treeMap = new TreeMap<>();
        Map<Integer, Integer> linkedHashMap = new LinkedHashMap<>();
        
        long startTime, endTime;
        
        // HashMap Insertion Test
        startTime = System.nanoTime();
        for (int i = 0; i < size; i++) {
            hashMap.put(i, i);
        }
        endTime = System.nanoTime();
        System.out.println("HashMap Insertion Time: " + (endTime - startTime) + " ns");

        // TreeMap Insertion Test
        startTime = System.nanoTime();
        for (int i = 0; i < size; i++) {
            treeMap.put(i, i);
        }
        endTime = System.nanoTime();
        System.out.println("TreeMap Insertion Time: " + (endTime - startTime) + " ns");
        
        // LinkedHashMap Insertion Test
        startTime = System.nanoTime();
        for (int i = 0; i < size; i++) {
            linkedHashMap.put(i, i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedHashMap Insertion Time: " + (endTime - startTime) + " ns");
    }
}