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. To fix this, you will use a method called linear probing, which looks for the next empty spot in the table.

🎯 Goal: Create a hash table with open addressing using linear probing to handle collisions. Insert keys and show the final state of the table.

📋 What You'll Learn

Create an integer array called hashTable of size 7 initialized with -1 to represent empty slots.

Create an integer variable called tableSize and set it to 7.

Write a function called linearProbingInsert that takes an integer key and inserts it into hashTable using linear probing.

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

Print the final state of hashTable showing all slots separated by spaces.

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding collision handling in hash tables is important for software engineers working on performance-critical systems and data storage solutions.

1

Create the hash table array

Create an integer array called hashTable of size 7 and initialize all elements to -1 to represent empty slots.

DSA C++

# Create the hashTable array of size 7 with all elements as -1
# Your code here

Hint

Use an array of size 7 and set each element to -1 to show it is empty.

2

Set the table size variable

Create an integer variable called tableSize and set it to 7.

DSA C++

int hashTable[7] = {-1, -1, -1, -1, -1, -1, -1};
// Create the tableSize variable and set it to 7
# Your code here

Hint

Use a simple integer variable to store the size of the hash table.

3

Write the linear probing insert function

Write a function called linearProbingInsert that takes an integer key and inserts it into hashTable using linear probing. Use tableSize for the array size. The function should find the index by key % tableSize. If the spot is taken, move to the next index until an empty spot (-1) is found.

DSA C++

int hashTable[7] = {-1, -1, -1, -1, -1, -1, -1};
int tableSize = 7;

// Write the linearProbingInsert function below
# Your code here

Hint

Use a loop to find the next empty spot if the calculated index is occupied.

4

Insert keys and print the hash table

Insert the keys 10, 20, 15, 7, and 32 into hashTable using linearProbingInsert. Then print all elements of hashTable separated by spaces on one line.

DSA C++

int hashTable[7] = {-1, -1, -1, -1, -1, -1, -1};
int tableSize = 7;

void linearProbingInsert(int key) {
    int index = key % tableSize;
    while (hashTable[index] != -1) {
        index = (index + 1) % tableSize;
    }
    hashTable[index] = key;
}

// Insert keys 10, 20, 15, 7, 32 and print the hashTable
# Your code here

Hint

Call the insert function for each key, then use a loop to print all elements separated by spaces.

Practice

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

easy

A. Rehash all elements to a new table when a collision occurs.

B. Use a linked list at each slot to store multiple elements.

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

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

Solution

1. Step 1: Understand linear probing concept

   Linear probing handles collisions by checking the next slot in order if the original slot is occupied.

2. Step 2: Compare with other methods

   Other options describe chaining or resizing, not linear probing.

3. Final Answer:

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

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 collision means resizing immediately
• Assuming random slot probing

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. (i * 2) % m

B. (i + 1) % m

C. (i - 1) % m

D. (i + 3) % m

Solution

1. Step 1: Recall linear probing formula

   Linear probing moves to the next slot by adding 1 to the current index, wrapping around using modulo.

2. Step 2: Verify modulo usage

   Modulo with table size m ensures index stays within bounds.

3. Final Answer:

   (i + 1) % m -> Option B

4. Quick Check:

   Next index = (current + 1) mod size [OK]

Hint: Next slot in linear probing is (i+1) mod table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• Not using modulo to wrap index
• Subtracting instead of adding

3. Consider a hash table of size 7 using linear probing. The hash function is h(k) = k % 7. Insert keys 10, 20, 15 in order. What is the final state of the table (index: value)?

medium

A. 0: null, 1: 15, 2: null, 3: 10, 4: null, 5: null, 6: 20

B. 0: null, 1: null, 2: 15, 3: 10, 4: 20, 5: null, 6: null

C. 0: null, 1: null, 2: 10, 3: 20, 4: 15, 5: null, 6: null

D. 0: null, 1: null, 2: 10, 3: 15, 4: 20, 5: null, 6: null

Solution

1. Step 1: Compute hashes and insert 10

   h(10) = 10 % 7 = 3, index 3 empty, insert 10 at 3.

2. Step 2: Insert 20

   h(20) = 20 % 7 = 6, index 6 empty, insert 20 at 6.

3. Step 3: Insert 15

   h(15) = 15 % 7 = 1, index 1 empty, insert 15 at 1.

4. Final Answer:

   0: null, 1: 15, 2: null, 3: 10, 4: null, 5: null, 6: 20 -> Option A

5. Quick Check:

   Positions 1:15, 3:10, 6:20 [OK]

Hint: Calculate hash, insert keys, probe next if occupied [OK]

Common Mistakes:

• Miscomputing hash values
• Not applying modulo correctly
• Placing keys at wrong indices

4. The following code snippet attempts to insert keys into a hash table using linear probing. Identify the bug:

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;
}

int main() {
  int size = 5;
  int table[5] = {-1, -1, -1, -1, -1};
  insert(table, size, 5);
  insert(table, size, 10);
  insert(table, size, 15);
  insert(table, size, 20);
  insert(table, size, 25);
  insert(table, size, 30);
  return 0;
}

medium

A. Infinite loop possible when table is full because no stop condition in while loop.

B. Hash function is incorrect; should use (key + 1) % size.

C. No bug, code works correctly for all insertions.

D. Array initialization with -1 is invalid in C++.

Solution

1. Step 1: Analyze insertion loop

   The while loop probes next index until an empty slot (-1) is found.

2. Step 2: Check for full table scenario

   If the table is full, the loop will cycle endlessly without a stop condition.

3. Step 3: Confirm other options

   Hash function is correct modulo. Array initialization with -1 is valid. So only infinite loop is the bug.

4. Final Answer:

   Infinite loop possible when table is full because no stop condition in while loop. -> Option A

5. Quick Check:

   Full table causes infinite loop in linear probing [OK]

Hint: Check if loop stops when table is full [OK]

Common Mistakes:

• Ignoring full table infinite loop
• Thinking hash function is wrong
• Assuming array init with -1 is invalid

5. You have a hash table of size 10 using linear probing. The table currently stores keys at indices: 2, 3, 4, 5, 6. You want to insert key 12 where h(k) = k % 10. If index 2 is occupied, what sequence of indices will be checked before insertion? What index will key 12 be inserted at if indices 2 to 6 are occupied but index 7 is free?

hard

A. Check indices 2, 4, 6, 8; insert at 8

B. Check indices 2, 3, 4; insert at 4

C. Check indices 2, 3, 4, 5, 6, 7; insert at 7

D. Check indices 2, 3, 4, 5, 6; insert at 2

Solution

1. Step 1: Calculate initial index for key 12

   h(12) = 12 % 10 = 2, so start checking at index 2.

2. Step 2: Apply linear probing sequence

   Since indices 2, 3, 4, 5, 6 are occupied, check next indices sequentially: 2, 3, 4, 5, 6, then 7.

3. Step 3: Find first free slot

   Index 7 is free, so insert key 12 at index 7.

4. Final Answer:

   Check indices 2, 3, 4, 5, 6, 7; insert at 7 -> Option C

5. Quick Check:

   Linear probe checks sequential slots until free [OK]

Hint: Probe sequentially until free slot found [OK]

Common Mistakes:

• Skipping indices in probing
• Inserting at first occupied slot
• Not wrapping index with modulo