Chapter 3 — Hash Maps

After Chapter 2a, you felt the friction. Every time you needed to check whether a value had been seen before, you were either scanning the entire array (O(n)) or pre-sorting it (O(n log n)). The HashMap exists to eliminate that friction entirely. It is not a clever trick — it is a direct solution to a specific physical problem: given any key, jump to its value in memory without searching. After this chapter, you will understand not just how to use a HashMap, but why it works at the memory level, when it is O(1) versus when it is not, how JavaScript's Map and {} differ under the hood, and why 40% of medium array and string problems collapse the moment you ask "can a HashMap hold the state I need?" This is the most important data structure chapter in this book.

Part 1: The Problem a HashMap Solves

You have an array of 1 million user IDs. A request comes in — is user ID 482917 in this array?

With an unsorted array, you scan from index 0 until you find it or exhaust the array. O(n). At 1 million elements, that is 1 million comparisons in the worst case.

You already know sorting helps — a sorted array lets you binary search in O(log n), about 20 comparisons. But sorting costs O(n log n) upfront and requires the array to be sorted before any queries arrive.

What if you could answer the question in O(1) — one operation, regardless of how many elements you have? Not O(log n). O(1). Constant. The same speed whether you have 10 elements or 10 million.

This seems impossible. To know whether something is in a collection, you have to look somewhere. The trick is making "somewhere" be a single, directly computable location.

The trick is to turn the key into an index.

If you could take user ID 482917 and compute, in O(1), exactly which memory location it lives in — the way arr[i] computes base + i × elementSize — you would have O(1) lookup. No searching. No sorting. Just arithmetic.

That is what a HashMap does. The mechanism for converting a key into an index is called a hash function.

Part 2: The Hash Function — Turning Anything Into an Index

A hash function takes an arbitrary key — a number, a string, an object — and returns an integer. That integer is used as an array index.

The simplest imaginable hash function for integer keys:

hash(key) = key % capacity

Where capacity is the number of slots in your backing array (also called buckets).

If you have 10 buckets (indices 0–9) and you want to store the key 482917:

hash(482917) = 482917 % 10 = 7

Store the value at bucket 7. To look it up later: compute 482917 % 10 = 7, jump to bucket 7, done. O(1).

For string keys, you need to turn the string into an integer first. A common approach:

function hashString(key, capacity) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * 31 + key.charCodeAt(i)) % capacity;
  }
  return hash;
}

This multiplies the running hash by 31 (a prime number) and adds each character's ASCII code. The result is always in [0, capacity - 1].

Why 31? Primes distribute bits more uniformly than composite numbers, reducing clustering in the output. The specific value 31 is a historical choice — Java's String.hashCode() uses it, it fits in 5 bits, and it produces good distribution empirically. You do not need to derive the best prime — just know that primes are preferred for this purpose.

What makes a hash function good?

Two properties matter:

1. Deterministic: The same key must always produce the same hash. hash("user") = 4 today and hash("user") = 4 tomorrow. If this is violated, you can never find what you stored.

2. Uniform distribution: Different keys should hash to different buckets as evenly as possible. If all keys hash to bucket 0, you have a pile in one slot and empty everywhere else — equivalent to an unsorted linked list, O(n) lookup.

A real production hash function (like MurmurHash3 or xxHash) takes these properties to an extreme, distributing keys so evenly that collision probability approaches the theoretical minimum. But even the simple examples above are sufficient to understand what a HashMap is doing.

Part 3: The Collision Problem

Here is the unavoidable problem: if you have more keys than buckets, two different keys must share a bucket. This is mathematically guaranteed by the pigeonhole principle — if you have n pigeons and k < n holes, at least one hole must have more than one pigeon.

Even before you run out of buckets, two keys can hash to the same index by accident:

hash(482917) = 482917 % 10 = 7
hash(237)    = 237 % 10 = 7

Both key 482917 and key 237 hash to bucket 7. This is called a collision. What do you do when two keys want the same slot?

There are two main strategies. Both are used in real systems.

