Hash Table Concept and Hash Functions in DSA C

Mental Model

A hash table stores data so you can find it very fast by turning the data into a number called a hash.

Analogy: Imagine a library where each book has a special code that tells you exactly which shelf and spot to find it quickly without searching all shelves.

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

Hash Function: key -> index (0 to 4)

Dry Run Walkthrough

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

Goal: Store keys so they can be found quickly by their hash index

Step 1: Calculate hash for key 12: 12 % 5 = 2, insert 12 at index 2

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

Why: We use the hash function to find the correct index to store key 12

Step 2: Calculate hash for key 22: 22 % 5 = 2, insert 22 at index 2 using chaining

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

Why: Collision happens at index 2, so we add 22 in a linked list at that index

Step 3: Calculate hash for key 32: 32 % 5 = 2, insert 32 at index 2 using chaining

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

Why: Another collision at index 2, so we add 32 at the front of the linked list

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 5

// Node for chaining
typedef struct Node {
    int key;
    struct Node* next;
} Node;

// Hash table with chaining
Node* hashTable[TABLE_SIZE];

// Hash function: key modulo table size
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// Insert key into hash table
void insert(int key) {
    int index = hashFunction(key); // get index
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = hashTable[index]; // insert at head
    hashTable[index] = newNode;
}

// Print hash table
void printTable() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("[%d] -> ", i);
        Node* curr = hashTable[i];
        while (curr != NULL) {
            printf("%d -> ", curr->key);
            curr = curr->next;
        }
        printf("null\n");
    }
}

int main() {
    // Initialize hash table
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }

    // Insert keys
    insert(12);
    insert(22);
    insert(32);

    // Print final table
    printTable();
    return 0;
}

int index = hashFunction(key);

Calculate hash index for the key

newNode->next = hashTable[index];

Insert new node at the head of the linked list at index

hashTable[index] = newNode;

Update head pointer to new node

while (curr != NULL) { printf("%d -> ", curr->key); curr = curr->next; }

Traverse linked list to print all keys at index

Output

[0] -> null

[1] -> null

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

[3] -> null

[4] -> null

Complexity Analysis

Time: O(1) average for insert and search because hash function gives direct index; O(n) worst if many collisions form long chains

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

vs Alternative: Compared to arrays or lists, hash tables provide faster average lookup by avoiding full scans, but need extra space for chaining

Edge Cases

Inserting keys that all hash to the same index

All keys form a linked list at one index, slowing down search to O(n)

DSA C

newNode->next = hashTable[index];

Empty hash table before any insertions

All indices point to null, no keys stored

DSA C

for (int i = 0; i < TABLE_SIZE; i++) { hashTable[i] = NULL; }

When to Use This Pattern

When you need very fast lookup or insertion by key and can accept some extra memory, use a hash table with a hash function to jump directly to data location.

Common Mistakes

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

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

Summary

Stores data using a hash function to find an index quickly.

Use when you want fast insert and search by key.

The key insight is turning keys into indices to avoid scanning all data.

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