Hash Table Concept and Hash Functions in DSA C - Build from Scratch

Hash Table Concept and Hash Functions

📖 Scenario: Imagine you are organizing a small library. You want to quickly find books by their unique ID numbers. To do this, you decide to use a hash table, which helps you store and find books fast using a special function called a hash function.

🎯 Goal: You will create a simple hash table in C that stores book IDs and their titles. You will write a hash function to find the correct place to store each book. Finally, you will print the stored books to see how the hash table works.

📋 What You'll Learn

Create an array to represent the hash table with 10 slots

Write a hash function that returns the index by taking the book ID modulo 10

Store three books with given IDs and titles in the hash table

Print the contents of the hash table showing index and stored book title

💡 Why This Matters

🌍 Real World

Hash tables are used in many applications like databases, caches, and dictionaries to quickly find data using keys.

💼 Career

Understanding hash tables is important for software developers and engineers to optimize data storage and retrieval in real-world systems.

1

Create the hash table array

Create a hash table array called hashTable of size 10 that can store pointers to strings (book titles). Initialize all elements to NULL.

DSA C

# Create the hash table array with 10 slots initialized to NULL
# Your code here

Hint

Use char *hashTable[10] = {NULL}; to create an array of 10 string pointers all set to NULL.

2

Write the hash function

Write a function called hashFunction that takes an integer bookID and returns bookID % 10 as the index.

DSA C

# Write the hashFunction that returns bookID modulo 10
int hashFunction(int bookID) {
    // Your code here
}

Hint

The hash function should return the remainder when bookID is divided by 10.

3

Store books in the hash table

Store the following books in the hashTable using the hashFunction to find the index:
Book ID 21 with title "C Programming"
Book ID 32 with title "Data Structures"
Book ID 43 with title "Algorithms"

DSA C

# Store the three books in the hash table using hashFunction
// Your code here

Hint

Use the hash function to get the index and assign the book title to that index in hashTable.

4

Print the hash table contents

Add a main function that stores the books as before and then prints the index and book title for each non-NULL slot in hashTable using a for loop.

DSA C

# Print the hash table contents showing index and book title
// Your code here

Hint

Use a for loop from 0 to 9. Inside, check if hashTable[i] is not NULL. If so, print the index and the book title.

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