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

Concept Flow - Hash Table Concept and Hash Functions

Start: Insert key-value pair

↓

Compute hash(key)

↓

Map hash to index in array

↓

Check bucket at index

↓

Insert

↓

Add to bucket list

↓

Done

Shows how a key-value pair is inserted by hashing the key, finding the index, and handling collisions if needed.

Execution Sample

DSA C++

hash = key % 5;
if (table[hash] == empty) {
  table[hash] = value;
} else {
  add value to bucket list;
}

Inserts a value into a hash table of size 5 using modulo hash function and handles collisions by chaining.

Execution Table

Step	Operation	Key	Hash Computed	Bucket State Before	Bucket State After	Visual State
1	Insert	12	12 % 5 = 2	Empty	12	[Empty, Empty, 12, Empty, Empty]
2	Insert	7	7 % 5 = 2	12	12 -> 7	[Empty, Empty, 12 -> 7, Empty, Empty]
3	Insert	5	5 % 5 = 0	Empty	5	[5, Empty, 12 -> 7, Empty, Empty]
4	Insert	17	17 % 5 = 2	12 -> 7	12 -> 7 -> 17	[5, Empty, 12 -> 7 -> 17, Empty, Empty]
5	Insert	20	20 % 5 = 0	5	5 -> 20	[5 -> 20, Empty, 12 -> 7 -> 17, Empty, Empty]
6	Stop	-	-	-	-	All keys inserted

💡 All keys inserted; hash table buckets updated with chaining for collisions.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
table[0]	Empty	Empty	Empty	5	5	5 -> 20	5 -> 20
table[1]	Empty	Empty	Empty	Empty	Empty	Empty	Empty
table[2]	Empty	12	12 -> 7	12 -> 7	12 -> 7 -> 17	12 -> 7 -> 17	12 -> 7 -> 17
table[3]	Empty	Empty	Empty	Empty	Empty	Empty	Empty
table[4]	Empty	Empty	Empty	Empty	Empty	Empty	Empty

Key Moments - 3 Insights

Why do keys 12, 7, and 17 all go to the same bucket?

Because their hash values (key % 5) all equal 2, so they map to the same index, causing a collision handled by chaining (see steps 1, 2, and 4 in execution_table).

What happens when the bucket is empty before insertion?

The value is directly inserted into the bucket without chaining, as shown in steps 1 and 3 where buckets were empty before insertion.

How does chaining help with collisions?

Chaining stores multiple values in a linked list at the same bucket index, allowing multiple keys with the same hash to coexist, as seen in steps 2, 4, and 5.

Visual Quiz - 3 Questions

Look at the execution_table, what is the bucket state at index 2 after step 4?

A 12 -> 7 -> 17

B 12 -> 7

C 7 -> 17

D Empty

💡 Hint

Check the 'Bucket State After' column for step 4 in execution_table.

At which step does the bucket at index 0 first become non-empty?

A Step 1

B Step 5

C Step 3

D Step 2

💡 Hint

Look at the 'Bucket State After' for table[0] in variable_tracker after each step.

If the hash function changed to key % 3, which bucket would key 20 go to?

A Bucket 0

B Bucket 2

C Bucket 1

D Bucket 3

💡 Hint

Calculate 20 % 3 and check which bucket index it corresponds to.

Concept Snapshot

Hash Table stores key-value pairs using a hash function.
Hash function maps keys to array indices.
Collisions handled by chaining (linked lists at buckets).
Insertion: compute hash, go to bucket, add value.
Fast average lookup and insert if hash distributes well.

Full Transcript

A hash table stores data by converting keys into array indices using a hash function. When inserting a key-value pair, the key is hashed to find the bucket index. If the bucket is empty, the value is stored directly. If not, chaining is used to add the value to a linked list at that bucket. This way, multiple keys with the same hash can be stored without overwriting. The example shows inserting keys 12, 7, 5, 17, and 20 into a hash table of size 5 using modulo hashing. Collisions occur at bucket 2 and bucket 0, handled by chaining. The variable tracker shows how each bucket changes after each insertion. Key moments clarify why collisions happen and how chaining solves them. The quiz tests understanding of bucket states and hash calculations.

