HashMap vs. TreeMap vs. LinkedHashMap

In Java, HashMap, TreeMap, and LinkedHashMap are three commonly used implementations of the Map interface. Each has its own characteristics and use cases. Let’s compare them in detail:

---

1. HashMap

• Underlying Data Structure: Hash table.
• Ordering: No guaranteed order of keys.
• Performance:
• Average time complexity: O(1) for get() and put() operations.
• Worst-case time complexity: O(n) due to hash collisions.
• Use Case: When you need fast lookups and don’t care about the order of keys.

Example:

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

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Cherry", 3);

        System.out.println("HashMap: " + map); // Output: {Apple=1, Cherry=3, Banana=2} (order may vary)
    }
}

---

2. TreeMap

• Underlying Data Structure: Red-Black Tree (a self-balancing binary search tree).
• Ordering: Keys are sorted in natural order (or by a custom comparator).
• Performance:
• Time complexity: O(log n) for get() and put() operations.
• Use Case: When you need keys to be sorted.

Example:

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

public class TreeMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new TreeMap<>();
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Cherry", 3);

        System.out.println("TreeMap: " + map); // Output: {Apple=1, Banana=2, Cherry=3} (sorted order)
    }
}

---

3. LinkedHashMap

• Underlying Data Structure: Hash table + Linked list.
• Ordering: Maintains insertion order of keys.
• Performance:
• Average time complexity: O(1) for get() and put() operations.
• Use Case: When you need to maintain the insertion order of keys.

Example:

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Cherry", 3);

        System.out.println("LinkedHashMap: " + map); // Output: {Apple=1, Banana=2, Cherry=3} (insertion order)
    }
}

---

4. Comparison Table

Feature	HashMap	TreeMap	LinkedHashMap
Underlying Structure	Hash table	Red-Black Tree	Hash table + Linked list
Ordering	No order	Sorted (natural or custom)	Insertion order
Performance	O(1) average, O(n) worst	O(log n)	O(1) average
Use Case	Fast lookups, no order	Sorted keys	Maintain insertion order
Null Keys/Values	Allows one null key, multiple null values	No null keys (if natural ordering), allows null values	Allows one null key, multiple null values

---

5. When to Use Which?

• Use HashMap when:
• You need fast lookups and don’t care about the order of keys.
• Example: Storing user preferences where order doesn’t matter.
• Use TreeMap when:
• You need keys to be sorted (natural order or custom order).
• Example: Storing a dictionary in alphabetical order.
• Use LinkedHashMap when:
• You need to maintain the insertion order of keys.
• Example: Implementing a cache with LRU (Least Recently Used) eviction policy.

---

6. Example Combining All Three

import java.util.*;

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

        // TreeMap
        Map<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("Apple", 1);
        treeMap.put("Banana", 2);
        treeMap.put("Cherry", 3);
        System.out.println("TreeMap: " + treeMap); // Output: {Apple=1, Banana=2, Cherry=3} (sorted order)

        // LinkedHashMap
        Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("Apple", 1);
        linkedHashMap.put("Banana", 2);
        linkedHashMap.put("Cherry", 3);
        System.out.println("LinkedHashMap: " + linkedHashMap); // Output: {Apple=1, Banana=2, Cherry=3} (insertion order)
    }
}

---

By understanding the differences between HashMap, TreeMap, and LinkedHashMap, you can choose the right implementation for your specific use case in Java!