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

Mental Model

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

Analogy: Imagine a big 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 for each book that tells you exactly where to look, so you find it instantly.

Array: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Keys:   k1  k2  k3  k4  k5  k6  k7  k8  k9  k10
Values: v1  v2  v3  v4  v5  v6  v7  v8  v9  v10

Dry Run Walkthrough

Input: We want to store and find phone numbers by name quickly: Add (Alice, 123), (Bob, 456), (Carol, 789), then find Bob's number.

Goal: Show how a hash map lets us find Bob's number fast without checking all entries.

Step 1: Compute hash code for 'Alice' to find her slot

Array: [Alice:123] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Why: We use a hash code to know where to put Alice's number quickly.

Step 2: Compute hash code for 'Bob' to find his slot

Array: [Alice:123] [Bob:456] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Why: Bob's hash code points to a different slot, so we store his number there.

Step 3: Compute hash code for 'Carol' to find her slot

Array: [Alice:123] [Bob:456] [Carol:789] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Why: Carol's hash code points to another slot, so we store her number there.

Step 4: To find Bob's number, compute hash code for 'Bob' and go directly to his slot

Array: [Alice:123] [Bob:456 ↑] [Carol:789] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Why: We jump directly to Bob's slot without checking others, so it's fast.

Result:

Array: [Alice:123] [Bob:456] [Carol:789] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Answer: Bob's number is 456

Annotated Code

DSA Javascript

class HashMap {
  constructor(size = 10) {
    this.size = size;
    this.buckets = Array(size).fill(null);
  }

  // Simple hash function: sum of char codes mod size
  hash(key) {
    let hashValue = 0;
    for (const char of key) {
      hashValue += char.charCodeAt(0);
    }
    return hashValue % this.size;
  }

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

  get(key) {
    const index = this.hash(key);
    const entry = this.buckets[index];
    if (entry && entry.key === key) {
      return entry.value;
    }
    return null;
  }
}

// Driver code
const map = new HashMap();
map.set('Alice', 123);
map.set('Bob', 456);
map.set('Carol', 789);
console.log('Bob\'s number is', map.get('Bob'));

const index = this.hash(key);

Calculate the slot index using the hash function

this.buckets[index] = { key, value };

Store the key-value pair directly at the computed index

const entry = this.buckets[index];

Retrieve the entry at the computed index

if (entry && entry.key === key) { return entry.value; }

Check if the key matches to return the correct value

Output

Bob's number is 456

Complexity Analysis

Time: O(1) on average because the hash function lets us jump directly to the data slot without searching.

Space: O(n) because we store n key-value pairs in an array of fixed size.

vs Alternative: Compared to searching a list which is O(n), hash maps give much faster lookups by using hashing.

Edge Cases

Empty map

Getting any key returns null because nothing is stored yet.

DSA Javascript

if (entry && entry.key === key) { return entry.value; }

Key not found

Returns null because the slot is empty or key does not match.

DSA Javascript

if (entry && entry.key === key) { return entry.value; }

Collision (two keys hash to same index)

Current simple code overwrites previous entry, so last stored value remains.

DSA Javascript

this.buckets[index] = { key, value };

When to Use This Pattern

When you need to store and find data by keys very fast, especially when searching a list is too slow, reach for the hash map pattern because it uses hashing to jump directly to data.

Common Mistakes

Mistake: Not handling collisions, causing data loss when two keys hash to the same slot.
Fix: Implement collision handling like chaining or open addressing to store multiple entries per slot.

Mistake: Using a poor hash function that causes many collisions.
Fix: Use a better hash function that spreads keys evenly across slots.

Summary

A hash map stores key-value pairs so you can find values quickly by their keys.

Use it when you want fast lookup, insertion, and deletion by key instead of searching through all data.

The key insight is using a hash function to jump directly to the data's location instead of checking one by one.

Practice

1. Why do we use a hash map in programming?
hashMap = {}

easy

A. To store key-value pairs for fast data lookup

B. To store data in a sorted order automatically

C. To perform mathematical calculations faster

D. To create a list of items without duplicates

Solution

1. Step 1: Understand the purpose of a hash map

   A hash map stores data as key-value pairs, allowing quick access to values using keys.

