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

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

Start: Need to store key-value pairs

↓

Use simple list/array?

↓

Problem: Slow search (linear time)

↓

Use Hash Function to convert key to index

↓

Store value at computed index

↓

Retrieve value quickly by key using hash

↓

Handle collisions if two keys map to same index

↓

Result: Fast insert, search, delete operations

Shows the flow from needing to store key-value pairs, facing slow search in lists, to using hashing for fast access.

Execution Sample

DSA Typescript

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

Stores values by keys and retrieves the value for 'apple' quickly.

Execution Table

Step	Operation	Key	Hash Index	Collision?	Action	Map State (key:value pairs)
1	Insert	'apple'	hash('apple')=2	No	Store 5 at index 2	{2: ('apple', 5)}
2	Insert	'banana'	hash('banana')=5	No	Store 3 at index 5	{2: ('apple', 5), 5: ('banana', 3)}
3	Retrieve	'apple'	hash('apple')=2	No	Return 5 from index 2	{2: ('apple', 5), 5: ('banana', 3)}
4	Insert	'grape'	hash('grape')=2	Yes	Handle collision at index 2	{2: [('apple', 5), ('grape', 7)], 5: ('banana', 3)}
5	Retrieve	'grape'	hash('grape')=2	Yes	Search list at index 2, return 7	{2: [('apple', 5), ('grape', 7)], 5: ('banana', 3)}
6	Retrieve	'orange'	hash('orange')=7	No	Index 7 empty, return null	{2: [('apple', 5), ('grape', 7)], 5: ('banana', 3)}

💡 All operations done; collisions handled by chaining; fast access achieved.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 6
map	{}	{2: ('apple', 5)}	{2: ('apple', 5), 5: ('banana', 3)}	{2: [('apple', 5), ('grape', 7)], 5: ('banana', 3)}	{2: [('apple', 5), ('grape', 7)], 5: ('banana', 3)}
hash('apple')	N/A	2	2	2	2
hash('banana')	N/A	N/A	5	5	5
hash('grape')	N/A	N/A	N/A	2	2
hash('orange')	N/A	N/A	N/A	N/A	7

Key Moments - 3 Insights

Why do we need a hash function instead of just storing keys in a list?

Because storing keys in a list means searching is slow (linear time). The hash function converts keys to indexes for fast access, as shown in steps 1-3 of the execution_table.

What happens when two keys produce the same hash index?

This is called a collision. We handle it by storing multiple key-value pairs at the same index, like in step 4 where 'grape' collides with 'apple' and both are stored in a list at index 2.

How does the hash map find the correct value when collisions happen?

It searches the list at the collided index for the matching key, as shown in step 5 where it finds 'grape' among multiple entries at index 2.

Visual Quiz - 3 Questions

Look at the execution_table, what is stored at index 5 after step 2?

A ('apple', 5)

B ('banana', 3)

C ('grape', 7)

D Empty

💡 Hint

Check the Map State column at step 2 in the execution_table.

At which step does a collision first occur?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for the Collision? column in the execution_table.

If the hash function changed so 'grape' hashed to index 7, what would happen at step 4?

A No collision, store 'grape' at index 7

B Error because index 7 is empty

C Collision at index 7

D Overwrite 'banana' at index 5

💡 Hint

Refer to how collisions are handled and the Map State in the execution_table.

Concept Snapshot

Hash Map stores key-value pairs for fast access.
Uses a hash function to convert keys to indexes.
Handles collisions by storing multiple pairs at one index.
Provides near constant time insert, search, and delete.
Solves slow search problem of simple lists.

Full Transcript

A hash map exists to store key-value pairs efficiently. Without it, storing keys in a list means searching is slow because you check each item one by one. The hash map uses a hash function to convert keys into indexes, so it can store and find values quickly. Sometimes, two keys get the same index, causing a collision. The hash map handles this by storing multiple pairs at that index, usually in a list. This way, it keeps operations fast even with collisions. The example shows inserting 'apple' and 'banana' with no collisions, then 'grape' causing a collision with 'apple'. Retrieving values uses the hash to find the index and then searches the list if needed. This solves the problem of slow search in simple lists.

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