Maps

The Map interface is the most frequently used abstraction in Java interviews, and the choice of which Map implementation to use reveals your depth as an engineer. HashMap gives you O(1) unordered access. LinkedHashMap preserves insertion order and enables LRU caches. TreeMap delivers sorted iteration with O(log n) operations. ConcurrentHashMap handles multi-threaded access without coarse locking. Each implementation makes different trade-offs, and interviewers expect you to articulate those trade-offs fluently.

This chapter dissects every major Map implementation in Java’s standard library, builds interview-grade solutions with each one, and provides the vocabulary you need to discuss them under pressure.

The Map Interface

Before comparing implementations, anchor yourself in the interface they share. Every Map<K, V> provides:

Method	Description
put(K, V)	Insert or update a key-value pair
get(K)	Retrieve the value for a key (or null)
containsKey(K)	Check if a key exists
remove(K)	Remove a key-value pair
entrySet()	Get all key-value pairs as Set<Map.Entry<K,V>>
keySet()	Get all keys
values()	Get all values
computeIfAbsent(K, Function)	Compute value only if key is absent — avoids the check-then-act race
merge(K, V, BiFunction)	Insert if absent, otherwise merge with existing value
getOrDefault(K, V)	Return default instead of null for missing keys

The computeIfAbsent and merge methods are underused in interview code. They eliminate the verbose pattern of if (!map.containsKey(key)) { map.put(key, new ArrayList<>()); } and replace it with a single, intent-revealing call.

HashMap — Unordered, O(1) Average

HashMap is covered extensively in the previous chapter. The key points to recall:

• No ordering guarantee — iteration order is unpredictable and changes after resizing.
• Allows one null key and any number of null values.
• O(1) average for put, get, remove — O(log n) worst case after treeification.
• Not thread-safe — concurrent modification causes ConcurrentModificationException during iteration or silent data corruption.

When an interviewer asks “which Map would you use?”, start with HashMap unless the problem requires ordering, sorting, or concurrency. It is the default choice.

LinkedHashMap — Insertion Order Preserved

LinkedHashMap extends HashMap with a doubly-linked list that threads through all entries in insertion order. Every entry maintains before and after pointers in addition to the hash bucket chain:

Bucket Array:
[0] → Entry("dog", 3)
[1] → null
[2] → Entry("cat", 5) → Entry("bat", 2)   (bucket chain)
[3] → null

Doubly-Linked List (insertion order):
HEAD ↔ "cat" ↔ "dog" ↔ "bat" ↔ TAIL

Iteration follows the linked list, not the bucket array. This guarantees insertion-order traversal with no performance penalty — put, get, and remove remain O(1).

Access Order Mode

The constructor new LinkedHashMap<>(capacity, loadFactor, true) switches from insertion order to access order. Every get() or put() moves the accessed entry to the tail of the linked list. This is the foundation of an LRU (Least Recently Used) cache: the head of the list is always the least recently accessed entry.

LRU Cache Implementation

The LRU Cache is the single most commonly asked Map-based interview question. LeetCode 146 appears at Google, Meta, Amazon, and Microsoft with high frequency. LinkedHashMap makes the implementation remarkably concise:

public class LRUCache<K, V> extends java.util.LinkedHashMap<K, V> {

    private final int maxCapacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // access-order mode
        this.maxCapacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }
}

That is the entire implementation. Three things make it work:

1. Access-order mode (true in the constructor) — every get() moves the entry to the tail.
2. removeEldestEntry hook — called after every put(). When the map exceeds capacity, it returns true, and LinkedHashMap removes the head entry (the least recently used one).
3. O(1) everything — insertion, lookup, eviction, and order maintenance all run in constant time.

Usage:

var cache = new LRUCache<Integer, String>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1);           // Access "one" — moves to tail
cache.put(4, "four");   // Evicts key 2 (least recently used)
// Cache now contains: {3="three", 1="one", 4="four"}

Interview follow-up: “What if I need thread safety?” Wrap the cache with Collections.synchronizedMap() for coarse-grained locking, or implement a custom LRU cache using ConcurrentHashMap + a ConcurrentLinkedDeque for fine-grained concurrency. The synchronized wrapper is sufficient for most interview discussions.

Interview follow-up: “Implement LRU Cache without LinkedHashMap.” Use a HashMap for O(1) lookups and a doubly-linked list for O(1) eviction/promotion. This is the classic from-scratch implementation interviewers want when they specify “design from scratch”:

public class LRUCacheFromScratch<K, V> {

