Collision Handling Using Open Addressing Linear Probing in DSA Go - Execution Trace

Concept Flow - Collision Handling Using Open Addressing Linear Probing

Start: Insert key

↓

Compute hash index

↓

Check slot at index

↓

Place key

↓

Repeat check until empty slot found

↓

Done

When inserting a key, compute its hash index. If the slot is empty, place the key. If occupied, move to the next slot and repeat until an empty slot is found.

Execution Sample

DSA Go

hashTable := make([]int, 5)
keys := []int{7, 12, 17}
for _, key := range keys {
  index := key % 5
  for hashTable[index] != 0 {
    index = (index + 1) % 5
  }
  hashTable[index] = key
}

Insert keys 7, 12, and 17 into a hash table of size 5 using linear probing to handle collisions.

Execution Table

Step	Operation	Key	Computed Index	Slot Status	Pointer Movement	Hash Table State
1	Insert key	7	7 % 5 = 2	Slot 2 empty	Place at index 2	[0, 0, 7, 0, 0]
2	Insert key	12	12 % 5 = 2	Slot 2 occupied (7)	Move to index 3	[0, 0, 7, 0, 0]
3	Check slot	12	3	Slot 3 empty	Place at index 3	[0, 0, 7, 12, 0]
4	Insert key	17	17 % 5 = 2	Slot 2 occupied (7)	Move to index 3	[0, 0, 7, 12, 0]
5	Check slot	17	3	Slot 3 occupied (12)	Move to index 4	[0, 0, 7, 12, 0]
6	Check slot	17	4	Slot 4 empty	Place at index 4	[0, 0, 7, 12, 17]
7	End	-	-	-	-	[0, 0, 7, 12, 17]

💡 All keys inserted; no empty slots left for next keys.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	Final
hashTable	[0, 0, 0, 0, 0]	[0, 0, 7, 0, 0]	[0, 0, 7, 12, 0]	[0, 0, 7, 12, 17]	[0, 0, 7, 12, 17]
key	-	7	12	17	-
index	-	2	3	4	-

Key Moments - 3 Insights

Why do we move to the next index when the computed slot is occupied?

Because the slot at the computed index is already taken (see steps 2 and 4 in execution_table), linear probing moves sequentially to find the next empty slot.

What happens if the index reaches the end of the table?

The index wraps around to the start using modulo operation (index + 1) % size, ensuring we check all slots circularly (see pointer movement in steps 2, 5).

Why do we stop inserting when we find an empty slot?

Because the key can be safely placed there without overwriting existing keys, ensuring no data loss (see steps 1, 3, and 6 where keys are placed).

Visual Quiz - 3 Questions

Look at the execution_table, what is the hashTable state after inserting key 12?

A [0, 0, 7, 0, 0]

B [0, 0, 7, 12, 0]

C [0, 0, 0, 12, 0]

D [0, 0, 7, 12, 17]

💡 Hint

Check the hashTable State column at step 3 in execution_table.

At which step does the index wrap around to the start of the table?

A No wrap around occurs

B Step 5

C Step 2

D Step 6

💡 Hint

Look at the Pointer Movement column; index moves from 2 to 3, then 3 to 4, no modulo wrap shown.

If we insert key 22 next, at which index will it be placed?

A Index 1

B Index 2

C Index 0

D Index 4

💡 Hint

22 % 5 = 2, slots 2,3,4 occupied, so linear probing moves to next empty slot starting from 0.

Concept Snapshot

Collision Handling Using Open Addressing Linear Probing:
- Compute hash index for key.
- If slot empty, insert key.
- If occupied, move to next slot (index+1)%size.
- Repeat until empty slot found.
- Ensures all keys stored without chaining.
- Wraps around table if needed.

Full Transcript

