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.

Practice

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

easy

A. To encrypt the data before storing

B. To convert a key into an index for storing data

C. To sort the data stored in the hash table

D. To count the number of elements in the table

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 data storage

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

3. Final Answer:

   To convert a key into an index for storing data -> Option B

4. Quick Check:

   Hash function = key to index [OK]

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

Common Mistakes:

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

2. Which of the following is the correct way to declare a hash function in C that takes an integer key and returns an integer index?

easy

A. int hashFunction(void key);

B. void hashFunction(int key);

C. int hashFunction(int key);

D. hashFunction int(int key);

Solution

1. Step 1: Check function return type and parameters

   The function should return an int and take an int parameter.

2. Step 2: Verify syntax correctness

   int hashFunction(int key); matches C syntax: return type first, then function name, then parameter list.

3. Final Answer:

   int hashFunction(int key); -> Option C

4. Quick Check:

   Correct C function declaration = int hashFunction(int key); [OK]

Hint: Function syntax: return_type name(parameter_type parameter) [OK]

Common Mistakes:

• Using void return type when int is needed
• Incorrect parameter type syntax
• Wrong order of function declaration parts

3. Consider the following C code snippet for a simple hash function and hash table insertion:

#include <stdio.h>

int hashFunction(int key) {
    return key % 5;
}

int main() {
    int hashTable[5] = {-1, -1, -1, -1, -1};
    int keys[] = {12, 22, 32};
    for (int i = 0; i < 3; i++) {
        int index = hashFunction(keys[i]);
        hashTable[index] = keys[i];
    }
    for (int i = 0; i < 5; i++) {
        printf("%d ", hashTable[i]);
    }
    return 0;
}

What is the output of this program?

medium

A. -1 -1 32 -1 -1

B. 12 22 32 -1 -1

C. -1 22 32 -1 12

D. 12 -1 -1 22 32

Solution

1. Step 1: Calculate hash indices for each key

   12 % 5 = 2, 22 % 5 = 2, 32 % 5 = 2.

2. Step 2: Insert keys into hashTable at calculated indices

   All keys map to index 2, so last key 32 overwrites previous ones. hashTable = {-1, -1, 32, -1, -1}.

3. Final Answer:

   -1 -1 32 -1 -1 -> Option A

4. Quick Check:

   Collision overwrites at index 2 = -1 -1 32 -1 -1 [OK]

Hint: Check modulo results and overwrites in array [OK]

Common Mistakes:

• Assuming keys store at different indices
• Ignoring collisions overwrite
• Miscomputing modulo operation

4. The following C code tries to insert keys into a hash table but has a bug:

int hashFunction(int key) {
    return key % 10;
}

int main() {
    int hashTable[10];
    int keys[] = {5, 15, 25};
    for (int i = 0; i < 3; i++) {
        int index = hashFunction(keys[i]);
        if (hashTable[index] == -1) {
            hashTable[index] = keys[i];
        }
    }
    return 0;
}

What is the bug in this code?

medium

A. Keys array is not declared correctly

B. hashFunction returns wrong index

C. Loop condition should be i <= 3

D. hashTable array is not initialized to -1

Solution

1. Step 1: Check initialization of hashTable

   hashTable is declared but not initialized, so values are garbage, not -1.

2. Step 2: Understand impact on insertion condition

   Condition 'hashTable[index] == -1' may never be true, so keys won't insert properly.

3. Final Answer:

   hashTable array is not initialized to -1 -> Option D

4. Quick Check:

   Uninitialized array causes insertion failure [OK]

Hint: Always initialize hash table slots before use [OK]

Common Mistakes:

• Assuming default zero initialization
• Changing loop bounds incorrectly
• Misunderstanding hash function correctness

5. You want to design a hash function for strings in C that maps each string to an index in a hash table of size 10. Which approach below is the best to reduce collisions?

hard

A. Multiply each character's ASCII by its position, sum all, then modulo 10

B. Use only the ASCII value of the first character modulo 10

C. Return a fixed index like 0 for all strings

D. Sum ASCII values of all characters and take modulo 10

Solution

1. Step 1: Evaluate simple sum method

   Summing ASCII values (Sum ASCII values of all characters and take modulo 10) can cause many collisions for anagrams.

2. Step 2: Consider position-weighted sum

   Multiplying each character by its position (Multiply each character's ASCII by its position, sum all, then modulo 10) creates more unique values, reducing collisions.

3. Step 3: Reject poor methods

   Using only first character (Use only the ASCII value of the first character modulo 10) or fixed index (Return a fixed index like 0 for all strings) causes many collisions.

4. Final Answer:

   Multiply each character's ASCII by its position, sum all, then modulo 10 -> Option A

5. Quick Check:

   Position-weighted sum reduces collisions best [OK]

Hint: Use character positions to spread hash values [OK]

Common Mistakes:

• Using only first character causes collisions
• Ignoring character positions
• Using fixed index for all keys