📦 Section 4 · Question #14

What is Map and what implementations exist

The Map interface (java.util.Map), also known as an associative array or dictionary, represents a data structure that maps unique Keys to Values:

📦 Collections 📄 Source Markdown

🟢 Junior Level

1. What is a Map

The Map<K, V> interface (java.util.Map), also known as an associative array or dictionary, represents a data structure that maps unique Keys to Values:

  • Keys (K): Must be strictly unique. Adding an existing key replaces the previous associated value.
  • Values (V): May contain duplicates; multiple keys can point to identical values.
  • Each key maps to at most one corresponding value.
Map<String, Integer> salaries = new HashMap<>();
salaries.put("Alex", 120_000);
salaries.put("Maria", 150_000);

// Retrieving a value by key:
Integer alexSalary = salaries.get("Alex"); // 120000

// Checking key existence:
boolean hasMaria = salaries.containsKey("Maria"); // true

2. Why Does Map NOT Extend Collection?

A quintessential Java interview question: Map is deliberately separate from the Collection interface hierarchy due to two fundamental architectural reasons:

  1. Incompatible Element Semantics: Collection<E> manages a container of discrete single items (add(E e), iterator()), whereas Map<K, V> manages 2-dimensional key-value pairs (put(K key, V value)).
  2. Collection Views: Rather than supporting direct iteration, Map exposes three distinct collection views:
    • keySet() $\to$ Set<K> (a set of unique keys).
    • values() $\to$ Collection<V> (a collection of non-unique values).
    • entrySet() $\to$ Set<Map.Entry<K, V>> (a set of key-value pair entries).

3. Master Summary Table of Map Implementations

Implementation Key Ordering Complexity (get/put) null Allowed? Thread-Safe? Primary Use Case
HashMap Non-deterministic $O(1)$ average Key: ✅ (1), Val: ✅ ❌ No General-purpose default mapping
LinkedHashMap Insertion or Access Order $O(1)$ average Key: ✅ (1), Val: ✅ ❌ No Deterministic traversal, LRU cache
TreeMap Sorted (Comparable/Comparator) $O(\log N)$ Key: ❌ (NPE), Val: ✅ ❌ No Sorted reporting, range queries
ConcurrentHashMap Non-deterministic $O(1)$ average Key: ❌, Val: ❌ ✅ Yes Scalable high-concurrency systems
EnumMap Declaration order of enum $O(1)$ (Array index) Key: ❌, Val: ✅ ❌ No Enum keys (fastest map in JVM)
WeakHashMap Non-deterministic $O(1)$ average Key: ✅, Val: ✅ ❌ No GC-driven metadata associations
IdentityHashMap Non-deterministic (==) $O(1)$ average Key: ✅, Val: ✅ ❌ No Serializers, cyclic graph traversal

🟡 Middle Level

1. Specialized High-Performance Implementations

EnumMap: Peak Mechanical Sympathy

When keys are instances of an enum, using HashMap is an architectural anti-pattern. EnumMap is backed by a compact, single-dimensional array:

enum TaskPriority { LOW, MEDIUM, HIGH, URGENT }

Map<TaskPriority, String> tasks = new EnumMap<>(TaskPriority.class);
tasks.put(TaskPriority.HIGH, "Hotfix production outage");
  • Why it surpasses HashMap: Keys are indexed directly by their enum.ordinal(). This eliminates hashCode() computation, eliminates hash collisions, requires no bucket linked lists or trees, and achieves direct array reads (vals[key.ordinal()]) in 1 CPU clock cycle.

IdentityHashMap: Reference Identity (==)

Unlike all other standard maps, IdentityHashMap completely ignores equals() and hashCode(). Keys $k_1$ and $k_2$ match if and only if $k_1 == k_2$.

  • Internally uses open addressing in a flat array Object[] table, alternating keys and values (table[i] = key, table[i+1] = value), hashed using System.identityHashCode().
  • Indispensable in serialization frameworks (Jackson, Kryo) and deep-cloning utilities to track visited objects and prevent infinite recursion in cyclic graphs.

WeakHashMap: Weak Key Tracking

Keys are wrapped inside java.lang.ref.WeakReference. When a key object loses all strong references across the application, the garbage collector marks the key for collection. Upon subsequent operations on the map, stale entries are purged via an internal ReferenceQueue.

