Java Maps: HashMap vs. LinkedHashMap vs. TreeMap Explained

In Java, the Map interface is part of the java.util package and represents a collection that stores key-value pairs. Each key in a Map must be unique, and it maps to a single value. Maps are crucial for various programming scenarios where you need to associate data points, like a dictionary or a lookup table. The Java platform provides several concrete implementations of the Map interface, each offering different characteristics in terms of ordering, performance, and memory usage. The most commonly used implementations are HashMap, LinkedHashMap, and TreeMap.

HashMap

HashMap is a hash table-based implementation of the Map interface. It provides fast (constant-time average) performance for the basic operations (get and put).

• Characteristics:
  • Unordered: Does not guarantee any specific order of elements; the order can change over time.
  • Nulls: Allows one null key and multiple null values.
  • Performance: Offers average constant-time O(1) performance for put, get, and remove operations, assuming a good hash function and minimal collisions. In the worst-case scenario (many hash collisions leading to a degenerate linked list), performance can degrade to O(n).
  • Synchronization: HashMap is not synchronized. If multiple threads access a hash map concurrently and at least one of the threads modifies the map, it must be synchronized externally.
  • Memory: Generally efficient in memory unless dealing with a very high load factor and poor hash functions.
• Underlying Data Structure: Hash table (an array of buckets). Each bucket typically stores a linked list of entries, but in Java 8 and later, if a bucket contains too many entries (a "treeify" threshold, typically 8), the linked list is converted into a balanced red-black tree to improve worst-case performance from O(n) to O(log n).
• Use Cases:
  • General-purpose mapping where the order of elements is not important.
  • Implementing caches where fast lookups are crucial.
  • Counting frequencies of items.

LinkedHashMap

LinkedHashMap extends HashMap but also maintains a doubly-linked list running through all its entries. This linked list defines the iteration order, which is normally the order in which keys were inserted into the map (insertion order).

• Characteristics:
  • Ordered (Insertion Order): Iterates over its elements in the order in which the entries were inserted. An alternate constructor allows creating a LinkedHashMap that orders its entries by access order (least-recently accessed to most-recently accessed), useful for implementing LRU caches.
  • Nulls: Allows one null key and multiple null values, similar to HashMap.
  • Performance: Performance is marginally slower than HashMap due to the overhead of maintaining the linked list, but put, get, and remove operations are still O(1) on average. Iteration performance is generally better than HashMap as it traverses the linked list.
  • Synchronization: LinkedHashMap is not synchronized.
  • Memory: Uses slightly more memory than HashMap to maintain the linked list.
• Underlying Data Structure: Hash table (like HashMap) + doubly-linked list. Each entry in the map is also a node in the doubly-linked list.
• Use Cases:
  • When you need a map that remembers the order in which elements were added.
  • Implementing LRU (Least Recently Used) caches (using the access order constructor).
  • Building web applications where session attributes need to preserve order.

LinkedHashMap maintains insertion order (by default). This means there's a clear "oldest" (first inserted) and "latest" (last inserted) element.

1. Deleting the Oldest Object with LinkedHashMap

The oldest object is simply the first entry in the LinkedHashMap's iteration order. You can obtain its key using an iterator and then remove it.

Method:
1. Check if the map is empty.
2. Get an iterator for the entrySet().

3. Get the next() entry from the iterator, which will be the oldest.
4. Use map.remove(key) to delete it.

Example:

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

public class LinkedHashMapDeletion {

    public static void main(String[] args) {
        LinkedHashMap<String, Integer> lhm = new LinkedHashMap<>();
        lhm.put("Apple", 1);   // Oldest
        lhm.put("Banana", 2);
        lhm.put("Cherry", 3);
        lhm.put("Date", 4);    // Latest

        System.out.println("Original LinkedHashMap: " + lhm);

        // --- Deleting the oldest object ---
        String oldestKey = null;
        Integer oldestValue = null;

        if (!lhm.isEmpty()) {
            Iterator<Map.Entry<String, Integer>> iterator = lhm.entrySet().iterator();
            if (iterator.hasNext()) {
                Map.Entry<String, Integer> oldestEntry = iterator.next();
                oldestKey = oldestEntry.getKey();
                oldestValue = lhm.remove(oldestKey); // Remove by key
                System.out.println("\nDeleted oldest object:");
                System.out.println("Key: " + oldestKey + ", Value: " + oldestValue);
            }
        } else {
            System.out.println("\nMap is empty, no oldest object to delete.");
        }

        System.out.println("LinkedHashMap after deleting oldest: " + lhm);
        // Expected output: {Banana=2, Cherry=3, Date=4}
    }
}