    record Node<K, V>(K key, V value, Node<K, V>[] neighbors) {
        // neighbors[0] = prev, neighbors[1] = next
        @SuppressWarnings("unchecked")
        Node(K key, V value) {
            this(key, value, new Node[2]);
        }
    }

    private final int capacity;
    private final java.util.HashMap<K, Node<K, V>> map;
    private final Node<K, V> head;  // Sentinel — most recently used side
    private final Node<K, V> tail;  // Sentinel — least recently used side

    public LRUCacheFromScratch(int capacity) {
        this.capacity = capacity;
        this.map = new java.util.HashMap<>();
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.neighbors()[1] = tail;
        tail.neighbors()[0] = head;
    }

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        moveToHead(node);
        return node.value();
    }

    public void put(K key, V value) {
        Node<K, V> existing = map.get(key);
        if (existing != null) {
            removeNode(existing);
        }

        var node = new Node<>(key, value);
        addAfterHead(node);
        map.put(key, node);

        if (map.size() > capacity) {
            Node<K, V> evicted = tail.neighbors()[0];
            removeNode(evicted);
            map.remove(evicted.key());
        }
    }

    private void addAfterHead(Node<K, V> node) {
        node.neighbors()[0] = head;
        node.neighbors()[1] = head.neighbors()[1];
        head.neighbors()[1].neighbors()[0] = node;
        head.neighbors()[1] = node;
    }

    private void removeNode(Node<K, V> node) {
        node.neighbors()[0].neighbors()[1] = node.neighbors()[1];
        node.neighbors()[1].neighbors()[0] = node.neighbors()[0];
    }

    private void moveToHead(Node<K, V> node) {
        removeNode(node);
        addAfterHead(node);
    }
}

This from-scratch version exposes the mechanics: a HashMap for O(1) key lookup, a doubly-linked list for O(1) order manipulation, and sentinel nodes that eliminate null checks at the boundaries.

TreeMap — Sorted by Key, O(log n)

TreeMap stores entries in a Red-Black tree, maintaining keys in sorted order (natural ordering or a custom Comparator). Every operation — put, get, remove — runs in O(log n) because it traverses the tree from root to leaf.

When HashMap Is Not Enough

Use TreeMap when the problem requires:

• Sorted iteration — processing keys in ascending or descending order
• Range queries — finding all keys between a lower and upper bound
• Floor/ceiling lookups — finding the nearest key ≤ or ≥ a given value

TreeMap implements NavigableMap, which provides methods that HashMap cannot offer:

Method	Description
floorKey(K)	Greatest key ≤ given key
ceilingKey(K)	Smallest key ≥ given key
lowerKey(K)	Greatest key < given key
higherKey(K)	Smallest key > given key
subMap(K from, K to)	View of entries in range [from, to)
headMap(K to)	View of entries with keys < to
tailMap(K from)	View of entries with keys ≥ from
firstKey() / lastKey()	Smallest / largest key

Interval Scheduling with TreeMap

Problem: Given a list of intervals [start, end], determine if a new interval conflicts with any existing one.

This is the core of calendar scheduling and meeting room problems. TreeMap’s floorKey and ceilingKey make the check elegant:

public class IntervalScheduler {

    private final java.util.TreeMap<Integer, Integer> calendar = new java.util.TreeMap<>();

    public boolean book(int start, int end) {
        // Find the interval that starts at or before this one
        var prevEntry = calendar.floorEntry(start);
        if (prevEntry != null && prevEntry.getValue() > start) {
            return false;  // Previous interval overlaps
        }

        // Find the interval that starts at or after this one
        var nextEntry = calendar.ceilingEntry(start);
        if (nextEntry != null && nextEntry.getKey() < end) {
            return false;  // Next interval overlaps
        }

        calendar.put(start, end);
        return true;
    }
}

How it works: For any new interval [start, end], only two existing intervals can possibly overlap — the one immediately before (by start time) and the one immediately after. floorEntry and ceilingEntry find those two candidates in O(log n). Checking overlap is O(1). Total: O(log n) per booking.

Without TreeMap: You would need to scan all existing intervals — O(n) per booking. For n bookings, that is O(n²) total versus O(n log n) with TreeMap.

TreeMap Dos and Don’ts

• Do not use null keys. TreeMap throws NullPointerException because it must compare keys via compareTo() or a Comparator.
• Do ensure consistency between compareTo() and equals(). If compareTo() returns 0 for two keys, TreeMap treats them as equal — even if equals() returns false. This can silently overwrite entries.
• Do use subMap() for range-based queries instead of iterating and filtering manually.

