Collections

65. Map Implementations Compared

HashMap is the general-purpose O(1) map; LinkedHashMap preserves insertion (or access) order; TreeMap is sorted; Hashtable is legacy — avoid it; EnumMap and IdentityHashMap are specialised.

Java 21 (core language)

Explanation

HashMap<K,V>: O(1) average for get/put/remove. Allows one null key and multiple null values. Iteration order is unpredictable. Not thread-safe. Load factor default 0.75 — resize when 75% full.

LinkedHashMap<K,V>: extends HashMap, maintains a doubly-linked list of entries for insertion-order iteration. Optional access-order mode (new LinkedHashMap<>(16, 0.75f, true)) — entries are moved to the tail on get, enabling LRU caches.

TreeMap<K,V>: red-black tree, O(log n) operations, keys sorted by natural order or Comparator. Implements NavigableMap with floorEntry, ceilingEntry, subMap, headMap, tailMap. Does not allow null keys.

Hashtable: synchronised legacy class, does not allow null keys or values. Replaced by ConcurrentHashMap. Never use in new code.

Example

import java.util.*;

public class MapImplementations {
    public static void main(String[] args) {
        // HashMap: general purpose
        Map<String, Integer> hash = new HashMap<>();
        hash.put("one", 1); hash.put("two", 2); hash.put("three", 3);
        hash.put(null, 0);  // null key allowed!
        System.out.println("HashMap: " + hash); // order unpredictable

        // LinkedHashMap: insertion order
        Map<String, Integer> linked = new LinkedHashMap<>();
        linked.put("one", 1); linked.put("two", 2); linked.put("three", 3);
        System.out.println("LinkedHashMap: " + linked); // {one=1, two=2, three=3}

        // TreeMap: sorted order
        TreeMap<String, Integer> tree = new TreeMap<>();
        tree.put("banana", 2); tree.put("apple", 1); tree.put("cherry", 3);
        System.out.println("TreeMap: " + tree); // {apple=1, banana=2, cherry=3}
        System.out.println("firstEntry: " + tree.firstEntry()); // apple=1
        System.out.println("headMap(<cherry): " + tree.headMap("cherry")); // {apple=1, banana=2}

        // LRU cache using LinkedHashMap access-order mode
        int capacity = 3;
        Map<Integer, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
            @Override protected boolean removeEldestEntry(Map.Entry<Integer, String> e) {
                return size() > capacity;
            }
        };
        lru.put(1, "A"); lru.put(2, "B"); lru.put(3, "C");
        lru.get(1); // access makes 1 most-recent
        lru.put(4, "D"); // evicts least-recently-used (2)
        System.out.println("LRU cache: " + lru); // {3=C, 1=A, 4=D}
    }
}

Sources