Map Interface in Java: HashMap, TreeMap and More

Every non-trivial Java application maps one thing to another: user IDs to sessions, product codes to prices, words to counts. The Map interface is how Java models that relationship, and it is the single most-used part of the collections framework after List. It is also one of the most heavily tested areas in Java interviews, so understanding the interface — not just HashMap — pays off twice.

This guide covers what Map guarantees, the four implementations you will actually meet in code, and how to choose between them.

Where Map fits in the collections framework

Here is a detail interviewers love: Map does not extend Collection. The Java Collections Framework has two separate hierarchies. Collection (with List, Set, Queue) models a group of individual elements. Map models key-value pairs, where each key appears at most once.

The hierarchy that matters in practice:

• Map<K, V> — the root interface
• SortedMap<K, V> and NavigableMap<K, V> — add sorted-key behavior, implemented by TreeMap
• HashMap, LinkedHashMap, TreeMap — the three modern implementations
• Hashtable — the legacy synchronized implementation from Java 1.0
• ConcurrentHashMap — the modern thread-safe choice

Even though Map sits outside Collection, it bridges back through three view methods: keySet() returns a Set<K>, values() returns a Collection<V>, and entrySet() returns a Set<Map.Entry<K, V>>. These views are live — remove a key from keySet() and the entry disappears from the map.

Interview note: "Why doesn't Map extend Collection?" is a classic warm-up question. The short answer: a Map stores pairs, not elements, so methods like add(E e) make no sense for it. Mentioning the entrySet() bridge shows you understand the design, not just the fact.

Core Map methods you use daily

The interface is compact. These ten methods cover 95% of real usage:

A runnable example showing the basics:

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

public class MapBasics {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("laptop", 12);
        stock.put("mouse", 40);
        stock.put("laptop", 10);   // replaces 12, put returns 12

        System.out.println(stock.get("laptop"));          // 10
        System.out.println(stock.get("keyboard"));        // null
        System.out.println(stock.getOrDefault("keyboard", 0)); // 0
        System.out.println(stock.containsKey("mouse"));   // true
        System.out.println(stock.size());                 // 2
    }
}

Notice two things: putting an existing key silently replaces the value, and get() on a missing key returns null rather than throwing. That second behavior causes real bugs — prefer getOrDefault() when a sensible fallback exists.

Common mistake: A common mistake beginners make is calling get() and immediately using the result: stock.get("keyboard") + 1 throws a NullPointerException when the key is absent, because unboxing null to int fails. Always handle the missing-key case with getOrDefault() or an explicit check.

The four main implementations

HashMap: the default choice

HashMap stores entries in an array of buckets indexed by the key's hash code. Average put/get/remove are O(1). Iteration order is unspecified and can change when the map resizes. It permits one null key and any number of null values, and it is not thread-safe.

If you are curious what actually happens on a put() call — hashing, collisions, treeification — read how HashMap works internally. It is the most common deep-dive question in Java interviews.

LinkedHashMap: predictable order

LinkedHashMap extends HashMap and additionally threads a doubly linked list through its entries. You keep O(1) operations and gain insertion-order iteration. Pass accessOrder = true to the constructor and it reorders on every get() instead — the standard building block for an LRU cache.

TreeMap: sorted keys

TreeMap implements NavigableMap using a Red-Black tree. Every operation is O(log n), but keys stay sorted — by natural ordering or a Comparator you supply. You also get navigation methods no hash-based map can offer: firstKey(), lastKey(), floorKey(), ceilingKey(), headMap(), tailMap() and subMap() for range queries.

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

public class TreeMapDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> slabs = new TreeMap<>();
        slabs.put(0, "No tax");
        slabs.put(400000, "5 percent");
        slabs.put(800000, "10 percent");
        slabs.put(1200000, "15 percent");

        // Which slab does an income of 950000 fall into?
        Map.Entry<Integer, String> slab = slabs.floorEntry(950000);
        System.out.println(slab.getKey() + " -> " + slab.getValue());
        // 800000 -> 10 percent

        System.out.println(slabs.firstKey());  // 0
        System.out.println(slabs.headMap(800000));
        // {0=No tax, 400000=5 percent}
    }
}

