jd five

Maps

Learning goals

By the end of this chapter you should be able to:

  • Use Map for key → value lookup and explain one-key-only semantics
  • Choose HashMap, LinkedHashMap, TreeMap, or ConcurrentHashMap
  • Apply computeIfAbsent, merge, and getOrDefault idioms
  • Build a simple LRU cache with access-order LinkedHashMap (Java 21+ pollFirstEntry)

Maps: keys as the index

Unlike List, a Map indexes by an arbitrary key — usually not an integer position.

Map<String, Integer> wordCount = new HashMap<>();
wordCount.merge("java", 1, Integer::sum);
wordCount.computeIfAbsent("kotlin", k -> 0);

Each key maps to at most one value. Replacing a value does not change key order (implementation-dependent iteration).

Null rules matter: HashMap allows one null key and null values; ConcurrentHashMap allows neither — plan accordingly in concurrent caches.

A Map maps keys to values; each key appears at most once. HashMap allows one null key and null values. ConcurrentHashMap allows no null keys or values.

This guide keeps maps that differ by default lookup, iteration/eviction order, sorted keys + ranges, thread-safe concurrent updates, and immutable snapshots. Niche key semantics (weak/identity/enum-only) are omitted here—use HashMap or TreeMap unless a textbook problem specifically needs them.

HashMap — not concurrent

Hash table: keys land in buckets by hash code; long buckets may become trees (Java 8+). Average get / put / remove O(1).

Initialize: Map<K,V> m = new HashMap<>(); — or new HashMap<>(initialCapacity) / new HashMap<>(anotherMap).

Sharing across threads: wrap when you need one big lock around the whole map (simple; often beaten by ConcurrentHashMap under load):

Map<String, String> m = Collections.synchronizedMap(new HashMap<>());

Prefer new ConcurrentHashMap<>() for scalable concurrent put/get—see below.

Why / vs alternatives: Default mutable map for fast arbitrary-key lookup. LinkedHashMap when iteration order must follow insert or access; TreeMap when keys must stay sorted or you need ranges; ConcurrentHashMap when many threads mutate the map.

  • get(key) — returns the value for key, or null if no mapping (or if null is stored—disambiguate with containsKey).
  • put(key, value) — associates key with value; returns the previous value or null.
  • putIfAbsent(key, value) — puts only if key absent; returns current value.
  • remove(key) — removes mapping for key; returns old value.
  • remove(key, value) — removes only if current value equals given value.
  • replace(key, value) — replaces value if key exists.
  • replace(key, old, new) — replaces only if current value equals old.
  • containsKey(key) / containsValue(value) — whether some entry matches.
  • getOrDefault(key, default) — returns stored value or default.
  • compute, computeIfAbsent, computeIfPresent, merge — update value from key and/or old value with a function.
  • size(), isEmpty(), clear() — size, empty check, remove all.
  • keySet() — view of all keys; changes reflect the map.
  • values() — view of all values.
  • entrySet() — view of Map.Entry pairs; use for iterating both key and value.
  • forEach(biConsumer) — (key, value) for each entry.

LinkedHashMap — not concurrent

Same operations as HashMap, plus iteration order: insertion order, or access order if accessOrder = true (needed for LRU-style recency).

Initialize: new LinkedHashMap<>() — insertion order only. For LRU recency: new LinkedHashMap<>(initialCapacity, loadFactor, true) — third argument true is access order; loadFactor is usually 0.75f (same default as HashMap—controls when the table rehashes, not cache size). LinkedHashSet has no such option—it only ever follows insertion order.

Sharing across threads:

Map<String, String> m = Collections.synchronizedMap(new LinkedHashMap<>());

Preserves insertion or access order under the wrapper’s lock (match accessOrder to your new LinkedHashMap<>(…, …, true) build).

Why / vs alternatives: HashMap iteration order is unpredictable—bad when you need deterministic traversal or who-was-used-last eviction. TreeMap if you need sorted keys, not just stable insert/access order.

LRU-style cap (no subclass): Use access-order map, put/get as usual, then if size() is over your max, evict the eldest entry: in this mode, encounter order is least-recently used → most-recently used, so the head is the LRU victim.

Java 21+: LinkedHashMap implements SequencedMap. Prefer pollFirstEntry()—it removes the first entry in encounter order (here: LRU) in one call. firstEntry() if you only need to read the head.

