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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Simple Hash Function Modulo Operation

What is the output of the following code that simulates a hash function using modulo operation on keys?

DSA C

int keys[] = {10, 22, 31, 4, 15};
int size = 10;
for (int i = 0; i < 5; i++) {
    int hash = keys[i] % size;
    printf("%d -> %d\n", keys[i], hash);
}

A

10 -> 0
22 -> 2
31 -> 3
4 -> 4
15 -> 5

B

10 -> 1
22 -> 2
31 -> 3
4 -> 4
15 -> 5

C

10 -> 0
22 -> 2
31 -> 1
4 -> 4
15 -> 5

D

10 -> 0
22 -> 1
31 -> 2
4 -> 3
15 -> 4

💡 Hint

Remember that modulo operation returns the remainder after division.

Each key is divided by the size (10), and the remainder is the hash value. For example, 10 % 10 = 0, 22 % 10 = 2, etc.

🧠 Conceptual

intermediate

Understanding Hash Collisions

Which of the following statements best describes a hash collision in a hash table?

A A key is not found in the hash table.

B Two different keys produce the same hash value.

C The hash function returns a negative number.

D The hash table is empty.

💡 Hint

Think about what happens when two keys map to the same slot.

A hash collision occurs when two distinct keys generate the same hash index, causing them to compete for the same position in the table.

❓ Predict Output

advanced

Output of Hash Function with String Keys

What is the output of this code that calculates a simple hash for strings by summing ASCII values and taking modulo?

DSA C

char* keys[] = {"abc", "bcd", "ace"};
int size = 5;
for (int i = 0; i < 3; i++) {
    int sum = 0;
    for (int j = 0; keys[i][j] != '\0'; j++) {
        sum += keys[i][j];
    }
    int hash = sum % size;
    printf("%s -> %d\n", keys[i], hash);
}

A

abc -> 1
bcd -> 3
ace -> 0

B

abc -> 3
bcd -> 0
ace -> 1

C

abc -> 4
bcd -> 2
ace -> 2

D

abc -> 2
bcd -> 4
ace -> 1

💡 Hint

Calculate ASCII sums carefully, then apply modulo 5.

Sum of ASCII values modulo table size (5): 'abc' (97+98+99=294) % 5 = 4 'bcd' (98+99+100=297) % 5 = 2 'ace' (97+99+101=297) % 5 = 2

🔧 Debug

advanced

Identify the Error in Hash Function Implementation

What error does the following hash function code produce when compiling or running?

DSA C

int hash(char* key, int size) {
    int sum = 0;
    for (int i = 0; key[i] != '\0'; i++)
        sum += key[i];
    return sum / size;
}

int main() {
    char* key = "test";
    int size = 10;
    int h = hash(key, size);
    printf("Hash: %d\n", h);
    return 0;
}

A No error; outputs hash value.

B Runtime error: division by zero if size is zero.

C Syntax error: missing braces in for loop.

D Logical error: uses division instead of modulo, wrong hash output.

💡 Hint

Check the arithmetic operation used to reduce the sum to a hash index.

The function uses division (sum / size) instead of modulo (sum % size), so the hash value is incorrect and may exceed table size.

🧠 Conceptual

expert

Choosing a Good Hash Function Property

Which property is most important for a hash function to minimize collisions in a hash table?

A Uniform distribution of hash values across the table.

B Fast computation time regardless of input size.

C Deterministic output for the same input.

D Ability to handle only numeric keys.

💡 Hint

Think about how keys spread in the hash table.

Uniform distribution ensures keys spread evenly, reducing collisions and improving performance.

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