Notice floorEntry(950000): it finds the greatest key less than or equal to 950000 in O(log n). Doing this with a HashMap would require scanning every key.

Hashtable: legacy, avoid in new code

Hashtable predates the collections framework. Every method is synchronized, it forbids null keys and values, and it is slower than the alternatives under any workload. It survives only for backward compatibility. If you need thread safety, use ConcurrentHashMap — the full reasoning is in HashMap vs Hashtable.

Choosing the right implementation

Decision rule in one line: default to HashMap; upgrade to LinkedHashMap for order, TreeMap for sorting or range queries, ConcurrentHashMap for concurrent writes.

Pro tip: Declare variables and method parameters as Map<K, V>, not as a concrete class. Map<String, Integer> counts = new HashMap<>(); lets you swap the implementation later — say to TreeMap for a sorted report — by changing one word.

Iterating over a Map

The entrySet() loop is the standard pattern because it reads key and value in a single pass:

Map<String, Integer> marks = Map.of("Java", 88, "SQL", 92, "React", 79);

for (Map.Entry<String, Integer> e : marks.entrySet()) {
    System.out.println(e.getKey() + " scored " + e.getValue());
}

// Java 8 style
marks.forEach((subject, score) ->
    System.out.println(subject + " scored " + score));

Avoid iterating keySet() and calling get(key) inside the loop — it performs a second lookup per entry for no benefit. For a full tour of iteration patterns and their trade-offs, see HashMap operations and iteration.

Also remember Map.of(...) (Java 9+) creates an immutable map — calling put() on it throws UnsupportedOperationException.

Java 8+ methods that clean up your code

Three default methods added in Java 8 remove the most common if-else boilerplate:

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

public class ModernMapMethods {
    public static void main(String[] args) {
        String text = "to be or not to be";
        Map<String, Integer> freq = new HashMap<>();
        for (String word : text.split(" ")) {
            freq.merge(word, 1, Integer::sum);
        }
        System.out.println(freq); // {not=1, be=2, or=1, to=2}

        Map<Integer, List<String>> byLength = new HashMap<>();
        for (String word : text.split(" ")) {
            byLength.computeIfAbsent(word.length(), k -> new ArrayList<>())
                    .add(word);
        }
        System.out.println(byLength); // {2=[to, be, or, to, be], 3=[not]}
    }
}

merge(key, 1, Integer::sum) means "insert 1 if absent, otherwise combine with the old value" — a one-line word counter. computeIfAbsent builds the missing ArrayList exactly once per key, replacing the four-line "check, create, put, add" dance. Both patterns come up constantly in coding rounds; practicing them is worth an evening before your collections interview.

Rules your keys must follow

Whatever implementation you choose, keys carry contracts:

• Hash-based maps (HashMap, LinkedHashMap) require consistent hashCode() and equals(). Two equal keys must return the same hash code.
• TreeMap ignores hashCode() entirely and relies on compareTo() or your Comparator. If compareTo() returns 0, TreeMap treats the keys as duplicates even when equals() says otherwise.
• Never mutate a key after inserting it. If a field used in hashCode() changes, the entry is stranded in the wrong bucket and get() will never find it again.

Common mistake: A common mistake beginners make is using a mutable object — like a List or a custom class with settable fields — as a map key, then modifying it. The entry becomes unreachable, the map "loses" data, and the bug only shows up far from the code that caused it. Prefer immutable keys: String, Integer, enums, or records.

Master these rules and the implementation table above, and most Map questions — in interviews and in production code — become straightforward. The natural next step is going one level deeper into HashMap's internal mechanics, where the hashCode/equals contract stops being theory and starts explaining real performance behavior.