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

Concept Flow - Hash Table Concept and Hash Functions

Start: Insert or Search Key

↓

Apply Hash Function to Key

↓

Compute Index = Hash Value % Table Size

↓

Access Bucket at Index

↓

If Insert: Add Key-Value Pair to Bucket

↓

If Search: Check Bucket for Key

↓

Return Value or Indicate Not Found

The hash table uses a hash function to convert a key into an index, then accesses that index to insert or find the key-value pair.

Execution Sample

DSA C

int hash(int key, int table_size) {
    return key % table_size;
}

// Insert key 10 into table of size 5
int index = hash(10, 5);

This code computes the index for key 10 in a hash table of size 5 using modulo hash function.

Execution Table

Step	Operation	Key	Hash Value	Index (Hash % Size)	Bucket State	Visual State
1	Compute hash for key	10	10	10 % 5 = 0	Bucket 0: []	[] -> [] -> [] -> [] -> []
2	Insert key-value pair	10	10	0	Bucket 0: [(10, value)]	[(10)] -> [] -> [] -> [] -> []
3	Compute hash for key	15	15	15 % 5 = 0	Bucket 0: [(10, value)]	[(10)] -> [] -> [] -> [] -> []
4	Insert key-value pair	15	15	0	Bucket 0: [(10, value), (15, value)]	[(10)->(15)] -> [] -> [] -> [] -> []
5	Search for key	10	10	0	Bucket 0: [(10, value), (15, value)]	[(10)->(15)] -> [] -> [] -> [] -> []
6	Found key 10 in bucket 0	10	10	0	Bucket 0 unchanged	[(10)->(15)] -> [] -> [] -> [] -> []
7	Search for key	7	7	7 % 5 = 2	Bucket 2: []	[(10)->(15)] -> [] -> [] -> [] -> []
8	Key 7 not found in bucket 2	7	7	2	Bucket 2 unchanged	[(10)->(15)] -> [] -> [] -> [] -> []

💡 All operations complete; keys inserted or searched with hash function mapping to buckets.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 6	After Step 8
key	N/A	10	10	15	10	7
hash_value	N/A	10	10	15	10	7
index	N/A	0	0	0	0	2
bucket_0	[]	[]	[(10, value)]	[(10, value)->(15, value)]	[(10, value)->(15, value)]	[(10, value)->(15, value)]
bucket_2	[]	[]	[]	[]	[]	[]

Key Moments - 3 Insights

Why do multiple keys like 10 and 15 end up in the same bucket?

Because the hash function maps both keys to the same index 0 (10 % 5 = 0 and 15 % 5 = 0), causing a collision handled by storing both in the same bucket (see steps 3 and 4 in execution_table).

What happens when searching for a key not present in the table?

The hash function computes the index, but the bucket at that index is empty or does not contain the key, so the search returns not found (see steps 7 and 8 in execution_table).

Why use modulo (%) with table size in the hash function?

Modulo ensures the hash value fits within the table size range, giving a valid index (see step 1 and 3 where hash values are reduced by modulo).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the state of bucket 0?

A [(10, value)]

B [(15, value)]

C [(10, value), (15, value)]

D []

💡 Hint

Refer to the 'Bucket State' column at step 4 in execution_table.

At which step does the search for key 7 conclude it is not found?

A Step 8

B Step 6

C Step 7

D Step 5

💡 Hint

Check the 'Operation' and 'Key' columns for key 7 in execution_table.

If the table size changed from 5 to 10, what would be the index for key 15?

A 0

B 5

C 10

D 15

💡 Hint

Calculate 15 % 10 and compare with the 'Index' column logic in execution_table.

Concept Snapshot

Hash Table uses a hash function to convert keys into indexes.
Index = hash(key) % table_size ensures valid bucket access.
Collisions happen when multiple keys map to the same index.
Buckets store key-value pairs; search checks bucket contents.
Efficient average lookup, insert, and delete operations.

Full Transcript

A hash table stores data by converting keys into indexes using a hash function. The hash function computes a number from the key, then modulo operation limits it to the table size. This index points to a bucket where the key-value pair is stored. When inserting, if multiple keys map to the same bucket, they are stored together, handling collisions. Searching uses the same hash function to find the bucket and then looks for the key inside it. If the key is not found, the search ends. This method allows fast access to data by key.