Strategy 1: Chaining

Each bucket does not store a single value. It stores a linked list of all key-value pairs that hashed to that bucket.

Bucket 0: → null
Bucket 1: → null
Bucket 2: → null
Bucket 3: → { key: "abc", val: 10 } → null
Bucket 4: → null
Bucket 5: → null
Bucket 6: → null
Bucket 7: → { key: 482917, val: "Alice" } → { key: 237, val: "Bob" } → null
Bucket 8: → null
Bucket 9: → null

To look up key 237:

1. Compute hash(237) = 7. Jump to bucket 7.
2. Scan the linked list at bucket 7 for an entry where key === 237.
3. Found: return "Bob".

When does this fail? If all n keys hash to the same bucket, the linked list has n entries. Lookup degrades to O(n) — a linear scan of the chain. This is the worst case for a HashMap and happens when the hash function produces poor distribution or when an adversary crafts inputs to cause collisions (a real security concern for web servers accepting untrusted input as hash keys).

Average case: If keys are distributed uniformly, each bucket has n/capacity entries on average. This ratio (n/capacity) is called the load factor. If the load factor is kept below a threshold (typically 0.75), average chain length is less than 1, making lookups effectively O(1) on average.

Strategy 2: Open Addressing (Linear Probing)

Instead of a linked list at each bucket, every entry lives directly in the backing array. When a collision occurs, you probe for the next empty slot.

Insert key=482917, val="Alice":  hash=7. Slot 7 is empty. Write there.
Insert key=237,    val="Bob":    hash=7. Slot 7 is full. Try slot 8. Empty. Write there.

Array: [..., _, _, 7:(482917,"Alice"), 8:(237,"Bob"), _, _]
                   ↑                   ↑
                   primary slot        probed to next slot

Lookup for key 237:

1. Compute hash(237) = 7. Check slot 7 — key is 482917, not 237.
2. Probe to slot 8. Key is 237. Found. Return "Bob".

Advantages over chaining: Better cache performance — all data is in one contiguous array, so CPU cache lines cover nearby slots. No pointer overhead from linked list nodes.

Disadvantage: Clustering. When many keys hash to nearby slots, probing chains grow, and each new collision extends the chain further. Performance degrades faster than chaining under high load. Deletion is also tricky — you cannot simply empty a slot, because that would break probe sequences for other keys. You must mark it as "deleted" (a tombstone), not "empty".

Real-world usage: Python's dict uses open addressing with a variant called pseudorandom probing. JavaScript's V8 uses a combination. Redis uses chaining. Java's HashMap uses chaining but switches chains to red-black trees when a chain exceeds 8 entries (to cap worst-case at O(log n) instead of O(n)).

Part 4: Load Factor and Rehashing

You now understand that performance depends on keeping the load factor (n_entries / n_buckets) low. But as you insert more elements, the load factor rises. What happens when it crosses the threshold?

The HashMap rehashes: it allocates a new, larger backing array (typically double the size), recomputes the hash of every existing key relative to the new capacity, and inserts each entry into the new array.

Before rehash (capacity=4, entries=3, load factor=0.75 — threshold hit):
Bucket 0: → { key:"a", val:1 }
Bucket 1: → { key:"b", val:2 }
Bucket 2: → null
Bucket 3: → { key:"c", val:3 }

Allocate new array, capacity=8.
Recompute: hash("a") % 8 = ?, hash("b") % 8 = ?, hash("c") % 8 = ?
(All new positions — capacity changed, so all hash indices change)

After rehash (capacity=8):
Bucket 1: → { key:"a", val:1 }
Bucket 5: → { key:"b", val:2 }
Bucket 7: → { key:"c", val:3 }
(positions are illustrative — actual depends on hash function)

Rehashing costs O(n) — every entry must be reinserted. This sounds bad. But like array push resizing (Chapter 1), it is amortized O(1) per insertion because rehashing happens at most every n insertions (when the load doubles again after the last rehash). The total cost of all rehashes across n insertions is O(n), so the amortized cost per insertion is O(1).

