Map

A Map<K, V> stores key-to-value associations with unique keys. It is the most heavily used data structure in real systems — caches, indexes, counters, and configuration all live in maps. A Map is not a Collection; it exposes its contents through the keySet(), values(), and entrySet() views.

Choosing an Implementation

Implementation	Order	get/put	Thread-safe	Notes
HashMap	None	O(1) avg	No	The default choice
LinkedHashMap	Insertion (or access)	O(1) avg	No	LRU caches via access order
TreeMap	Sorted by key	O(log n)	No	Range queries, navigation
ConcurrentHashMap	None	O(1) avg	Yes (lock-striped)	High-concurrency, no null keys/values

Use HashMap until you have a reason not to. Use LinkedHashMap for predictable iteration or LRU eviction, TreeMap for sorted/range access, and ConcurrentHashMap whenever a map is shared across threads.

Core Operations

Map<String, Integer> ages = new HashMap<>();
ages.put("Ada", 36);
ages.put("Linus", 24);

int ada = ages.get("Ada");                 // 36
int bob = ages.getOrDefault("Bob", -1);    // -1, no NPE
ages.putIfAbsent("Ada", 99);               // ignored, key exists

System.out.println(ada + " " + bob + " " + ages.get("Ada"));

Output:

36 -1 36

computeIfAbsent and merge

These two methods eliminate most boilerplate around maps. computeIfAbsent lazily builds a value (ideal for multimaps); merge combines a new value with any existing one (ideal for counters).

// Multimap: group words by first letter
Map<Character, List<String>> byLetter = new HashMap<>();
for (String w : List.of("ant", " box", "arc", "bee")) {
    byLetter.computeIfAbsent(w.charAt(0), k -> new ArrayList<>()).add(w);
}

// Frequency counter
Map<String, Integer> freq = new HashMap<>();
for (String w : List.of("a", "b", "a", "a")) {
    freq.merge(w, 1, Integer::sum);
}

System.out.println(byLetter);
System.out.println(freq);

Output:

{a=[ant, arc], b=[box, bee]}
{a=3, b=1}

Iterating a Map

Iterate entrySet() to access keys and values together in a single pass — never loop keySet() and call get() per key.

Map<String, Integer> scores = Map.of("Ada", 90, "Linus", 80);
for (Map.Entry<String, Integer> e : scores.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}
scores.forEach((k, v) -> { /* lambda form */ });

The equals/hashCode Contract for Keys

Hash-based maps locate entries by hashCode() then confirm with equals(). A key whose hash or equality is broken — or whose hashed fields mutate after insertion — becomes unreachable.

record CacheKey(String region, String id) {}  // correct equals + hashCode

Map<CacheKey, String> cache = new HashMap<>();
cache.put(new CacheKey("eu", "42"), "hit");
System.out.println(cache.get(new CacheKey("eu", "42")));  // hit

Output:

hit

Use immutable keys. String, boxed numbers, records, and enums are ideal. A mutable key whose hashCode changes after put is a classic source of “the value is in the map but get returns null” bugs.

Best Practices

• Default to HashMap; share state across threads with ConcurrentHashMap, never a synchronized HashMap.
• Use getOrDefault, computeIfAbsent, and merge instead of containsKey + get + put ladders.
• Iterate entrySet(), not keySet() + get().
• Keep keys immutable and consistent in equals/hashCode.
• Pre-size with new HashMap<>(expectedSize) for large, known datasets to avoid rehashing.

Interview Questions

Q: How does HashMap resolve collisions, and what changed in Java 8? A: Entries hashing to the same bucket form a linked list. Since Java 8, a bucket with more than 8 entries (when the table size is ≥ 64) is treeified into a red-black tree, lowering worst-case lookup from O(n) to O(log n). It reverts to a list if the bucket shrinks below 6.

Q: Why must HashMap keys be immutable? A: The bucket index is derived from hashCode() at insertion time. If a mutable field that feeds hashCode changes afterward, the key hashes to a different bucket and the entry becomes unreachable — get returns null even though the entry exists.

Q: How does ConcurrentHashMap achieve thread safety without locking the whole map? A: Modern implementations lock only the individual bucket being updated (CAS for empty bins, a synchronized block per bin head otherwise), allowing concurrent reads and disjoint writes. Reads are largely lock-free. It forbids null keys and values to avoid ambiguity between “absent” and “mapped to null.”

Q: What is the difference between HashMap and Hashtable? A: Hashtable is legacy: every method is synchronized (coarse-grained, slow under contention) and it forbids null. HashMap is unsynchronized and faster; for concurrency use ConcurrentHashMap, which scales far better than Hashtable.