Which Map implementations does Java offer beyond HashMap, and when do you pick each?

Public candidate reviews of Zalando interviews mention "maps, its implementations and working" as a topic. HashMap internals are covered in the ConcurrentHashMap answer earlier in this chapter; this answer is about choosing between the implementations, which is where interviewers usually push next.

Start from the contract, not the class. Ask what the caller needs: plain lookup, a predictable iteration order, sorted keys and range queries, enum keys, safe sharing between threads, or special key semantics. Each standard implementation exists for one of those.

LinkedHashMap as an LRU cache. The Javadoc says an access-ordered LinkedHashMap is "well-suited to building LRU caches", and removeEldestEntry lets you evict on insert:

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxEntries;

    public LruCache(int maxEntries) {
        super(16, 0.75f, true);            // true = access order, so get() moves an entry to the end
        this.maxEntries = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxEntries;        // evict the least recently accessed entry
    }
}

Verified with OpenJDK 21.0.13: with a capacity of two, putting dress and shoes, reading dress, then putting jacket leaves [dress, jacket]. Two caveats to say out loud. In access-order mode even get is a structural modification, so the class is not safe to share without external synchronization. For a production cache that many request threads share, a purpose-built cache library or a ConcurrentHashMap with a bounded eviction policy is the better answer.

TreeMap versus ConcurrentSkipListMap. Both are NavigableMaps with sorted keys and range views. TreeMap is single-threaded with a guaranteed log(n) bound. ConcurrentSkipListMap lets threads insert and read at the same time with an expected, not guaranteed, log(n) cost, and its iterators are weakly consistent. Use it when the sorted structure is shared, for example a time-ordered buffer of index updates.

The two traps. WeakHashMap holds keys weakly but values strongly, and the Javadoc warns that a value that refers back to its own key, directly or indirectly, prevents the key from ever being collected, which turns the "self-cleaning" map into a leak. IdentityHashMap "intentionally violates Map's general contract" by comparing with ==; two equal Strings built separately are two different keys.

How to close the answer. "In a search service, most maps are HashMaps inside one request. Shared state is a ConcurrentHashMap with atomic compute or merge, sorted shared state is a skip list, and anything that must evict is a real bounded cache, not an unbounded map."

Alternate interview scenarios