Hash Table Concept and Hash Functions in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a hash table array of size 10.

DSA C

int hashTable[[1]];

Drag options to blanks, or click blank then click option'

A10

B5

C0

D100

Attempts:

3 left

💡 Hint

Common Mistakes

Using zero size array which is invalid.

Choosing a size too small like 0 or 1.

The hash table size is commonly set to 10 here for simplicity.

2fill in blank

medium

Complete the hash function to compute index using modulo operator.

DSA C

int hashFunction(int key) {
    return key [1] 10;
}

Drag options to blanks, or click blank then click option'

A*

B%

C-

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or multiplication instead of modulo.

Returning key directly without limiting index range.

Modulo operator (%) returns remainder, used to keep index within table size.

3fill in blank

hard

Fix the error in the insertion function to store value at correct index.

DSA C

void insert(int key, int value) {
    int index = hashFunction(key);
    hashTable[[1]] = value;
}

Drag options to blanks, or click blank then click option'

Akey

Bvalue

ChashTable

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using key as index which may be out of bounds.

Using value or hashTable as index which is incorrect.

We must use the computed index to store the value in the hash table.

4fill in blank

hard

Fill both blanks to complete the search function returning value or -1 if not found.

DSA C

int search(int key) {
    int index = hashFunction(key);
    if (hashTable[[1]] != [2]) {
        return hashTable[index];
    }
    return -1;
}

Drag options to blanks, or click blank then click option'

Aindex

Bkey

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with key instead of empty value.

Using wrong index or wrong empty value.

Check if the slot at 'index' is not empty (0 means empty here).

5fill in blank

hard

Fill all three blanks to complete a hash function using multiplication and modulo.

DSA C

int hashFunction(int key) {
    int hash = (key [1] 31) [2] 10;
    return hash [3] 0 ? hash : -hash;
}

Drag options to blanks, or click blank then click option'

A*

B%

C>

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of multiplication.

Using wrong comparison operator.

Not handling negative hash values.

Multiply key by 31, modulo 10, then check if hash is positive.

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