ConcurrentHashMap — Thread-Safe Without Full Synchronization

ConcurrentHashMap is the standard answer to “How do you make a HashMap thread-safe?” The older approach — Collections.synchronizedMap() — wraps every method in a synchronized block, allowing only one thread to access the map at a time. ConcurrentHashMap permits concurrent reads and segmented concurrent writes.

Internal Architecture (Java 8+)

ConcurrentHashMap abandoned segment-based locking (Java 7 and earlier) in favor of a more granular strategy:

• Node-level CAS (Compare-And-Swap) for insertions into empty buckets. No lock needed if the bucket is empty — an atomic CAS places the first node.
• Per-bucket synchronization for insertions into occupied buckets. Only the first node in the bucket chain is locked, so writes to different buckets proceed in parallel.
• Lock-free reads — traversals never acquire locks, relying on volatile reads and the immutability of node keys and values once published.

This design scales linearly with the number of cores for read-heavy workloads. Write-heavy workloads still benefit from reduced contention compared to a single global lock.

computeIfAbsent for Thread-Safe Lazy Initialization

The computeIfAbsent method is atomic in ConcurrentHashMap (unlike HashMap, where it is not thread-safe). This makes it the go-to pattern for lazy initialization in concurrent code:

var cache = new java.util.concurrent.ConcurrentHashMap<String, ExpensiveObject>();

// Thread-safe: the mapping function runs at most once per key
ExpensiveObject value = cache.computeIfAbsent("config", key -> loadFromDatabase(key));

Without computeIfAbsent, the check-then-act pattern creates a race condition:

// BROKEN — two threads can both see key as absent and compute twice
if (!cache.containsKey("config")) {
    cache.put("config", loadFromDatabase("config"));
}

Concurrent Word Frequency Counter with Virtual Threads

Problem: Count word frequencies in a large file using multiple threads.

Java 25 virtual threads make this pleasantly concurrent:

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.LongAdder;
import java.util.List;

public class ConcurrentWordCounter {

    public ConcurrentHashMap<String, LongAdder> countWords(List<String> lines)
            throws InterruptedException {

        var frequencies = new ConcurrentHashMap<String, LongAdder>();

        // Partition lines and process each chunk in a virtual thread
        try (var executor = java.util.concurrent.Executors.newVirtualThreadPerTaskExecutor()) {
            for (String line : lines) {
                executor.submit(() -> {
                    for (String word : line.toLowerCase().split("\\W+")) {
                        if (!word.isEmpty()) {
                            frequencies.computeIfAbsent(word, _ -> new LongAdder())
                                       .increment();
                        }
                    }
                });
            }
        }
        // ExecutorService.close() waits for all tasks to complete

        return frequencies;
    }

    public void printTopWords(ConcurrentHashMap<String, LongAdder> frequencies, int topN) {
        frequencies.entrySet().stream()
            .sorted((a, b) -> Long.compare(b.getValue().sum(), a.getValue().sum()))
            .limit(topN)
            .forEach(e -> System.out.println(e.getKey() + ": " + e.getValue().sum()));
    }
}

Why LongAdder instead of AtomicLong? Under high contention, AtomicLong.incrementAndGet() causes CAS retries as multiple threads compete to update the same value. LongAdder distributes the count across multiple cells and sums them on demand — dramatically reducing contention for hot keys.

Why virtual threads? Each line processes in its own virtual thread. The JVM schedules millions of virtual threads onto a small pool of platform threads (carrier threads). This eliminates the thread pool sizing problem — you do not need to decide how many threads to create. The JVM handles it.

ConcurrentHashMap Pitfalls

• No null keys or values. Unlike HashMap, ConcurrentHashMap rejects null because get() returning null would be ambiguous — does the key not exist, or is the value null?
• Compound operations are not atomic. if (!map.containsKey(k)) map.put(k, v) is a race condition. Use putIfAbsent or computeIfAbsent instead.
• Size is approximate. In a concurrent environment, size() is an estimate because elements can be added or removed during the count. Use mappingCount() for a long-valued estimate on large maps.

EnumMap — O(1) with Enum Keys

When keys are enum values, EnumMap provides the fastest Map implementation. It is backed by a plain array indexed by ordinal() — no hashing, no collisions, no boxing:

enum Priority { LOW, MEDIUM, HIGH, CRITICAL }

var counts = new java.util.EnumMap<Priority, Integer>(Priority.class);
counts.put(Priority.HIGH, 42);
counts.put(Priority.LOW, 7);
// Iteration follows enum declaration order: LOW, MEDIUM, HIGH, CRITICAL