LinkedHashMap<String, String> cache = new LinkedHashMap<>(64, 0.75f, true);

cache.put(key, value);
if (cache.size() > 100) {
    cache.pollFirstEntry(); // eldest / LRU in access-order mode
}

Older Java: There was no getEldestKey()—the portable spell was first key in iteration order: cache.remove(cache.keySet().iterator().next()); (same semantics for access-order LinkedHashMap).

Change 100 to your limit. Often you run the check right after put.

TreeMap — not concurrent

Red-black tree keyed by Comparable keys or a Comparator. get / put / remove O(log n). Keys stay sorted. NavigableMap range and neighbour APIs.

Initialize: NavigableMap<K,V> m = new TreeMap<>(); — or new TreeMap<>(comparator) / new TreeMap<>(existingSortedMap).

Sharing across threads:

NavigableMap<String, Integer> m = Collections.synchronizedNavigableMap(new TreeMap<>());

Keeps headMap/subMap/NavigableMap APIs on the wrapped map.

Why / vs alternatives: HashMap cannot maintain order or answer subMap/headMap/tailMap / nearest-key queries in logarithmic time. Trade-off: slower single ops than HashMap average O(1). Concurrent mutation needs external locking or redesign (e.g. shard by key).

All HashMap operations, plus:

  • firstKey() / lastKey() — smallest / largest key.
  • lowerKey(k), floorKey(k), ceilingKey(k), higherKey(k) — nearest keys relative to k.
  • firstEntry() / lastEntry() / pollFirstEntry() / pollLastEntry() — entry views at ends.
  • descendingMap() — map view in reverse order.
  • headMap(toKey) — keys < toKey (default overload).
  • tailMap(fromKey) — keys ≥ fromKey.
  • subMap(from, to) — from ≤ key < to for default bounded pairs.

Overloads with boolean control endpoint inclusivity. Views are live.

ConcurrentHashMap — concurrent

Concurrent HashMap for high read/write concurrency. No null keys or values. Iterators are weakly consistent.

Initialize: Map<K,V> m = new ConcurrentHashMap<>(); — or new ConcurrentHashMap<>(initialCapacity) / new ConcurrentHashMap<>(anotherMap).

Sizing (optional)—same shape as HashMap overloads; no boolean “enable concurrency” flag (this class is always safe for concurrent Map mutation):

Map<String, String> m = new ConcurrentHashMap<>(32, 0.75f);

Internal striping picks up from here.

Why / vs alternatives: HashMap is not safe under concurrent writers. Collections.synchronizedMap(new HashMap<>()) serializes every operation—simple but often slower under contention. ConcurrentHashMap is the standard building block for shared caches, registries, and Collections.newSetFromMap concurrent sets.

  • Same get, put, remove, replace, compute*, merge, forEach, keySet, values, entrySet usage as HashMap, with concurrent semantics.
  • putAll — bulk put.

Immutable maps — immutable · safe to share

Initialize: Map.of(k1, v1, k2, v2) — up to 10 pairs via overloads; or Map.copyOf(existingMap).

Why / vs alternatives: Publish configuration or defaults callers cannot put—fewer accidental mutations. Map.of rejects null keys/values. Large evolving maps → HashMap.

Next: Queues & deques

Practice checkpoint

  1. Count frequency of words in a file — core call pattern? Answer: map.merge(word, 1, Integer::sum) or compute.

  2. get(key) returns null — does key exist? Answer: unknown — could be missing or mapped to null; use containsKey or getOrDefault.

  3. Thread-safe cache with high read/write concurrency — which map? Answer: ConcurrentHashMap (not Collections.synchronizedMap(new HashMap<>()) under heavy contention).

  4. LRU cap of 100 entries after access-order inserts — eviction call (Java 21+)? Answer: after put, if size() > 100, pollFirstEntry() on access-order LinkedHashMap.

Interview angles

  • HashMap buckets → trees: long chains become red-black trees (Java 8+) for O(log n) worst case in a bucket.
  • LinkedHashMap access order: encounter order = LRU → MRU; head is eviction victim.
  • ConcurrentHashMap: striping / CAS — no global lock on every get.
  • Immutable config: Map.of / Map.copyOf — no null keys/values in Map.of.

Next: /java/learn/collections/queues-and-deques/