Map

A Map stores key-to-value associations with unique keys, and the implementation you pick decides whether you get speed, insertion order, or sorted order.

A Map<K, V> associates unique keys with values — it is not a Collection (it does not extend that interface), but it is a core part of the Java Collections Framework. Java ships several implementations with different tradeoffs around ordering, performance, and null handling: HashMap, LinkedHashMap, TreeMap, and the legacy Hashtable.

What Is a Map

A Map maps each key to exactly one value. Keys are unique — putting a new value for an existing key replaces (overwrites) the old value rather than adding a second entry. Values may repeat across different keys.

Map does NOT extend Collection. List, Set, and Queue extend Collection; Map is a separate root interface in the framework. You can view a map's keys, values, or entries as collections via keySet(), values(), and entrySet(), but the map itself is not one.

Re-putting an existing key replaces its value; size stays 2 because keys are unique.

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

Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);
ages.put("Bob", 25);
ages.put("Alice", 31); // overwrites 30

System.out.println(ages.get("Alice")); // 31
System.out.println(ages.size());       // 2

Core Operations

The essential Map methods: put(key, value) inserts or replaces, get(key) retrieves (or returns null if absent), containsKey/containsValue check membership, remove(key) deletes an entry, size() and isEmpty() report bulk state, and entrySet()/keySet()/values() give collection views for iteration.

Map<String, Integer> stock = new HashMap<>();
stock.put("apples", 10);
stock.put("pears", 4);

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

int qty = stock.getOrDefault("bananas", 0); // 0, no exception
stock.putIfAbsent("apples", 999);           // no-op, key exists
stock.merge("apples", 5, Integer::sum);     // apples -> 15

HashMap