This is why HashMap insertion is described as O(1) amortized — the same reasoning as dynamic array push.

A critical nuance: In the single worst-case insertion that triggers a rehash, the operation costs O(n). If you are building a system where latency spikes are unacceptable (a real-time game, a trading system), this occasional O(n) is a problem even if the average is O(1). Redis solves this with incremental rehashing: instead of rehashing all entries at once, Redis maintains two hash tables simultaneously during rehash and moves a few entries per operation, spreading the O(n) cost across many requests. No single request pays the full rehash cost.

Part 5: The Full Complexity Picture

The average case is what you cite in interviews. The worst case is what you understand and design around in production. In practice, with a good hash function and a load factor kept below 0.75, the worst case is vanishingly rare — but it is not zero, and it is exploitable if an adversary can craft keys that all collide. Production languages address this with randomized hash seeds (a random value mixed into the hash function at startup) so that the adversary cannot predict which keys collide.

Part 6: JavaScript's Map and {} — What They Actually Are

You have two built-in HashMap-like structures in JavaScript. They are not interchangeable. Understanding the difference matters for both interviews and production code.

The {} Object

A plain JavaScript object is not a purpose-built HashMap. It is a general-purpose object with a prototype chain, used for both data storage and method inheritance. Under the hood, V8 does not always represent {} as a hash table.

For objects with a fixed, small set of string keys (a common case — think {name: "Alice", age: 30}), V8 uses hidden classes and inline caches instead of a hash table. It compiles property access into direct memory offsets — closer to struct field access in C than to hash table lookup. This is dramatically faster than hashing.

When you dynamically add and remove properties, or use many different keys, V8 falls back to a hash table representation. But the startup assumption is always "this might be a fixed-shape object, let me optimize for that."

Practical consequences of using {}:

• Keys are always coerced to strings. obj[1] and obj["1"] access the same slot. obj[{}] stores under the key "[object Object]". This causes subtle bugs when using non-string keys.
• {} inherits from Object.prototype. Keys like "constructor", "toString", "hasOwnProperty" may collide with prototype methods. This is a security issue in some contexts (prototype pollution attacks).
• Iteration order is defined but quirky: integer-like string keys are iterated first in ascending numeric order, then other string keys in insertion order. This trips up developers who expect pure insertion order.

The Map

Map was introduced in ES6 precisely to give JavaScript a proper HashMap:

• Any key type: objects, functions, numbers, strings — unlike {} which converts everything to strings.
• Guaranteed insertion-order iteration: map.forEach() and for...of always visit entries in the order they were inserted.
• No prototype pollution: Map has no inherited keys. map.get("constructor") returns undefined, not a function.
• Explicit size: map.size gives you the count in O(1). With {}, you need Object.keys(obj).length which is O(n).
• Better performance for frequent adds and deletes: V8 optimizes Map as a true hash table from the start, without the hidden-class machinery that adds overhead when shapes change.

When to use which:

Use Map when:

• Keys are not strings (especially when keys are objects or mixed types)
• You need the size frequently
• You are frequently adding and removing keys
• You need reliable iteration order
• You are building a cache, frequency table, or any algorithmic data structure

Use {} when:

• You are defining a fixed-shape data object (a "record" or "DTO")
• You need JSON serialization (JSON.stringify does not serialize Map)
• You are using it as configuration or options

In DSA interview problems, always use Map (or Set for membership-only). The semantics are cleaner and the intent is explicit.

The Set

A Set is a HashMap where you only care about keys, not values. Internally it is a hash table that stores keys and uses a sentinel as the value. Operations: set.add(key), set.has(key), set.delete(key) — all O(1) average. Use it when you need "have I seen this before?" without needing to store any associated value.

Part 7: Building a HashMap From Scratch

To cement the understanding, here is a minimal HashMap implementation in JavaScript using chaining. This is what you would implement if asked in an interview.