Practice

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

easy

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

B. To sort the keys in ascending order

C. To encrypt the data stored in the 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 an index number that points to a position in the hash table.

2. Step 2: Identify the purpose in context

   This index helps quickly find or store the value associated with the key without searching the entire table.

3. Final Answer:

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

4. Quick Check:

   Hash function = key to index [OK]

Hint: Hash function maps keys to indexes fast [OK]

Common Mistakes:

• Thinking hash functions sort keys
• Confusing hashing with encryption
• Assuming hash function counts elements

2. Which of the following is the correct syntax to declare a hash table using unordered_map in C++?

easy

A. hash_map table;

B. unordered_map table;

C. map table;

D. unordered table;

Solution

1. Step 1: Recall C++ hash table declaration

   The standard C++ hash table is declared using unordered_map from the STL.

2. Step 2: Check each option

   unordered_map table; uses unordered_map which is correct syntax. hash_map table; uses hash_map which is non-standard. map table; uses map which is a balanced tree, not a hash table. unordered table; uses unordered which is invalid.

3. Final Answer:

   unordered_map<int, string> table; -> Option B

4. Quick Check:

   unordered_map syntax = correct [OK]

Hint: Use unordered_map for hash tables in C++ [OK]

Common Mistakes:

• Using map instead of unordered_map
• Using non-standard hash_map
• Incorrect container names

3. What will be the output of the following C++ code snippet?

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map table;
    table[1] = "apple";
    table[2] = "banana";
    table[3] = "cherry";
    cout << table[2] << endl;
    return 0;
}

medium

A. Compilation error

B. apple

C. cherry

D. banana

Solution

1. Step 1: Understand the unordered_map insertions

   Keys 1, 2, 3 are assigned values "apple", "banana", and "cherry" respectively.

2. Step 2: Check the output statement

   The code prints the value stored at key 2, which is "banana".

3. Final Answer:

   banana -> Option D

4. Quick Check:

   table[2] = banana [OK]

Hint: Access value by key directly with table[key] [OK]

Common Mistakes:

• Confusing keys and values
• Assuming order matters in unordered_map
• Expecting compilation error due to syntax

4. Identify the error in the following C++ code that uses a hash table:

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map table;
    table.insert("key1", 100);
    cout << table["key1"] << endl;
    return 0;
}

medium

A. insert() requires a pair, not two separate arguments

B. unordered_map keys cannot be strings

C. table["key1"] is invalid syntax

D. Missing #include <map> header

Solution

1. Step 1: Check insert() method usage

   The insert() method expects a single argument of type pair, not two separate arguments.

2. Step 2: Identify correct usage

   Correct usage: table.insert(make_pair("key1", 100)); or table["key1"] = 100;

3. Final Answer:

   insert() requires a pair, not two separate arguments -> Option A

4. Quick Check:

   insert() needs pair argument [OK]

Hint: insert() needs pair, not separate key and value [OK]

Common Mistakes:

• Passing key and value as separate arguments to insert()
• Thinking string keys are invalid
• Confusing table[key] syntax

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

hard

A. Sum ASCII values of all characters modulo table size

B. Use the length of the string modulo table size

C. Use polynomial rolling hash combining character codes and powers

D. Use the first character's ASCII value only

Solution

1. Step 1: Evaluate simple hash methods

   Summing ASCII values or using string length often causes many collisions because different strings can have same sums or lengths.

2. Step 2: Understand polynomial rolling hash

   This method combines character codes with powers of a base number, spreading keys more evenly and reducing collisions.

3. Step 3: Compare options

   Use polynomial rolling hash combining character codes and powers is the best because it balances speed and collision reduction for strings.

4. Final Answer:

   Use polynomial rolling hash combining character codes and powers -> Option C

5. Quick Check:

   Polynomial rolling hash = fewer collisions [OK]

Hint: Polynomial rolling hash reduces collisions best [OK]

Common Mistakes:

• Using simple sums causing many collisions
• Ignoring string content beyond length or first char
• Choosing inefficient or weak hash functions