Note on removeEldestEntry:
LinkedHashMap also has a protected method removeEldestEntry(Map.Entry eldest) which you can override to implement a policy for automatic removal of the oldest entry when a new entry is added. This is commonly used for implementing LRU (Least Recently Used) caches, but it's not for explicit, on-demand deletion of the oldest element.

2. Deleting the Latest Object with LinkedHashMap

The latest object is the last entry in the LinkedHashMap's iteration order. Since LinkedHashMap iterators are forward-only, getting the last element requires iterating through all elements or converting to a collection that allows direct access to the last element.

Method:
1. Check if the map is empty.
2. Iterate through the entrySet() and keep track of the last element encountered.
Alternatively, and often simpler: Convert entrySet() into a List, then get the last element from the list.
3. Use map.remove(key) to delete it.

Example (using List conversion for simplicity):

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class LinkedHashMapDeletion {

    public static void main(String[] args) {
        LinkedHashMap<String, Integer> lhm = new LinkedHashMap<>();
        lhm.put("Apple", 1);
        lhm.put("Banana", 2);
        lhm.put("Cherry", 3);
        lhm.put("Date", 4);    // Latest

        System.out.println("Original LinkedHashMap: " + lhm);

        // --- Deleting the latest object ---
        String latestKey = null;
        Integer latestValue = null;

        if (!lhm.isEmpty()) {
            // Convert the entry set to a list to easily access the last element
            List<Map.Entry<String, Integer>> entryList = new ArrayList<>(lhm.entrySet());
            Map.Entry<String, Integer> latestEntry = entryList.get(entryList.size() - 1);

            latestKey = latestEntry.getKey();
            latestValue = lhm.remove(latestKey); // Remove by key
            System.out.println("\nDeleted latest object:");
            System.out.println("Key: " + latestKey + ", Value: " + latestValue);
        } else {
            System.out.println("\nMap is empty, no latest object to delete.");
        }

        System.out.println("LinkedHashMap after deleting latest: " + lhm);
        // Expected output: {Apple=1, Banana=2, Cherry=3}
    }
}

Alternative for latest (Java 8 Stream):

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

public class LinkedHashMapDeletionStream {

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

        System.out.println("Original LinkedHashMap: " + lhm);

        if (!lhm.isEmpty()) {
            Optional<Map.Entry<String, Integer>> latestEntryOptional = lhm.entrySet().stream()
                .reduce((first, second) -> second); // The accumulator returns the second element, effectively keeping the last one seen.

            if (latestEntryOptional.isPresent()) {
                Map.Entry<String, Integer> latestEntry = latestEntryOptional.get();
                String latestKey = latestEntry.getKey();
                Integer latestValue = lhm.remove(latestKey);
                System.out.println("\nDeleted latest object (Stream):");
                System.out.println("Key: " + latestKey + ", Value: " + latestValue);
            }
        } else {
            System.out.println("\nMap is empty, no latest object to delete.");
        }

        System.out.println("LinkedHashMap after deleting latest (Stream): " + lhm);
    }
}

TreeMap

TreeMap is a NavigableMap implementation based on a Red-Black tree. It stores entries in ascending order of keys, either according to their natural ordering (if keys implement Comparable) or according to a custom Comparator provided at map creation time.

• Characteristics:
  • Ordered (Sorted Order): Stores and retrieves elements in a sorted order based on the keys. Keys must be comparable.
  • Nulls: Does not allow null keys (throws NullPointerException if you try to insert one) because it relies on key comparison. It allows multiple null values.
  • Performance: Operations like put, get, and remove have O(log n) time complexity due to the tree traversal required to locate or insert elements.
  • Synchronization: TreeMap is not synchronized.
  • Memory: Generally uses more memory than HashMap or LinkedHashMap due to the overhead of storing nodes with left/right pointers and color information for the tree structure.
• Underlying Data Structure: Red-Black tree (a self-balancing binary search tree).
• Use Cases:
  • When you need keys to be sorted (e.g., retrieving elements in a specific range).
  • Implementing dictionaries or symbol tables where sorted order is important.
  • When you need to perform range queries (e.g., finding all keys between X and Y).

Common Map Operators (Methods)

The following are common methods provided by the Map interface, which are implemented by HashMap, LinkedHashMap, and TreeMap:

Comparison of HashMap vs LinkedHashMap vs TreeMap