Hash Table Concept and Hash Functions in DSA C++

Mental Model

A hash table stores data by turning keys into numbers to find values quickly. It uses a special function to decide where to put each item.

Analogy: Imagine a library where each book has a unique code. Instead of searching all shelves, you use the code to go directly to the right shelf and spot.

Hash Table:
[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Hash Function: key % 5
Example: key=12 -> 12 % 5 = 2 -> store at index 2

Dry Run Walkthrough

Input: Insert keys 12, 7, 22 into a hash table of size 5 using hash function key % 5

Goal: Show how keys are placed in the table using the hash function

Step 1: Calculate hash for key 12 and insert at index

[0] -> null
[1] -> null
[2] -> 12 -> null
[3] -> null
[4] -> null

Why: 12 % 5 = 2, so 12 goes to index 2

Step 2: Calculate hash for key 7 and insert at index

[0] -> null
[1] -> null
[2] -> 12 -> 7 -> null
[3] -> null
[4] -> null

Why: 7 % 5 = 2, index 2 has 12, so we use chaining and add 7 to the list at index 2

Step 3: Calculate hash for key 22 and insert at index

[0] -> null
[1] -> null
[2] -> 12 -> 7 -> 22 -> null
[3] -> null
[4] -> null

Why: 22 % 5 = 2, index 2 has 12 -> 7, so add 22 to the chain at index 2

Result:

[0] -> null
[1] -> null
[2] -> 12 -> 7 -> 22 -> null
[3] -> null
[4] -> null

Annotated Code

DSA C++

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

class HashTable {
    int size;
    list<int>* table;

public:
    HashTable(int s) {
        size = s;
        table = new list<int>[size];
    }

    int hashFunction(int key) {
        return key % size; // map key to index
    }

    void insert(int key) {
        int index = hashFunction(key); // find index
        table[index].push_back(key); // add key to chain
    }

    void display() {
        for (int i = 0; i < size; i++) {
            cout << "[" << i << "] -> ";
            for (int key : table[i]) {
                cout << key << " -> ";
            }
            cout << "null" << endl;
        }
    }
};

int main() {
    HashTable ht(5);
    ht.insert(12);
    ht.insert(7);
    ht.insert(22);
    ht.display();
    return 0;
}

int index = hashFunction(key); // find index

compute index using hash function key % size

table[index].push_back(key); // add key to chain

insert key at the computed index using chaining

for (int i = 0; i < size; i++) { ... }

iterate over all indices to print chains

Output

[0] -> null

[1] -> null

[2] -> 12 -> 7 -> 22 -> null

[3] -> null

[4] -> null

Complexity Analysis

Time: O(1) average for insert because hash function directly finds index; worst O(n) if many collisions

Space: O(n) because we store all keys in the table and chains

vs Alternative: Compared to arrays or lists, hash tables provide faster average lookup and insert by avoiding full scans

Edge Cases

Inserting keys that hash to the same index

Keys are stored in a linked list (chain) at that index to handle collisions

DSA C++

table[index].push_back(key); // add key to chain

Empty hash table before any insert

All indices point to empty chains (null)

DSA C++

for (int i = 0; i < size; i++) { cout << ... }

When to Use This Pattern

When you need fast lookup by key and can accept some collisions, use a hash table with a hash function to map keys to indices.

Common Mistakes

Mistake: Not handling collisions, causing overwriting of existing keys
Fix: Use chaining or open addressing to store multiple keys at the same index

Mistake: Using a poor hash function causing many collisions
Fix: Choose a hash function that distributes keys evenly across indices

Summary

Stores data by converting keys into indices using a hash function.

Use when you want quick access to data by key without searching all items.

The key insight is that a good hash function lets you jump directly to where data lives.

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