class HashMap {
  constructor(capacity = 16) {
    this.capacity = capacity;
    this.size = 0;
    this.buckets = new Array(capacity).fill(null).map(() => []);
    // Each bucket is an array of [key, value] pairs (the chain)
  }

  // Turn any string key into a bucket index
  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash * 31 + key.charCodeAt(i)) % this.capacity;
    }
    return hash;
  }

  set(key, value) {
    const index = this._hash(key);
    const chain = this.buckets[index];

    // Check if key already exists in this chain — update if so
    for (let i = 0; i < chain.length; i++) {
      if (chain[i][0] === key) {
        chain[i][1] = value;  // update existing
        return;
      }
    }

    // Key not found — insert new entry
    chain.push([key, value]);
    this.size++;

    // Rehash if load factor exceeds 0.75
    if (this.size / this.capacity > 0.75) {
      this._rehash();
    }
  }

  get(key) {
    const index = this._hash(key);
    const chain = this.buckets[index];

    for (let i = 0; i < chain.length; i++) {
      if (chain[i][0] === key) return chain[i][1];
    }

    return undefined;  // key not found
  }

  has(key) {
    return this.get(key) !== undefined;
  }

  delete(key) {
    const index = this._hash(key);
    const chain = this.buckets[index];

    for (let i = 0; i < chain.length; i++) {
      if (chain[i][0] === key) {
        chain.splice(i, 1);  // remove from chain
        this.size--;
        return true;
      }
    }
    return false;
  }

  _rehash() {
    const oldBuckets = this.buckets;
    this.capacity *= 2;
    this.buckets = new Array(this.capacity).fill(null).map(() => []);
    this.size = 0;

    // Reinsert every entry with new capacity
    for (const chain of oldBuckets) {
      for (const [key, value] of chain) {
        this.set(key, value);  // _hash will now use new capacity
      }
    }
  }
}

Trace a short sequence:

new HashMap(4)   → capacity=4, buckets=[[], [], [], []]

set("name", "Alice"):
  hash("name") % 4 = ?
  'n'=110: hash = 0*31 + 110 = 110
  'a'=97:  hash = 110*31 + 97 = 3507 % 4 = 3
  'm'=109: hash = 3*31 + 109 = 202 % 4 = 2  (wait, let me redo)

  Actually: (((0*31+110)%4)*31+97)%4*31+109... let's just say hash=2 for illustration.
  buckets[2] = [["name","Alice"]]
  size=1. load=1/4=0.25. No rehash.

set("age", 30):
  hash("age") → let's say 1
  buckets[1] = [["age", 30]]
  size=2. load=2/4=0.5. No rehash.

set("city", "Mumbai"):
  hash("city") → let's say 2  ← collision with "name"!
  buckets[2] = [["name","Alice"], ["city","Mumbai"]]
  size=3. load=3/4=0.75. Rehash triggered!

_rehash():
  oldBuckets = current buckets
  capacity = 8
  buckets = [[], [], [], [], [], [], [], []]
  Reinsert "name"→Alice, "age"→30, "city"→Mumbai with new capacity
  All three get new bucket positions (hash % 8 instead of hash % 4)

get("city"):
  hash("city") % 8 → some index, say 6
  buckets[6] = [["city","Mumbai"]]
  Scan chain: found at index 0. Return "Mumbai". ✓

The scan of the chain at get is what makes lookup O(1) on average — chains are short (length ≈ 1 with good distribution and low load factor) — and O(n) in the worst case (all keys in one chain).

Part 8: The Four-Question Framework Applied

Problem: Given an array of integers, return true if any value appears at least twice.

Input:  [1, 2, 3, 1]
Output: true   (1 appears twice)

Q1: What do I have? An array of n integers. n can be large. No constraints on value range.

Q2: What do I want? A boolean: has any value been seen more than once?

Q3: Brute force? For each element, scan the rest of the array for a match. O(n²).

function containsDuplicateBrute(nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) return true;
    }
  }
  return false;
}

Q4: Where is the waste?

For each element, the brute force scans n elements to find a duplicate. That scan is O(n) — it is a membership check on an unsorted array.