2. Step 2: Compare with other data structures

   Unlike lists or arrays, hash maps provide faster lookup by key, not by position or order.

3. Final Answer:

   To store key-value pairs for fast data lookup -> Option A

4. Quick Check:

   Hash map = fast key-value lookup [OK]

Hint: Hash maps store data by keys for quick access [OK]

Common Mistakes:

• Thinking hash maps sort data automatically
• Confusing hash maps with arrays or lists
• Assuming hash maps are for math calculations

2. Which of the following is the correct way to create an empty hash map (object) in JavaScript?

easy

A. const map = []

B. const map = {}

C. const map = () => {}

D. const map = new Map[]

Solution

1. Step 1: Recall JavaScript syntax for objects

   In JavaScript, curly braces {} create an empty object, which can be used as a hash map.

2. Step 2: Check other options

   Square brackets [] create arrays, () => {} is a function, and new Map[] is invalid syntax.

3. Final Answer:

   const map = {} -> Option B

4. Quick Check:

   Empty object = {} [OK]

Hint: Use curly braces {} to create empty hash maps in JavaScript [OK]

Common Mistakes:

• Using [] which creates an array, not a hash map
• Trying to use function syntax for hash map
• Incorrect new Map[] syntax

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

const map = {};
map['apple'] = 5;
map['banana'] = 3;
console.log(map['apple']);

medium

A. 5

B. Error

C. 3

D. undefined

Solution

1. Step 1: Assign values to keys in the hash map

   The code sets map['apple'] = 5 and map['banana'] = 3, storing these key-value pairs.

2. Step 2: Access the value for key 'apple'

   console.log(map['apple']) prints the value 5 stored at key 'apple'.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   map['apple'] = 5, output = 5 [OK]

Hint: Access value by key to get stored number [OK]

Common Mistakes:

• Expecting output to be 'undefined' if key exists
• Confusing values of different keys
• Thinking it causes an error

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

const map = {};
map.apple = 10;
console.log(map['applee']);

medium

A. Syntax error in object creation

B. Using dot notation instead of brackets

C. Cannot assign values to an empty object

D. Accessing a key that does not exist

Solution

1. Step 1: Check key assignment

   map.apple = 10 correctly assigns value 10 to key 'apple'.

2. Step 2: Check key access

   console.log(map['applee']) tries to access key 'applee' which was never assigned, so it returns undefined.

3. Final Answer:

   Accessing a key that does not exist -> Option D

4. Quick Check:

   Wrong key access = undefined [OK]

Hint: Check spelling of keys when accessing hash map values [OK]

Common Mistakes:

• Thinking dot notation is wrong here
• Expecting error on accessing missing key
• Assuming empty object cannot store values

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

const words = ['cat', 'dog', 'cat', 'bird'];
const counts = {};
// Fill counts here
console.log(counts);

hard

A. for (const w of words) { counts[w] = 1; }

B. for (const w of words) { counts[w] = counts[w] + 1; }

C. for (const w of words) { counts[w] = (counts[w] || 0) + 1; }

D. for (const w of words) { counts[w] += 1; }

Solution

1. Step 1: Understand counting logic

   We need to add 1 to the count for each word. If the word is new, start from 0.

2. Step 2: Analyze each option

   for (const w of words) { counts[w] = 1; } sets count to 1 always, ignoring repeats. for (const w of words) { counts[w] = counts[w] + 1; } tries to add 1 but counts[w] is undefined initially causing NaN. for (const w of words) { counts[w] = (counts[w] || 0) + 1; } uses (counts[w] || 0) + 1 to handle undefined keys correctly. for (const w of words) { counts[w] += 1; } tries to add 1 without initialization, causing NaN.

3. Final Answer:

   for (const w of words) { counts[w] = (counts[w] || 0) + 1; } -> Option C

4. Quick Check:

   Initialize with 0 or use || 0 before adding [OK]

Hint: Use (counts[key] || 0) + 1 to count safely [OK]

Common Mistakes:

• Not initializing counts before adding
• Overwriting counts instead of incrementing
• Assuming counts[w] is always defined