Use EnumMap whenever your keys are a known, fixed set of enum constants. It uses less memory than HashMap and runs faster for every operation.

IdentityHashMap — Reference Equality

IdentityHashMap uses == instead of equals() for key comparison and System.identityHashCode() instead of hashCode(). Two keys are equal only if they are the same object reference.

When is this useful?

• Serialization frameworks that need to track object identity to handle circular references.
• Interning checks where you want to distinguish between new String("hello") and another new String("hello").
• Graph algorithms where node identity matters more than structural equality.

This is niche, but interviewers occasionally ask about it to test edge case awareness.

Classic Interview Problems

Subarray Sum Equals K

Problem: Given an array of integers and a target k, find the total number of contiguous subarrays whose sum equals k.

The brute force checks all O(n²) subarrays. The prefix sum technique with a HashMap reduces this to O(n):

int subarraySum(int[] nums, int k) {
    var prefixCounts = new java.util.HashMap<Integer, Integer>();
    prefixCounts.put(0, 1);  // Empty prefix has sum 0

    int currentSum = 0;
    int count = 0;

    for (int num : nums) {
        currentSum += num;
        // If (currentSum - k) was a previous prefix sum,
        // then the subarray between that prefix and here sums to k
        count += prefixCounts.getOrDefault(currentSum - k, 0);
        prefixCounts.merge(currentSum, 1, Integer::sum);
    }

    return count;
}

Key insight: If prefixSum[j] - prefixSum[i] == k, then the subarray from i+1 to j sums to k. Rearranging: prefixSum[j] - k == prefixSum[i]. For each j, check how many previous prefix sums equal currentSum - k. The HashMap stores those counts.

Complexity: O(n) time, O(n) space.

Longest Consecutive Sequence

Problem: Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Must run in O(n) time.

Sorting gives O(n log n). A HashSet gives O(n):

int longestConsecutive(int[] nums) {
    var numSet = new java.util.HashSet<Integer>();
    for (int num : nums) numSet.add(num);

    int longest = 0;

    for (int num : numSet) {
        // Only start counting from the beginning of a sequence
        if (!numSet.contains(num - 1)) {
            int length = 1;
            int current = num;
            while (numSet.contains(current + 1)) {
                current++;
                length++;
            }
            longest = Math.max(longest, length);
        }
    }

    return longest;
}

Key insight: The if (!numSet.contains(num - 1)) check ensures you only start counting from the beginning of a consecutive sequence. Without this guard, you would re-count subsequences and the algorithm degrades to O(n²). With the guard, each element is visited at most twice (once in the outer loop, once in the inner while loop), giving O(n) total.

Complexity: O(n) time, O(n) space.

Performance Comparison

Feature	HashMap	LinkedHashMap	TreeMap	ConcurrentHashMap
Ordering	None	Insertion (or access)	Sorted by key	None
put/get/remove	O(1) avg	O(1) avg	O(log n)	O(1) avg
Null keys	1 allowed	1 allowed	Not allowed	Not allowed
Null values	Allowed	Allowed	Allowed	Not allowed
Thread-safe	No	No	No	Yes
Iterator	Fail-fast	Fail-fast	Fail-fast	Weakly consistent
Memory overhead	Moderate	Higher (linked list)	Higher (tree nodes)	Higher (CAS + nodes)
Best for	General purpose	LRU caches, ordered output	Range queries, sorted data	Concurrent access

Interviewer Tips

• Default to HashMap unless the problem requires ordering or concurrency. State this explicitly: “I’ll use a HashMap for O(1) lookups since ordering doesn’t matter here.”
• Know when to switch. If the interviewer asks “What if you need sorted output?”, pivot to TreeMap. If they ask “What about concurrent access?”, pivot to ConcurrentHashMap. Demonstrating that you know the full Map family earns strong signal.
• Use computeIfAbsent and merge instead of verbose check-then-act patterns. Interviewers notice clean, idiomatic code.
• Discuss memory trade-offs. HashMap stores keys, values, hash codes, and next pointers. For value types like integers, autoboxing adds overhead. If keys are integers in a bounded range [0, n), a plain array is faster and uses less memory.
• Know the fail-fast contract. Modifying a HashMap during iteration (without using the iterator’s remove()) throws ConcurrentModificationException. ConcurrentHashMap’s iterators are weakly consistent — they reflect some, but not necessarily all, modifications made after the iterator was created.
• Practice the LRU Cache problem until you can implement it in under 10 minutes, both with LinkedHashMap and from scratch with a HashMap + doubly-linked list. This problem appears at virtually every top-tier company.