Collision Handling Using Open Addressing Linear Probing in DSA C - Build from Scratch

Collision Handling Using Open Addressing Linear Probing

📖 Scenario: You are building a simple hash table to store integer keys. Sometimes, two keys want to go to the same spot in the table. To fix this, you will use a method called linear probing. This means if a spot is taken, you check the next spot until you find an empty one.

🎯 Goal: Create a hash table of size 7. Insert keys using linear probing to handle collisions. Finally, print the hash table showing where each key is stored.

📋 What You'll Learn

Create an integer array called hash_table of size 7 initialized with -1 to show empty spots

Create an integer variable called table_size and set it to 7

Write a function called hash_function that returns the index by taking key modulo table_size

Write a function called linear_probing_insert that inserts a key into hash_table using linear probing

Insert the keys 10, 20, 15, 7, and 32 into the hash table using linear_probing_insert

Print the final state of hash_table showing index and stored key

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding collision handling is important for software engineers working on efficient data storage and retrieval systems.

1

Create the hash table array and table size

Create an integer array called hash_table of size 7 initialized with -1 for empty spots. Also create an integer variable called table_size and set it to 7.

DSA C

int hash_table[7] = {-1, -1, -1, -1, -1, -1, -1};
int table_size = 7;
// Your code here

Hint

Use an array of size 7 and fill all spots with -1 to show they are empty.

2

Write the hash function

Write a function called hash_function that takes an integer key and returns key % table_size.

DSA C

int hash_function(int key) {
    // Your code here
}

Hint

The hash function returns the remainder when key is divided by table_size.

3

Write the linear probing insert function

Write a function called linear_probing_insert that takes an integer key and inserts it into hash_table using linear probing. Use hash_function to find the start index. If the spot is taken (not -1), move to the next index (wrap around using modulo) until an empty spot is found.

DSA C

void linear_probing_insert(int key) {
    // Your code here
}

Hint

Keep moving to the next index until you find -1, then insert the key there.

4

Insert keys and print the hash table

Insert the keys 10, 20, 15, 7, and 32 into hash_table using linear_probing_insert. Then print the index and key stored at each position in the format: Index i: key.

DSA C

int main() {
    // Insert keys 10, 20, 15, 7, 32
    // Print the hash table
    // Your code here
    return 0;
}

Hint

Insert keys one by one and print all indices with their stored keys.