2. Functional Mutation API (Java 8+)

Java 8 modernized map manipulation with higher-order functional methods:

Map<String, List<String>> userRoles = new HashMap<>();

// computeIfAbsent: initializes and inserts the collection only if key was missing:
userRoles.computeIfAbsent("john", k -> new ArrayList<>()).add("ROLE_ADMIN");

// merge: perfect for atomic-like counters and string aggregations:
Map<String, Integer> wordFrequency = new HashMap<>();
wordFrequency.merge("engine", 1, Integer::sum); // inserts 1 if absent, else oldVal + 1

// getOrDefault: avoids null checks and NullPointerExceptions:
int count = wordFrequency.getOrDefault("missing", 0);

3. Immutable Factory Methods (Java 9+)

Map.of() and Map.ofEntries() return unmodifiable, compact map implementations:

// Up to 10 key-value pairs:
Map<String, String> config = Map.of(
    "env", "production",
    "timeout", "5000"
);

// More than 10 pairs:
Map<Integer, String> statusCodes = Map.ofEntries(
    Map.entry(200, "OK"),
    Map.entry(404, "Not Found"),
    Map.entry(500, "Internal Server Error")
);

Architectural Properties:

  • Strictly reject null keys and values (NullPointerException).
  • Consume $2\times\text{ to }3\times$ less memory than HashMap by utilizing a flat linear-probing array instead of allocating individual Node objects.
  • Randomized Iteration Order: Key encounter order is intentionally shuffled on every JVM execution to prevent applications from writing code that depends on pseudo-accidental ordering.

🔴 Senior Level

1. Java 21 Architectural Evolution: SequencedMap (JEP 431)

Prior to Java 21, Java lacked a common abstraction for maps with a well-defined encounter order. Java 21 introduced SequencedMap<K, V>:

          ┌─────────────────┐
          │   Map<K, V>     │
          └────────┬────────┘
                   │ extends
          ┌────────┴────────┐
          │ SequencedMap    │
          └───┬─────────┬───┘
              │         │
     implements         implements
              │         │
   ┌──────────┴──┐   ┌──┴───────────┐
   │LinkedHashMap│   │ NavigableMap │
   └─────────────┘   └──┬───────────┘
                        │ implements
                     ┌──┴───────────┐
                     │   TreeMap    │
                     └──────────────┘

SequencedMap standardizes first/last entry manipulation across ordered maps:

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.putFirst("A", 1);
map.putLast("Z", 26);

Map.Entry<String, Integer> first = map.firstEntry(); // "A" -> 1
Map.Entry<String, Integer> last = map.lastEntry();   // "Z" -> 26

// Constant-time zero-copy reverse view:
SequencedMap<String, Integer> reversed = map.reversed();

Note: HashMap does not implement SequencedMap because it provides no ordering guarantees.

2. Constructing an LRU Cache via LinkedHashMap

LinkedHashMap provides native support for building an in-memory Least Recently Used (LRU) eviction cache via its special constructor and removeEldestEntry() hook:

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

    public LruCache(int maxCapacity) {
        // accessOrder = true: elements are reordered upon read (get) as well as write (put)
        super(maxCapacity, 0.75f, true);
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // Automatically evicts the least recently accessed entry when capacity is exceeded:
        return size() > maxCapacity;
    }
}

[!WARNING] Thread-Safety Warning: This pattern is not thread-safe. When accessOrder = true, calling get(key) is a structural mutation (it unlinks the node and appends it to the tail of the doubly-linked list). Concurrent reads without synchronization will corrupt pointers, create circular loops, or throw ConcurrentModificationException. For production concurrency, utilize dedicated caching engines like Caffeine.

3. Obsolete Legacy Maps: Hashtable and Properties

  • Hashtable: Originating in Java 1.0, every method is guarded by a method-level synchronized lock on the entire instance. It rejects null keys and values. Completely superseded by ConcurrentHashMap.
  • Properties: Extends Hashtable<Object, Object>. A severe type-safety design flaw: while setProperty(String, String) and getProperty(String) accept and return strings, because it inherits Hashtable.put(Object, Object), developers can insert arbitrary non-string objects, causing runtime ClassCastExceptions when calling getProperty().

4 Tricky Questions

1. Why does Map not extend Collection, but Map.values() returns a Collection<V>?

