Map Interface: HashMap, LinkedHashMap, TreeMap, Hashtable

A Map associates unique keys with values — it is not a Collection, because it stores pairs rather than single elements, but it is just as central to everyday Java code. Java provides four commonly used implementations, differing in ordering, null handling, and thread safety.

Why it matters

Maps are how Java programs answer "given this key, what is the value?" without scanning a list: a user by id, a price by product code, a count by word. Picking the wrong implementation shows up as real bugs — output that changes order between runs, a NullPointerException on a null key, or a lookup that slows down as data grows — so knowing the four trade-offs is worth more than memorising their method names.

HashMap — The Default Choice

HashMap stores key-value pairs in a hash table keyed by the key's hash code, giving average O(1) get(), put(), and remove(). Iteration order is unspecified and can change. HashMap allows exactly one null key and any number of null values. Internally, it maintains a load factor (default 0.75) — once the table is 75% full, it resizes (roughly doubles) and rehashes all entries, which is an O(n) operation that happens infrequently enough not to affect the amortized O(1) average.

LinkedHashMap — Predictable Iteration Order

LinkedHashMap extends HashMap and additionally threads a doubly linked list through the entries, preserving insertion order by default (or, with a constructor flag, access order — useful for building an LRU cache). It has the same O(1) average performance as HashMap with a small constant overhead, and it also permits one null key.

TreeMap — Sorted by Key

TreeMap is backed by a red-black tree and keeps keys in sorted order (natural order, or a supplied Comparator). get(), put(), and remove() run in O(log n) time. TreeMap does not allow a null key (it throws NullPointerException, since it needs to compare keys to place them), though it does allow null values. It also offers navigation methods like firstKey(), ceilingKey(), and headMap().

Hashtable — Legacy, Synchronized

Hashtable is a pre-Collections-Framework class (like Vector) that was retrofitted to implement Map. Every method is synchronized, making it thread-safe but slower than HashMap for single-threaded use. Unlike HashMap, Hashtable permits no null keys and no null values — attempting either throws NullPointerException immediately. Modern concurrent code prefers ConcurrentHashMap instead of Hashtable.

• HashMap: no order, O(1) average, one null key allowed, many null values allowed, not synchronized.
• LinkedHashMap: insertion (or access) order, O(1) average, one null key allowed.
• TreeMap: sorted by key, O(log n), no null keys, null values allowed.
• Hashtable: legacy, synchronized, no null keys or values allowed at all.

Time complexity

Examples

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

public class MapDemo {
    public static void main(String[] args) {
        Map<String, Integer> hashMap = new HashMap<>();
        hashMap.put("apple", 3);
        hashMap.put(null, 99); // allowed: one null key permitted
        System.out.println("HashMap null key value: " + hashMap.get(null));

        Map<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("banana", 5);
        treeMap.put("apple", 3);
        treeMap.put("cherry", 8);
        System.out.println("TreeMap sorted: " + treeMap);

        try {
            treeMap.put(null, 1); // TreeMap cannot place a null key
        } catch (NullPointerException e) {
            System.out.println("TreeMap rejected null key");
        }
    }
}

HashMap null key value: 99
TreeMap sorted: {apple=3, banana=5, cherry=8}
TreeMap rejected null key

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

public class CollisionDemo {
    public static void main(String[] args) {
        // "Aa" and "BB" are different strings with the same hash code
        System.out.println("Aa".hashCode());
        System.out.println("BB".hashCode());

        Map<String, Integer> stock = new HashMap<>();
        stock.put("Aa", 10);
        stock.put("BB", 20);

        // Both land in the same bucket; equals() tells them apart
        System.out.println(stock.get("Aa"));
        System.out.println(stock.get("BB"));
        System.out.println(stock.size());
    }
}

2112
2112
10
20
2

Where this is used

Counting and grouping are the most common everyday uses of a map: page views per URL, orders per customer, errors per type. merge() does the "insert 1 or add 1" step in a single call, so there is no separate check for whether the key already exists.

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

public class PageViews {
    public static void main(String[] args) {
        List<String> requests = List.of("/home", "/pricing", "/home", "/blog", "/home");

        Map<String, Integer> views = new HashMap<>();
        for (String path : requests) {
            views.merge(path, 1, Integer::sum);
        }

        System.out.println("/home: " + views.get("/home"));
        System.out.println("/pricing: " + views.get("/pricing"));
        System.out.println("/missing: " + views.getOrDefault("/missing", 0));
    }
}

/home: 3
/pricing: 1
/missing: 0

Exercise

Count how many times each word appears in a sentence and print the result in alphabetical order. Start from the code below and replace the TODO.

The expected output is {be=2, not=1, or=1, to=2}. Once it works, change TreeMap to HashMap and explain why the printed order is no longer guaranteed.

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

public class WordCount {
    public static void main(String[] args) {
        String text = "to be or not to be";
        Map<String, Integer> counts = new TreeMap<>();

        // TODO: split text on spaces and count each word

        System.out.println(counts);
    }
}

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

public class WordCount {
    public static void main(String[] args) {
        String text = "to be or not to be";
        Map<String, Integer> counts = new TreeMap<>();

        for (String word : text.split(" ")) {
            counts.merge(word, 1, Integer::sum);
        }

        System.out.println(counts); // {be=2, not=1, or=1, to=2}
    }
}

Quick quiz

Interview questions

Go deeper

• How HashMap Works Internally
• Concurrent Collections: ConcurrentHashMap and CopyOnWriteArrayList