TreeMap vs LinkedHashMap in Java

1. Introduction

Java provides various types of Map implementations that are suitable for different scenarios. TreeMap and LinkedHashMap are two such implementations. TreeMap stores its entries in a sorted order, determined by the natural ordering of its keys, or by a Comparator provided at map creation time. LinkedHashMap, meanwhile, maintains insertion order, or optionally, access order of the elements.

2. Key Points

1. TreeMap is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation.

2. LinkedHashMap maintains a doubly-linked list running through all its entries, which defines the iteration ordering.

3. TreeMap has O(log n) time cost for the containsKey, get, put, and remove operations.

4. LinkedHashMap has O(1) time cost for the insertion, deletion, and access operations.

5. LinkedHashMap can be constructed to follow the order of insertion or the order in which entries were last accessed.

3. Differences

TreeMap	LinkedHashMap
Sorts keys by natural ordering or by a comparator.	Maintains keys in insertion order or last access order.
Has O(log n) time complexity for insertion, deletion, and searching.	Has O(1) time complexity for insertion, deletion, and searching.
No guarantees on iteration order in terms of insertion or access.	Iteration order is predictable (insertion order by default).

4. Example

// Import the necessary classes
import java.util.TreeMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class MapComparison {
    public static void main(String[] args) {
        // Step 1: Create a TreeMap
        Map<Integer, String> treeMap = new TreeMap<>();
        // Step 2: Create a LinkedHashMap
        Map<Integer, String> linkedHashMap = new LinkedHashMap<>();

        // Step 3: Add some entries to the TreeMap
        treeMap.put(3, "Three");
        treeMap.put(1, "One");
        treeMap.put(2, "Two");

        // Step 4: Add some entries to the LinkedHashMap
        linkedHashMap.put(3, "Three");
        linkedHashMap.put(1, "One");
        linkedHashMap.put(2, "Two");

        // Step 5: Print the contents of both maps
        System.out.println("TreeMap: " + treeMap);
        System.out.println("LinkedHashMap: " + linkedHashMap);
    }
}

Output:

TreeMap: {1=One, 2=Two, 3=Three}
LinkedHashMap: {3=Three, 1=One, 2=Two}

Explanation:

1. TreeMap and LinkedHashMap are created to store integers associated with strings.

2. Entries are added to both maps; however, TreeMap sorts them by the natural ordering of the keys.

3. LinkedHashMap maintains the insertion order of the keys.

4. The output displays the sorting behavior of TreeMap and the insertion-order maintenance of LinkedHashMap.

5. When to use?

- Use TreeMap when you need to maintain an order of the keys. It's beneficial when you're concerned with the sorted or navigable map operations.

- Use LinkedHashMap when you want to maintain the order of entries either by insertion or by access, and need quick insertion and access operations.