Answer: Collection<E> defines operations on a sequence of homogeneous single elements, mandating the add(E e) contract. Map operates on 2-dimensional associations (Map.Entry<K, V>), making single-element additions meaningless. Map.keySet() returns a Set<K> because map keys are guaranteed to be unique. However, Map.values() cannot return a Set<V> because multiple distinct keys can map to the exact same value. Therefore, values() returns the broader Collection<V> interface, permitting duplicate value elements.

2. Why is EnumMap architecturally superior to HashMap for enum keys?

Answer: EnumMap exploits the JVM guarantee that all enum constants have fixed, consecutive integer ordinals (ordinal()). Under the hood:

  • EnumMap stores values in a flat Object[] vals array sized to the number of enum constants.
  • Lookups and insertions bypass hashCode(), avoid bitwise masking, require no bucket lists, and never suffer hash collisions.
  • Access is compiled down to a single bounds check and indexed array read (vals[key.ordinal()]), executing in 1 CPU cycle with superior cache locality and zero node object allocation.

3. Why can reading from a LinkedHashMap via get() throw ConcurrentModificationException during iteration?

Answer: If the LinkedHashMap was instantiated with accessOrder = true (access-order mode for LRU caching), invoking get(key) modifies the structural ordering of the collection by relocating the accessed entry to the tail of its internal doubly-linked list. This structural mutation increments the internal modCount field. If an active Iterator is traversing keySet(), values(), or entrySet() while get() is invoked, the iterator’s next step detects that expectedModCount != modCount and throws a ConcurrentModificationException.

4. How does IdentityHashMap evaluate key equality, and in what mission-critical domains is it indispensable?

Answer: IdentityHashMap uses reference equality (k1 == k2) and System.identityHashCode(k) rather than virtual .equals() and .hashCode(). It is indispensable in:

  1. Object Graph Traversal / Serialization: Frameworks like Jackson, Kryo, or Spring Object-Copier maintain an IdentityHashMap<Object, Boolean> visited to track processed heap instances. This prevents infinite recursion when traversing circular references (A -> B -> A), even if A.equals(B) might otherwise evaluate to true.
  2. Dynamic Bytecode & Proxies: Associating internal metadata with runtime proxy instances without risking collisions with overridden domain equals() methods.

🎯 Interview Cheat Sheet

30-Second Elevator Pitch

“Map<K, V> represents a key-value dictionary that enforces key uniqueness while allowing duplicate values. It is intentionally decoupled from Collection because it operates on pairs, exposing collection views via keySet(), values(), and entrySet(). Primary implementations include HashMap ($O(1)$ general default), LinkedHashMap (preserves insertion or access order for LRU caches), TreeMap ($O(\log N)$ sorted via Red-Black Tree), and ConcurrentHashMap (lock-free CAS and bucket synchronization for high-concurrency). Specialized variants like EnumMap provide hardware-level array access for enums, and IdentityHashMap matches keys via == for object graph traversal. In Java 21, ordered maps implement SequencedMap.”

High-Impact Architectural Facts

  • Views Backing: keySet(), values(), and entrySet() return backed views, not copies; modifying or removing through a view iterator mutates the parent map.
  • EnumMap Speed: Flat array indexing via ordinal() eliminates hashing, collisions, and node overhead.
  • Java 9 Immutability: Map.of() uses flat compact arrays with linear probing, randomized iteration order, and null prohibition.
  • LRU Access Trap: In LinkedHashMap(cap, factor, true), get() mutates modCount, meaning concurrent reads require synchronization to avoid data corruption.
  • SequencedMap (Java 21): Extends Map with firstEntry(), lastEntry(), putFirst(), putLast(), and zero-copy reversed().

Common Pitfalls & Red Flags

  • ❌ Calling Map a Collection: An immediate red flag indicating unfamiliarity with the core JDK interface taxonomy.
  • ❌ Using WeakHashMap as a general cache: Keys are purged during Minor GC as soon as external strong references vanish.
  • ❌ Iterating a map via map.keySet() and calling map.get(key) inside the loop: An anti-pattern that costs $2\times$ lookups; always iterate over map.entrySet().
  • ❌ Using Hashtable in modern applications: Outdated, coarse synchronization bottleneck; replace with ConcurrentHashMap.