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.

Practice

1. What is the main idea behind linear probing in collision handling for hash tables?

easy

A. If a collision occurs, check the next slot sequentially until an empty slot is found.

B. Use a linked list to store multiple elements at the same index.

C. Double the size of the hash table when a collision happens.

D. Rehash all elements using a new hash function when a collision occurs.

Solution

1. Step 1: Understand linear probing concept

   Linear probing handles collisions by checking the next slot in the array sequentially when the desired slot is occupied.

2. Step 2: Compare options with definition

   If a collision occurs, check the next slot sequentially until an empty slot is found. correctly describes this sequential checking. Other options describe different collision handling methods.

3. Final Answer:

   If a collision occurs, check the next slot sequentially until an empty slot is found. -> Option A

4. Quick Check:

   Linear probing = sequential slot check [OK]

Hint: Linear probing means try next slot one by one [OK]

Common Mistakes:

• Confusing linear probing with chaining
• Thinking rehashing happens on every collision
• Assuming table size doubles automatically

2. Which of the following is the correct way to calculate the next index in linear probing for a hash table of size m when current index is i?

easy

A. next_index = (i + 3) % m

B. next_index = (i * 2) % m

C. next_index = (i - 1) % m

D. next_index = (i + 1) % m

Solution

1. Step 1: Recall linear probing formula

   Linear probing moves to the next slot by adding 1 to the current index and taking modulo with table size.

2. Step 2: Match formula with options

   next_index = (i + 1) % m matches this formula: (i + 1) % m. Other options use incorrect increments.

3. Final Answer:

   next_index = (i + 1) % m -> Option D

4. Quick Check:

   Linear probing next index = (i + 1) mod m [OK]

Hint: Linear probing adds 1 to index modulo table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• Subtracting instead of adding
• Adding a number other than 1

3. Consider a hash table of size 5 using linear probing. The hash function is h(k) = k % 5. Insert keys 7, 12, 17 in order. What is the final state of the table?

medium

A. [7, 12, 17, null, null]

B. [7, null, 12, 17, null]

C. [null, null, 7, 12, 17]

D. [null, 7, 12, 17, null]

Solution

1. Step 1: Calculate initial positions using hash function

   h(7) = 7 % 5 = 2, h(12) = 12 % 5 = 2, h(17) = 17 % 5 = 2.

2. Step 2: Insert keys using linear probing

   Insert 7 at index 2. For 12, index 2 is occupied, so try index 3. Insert 12 at index 3. For 17, indices 2 and 3 are occupied, so insert at index 4.

3. Final Answer:

   [null, null, 7, 12, 17] -> Option C

4. Quick Check:

   Keys placed at 2, 3, 4 sequentially [OK]

Hint: Check hash index, then next slots if occupied [OK]

Common Mistakes:

• Placing all keys at same index ignoring collisions
• Not wrapping around table size
• Misplacing keys at wrong indices

4. The following code snippet tries to insert keys into a hash table using linear probing. What is the error?

int hash(int key, int size) { return key % size; }
void insert(int table[], int size, int key) {
  int index = hash(key, size);
  while (table[index] != -1) {
    index = (index + 1) % size;
  }
  table[index] = key;
}

medium

A. The index update should subtract 1 instead of adding 1.

B. The table is not initialized with -1 for empty slots.

C. The while loop condition should check for table[index] == -1.

D. The hash function should use multiplication instead of modulo.

Solution

1. Step 1: Analyze the insert function logic

   The function checks for empty slots by comparing with -1, so the table must be initialized with -1 to mark empty slots.

2. Step 2: Identify missing initialization

   If the table is not initialized with -1, the condition table[index] != -1 may fail incorrectly, causing wrong insertions or infinite loops.

3. Final Answer:

   The table is not initialized with -1 for empty slots. -> Option B

4. Quick Check:

   Empty slots must be marked -1 [OK]

Hint: Initialize table slots with -1 before insertion [OK]

Common Mistakes:

• Ignoring table initialization
• Wrong loop condition in while
• Incorrect hash function usage

5. You have a hash table of size 7 using linear probing. Insert keys 10, 20, 15, 7, 32 in order using hash function h(k) = k % 7. After all insertions, what is the content of the table?

hard

A. [7, 15, null, 10, 32, null, 20]

B. [null, 15, 32, 10, null, 20, 7]

C. [null, 15, 32, 10, 20, 7, null]

D. [null, 15, 32, 10, 20, null, 7]

Solution

1. Step 1: Calculate initial indices for each key

   h(10)=3, h(20)=6, h(15)=1, h(7)=0, h(32)=4.

2. Step 2: Insert keys using linear probing

   Insert 10 at index 3. Insert 20 at index 6. Insert 15 at index 1. Insert 7 at index 0. Insert 32 at index 4 (empty). Final table: [7, 15, null, 10, 32, null, 20].

3. Step 3: Match with options

   [7, 15, null, 10, 32, null, 20] matches the correct order. Nulls at indices 2 and 5.

4. Final Answer:

   [7, 15, null, 10, 32, null, 20] -> Option A

5. Quick Check:

   Keys placed at their hash or next free slot [OK]

Hint: Calculate hash, insert or probe next free slot [OK]

Common Mistakes:

• Not probing when slot is occupied
• Misplacing keys at wrong indices
• Ignoring table size wrap-around