Why Hash Map Exists and What Problem It Solves in DSA Typescript - Why This Pattern

Mental Model

A hash map helps us find things quickly by using a special code to jump right to the answer instead of searching step by step.

Analogy: Imagine a huge library where books are arranged randomly. Without a system, you have to check every book to find one. A hash map is like having a special code that tells you exactly which shelf and spot the book is on, so you find it instantly.

Array: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Keys:   ?   ?   ?   ?   ?   ?   ?   ?   ?   ?
Values: ?   ?   ?   ?   ?   ?   ?   ?   ?   ?

Dry Run Walkthrough

Input: Store and find the phone number of 'Alice' quickly from a list of names and numbers.

Goal: Show how a hash map lets us find Alice's number fast without checking every entry.

Step 1: Calculate hash code for 'Alice' to find index in array

Array: [ ] [ ] [ ] [ ] [Alice -> 1234] [ ] [ ] [ ] [ ] [ ]
Keys:   ?   ?   ?   ?   Alice       ?   ?   ?   ?   ?
Values: ?   ?   ?   ?   1234        ?   ?   ?   ?   ?

Why: We use the hash code to know exactly where to store Alice's number.

Step 2: Calculate hash code for 'Bob' and store his number at the computed index

Array: [ ] [ ] [ ] [Bob -> 5678] [Alice -> 1234] [ ] [ ] [ ] [ ] [ ]
Keys:   ?   ?   ?   Bob         Alice       ?   ?   ?   ?   ?
Values: ?   ?   ?   5678        1234        ?   ?   ?   ?   ?

Why: Each name gets a unique spot using its hash code to avoid searching.

Step 3: To find Alice's number, calculate hash code and go directly to her spot

Array: [ ] [ ] [ ] [Bob -> 5678] [Alice -> 1234] [ ] [ ] [ ] [ ] [ ]
Keys:   ?   ?   ?   Bob         Alice       ?   ?   ?   ?   ?
Values: ?   ?   ?   5678        1234        ?   ?   ?   ?   ?
Found: Alice's number is 1234

Why: No need to check other entries; hash code points directly to Alice.

Result:

Array: [ ] [ ] [ ] [Bob -> 5678] [Alice -> 1234] [ ] [ ] [ ] [ ] [ ]
Keys:   ?   ?   ?   Bob         Alice       ?   ?   ?   ?   ?
Values: ?   ?   ?   5678        1234        ?   ?   ?   ?   ?
Answer: Alice's number is 1234

Annotated Code

DSA Typescript

class HashMap {
  private size: number;
  private buckets: Array<Array<[string, number]>>;

  constructor(size = 10) {
    this.size = size;
    this.buckets = Array.from({ length: size }, () => []);
  }

  private hash(key: string): number {
    let hash = 0;
    for (const char of key) {
      hash += char.charCodeAt(0);
    }
    return hash % this.size;
  }

  set(key: string, value: number): void {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value; // update existing
        return;
      }
    }
    bucket.push([key, value]); // add new
  }

  get(key: string): number | undefined {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    for (const [k, v] of bucket) {
      if (k === key) {
        return v;
      }
    }
    return undefined;
  }
}

// Driver code
const map = new HashMap();
map.set('Alice', 1234);
map.set('Bob', 5678);
const aliceNumber = map.get('Alice');
console.log(`Alice's number is ${aliceNumber}`);

const index = this.hash(key);

Calculate hash code to find bucket index

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

Check if key exists to update value

bucket.push([key, value]);

Add new key-value pair if not found

for (const [k, v] of bucket) { if (k === key) { return v; } }

Search bucket for key to retrieve value

Output

Alice's number is 1234

Complexity Analysis

Time: O(1) average because hash code lets us jump directly to the data without searching all entries

Space: O(n) because we store all key-value pairs in buckets

vs Alternative: Compared to searching a list which is O(n), hash map lookup is much faster on average

Edge Cases

Empty map

Getting any key returns undefined because nothing is stored

DSA Typescript

return undefined;

Collision where two keys hash to same index

Both keys are stored in the same bucket array and searched linearly

DSA Typescript

bucket.push([key, value]);

Updating existing key

Value is replaced instead of adding duplicate key

DSA Typescript

if (bucket[i][0] === key) { bucket[i][1] = value; return; }

When to Use This Pattern

When you need to store and find data quickly by key, especially when searching a list is too slow, reach for the hash map pattern because it provides fast average lookup.

Common Mistakes

Mistake: Not handling collisions, causing data loss or wrong results
Fix: Use buckets (arrays) at each index to store multiple key-value pairs and search them linearly

Mistake: Updating value by adding duplicate keys instead of replacing
Fix: Check if key exists in bucket and update value before adding new

Summary

