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

Concept Flow - Why Hash Map Exists and What Problem It Solves

Need to store key-value pairs

↓

Use simple list/array

↓

Problem: Slow search (linear scan)

↓

Idea: Use hash function

↓

Map key to index fast

↓

Store value at computed index

↓

Fast lookup, insert, delete

↓

Hash Map solves slow search problem

Shows how storing key-value pairs in a list is slow, so hash maps use a hash function to quickly find data.

Execution Sample

DSA Javascript

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

Stores fruit counts in a hash map and retrieves the count for 'apple' quickly.

Execution Table

Step	Operation	Key	Value	Hash Index	Collision?	Visual State
1	Insert	'apple'	5	hash('apple')=2	No	[null, null, ('apple',5), null, null]
2	Insert	'banana'	3	hash('banana')=4	No	[null, null, ('apple',5), null, ('banana',3)]
3	Lookup	'apple'	-	hash('apple')=2	-	Found ('apple',5) at index 2
4	Lookup	'banana'	-	hash('banana')=4	-	Found ('banana',3) at index 4
5	Lookup	'cherry'	-	hash('cherry')=2	Yes	Collision at index 2, check next slots
6	Insert	'cherry'	7	hash('cherry')=2	Yes	[null, null, ('apple',5), ('cherry',7), ('banana',3)]
7	Lookup	'cherry'	-	hash('cherry')=2	Yes	Found ('cherry',7) after resolving collision

💡 All operations done; hash map allows fast insert and lookup even with collisions.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
map array	[null, null, null, null, null]	[null, null, ('apple',5), null, null]	[null, null, ('apple',5), null, ('banana',3)]	[null, null, ('apple',5), null, ('banana',3)]	[null, null, ('apple',5), null, ('banana',3)]	[null, null, ('apple',5), null, ('banana',3)]	[null, null, ('apple',5), ('cherry',7), ('banana',3)]	[null, null, ('apple',5), ('cherry',7), ('banana',3)]
hash('apple')	-	2	2	2	2	2	2	2
hash('banana')	-	-	4	4	4	4	4	4
hash('cherry')	-	-	-	-	2	2	2	2

Key Moments - 3 Insights

Why can't we just use a list or array to store key-value pairs?

Using a list means searching for a key takes time proportional to the list size (linear search). The execution_table rows 1 and 2 show insertions, but lookups in rows 3 and 4 are fast because of hashing, unlike scanning a list.

What happens when two keys hash to the same index?

This is called a collision. The execution_table rows 5 and 6 show 'cherry' colliding with 'apple' at index 2, so the map stores 'cherry' in the next available slot to keep data accessible.

How does the hash map find a value quickly?

It uses the hash function to jump directly to the index where the key should be. The execution_table rows 3 and 4 show direct access to 'apple' and 'banana' without scanning the whole map.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is found at index 2?

A ('apple', 5)

B ('banana', 3)

C null

D ('cherry', 7)

💡 Hint

Check the 'Visual State' and 'Hash Index' columns at step 3.

At which step does a collision occur?

A Step 2

B Step 5

C Step 4

D Step 7

💡 Hint

Look at the 'Collision?' column in the execution_table.

If the hash function for 'banana' changed to 2, what would happen?

A No collisions, same as before

B Collision with 'apple' at index 2

C Collision with 'cherry' at index 4

D Map would be empty

💡 Hint

Refer to how collisions are handled when keys share the same hash index.

Concept Snapshot

Hash Map stores key-value pairs for fast access.
Uses a hash function to convert keys to array indices.
Avoids slow linear search by direct indexing.
Handles collisions by storing in next free slot.
Supports fast insert, lookup, and delete operations.

Full Transcript

A hash map exists to solve the problem of slow search in simple lists when storing key-value pairs. Instead of scanning each item, it uses a hash function to convert keys into array indices, allowing direct access. When two keys hash to the same index, a collision occurs, and the map stores the new key in the next available slot. This approach makes insertions and lookups very fast compared to lists. The example code shows inserting 'apple' and 'banana' with their counts, then quickly retrieving 'apple'. The execution table traces each step, showing how keys map to indices and how collisions are resolved. This visual helps understand why hash maps are essential for efficient data storage and retrieval.

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