HashMap is the general-purpose implementation: backed by a hash table, offering average O(1) put/get/remove (worst case O(n) for pathological hash collisions, or O(log n) in modern HotSpot when a single bucket's chain grows large enough to convert to a tree). It gives no guarantee about iteration order — the order can appear to change across JVM versions, runs, or after resizing.

It permits one null key and multiple null values.

Map<String, String> m = new HashMap<>();
m.put(null, "nullKeyValue");
m.put("x", null);
System.out.println(m.get(null)); // nullKeyValue
System.out.println(m.get("x"));  // null

LinkedHashMap

LinkedHashMap extends HashMap and additionally maintains a doubly-linked list through entries, giving predictable iteration order — by default, insertion order. It can also be configured for access order (most-recently-accessed last), which is the basis for building simple LRU caches by overriding removeEldestEntry.

Map<String, Integer> m = new LinkedHashMap<>();
m.put("c", 3);
m.put("a", 1);
m.put("b", 2);
System.out.println(m.keySet()); // [c, a, b] - insertion order preserved

TreeMap

TreeMap implements NavigableMap/SortedMap, keeping entries sorted by key — either the keys' natural ordering (they must implement Comparable) or a Comparator supplied at construction. Operations are O(log n) because it is backed by a red-black tree. TreeMap does not permit a null key (a null key throws NullPointerException when there is an existing comparator/natural ordering to apply, since comparisons against null fail).

Map<String, Integer> m = new TreeMap<>();
m.put("banana", 2);
m.put("apple", 1);
m.put("cherry", 3);
System.out.println(m.keySet()); // [apple, banana, cherry] - sorted

TreeMap<String, Integer> tm = (TreeMap<String, Integer>) m;
System.out.println(tm.firstKey()); // apple
System.out.println(tm.lastKey());  // cherry

Hashtable — Historical Context

Hashtable predates the Collections Framework (Java 1.0). It is synchronized (every method is effectively thread-safe on its own, though compound operations still need external locking), and unlike HashMap it disallows both null keys and null values, throwing NullPointerException on either.

Hashtable is legacy. For new single-threaded code, prefer HashMap; for thread-safe maps, prefer ConcurrentHashMap, which offers much better concurrent performance than a globally-synchronized Hashtable.

Null Behavior by Implementation

Null handling is implementation-specific, not a blanket Map rule — this is a frequent source of subtle bugs when swapping implementations.

HashMap        : 1 null key allowed, multiple null values allowed
LinkedHashMap  : same as HashMap (it IS a HashMap subclass)
TreeMap        : null key throws NullPointerException (usually); null values allowed
Hashtable      : no null keys, no null values (NullPointerException)
ConcurrentHashMap: no null keys, no null values (NullPointerException)

Hashing and Bucket Placement

Hash-based maps use key.hashCode() to compute a bucket index, then key.equals() to distinguish keys that land in the same bucket. If you use a mutable object as a key and mutate it after insertion in a way that changes its hashCode(), the map can no longer find that entry — it looks in the wrong bucket. Always use immutable, well-behaved keys (String, boxed numbers, enums, or immutable custom classes with a correct equals/hashCode pair).

A typical HotSpot JVM's HashMap also converts an overly long bucket chain (collision list) into a small red-black tree once it passes an internal threshold, to bound worst-case lookup to O(log n) instead of O(n) — this is a JVM-level performance optimization, not something guaranteed by the Java Language Specification.

Ordering Comparison

HashMap       : no ordering guarantee (implementation/hash-dependent)
LinkedHashMap : insertion order (or access order, if configured)
TreeMap       : sorted order (natural or Comparator-defined)
Hashtable     : no ordering guarantee

Practical Usage

Maps are the natural fit for lookup tables, caches, counting/grouping, and configuration data. A very common idiom is frequency counting.

String text = "the quick brown fox the lazy dog the";
Map<String, Integer> freq = new HashMap<>();
for (String word : text.split(" ")) {
    freq.merge(word, 1, Integer::sum);
}
System.out.println(freq.get("the")); // 3

Edge Cases

get() returning null is ambiguous: it could mean 'key absent' or 'key present with a null value' (in maps that allow null values). Use containsKey() to disambiguate, or avoid storing nulls entirely.

Iterating a map's keySet() or entrySet() and structurally modifying the map (adding/removing keys) during iteration — other than through the iterator's own remove() — throws ConcurrentModificationException in the standard implementations.

Complete Example

computeIfAbsent groups names by first letter in one pass; TreeMap keeps the letters sorted. Output: A: [Ann, Alice], B: [Bob, Ben], C: [Carl]

import java.util.*;

public class MapDemo {
    public static void main(String[] args) {
        Map<String, List<String>> byFirstLetter = new TreeMap<>();
        String[] names = {"Ann", "Bob", "Alice", "Ben", "Carl"};

        for (String name : names) {
            String key = name.substring(0, 1);
            byFirstLetter.computeIfAbsent(key, k -> new ArrayList<>()).add(name);
        }

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

Mental Model

Think of a HashMap as a set of labeled bins: hashCode() decides which bin a key lands in, equals() decides which item in that bin matches. LinkedHashMap is the same bins with a thread tying entries together in insertion order. TreeMap throws away the bins entirely and instead keeps a sorted tree by key.

Quick Reference

Map<K,V> m = new HashMap<>();
m.put(k, v); m.get(k); m.remove(k);
m.containsKey(k); m.containsValue(v);
m.getOrDefault(k, def); m.putIfAbsent(k, v);
m.merge(k, v, fn); m.computeIfAbsent(k, fn);
for (Map.Entry<K,V> e : m.entrySet()) { ... }
m.keySet(); m.values(); m.size(); m.isEmpty();

Key Takeaways

Map is not a Collection — it maps unique keys to values.

HashMap is fastest but order is unspecified; LinkedHashMap adds predictable order; TreeMap keeps sorted order at O(log n) cost.

Hashtable is legacy, synchronized, and disallows nulls entirely — prefer HashMap or ConcurrentHashMap in new code.

Null-key/null-value support differs per implementation — check before relying on it.

Never mutate a key's hash-affecting state after inserting it into a hash-based map.

Map<String, Integer> m = new TreeMap<>(); m.put(null, 1); // throws NullPointerException

Map<String, Integer> m = new HashMap<>(); m.put(null, 1); // OK, HashMap allows one null key

TreeMap needs to compare keys to place them in order, so a null key generally throws NullPointerException; HashMap has no such restriction.

if (m.get(key) != null) { // assume key exists } if (m.containsKey(key)) { // key definitely exists, even if its value is null } get() returning null is ambiguous between 'absent key' and 'present key mapped to null'. containsKey() disambiguates.

List<String> key = new ArrayList<>(List.of("a")); map.put(key, "value"); key.add("b"); // mutates the key already in the map

List<String> key = List.copyOf(List.of("a", "b")); // immutable map.put(key, "value");

Mutating a key after insertion can change its hashCode(), making the map unable to find the entry — use immutable keys.

for (String k: map.keySet()) { if (shouldRemove(k)) map.remove(k); // ConcurrentModificationException } map.keySet().removeIf(k -> shouldRemove(k));

Structurally modifying a map while iterating its view (other than via the iterator's own remove) throws ConcurrentModificationException; removeIf avoids this.

Why is Map not part of the Collection hierarchy in Java?

Collection models a group of individual elements (with add/remove of single items), while Map models key-to-value associations — a fundamentally different contract, so it is a separate root interface, though it interoperates via keySet()/values()/entrySet().

What happens when you put() a key that already exists in a Map?

The existing value is replaced with the new value; put() returns the previous value (or null if there was none). The map's size does not increase.

Which built-in Map implementation would you choose for an LRU cache and why?

LinkedHashMap configured with access-order (accessOrder=true) plus an overridden removeEldestEntry, since it tracks recency of access and can evict the least-recently-used entry automatically.

Why can HashMap's iteration order appear to change between runs?

Order depends on each key's hashCode() and the internal table's size/layout, which can differ across JVM versions, resizes, or insertion sequences — it was never a guarantee, just an unspecified implementation detail.

What is the practical difference between get() and getOrDefault()?

get() returns null when the key is absent (ambiguous with a stored null value); getOrDefault() lets you supply an explicit fallback value for the absent case, avoiding a separate containsKey() check.

Why does Hashtable throw NullPointerException on null values but HashMap does not?

Hashtable predates modern null-handling design decisions in the Collections Framework and was designed to disallow both null keys and values outright, partly because its synchronized methods made ambiguous null returns especially risky in concurrent contexts.

What guarantee, if any, does Java give about the order TreeMap iterates in?

TreeMap guarantees iteration in the sorted order defined by the keys' natural ordering (Comparable) or by the Comparator supplied at construction — this is a documented guarantee of the class, not an implementation accident like HashMap's apparent order.

Write a program that counts how many times each character appears in a given string using a Map, then prints the counts sorted alphabetically by character.

import java.util.*; public class CharCount { public static void main(String[] args) { String s = "sampleapp"; Map<Character, Integer> counts = new TreeMap<>(); for (char c : s.toCharArray()) { counts.merge(c, 1, Integer::sum); } for (Map.Entry<Character, Integer> e : counts.entrySet()) { System.out.println(e.getKey() + ": " + e.getValue()); } } }

TreeMap sorts characters automatically; merge(c, 1, Integer::sum) increments the count or initializes it to 1. Output is alphabetical: a:2, e:1, l:1, m:1, p:3, s:1.

What does this print?

null, then 2. remove() on an absent key returns null and does not throw or change the map's size.

Write a program that builds a Map<String, Integer> from an array of words to their lengths, using only word starting with a vowel, using computeIfAbsent-style logic is not needed here — just put/containsKey.

import java.util.*; public class VowelWords { public static void main(String[] args) { String[] words = {"apple", "banana", "orange", "kiwi", "egg"}; Map<String, Integer> result = new LinkedHashMap<>(); String vowels = "aeiouAEIOU"; for (String w : words) { if (!w.isEmpty() && vowels.indexOf(w.charAt(0)) >= 0) { result.put(w, w.length()); } } System.out.println(result); } }

LinkedHashMap preserves insertion order. Output: {apple=5, orange=6, egg=3} — banana and kiwi are skipped since they don't start with a vowel.

Map<String, Integer> m = new HashMap<>();
m.put("a", 1);
m.put("b", 2);
Integer removed = m.remove("c");
System.out.println(removed);
System.out.println(m.size());