Hash Table Concept and Hash Functions in DSA Typescript - Execution Trace

Concept Flow - Hash Table Concept and Hash Functions

Start: Insert key-value pair

↓

Apply hash function to key

↓

Get index in array

↓

Check if index slot is empty

↓

Insert pair

↓

Done

Shows how a key-value pair is inserted by hashing the key to find an index, then inserting or handling collisions.

Execution Sample

DSA Typescript

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

This code computes an index for a key by summing character codes and taking modulo with table size.

Execution Table

Step	Operation	Key	Hash Value	Index	Array Slot State	Visual State
1	Start insert	cat	-	-	[empty, empty, empty, empty]	[null, null, null, null]
2	Hash key	cat	99+97+116=312	312 % 4 = 0	[empty, empty, empty, empty]	[null, null, null, null]
3	Insert at index 0	cat	312	0	[('cat', value), empty, empty, empty]	[(cat, val), null, null, null]
4	Start insert	dog	-	-	[('cat', value), empty, empty, empty]	[(cat, val), null, null, null]
5	Hash key	dog	100+111+103=314	314 % 4 = 2	[('cat', value), empty, empty, empty]	[(cat, val), null, null, null]
6	Insert at index 2	dog	314	2	[('cat', value), empty, ('dog', value), empty]	[(cat, val), null, (dog, val), null]
7	Start insert	act	-	-	[('cat', value), empty, ('dog', value), empty]	[(cat, val), null, (dog, val), null]
8	Hash key	act	97+99+116=312	312 % 4 = 0	[('cat', value), empty, ('dog', value), empty]	[(cat, val), null, (dog, val), null]
9	Collision at index 0	act	312	0	[('cat', value) -> ('act', value), empty, ('dog', value), empty]	[(cat, val) -> (act, val), null, (dog, val), null]
10	Done	-	-	-	[('cat', value) -> ('act', value), empty, ('dog', value), empty]	[(cat, val) -> (act, val), null, (dog, val), null]

💡 All keys inserted; collisions handled by chaining at index 0.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	Final
hash	0	312	314	312	312
index	-	0	2	0	0
array	[null, null, null, null]	[null, null, null, null]	[(cat, val), null, null, null]	[(cat, val), null, (dog, val), null]	[(cat, val) -> (act, val), null, (dog, val), null]

Key Moments - 3 Insights

Why does 'act' cause a collision with 'cat'?

Because both 'cat' and 'act' produce the same hash value 312, resulting in the same index 0 in the array, as shown in execution_table rows 2, 8, and 9.

What happens when the array slot is not empty?

The new key-value pair is added to a linked list (chaining) at that index to handle collision, as seen in execution_table row 9.

Why do we use modulo with the array size?

Modulo ensures the hash value fits within the array bounds, mapping any large hash to a valid index, as shown in execution_table rows 2, 5, and 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the index computed for key 'dog'?

A 0

B 2

C 3

D 1

💡 Hint

Check the 'Index' column at step 5 in the execution_table.

At which step does a collision occur during insertion?

A Step 3

B Step 6

C Step 9

D Step 7

💡 Hint

Look for 'Collision' in the 'Operation' column in the execution_table.

If the array size changed to 5, what would be the new index for key 'cat'?

A 2

B 0

C 3

D 1

💡 Hint

Calculate (99+97+116) % 5 and compare with the 'Index' column logic.

Concept Snapshot

Hash Table stores key-value pairs using an array.
A hash function converts keys to array indices.
Collisions happen when different keys map to the same index.
Chaining (linked lists) handles collisions by storing multiple pairs at one index.
Modulo operation keeps indices within array bounds.

Full Transcript

A hash table stores data by converting keys into array indices using a hash function. The hash function sums character codes of the key and uses modulo with the array size to find the index. When inserting, if the slot is empty, the key-value pair is placed there. If not, a collision occurs, and the new pair is added to a linked list at that index. This process ensures efficient data storage and retrieval.

Practice

1. What is the main purpose of a hash function in a hash table?

easy

A. To sort the keys in ascending order

B. To count the number of elements in the table

C. To encrypt the stored data for security

D. To convert a key into an index for storing values

Solution

1. Step 1: Understand the role of a hash function

   A hash function takes a key and converts it into a number called an index.

2. Step 2: Connect index to storage in hash table

   This index tells where to store or find the value in the hash table.

3. Final Answer:

   To convert a key into an index for storing values -> Option D

4. Quick Check:

   Hash function = key to index [OK]

Hint: Hash function maps keys to storage spots [OK]

Common Mistakes:

• Thinking hash function sorts keys
• Confusing hash function with encryption
• Believing hash function counts elements

2. Which of the following is the correct way to declare a hash table (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 with new Map().

2. Step 2: Check each option's syntax

   const map = new Map(); uses correct syntax: new Map(). Others have syntax errors or wrong usage.

3. Final Answer:

   const map = new Map(); -> Option C

4. Quick Check:

   Map declaration = new Map<Key, Value>() [OK]

Hint: Use new Map() to declare [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. 10

B. Error

C. undefined

D. 5

Solution

1. Step 1: Understand Map set behavior

   Setting a key that already exists updates its value.

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 A

4. Quick Check:

   Updated value = 10 [OK]

Hint: Last set value for key is stored [OK]

Common Mistakes:

• Assuming first value stays
• Thinking get returns undefined if key repeated
• Confusing Map with object property behavior

4. Identify the error in the following TypeScript code using a hash table:

const map = new Map();
map.set(1, 'one');
map.set(2, 'two');
console.log(map.get('1'));

medium

A. Missing parentheses in map.get call

B. Using string '1' instead of number 1 as key

C. Map keys must be strings only

D. Cannot mix number and string values in Map

Solution

1. Step 1: Check Map key type

   Map is declared with number keys, so keys must be numbers.

2. Step 2: Analyze map.get argument

   map.get('1') uses string '1', which does not match number 1 key, so returns undefined.

3. Final Answer:

   Using string '1' instead of number 1 as key -> Option B

4. Quick Check:

   Key type mismatch causes undefined [OK]

Hint: Match key types exactly when using get() [OK]

Common Mistakes:

• Assuming '1' and 1 are same keys
• Thinking Map keys must be strings
• Ignoring type mismatch errors

5. You want to design a hash function for strings that minimizes collisions for English words. Which approach is best?

hard

A. Multiply each character code by a prime number and sum, then modulo table size

B. Use the length of the string as the hash value

C. Sum the ASCII codes of all characters and take modulo table size

D. Use the first character's ASCII code only

Solution

1. Step 1: Understand collision minimization

   Good hash functions spread keys evenly to reduce collisions.

2. Step 2: Evaluate each approach

   Sum the ASCII codes of all characters and take modulo table size sums codes but can cause many collisions (e.g., 'abc' and 'cab'). Use the length of the string as the hash value uses length only, very poor. Use the first character's ASCII code only uses first char only, also poor. Multiply each character code by a prime number and sum, then modulo table size uses weighted sum with primes, better distribution.

3. Final Answer:

   Multiply each character code by a prime number and sum, then modulo table size -> Option A

4. Quick Check:

   Weighted sum with primes = better hash [OK]

Hint: Use prime multipliers for better hash spread [OK]

Common Mistakes:

• Using simple sums causing collisions
• Ignoring character positions
• Using string length as hash