🟢 Junior Level

Map (Dictionary) — a collection of key-value pairs.

Analogy: A Map is like a paper dictionary: by a word (key) you find its definition (value). The key is unique (a word appears in the dictionary only once), the value can repeat (different words can have the same definition).

Map<String, Integer> ages = new HashMap<>();
ages.put("Ivan", 25);    // Put
ages.put("Maria", 30);

int age = ages.get("Ivan");  // Get → 25
boolean has = ages.containsKey("Ivan");  // → true

Main implementations:

Implementation	When to use
HashMap	Default (fast)
LinkedHashMap	Need order
TreeMap	Need sorting
ConcurrentHashMap	Multithreading

Map ≠ Collection!

• Map works with PAIRS (key-value)
• Collection works with SINGLE elements

---

🟡 Middle Level

Main implementations

HashMap:

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);  // O(1)
map.get("A");     // O(1)
// → Fast, no order

LinkedHashMap:

Map<String, Integer> map = new LinkedHashMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);
// → Order: C, A, B (as inserted)

TreeMap:

Map<String, Integer> map = new TreeMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);
// → Order: A, B, C (sorted)
// → floorKey, ceilingKey, subMap

Specialized Maps

EnumMap:

// For Enum keys — the fastest! Internally an array — index = enum.ordinal(), no hashing and no collisions. Direct indexing = O(1) with no overhead.
enum Status { ACTIVE, INACTIVE }
Map<Status, String> map = new EnumMap<>(Status.class);
// → Internally: array! O(1), minimum memory

WeakHashMap:

// Keys = weak references
// Removed when no strong references to key exist
Map<Object, String> map = new WeakHashMap<>();
// → For caches and metadata

IdentityHashMap:

// Comparison by == (address), not equals
Map<String, String> map = new IdentityHashMap<>();
map.put(new String("A"), "1");
map.put(new String("A"), "2");  // Two different keys!
// → For serialization, cycle detection

Java 9+ immutable Maps

// Factory methods
Map<String, Integer> map = Map.of(
    "A", 1,
    "B", 2,
    "C", 3
);
// → Cannot be modified!
// → Compact memory
// → Order is randomized!
// Map.of() limitations: maximum 10 pairs, null keys/values are prohibited. For > 10 pairs — use Map.ofEntries().

Java 8+ useful methods

map.computeIfAbsent(key, k -> new ArrayList<>())
   .add(value);

map.merge(key, 1, Integer::sum);  // Counter

map.putIfAbsent(key, value);

---

🔴 Senior Level

Java 21: SequencedMap

// LinkedHashMap and TreeMap → SequencedMap
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.putFirst("A", 1);   // New method!
map.putLast("Z", 26);   // New method!
map.firstEntry();       // New method!
map.reversed();         // Reverse order (view)

// HashMap is NOT SequencedMap (no order)

Memory Footprint

HashMap Entry: ~32-48 bytes
  → Node: hash, key, value, next

LinkedHashMap: ~48 bytes
  → + before, after references

TreeMap: ~40-56 bytes
  → Entry: key, value, left, right, parent, color

→ For millions of entries → gigabytes!

Load Factor trade-off

Load Factor = ratio of number of elements to number of buckets. With load factor 0.75 and a map of 100 elements — 133 buckets. When fill factor exceeds 75% — resize (table recreation).

Default: 0.75

0.75 = balance between:
  → Memory (lower → higher fill factor)
  → Collisions (higher → slower search)

Increase (0.9):
  → -20% memory
  → +collisions

Decrease (0.5):
  → +50% memory
  → -collisions

IdentityHashMap use cases

// 1. Cycle detection in object graphs
IdentityHashMap<Object, Boolean> visited = new IdentityHashMap<>();

// 2. Serialization (tracking already serialized)
IdentityHashMap<Object, Integer> serialized = new IdentityHashMap<>();

// 3. When equals is overridden but identity is needed

EnumMap: why is it the fastest?

// Internally: Object[] array
// Index = ordinal()_enum

// put(key, value):
array[key.ordinal()] = value;  // O(1), direct indexing!

// get(key):
return array[key.ordinal()];   // O(1), no hashing!

→ Faster than HashMap, less memory

Highload aspects

HashMap:
  → Treeification on collisions (> 8)
  → Resize: O(n), latency spike
  → Memory: ~32 bytes per entry

ConcurrentHashMap:
  → Lock-free reads
  → CAS + synchronized per bucket
  → Zero latency for reads

Production Experience

Real scenario: HashMap → EnumMap

// Before: HashMap<Status, Counter>
// 100,000 requests/sec → GC pressure

// After: EnumMap<Status, Counter>
// → -40% memory
// → +25% throughput

Best Practices

1. HashMap — by default
2. EnumMap — for Enum keys
3. LinkedHashMap — order or LRU
4. TreeMap — sorting/ranges
5. ConcurrentHashMap — multithreading
6. Map.of() — for static lookups
7. Immutable keys — mandatory!
8. computeIfAbsent/merge — atomic operations

Summary for Senior

• Map ≠ Collection (pairs vs single elements)
• SequencedMap (Java 21) → putFirst/reversed
• EnumMap = array → fastest
• IdentityHashMap = comparison by ==
• Load Factor = memory vs collisions trade-off
• computeIfAbsent/merge — atomic Java 8+
• Immutable keys — critical!
• Map.of() → compact immutable maps

---

🎯 Interview Cheat Sheet

Must know:

• Map — collection of key-value pairs, keys are unique, Map ≠ Collection
• HashMap = O(1), default; LinkedHashMap = O(1) + insertion order; TreeMap = O(log n) + sorting; ConcurrentHashMap = thread-safe
• EnumMap — fastest Map (internally array, index = ordinal), for enum keys
• WeakHashMap — keys are automatically removed when no strong references exist (for metadata, NOT for caches)
• IdentityHashMap — comparison by == instead of equals (for serialization, cycle detection)
• Load factor 0.75 — balance between memory and collisions
• Java 21: SequencedMap API (putFirst, putLast, reversed) for LinkedHashMap and TreeMap
• Java 8+: computeIfAbsent, merge, putIfAbsent — atomic operations
• Map.of() — immutable Maps, max 10 pairs, nulls prohibited

Frequent follow-up questions:

• Why is EnumMap the fastest? — Internally an array, direct indexing by ordinal(), no hashing and no collisions — O(1) with minimal overhead.
• How does WeakHashMap differ from a regular Map for caching? — WeakHashMap removes entries on EVERY Minor GC — the cache may disappear within milliseconds. For caches, Caffeine or SoftReference is better.
• When to use IdentityHashMap? — When reference comparison (==) is needed instead of equals: serialization, cycle detection in object graphs.
• What is SequencedMap? — Java 21 interface for ordered Maps: putFirst, putLast, firstEntry, reversed.

Red flags (DO NOT say):

• ❌ “Map is a Collection” — Map does NOT extend Collection, it works with key-value pairs
• ❌ “WeakHashMap is a good choice for caching” — cleanup is too aggressive, use Caffeine
• ❌ “IdentityHashMap is the same as HashMap” — IdentityHashMap compares keys by ==, not equals
• ❌ “Map.of() can be modified” — it’s an immutable collection, UnsupportedOperationException on modification

Related topics:

• [[15. What is the difference between HashMap, LinkedHashMap and TreeMap]]
• [[17. What is WeakHashMap]]
• [[18. What is ConcurrentHashMap]]
• [[16. When to use TreeMap]]