This visualization shows how collision handling works in a hash table using open addressing with linear probing. When inserting a key, we compute its hash index. If the slot is empty, we place the key there. If the slot is occupied, we move to the next slot sequentially until we find an empty slot. This process wraps around the table if we reach the end. The example inserts keys 7, 12, and 17 into a table of size 5, showing how collisions at index 2 are resolved by moving to the next available slots. The variable tracker shows the hash table state and index changes after each insertion. Key moments clarify why we move to the next slot and how wrapping works. The quiz tests understanding of the table state after insertions, index wrapping, and next insertion placement.

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 at each slot to store multiple elements.

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

D. Replace the existing element in the slot with the new one.

Solution

1. Step 1: Understand collision handling

   When two keys hash to the same slot, a collision occurs and must be resolved.

2. Step 2: Explain linear probing method

   Linear probing resolves collisions by checking the next slot in order until an empty one is found.

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 checks next slots one by one [OK]

Common Mistakes:

• Confusing linear probing with chaining
• Thinking linear probing replaces existing elements
• Assuming table size doubles on collision

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 + 1) % m

B. (i + 3) % m

C. (i - 1) % m

D. (i * 2) % m

Solution

1. Step 1: Understand linear probing index calculation

   Linear probing moves to the next slot by adding 1 to the current index.

2. Step 2: Apply modulo to wrap around

   To stay within table bounds, use modulo with table size: (i + 1) % m.

3. Final Answer:

   (i + 1) % m -> Option A

4. Quick Check:

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

Hint: Next slot = (current index + 1) mod table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• Not using modulo causing out-of-bound errors
• Subtracting instead of adding for next slot

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

medium

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

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

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

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

Solution

1. Step 1: Calculate initial positions

   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 taken, so check index 3 (empty), insert 12. For 17, indexes 2 and 3 taken, check index 4 (empty), insert 17.

3. Final Answer:

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

4. Quick Check:

   All keys placed sequentially after collision [OK]

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

Common Mistakes:

• Placing keys at wrong indices ignoring collisions
• Not applying modulo for hash function
• Assuming keys overwrite existing ones

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

func insert(table []int, key int) {
    m := len(table)
    index := key % m
    for table[index] != -1 {
        index = (index + 1) % m
    }
    table[index] = key
}

// Initial table: [-1, -1, -1, -1, -1]
// Insert keys: 3, 8, 13

medium

A. The loop condition should check for zero instead of -1.

B. The code does not handle the case when the table is full, causing an infinite loop.

C. The initial table should be initialized with zeros, not -1.

D. The modulo operation should be done with key, not m.

Solution

1. Step 1: Analyze loop condition and termination

   The loop continues while the slot is occupied (not -1). If the table is full, the loop never ends.

2. Step 2: Identify missing full table check

   There is no check to stop after probing all slots, so infinite loop can occur if table is full.

3. Final Answer:

   The code does not handle the case when the table is full, causing an infinite loop. -> Option B

4. Quick Check:

   Missing full table check causes infinite loop [OK]

Hint: Always check for full table to avoid infinite loops [OK]

Common Mistakes:

• Ignoring full table condition
• Confusing initial empty slot value
• Misusing modulo operation

5. You have a hash table of size 7 using linear probing. The hash function is h(k) = k % 7. You insert keys 10, 20, 15, 7, 32 in this order. After these insertions, you want to insert key 24. Which index will key 24 be placed at?

hard

A. Index 3

B. Index 4

C. Index 5

D. Index 6

Solution

1. Step 1: Insert keys and find their positions

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

2. Step 2: Find position for key 24

   h(24)=3, but index 3 occupied by 10. Check next index 4 (occupied by 32), then 5 (empty), so insert at 5.

3. Final Answer:

   Index 5 -> Option C

4. Quick Check:

   Linear probe from 3 to 5 for key 24 [OK]

Hint: Probe next slots until empty found [OK]

Common Mistakes:

• Stopping at first collision without probing
• Not applying modulo for wrap-around
• Misplacing keys ignoring occupied slots