A hash map stores key-value pairs for fast lookup using a hash code to find data quickly.

Use it when you want to find data by key without searching everything step by step.

The key insight is using a hash function to jump directly to where the data is stored.

Practice

1. Why do we use a Hash Map instead of a simple list to store key-value pairs?

easy

A. Because it allows fast lookup of values by keys

B. Because it stores data in sorted order automatically

C. Because it uses less memory than a list

D. Because it can only store numbers

Solution

1. Step 1: Understand the problem with lists

   Lists require checking each item one by one to find a value by key, which is slow for large data.

2. Step 2: How hash maps solve this

   Hash maps use a special function to find the exact place of a key quickly, making lookup fast.

3. Final Answer:

   Because it allows fast lookup of values by keys -> Option A

4. Quick Check:

   Fast key lookup = Because it allows fast lookup of values by keys [OK]

Hint: Hash maps speed up key-based searches [OK]

Common Mistakes:

• Thinking hash maps sort data automatically
• Believing hash maps use less memory always
• Assuming hash maps only store numbers

2. Which of the following is the correct way to create a hash map (Map) in TypeScript?

easy

A. const map = new Map();

B. const map = Map();

C. const map = new map();

D. const map = new Map(); string, number;

Solution

1. Step 1: Recall TypeScript Map syntax

   In TypeScript, a Map is created using new Map<KeyType, ValueType>().

2. Step 2: Check each option

   const map = new Map(); uses correct syntax with new Map<string, number>(). Others have syntax errors or wrong casing.

3. Final Answer:

   const map = new Map<string, number>(); -> Option A

4. Quick Check:

   Correct Map creation syntax = const map = new Map<string, number>(); [OK]

Hint: Use 'new Map<KeyType, ValueType>()' to create hash maps [OK]

Common Mistakes:

• Omitting 'new' keyword
• Using lowercase 'map' instead of 'Map'
• Incorrect generic syntax

3. What will be the output of the following TypeScript code?

const map = new Map();
map.set('apple', 5);
map.set('banana', 3);
map.set('apple', 10);
console.log(map.get('apple'));

medium

A. Error

B. 5

C. undefined

D. 10

Solution

1. Step 1: Understand map.set behavior

   When setting a key that already exists, the value is updated to the new one.

2. Step 2: Trace the code

   First 'apple' is set to 5, then updated to 10. So map.get('apple') returns 10.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Updated value for 'apple' = 10 [OK]

Hint: Last set value for a key overwrites previous [OK]

Common Mistakes:

• Assuming first value remains
• Thinking get returns undefined if key repeated
• Expecting error on duplicate keys

4. Identify the error in this TypeScript code that tries to use a hash map:

const map = new Map();
map['key'] = 'value';
console.log(map.get('key'));

medium

A. map.get() cannot be used to retrieve values

B. Map constructor requires key and value types

C. Using bracket notation to add key-value pairs does not work with Map

D. Map keys must be numbers only

Solution

1. Step 1: Understand how to add entries to Map

   Map entries must be added using map.set(key, value), not bracket notation.

2. Step 2: Analyze the code behavior

   Using map['key'] = 'value' adds a property to the object, not a Map entry, so map.get('key') returns undefined.

3. Final Answer:

   Using bracket notation to add key-value pairs does not work with Map -> Option C

4. Quick Check:

   Use map.set() to add entries [OK]

Hint: Use map.set() to add entries, not bracket notation [OK]

Common Mistakes:

• Adding entries with bracket notation
• Expecting map.get() to find bracket-added keys
• Thinking Map keys must be numbers

5. You want to count how many times each word appears in a list of words using a hash map in TypeScript. Which approach correctly solves this problem?

hard

A. Use a Set to store words and count size for each word

B. Use a Map, for each word check if it exists, then increment or set to 1

C. Use a Map with word as value and count as key

D. Use an array and push words, then count duplicates manually later

Solution

1. Step 1: Understand the counting problem

   We need to store each word as a key and count as a value, so Map<string, number> fits well.

2. Step 2: How to update counts

   For each word, check if it exists in the map; if yes, increment count, else set count to 1.

3. Step 3: Why other options fail

   Use an array and push words, then count duplicates manually later is inefficient and manual. Use a Map with word as value and count as key swaps key and value wrongly. Use a Set to store words and count size for each word's Set only stores unique words without counts.

4. Final Answer:

   Use a Map<string, number>, for each word check if it exists, then increment or set to 1 -> Option B

5. Quick Check:

   Counting words = Map with word keys and number counts [OK]

Hint: Map keys = words, values = counts; increment or set 1 [OK]

Common Mistakes:

• Using Set which can't count duplicates
• Swapping key and value types in Map
• Counting manually with arrays inefficiently