Replace the inner scan with a Set lookup: O(1). As you process each element, check if you have seen it before. If yes, return true. If no, record it.

function containsDuplicate(nums) {
  const seen = new Set();
  for (const num of nums) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

O(n) time, O(n) space. The waste was the inner O(n) scan. A Set's O(1) has eliminates it.

The general pattern this demonstrates:

Whenever your brute force contains "check if X has been seen before" as an inner operation, ask: "can I store what I've seen in a Set or Map?" If yes, that inner O(n) check becomes O(1), and the overall complexity drops by one power of n. O(n²) becomes O(n). O(n³) becomes O(n²).

This single observation handles a large fraction of interview problems.

Part 9: How to Think About This, Not Just Use It

The signal to reach for a HashMap is not "the problem involves counting" or "I need fast lookup." Those are symptoms. The root signal is deeper:

You are doing work at position j that requires knowledge of what happened at some earlier position i, and you do not know in advance which i to look at.

When that is true, a linear scan for i costs O(n) per position, giving O(n²) total. A HashMap stores what happened at every previous position, indexed by the value that matters, so the right i is found in O(1).

Concretely, ask yourself: "At each position in my scan, what question am I asking about the past?"

• "Have I seen this value before?" → Set
• "How many times have I seen this value?" → Map with value = count
• "What index did I last see this value at?" → Map with value = index
• "What is the complement of this value (target - current) and have I seen it?" → Map (Two Sum)
• "What prefix sum would pair with the current prefix sum to give sum = k?" → Map (Subarray Sum = k)

Each of these is a different "question about the past." The HashMap stores the answers indexed by the value you will ask about in the future.

The failure mode to watch for:

A HashMap gives O(1) lookup only when keys are well-distributed. If your keys are all identical or hash to the same bucket, you get O(n) per operation. This almost never matters with standard keys (strings, integers) and JavaScript's built-in Map. But if you ever use objects as keys in a Map, be aware: Map uses reference equality for object keys. Two different objects {a:1} and {a:1} are different keys even though they look the same. This is a common source of bugs when caching results keyed by objects.

Part 10: Where HashMaps Live in Real Systems

Redis — The Hash Table at the Core

Redis is fundamentally a giant HashMap. Its internal data structure is called dict (dictionary), implemented as two hash tables maintained simultaneously to enable incremental rehashing. When Redis rehashes:

• It maintains ht[0] (old table) and ht[1] (new table, double the size)
• On every read or write operation, Redis moves a fixed number of entries from ht[0] to ht[1]
• Once ht[0] is empty, it becomes the new ht[1], and ht[1] is freed

This means no single Redis operation ever pays the full O(n) rehash cost. The cost is amortized across all subsequent operations. This is how Redis guarantees sub-millisecond latency even during resizing — it never stops to do a large batch of work.

When you call redis.get("user:123:session"), Redis computes the hash of "user:123:session" using SipHash (a cryptographically-keyed hash that prevents adversarial collision attacks), finds the bucket in O(1), scans the (typically length-1) chain, and returns the value. The O(1) guarantee is physical — it is the hash table access you just derived.

Node.js require() — Module Cache as HashMap

When your Node.js application calls require('./utils'), Node does not re-execute utils.js every time. It checks Module._cache, a plain JavaScript object used as a HashMap, keyed by the resolved file path. If the path is already in the cache, it returns the cached module.exports object immediately — O(1). If not, it loads, executes, and caches the module.

This is why require is safe to call multiple times for the same module — the HashMap ensures it is only executed once. When you have a circular dependency (A requires B, B requires A), Node handles it by inserting a partially-initialized module into the cache before finishing execution, preventing infinite loops. The HashMap is the mechanism that makes both caching and circular dependency detection possible.

PostgreSQL Hash Joins

When PostgreSQL joins two tables — say, attempts joined with questions on question_id — it chooses between a nested loop join, a merge join, and a hash join based on cost estimates.

A hash join works exactly like a HashMap lookup:

1. Build phase: Scan the smaller table (questions). For each row, compute hash(question_id) and insert the row into an in-memory hash table keyed by question_id. Cost: O(n) where n is the size of the smaller table.

2. Probe phase: Scan the larger table (attempts). For each row, compute hash(question_id) and look up the matching question row in the hash table. Cost: O(m) where m is the size of the larger table.

Total: O(n + m) — linear in the sum of both table sizes. Compare to a naive nested loop join: O(n × m). For large tables, this is the difference between seconds and hours.

This is why EXPLAIN ANALYZE on a join query sometimes shows Hash Join — PostgreSQL recognized that building a temporary HashMap was cheaper than scanning one table for every row in the other. You now understand exactly what it is building and why.

Java's HashMap — Chain-to-Tree Escalation

Java 8 introduced a significant optimization to HashMap: when a single bucket's chain exceeds 8 entries, the chain is converted to a red-black tree. This caps the worst-case lookup at O(log n) instead of O(n), even in adversarial conditions.

This matters because Java web applications were historically vulnerable to Hash DoS attacks: an attacker sends HTTP POST data with many parameters whose keys all collide in Java's HashMap, turning every HashMap operation from O(1) to O(n) and causing CPU exhaustion. Converting long chains to trees reduces the attack surface from O(n) to O(log n).

JavaScript also randomizes hash seeds in Map implementations in modern engines, for the same reason. The security implication of "worst-case O(n) HashMap" is not academic.

Vocabulary Map

Practice Problems

Problem 1 — Trace and Predict

You are given a custom HashMap implementation with capacity 5 using chaining and the hash function hash(key) = key % 5.

Trace through the following sequence of operations. After each operation, draw the full state of the backing array (all 5 buckets with their chains):

insert(key=7,  value="A")
insert(key=12, value="B")
insert(key=2,  value="C")
insert(key=17, value="D")
get(key=12)
delete(key=7)
get(key=17)
insert(key=22, value="E")

After the trace, answer:

1. Which bucket has the longest chain at the end, and what does that tell you about the hash function key % 5 for the given inputs?
2. If you called get(key=7) after the delete, what would happen step by step? What does the code return and why?
3. The load factor after all inserts (before the delete) is 5/5 = 1.0. In a real HashMap with a 0.75 threshold, when would rehashing have triggered, and what would the new capacity be?

Problem 2 — Find the Waste

Here is a function that finds the first non-repeating character in a string:

function firstUniqueChar(s) {
  for (let i = 0; i < s.length; i++) {
    let isUnique = true;
    for (let j = 0; j < s.length; j++) {
      if (i !== j && s[i] === s[j]) {
        isUnique = false;
        break;
      }
    }
    if (isUnique) return i;
  }
  return -1;
}

Part A: Derive the time complexity. What is n? What is the exact number of comparisons in the worst case (when all characters are identical)?

Part B: Where is the waste? What information is being recomputed for every outer iteration that could be computed once?

Part C: Rewrite using a HashMap to achieve O(n) time, O(1) space (since the alphabet is bounded — at most 26 lowercase letters, so the Map never exceeds 26 entries regardless of input length). Write the full JavaScript solution and trace it on s = "leetcode", showing the Map state after each character is processed.

Part D: What is the minimum number of passes over the string that your O(n) solution requires, and why? Could it be done in a single pass? If yes, at what cost?

Problem 3 — Failure Analysis

A developer on your ScoreResume team implements a cache for expensive resume scoring computations:

const cache = {};

function getScore(resumeData) {
  const key = resumeData;  // resumeData is a JavaScript object
  
  if (cache[key]) {
    return cache[key];
  }
  
  const score = computeExpensiveScore(resumeData);
  cache[key] = score;
  return score;
}

Part A: This code has a fundamental bug that means the cache never works. Identify it precisely — explain what happens when you use a JavaScript object as a key in {}, what string is actually used as the key, and why this means every call is a cache miss.

Part B: Fix the bug by switching to a Map. But now there is a new problem: Map uses reference equality for object keys. Two calls with {sections: [...], skills: [...]} that are structurally identical but are different object references will be treated as different keys. Describe a strategy to handle this — what should the cache key actually be?

Part C: The developer changes the key to JSON.stringify(resumeData). This fixes the equality problem, but introduces a new performance issue. What is it? Under what conditions does JSON.stringify become the bottleneck instead of the cache lookup?

Part D: In production, the cache grows indefinitely — every unique resume ever scored is stored forever. Describe what eventually happens to the HashMap's performance as the number of entries grows into the millions, and what production caching systems (like Redis) do to prevent this.

Problem 4 — Design Under Constraints

Design a data structure that supports the following operations, all in O(1) average time:

• insert(val) — insert an integer value
• remove(val) — remove an integer value (if it exists)
• getRandom() — return a random element from the current set, where each element has an equal probability of being returned

This is LeetCode 380 — "Insert Delete GetRandom O(1)". It is asked at Google, Amazon, and Razorpay.

Why this is hard:

• Insert and remove in O(1) suggests a HashMap (direct lookup, no scanning)
• getRandom in O(1) with uniform probability suggests an array (random index access)
• But removing from an array is O(n) due to shifting
• So you need both, with a trick to make removal from the array O(1)

Your task: Design the data structure using a combination of a Map and an array. For each operation:

1. State exactly what is stored in the Map (keys and values)
2. State exactly what is stored in the array
3. Write the algorithm in plain English (or JavaScript)
4. Prove it is O(1) average

The key insight for remove: when you delete an element, you cannot shift the array. Instead, swap the element to delete with the last element in the array, then remove the last element (O(1)). But after swapping, the Map for the swapped element must be updated. Trace through insert(1), insert(2), insert(3), remove(1), getRandom() showing Map and array state after each operation.

Problem 5 — Reach Beyond

This problem asks you to reason about something not explicitly taught.

Two different keys that hash to the same bucket are a collision. But there is a subtler problem: keys that do not collide but are still "too close" in the hash space — clustering near a few buckets while others stay empty — also degrade performance.

Part A: Consider the hash function hash(n) = n % 10 applied to these 10 keys: {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}. Compute the hash for each key and show where they land. What is the load factor? What is the longest chain? What does this tell you about key % prime versus key % non-prime?

Part B: Now consider hash(n) = n % 7 for the same keys. Compute each hash. How does the distribution compare? Explain in physical terms why using a prime as the modulus produces better distribution for arithmetic sequences than a composite number.

Part C: String hash functions multiply by a constant at each step (we used 31). Consider two alternatives: multiplying by 1 (i.e., just summing character codes) versus multiplying by 31. Construct two strings that would produce the same hash under the "sum only" approach but different hashes under the "multiply by 31" approach. Explain why the multiplicative approach is strictly better — what property of strings does it preserve that simple summation does not?

Part D (connection to Chapter 2): A HashMap uses an array as its backing store. When you rehash, you double the capacity and reinsert all n entries — this is O(n). From Chapter 2, you know that dynamic array resizing also costs O(n) occasionally but is O(1) amortized. The argument for amortized O(1) HashMap insertion is identical to the argument for amortized O(1) array push. Write out the amortized argument for HashMap insertion explicitly — show the total cost of n insertions that trigger rehash at sizes 16, 32, 64, ..., up to size n. Prove the total cost is O(n).

What's Coming Next

You now have two foundational tools: arrays (fast index access, slow value search) and HashMaps (fast value access, no index). But both are flat — they store things without any notion of relationship or order beyond insertion sequence. Chapter 4 introduces recursion, which is not a data structure but a way of thinking that makes an entirely new class of problems tractable. Recursion is what makes it possible to express "do this on the whole problem by doing it on a smaller version of itself" — and it is the engine inside trees, graphs, backtracking, and divide-and-conquer sorting. Without recursion, Chapters 5 through 13 cannot be fully understood. With it, many problems that look impossibly complex become a few lines of elegant code.