Hash Table Concept and Hash Functions in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting keys in a hash table with chaining

Consider a hash table with 5 buckets (indices 0 to 4). The hash function is h(key) = key % 5. Keys are inserted in this order: 12, 7, 22, 17, 5. What is the state of the hash table after all insertions? Each bucket stores keys in insertion order using chaining (linked list).

DSA C++

Buckets:
0: 
1: 
2: 
3: 
4: 

Insert keys: 12, 7, 22, 17, 5
Hash function: h(key) = key % 5

Show each bucket's keys separated by ' -> ' and ending with 'null'.

A

0: 5 -> null
1: 7 -> 17 -> null
2: 12 -> null
3: null
4: 22 -> null

B

0: 5 -> null
1: 7 -> null
2: 12 -> 22 -> null
3: 17 -> null
4: null

C

0: 5 -> null
1: null
2: 12 -> 7 -> 22 -> 17 -> null
3: null
4: null

D

0: 5 -> null
1: 7 -> null
2: 12 -> null
3: 22 -> 17 -> null
4: null

💡 Hint

Calculate the bucket index for each key using the hash function and insert keys in order.

Calculate key % 5 for each key:

• 12 % 5 = 2 → bucket 2
• 7 % 5 = 2 → bucket 2
• 22 % 5 = 2 → bucket 2
• 17 % 5 = 2 → bucket 2
• 5 % 5 = 0 → bucket 0

Keys are inserted in order into their respective buckets using chaining. Bucket 0: 5 -> null. Bucket 2: 12 -> 7 -> 22 -> 17 -> null. Other buckets empty. This matches option C.

🧠 Conceptual

intermediate

Understanding hash function properties

Which property is most important for a hash function used in a hash table?

A It should always return the same hash value for the same input.

B It should produce a unique hash value for every possible input.

C It should be very slow to compute to prevent attacks.

D It should produce hash values that are always even numbers.

💡 Hint

Think about consistency when looking up keys.

The hash function must always return the same hash value for the same input to ensure that the key can be found in the hash table. Producing unique hash values for every input is impossible due to limited bucket size. Speed is important but not the most critical property here. Producing always even numbers would cause poor distribution.

🔧 Debug

advanced

Identify the error in this hash function implementation

This C++ hash function is intended to compute key % size but has a bug. What error will it cause?

DSA C++

int hashFunction(int key, int size) {
    return key / size;
}

// size is the number of buckets

A It will cause a division by zero error if size is zero.

B It will return the wrong bucket index because it uses division instead of modulo.

C It will cause a syntax error due to missing semicolon.

D It will cause a runtime error due to integer overflow.

💡 Hint

Check the operator used for hashing.

The function uses division / instead of modulo %. This will return the quotient, not the remainder, so keys will be mapped incorrectly to buckets.

🚀 Application

advanced

Choosing a hash function for string keys

You want to store string keys in a hash table. Which of these hash functions is best for distributing keys evenly?

A Sum the ASCII values of all characters and take modulo table size.

B Use a constant value for all keys.

C Use the ASCII value of the first character modulo table size.

D Use the length of the string modulo table size.

💡 Hint

Consider how well the function spreads different strings across buckets.

Summing ASCII values considers all characters, helping spread keys better. Using length or first character alone causes many collisions. Using a constant value puts all keys in one bucket, causing worst performance.

❓ Predict Output

expert

Output of custom hash function with collision handling

Given a hash table with 3 buckets (0,1,2) and this hash function:
int h(int key) { return (key * 7 + 3) % 3; }
Keys inserted in order: 1, 4, 7, 10.
Collision is handled by chaining (linked list). What is the final state of the hash table?

DSA C++

Buckets:
0: 
1: 
2: 

Insert keys: 1, 4, 7, 10
Hash function: h(key) = (key * 7 + 3) % 3

Show each bucket's keys separated by ' -> ' and ending with 'null'.

A

0: 1 -> null
1: 4 -> 7 -> 10 -> null
2: null

B

0: 1 -> 10 -> null
1: 4 -> null
2: 7 -> null

C

0: 10 -> null
1: 1 -> 4 -> 7 -> null
2: null

D

0: null
1: 1 -> 4 -> 7 -> 10 -> null
2: null

💡 Hint

Calculate the hash for each key and place them in buckets accordingly.

Calculate each key's bucket:

• h(1) = (1*7+3)%3 = 10%3 = 1
• h(4) = (4*7+3)%3 = 31%3 = 1
• h(7) = (7*7+3)%3 = 52%3 = 1
• h(10) = (10*7+3)%3 = 73%3 = 1

All keys map to bucket 1: 1 -> 4 -> 7 -> 10 -> null. Buckets 0 and 2 empty. This is option D.

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