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

Concept Flow - Hash Table Concept and Hash Functions

Start: Insert key-value pair

↓

Apply hash function on key

↓

Get index from hash value

↓

Check bucket at index

↓

Insert pair

↓

Done

↓

Insert pair

↓

Done

Shows how a key-value pair is inserted into a hash table using a hash function to find the index, then inserting or handling collisions.

Execution Sample

DSA Python

hash_table = [None] * 5
key = 'cat'
hash_value = hash(key)
index = hash_value % 5
hash_table[index] = (key, 'meow')

Inserts the key 'cat' with value 'meow' into a hash table of size 5 using a hash function.

Execution Table

Step	Operation	Key	Hash Value	Index	Bucket State	Visual State
1	Start insertion	cat			[None, None, None, None, None]	None -> None -> None -> None -> None
2	Compute hash	cat	e.g. 123456789			None -> None -> None -> None -> None
3	Calculate index	cat	123456789	4		None -> None -> None -> None -> None
4	Check bucket at index 4	cat	123456789	4	Empty	None -> None -> None -> None -> None
5	Insert ('cat', 'meow')	cat	123456789	4	Occupied	None -> None -> None -> None -> ('cat', 'meow')
6	Done	cat	123456789	4	Occupied	None -> None -> None -> None -> ('cat', 'meow')

💡 Insertion complete as bucket at index 4 was empty.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	Final
hash_table	[None, None, None, None, None]	[None, None, None, None, None]	[None, None, None, None, None]	[None, None, None, None, ('cat', 'meow')]	[None, None, None, None, ('cat', 'meow')]
key	cat	cat	cat	cat	cat
hash_value		123456789	123456789	123456789	123456789
index			4	4	4

Key Moments - 3 Insights

Why do we use the modulo operator (%) on the hash value?

Because the hash value can be very large, modulo limits it to the size of the hash table, giving a valid index (see Step 3 in execution_table).

What happens if the bucket at the computed index is already occupied?

We handle collisions by methods like chaining or probing (shown in concept_flow branch 'Handle collision'), but in this example, the bucket was empty (Step 4).

Why do we store key-value pairs instead of just values?

Because different keys can hash to the same index, storing pairs helps verify the correct key during lookup or collision handling.

Visual Quiz - 3 Questions

Look at the execution_table, what is the index computed for key 'cat'?

A 4

B 2

C 3

D 0

💡 Hint

Check the 'Index' column at Step 3 in the execution_table.

At which step does the hash table get updated with the new key-value pair?

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the step where 'Insert' operation happens and bucket state changes to 'Occupied'.

If the hash table size changed to 3, how would the index for 'cat' change?

A It would remain the same as before

B It would be hash('cat') % 3

C It would be hash('cat') % 5

D It would be 0

💡 Hint

Index depends on modulo with table size, see Step 3 in execution_table.

Concept Snapshot

Hash Table stores key-value pairs.
Hash function converts key to a number.
Modulo operator limits index to table size.
Insert at computed index.
Handle collisions if bucket occupied.
Fast average lookup and insertion.

Full Transcript

A hash table stores data as key-value pairs. To insert, we apply a hash function to the key, which gives a large number. We then use modulo with the table size to get a valid index. If the bucket at that index is empty, we insert the pair. If occupied, we handle collisions by chaining or probing. This process allows fast data access by key.