Collision handling (open addressing) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Collision handling (open addressing)

Start Insert

↓

Compute Hash Index

↓

Is Slot Empty?

No→Probe Next Slot

↓

Wrap Around if Needed

↓

Insert Key Here

↓

End Insert

When inserting, compute the hash index. If the slot is taken, check the next slot until an empty one is found, wrapping around if needed.

Execution Sample

Data Structures Theory

hash_table = [None]*5
keys = [12, 22, 32]
for key in keys:
  index = key % 5
  while hash_table[index] is not None:
    index = (index + 1) % 5
  hash_table[index] = key

Insert keys 12, 22, 32 into a hash table of size 5 using linear probing to handle collisions.

Analysis Table

Step	Key	Computed Index	Slot Empty?	Action	Hash Table State
1	12	2	Yes	Insert 12 at index 2	[None, None, 12, None, None]
2	22	2	No	Probe next index 3	[None, None, 12, None, None]
3	22	3	Yes	Insert 22 at index 3	[None, None, 12, 22, None]
4	32	2	No	Probe next index 3	[None, None, 12, 22, None]
5	32	3	No	Probe next index 4	[None, None, 12, 22, None]
6	32	4	Yes	Insert 32 at index 4	[None, None, 12, 22, 32]
7	-	-	-	All keys inserted	[None, None, 12, 22, 32]

💡 All keys inserted; no empty slots needed beyond index 4.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
hash_table	[None, None, None, None, None]	[None, None, 12, None, None]	[None, None, 12, None, None]	[None, None, 12, 22, None]	[None, None, 12, 22, None]	[None, None, 12, 22, None]	[None, None, 12, 22, 32]	[None, None, 12, 22, 32]
index	-	2	3	3	3	4	4	-

Key Insights - 3 Insights

Why do we check the next slot when the computed index is already occupied?

Because in open addressing, if the slot is taken, we must find the next available slot by probing, as shown in steps 2 and 4 in the execution_table.

What happens if we reach the end of the table while probing?

We wrap around to the start of the table and continue probing, as indicated by the modulo operation in the code and the wrap-around step in the concept_flow.

Why do we stop probing once we find an empty slot?

Because the empty slot is where we can safely insert the new key without overwriting existing data, as shown in steps 1, 3, and 6.

Visual Quiz - 3 Questions

Look at the execution_table, what is the hash_table state after inserting key 22?

A [None, None, 22, None, None]

B [None, None, 12, None, None]

C [None, None, 12, 22, None]

D [None, None, 12, None, 22]

💡 Hint

Check the hash_table state in row 3 of the execution_table after step 3.

At which step does the condition 'Slot Empty?' become false for the first time?

A Step 1

B Step 2

C Step 4

D Step 5

💡 Hint

Look at the 'Slot Empty?' column in the execution_table to find the first 'No'.

If the table size was 3 instead of 5, what would happen when inserting key 32?

A It would insert at index 0 after probing.

B It would cause an infinite loop probing slots.

C It would insert at index 2 without probing.

D It would overwrite an existing key.

💡 Hint

Consider modulo operation with table size 3 and how probing wraps around.

Concept Snapshot

Open addressing handles collisions by probing for the next empty slot.
Compute hash index: index = key % table_size.
If slot occupied, check next slot (linear probing).
Wrap around to start if end reached.
Insert key at first empty slot found.
No extra memory needed for chaining.

Full Transcript

Collision handling with open addressing means when two keys hash to the same index, we look for the next empty slot to place the new key. We start by computing the hash index using modulo operation. If the slot is empty, we insert the key there. If not, we move to the next slot, wrapping around to the start if we reach the end of the table. This process continues until an empty slot is found. The example shows inserting keys 12, 22, and 32 into a table of size 5. Key 12 goes to index 2 directly. Key 22 also hashes to 2 but finds it occupied, so it moves to index 3. Key 32 probes indexes 2 and 3, both occupied, and inserts at index 4. This method avoids linked lists and keeps all keys in the table itself.

Practice

1. What is the main idea behind open addressing in collision handling?

easy

A. Find another empty spot in the hash table when a collision occurs

B. Store collided elements in a separate linked list

C. Use multiple hash functions to avoid collisions

D. Resize the hash table immediately after a collision

Solution

1. Step 1: Understand collision handling methods

   Open addressing handles collisions by searching for another empty slot inside the hash table itself.

2. Step 2: Compare with other methods

   Unlike chaining (which uses linked lists), open addressing keeps all data inside the array by probing for free spots.

3. Final Answer:

   Find another empty spot in the hash table when a collision occurs -> Option A

4. Quick Check:

   Open addressing = find empty spot inside table [OK]

Hint: Open addressing means searching inside the table for free spots [OK]

Common Mistakes:

• Confusing open addressing with chaining
• Thinking collisions are ignored
• Assuming resizing happens immediately on collision

2. Which of the following is the correct syntax to start linear probing from index i in a hash table of size m?

easy

A. next_index = (i - 1) % m

B. next_index = (i * 2) % m

C. next_index = (i + 1) % m

D. next_index = (i + m) % 2

Solution

1. Step 1: Recall linear probing formula

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

2. Step 2: Apply modulo with table size

   To stay within the table size, use (i + 1) % m, where m is the table size.

3. Final Answer:

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

4. Quick Check:

   Linear probing = increment index by 1 modulo table size [OK]

Hint: Linear probing adds 1 and wraps with modulo table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• Incorrect modulo divisor
• Subtracting instead of adding

3. Given a hash table of size 5 and a hash function h(k) = k % 5, if keys 7, 12, and 17 are inserted using linear probing, what will be the final index of key 17?

medium

A. 3

B. 2

C. 0

D. 4

Solution

1. Step 1: Calculate initial hash indices

   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 try 3 (free). Insert 12 at 3. For 17, indices 2 and 3 are taken, try 4 (free). Insert 17 at 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Linear probing moves to next free slot: 17 at index 4 [OK]

Hint: Check initial hash, then probe next slots until free [OK]

Common Mistakes:

• Assuming all keys go to same index
• Not probing after collision
• Miscomputing modulo

4. What is the main problem with this linear probing insertion code snippet?

table = [None]*5
key = 12
index = key % 5
while table[index] is not None:
    index = (index + 1) % 5
# Missing insertion step here

medium

A. It never inserts the key into the table

B. It causes an infinite loop even if the table has empty slots

C. It uses wrong modulo operation

D. It overwrites existing keys without checking

Solution

1. Step 1: Analyze the loop behavior

   The loop finds the next free slot by incrementing index until it finds None.

2. Step 2: Check for insertion after loop

   After the loop, the code does not insert the key into the found free slot, so the key is never stored.

3. Final Answer:

   It never inserts the key into the table -> Option A

4. Quick Check:

   Missing insertion step means key not stored [OK]

Hint: Always insert key after finding free slot [OK]

Common Mistakes:

• Forgetting to insert after probing
• Ignoring full table infinite loop
• Wrong modulo usage

5. In a hash table using open addressing with linear probing, what happens if the table becomes completely full and you try to insert a new key?

hard

A. The new key overwrites the oldest key in the table

B. The insertion fails because no empty slot is available

C. The table automatically resizes and rehashes all keys

D. The insertion loops infinitely without stopping

Solution

1. Step 1: Understand open addressing limits

   Open addressing requires an empty slot to insert a new key by probing.

2. Step 2: Consider full table scenario

   If the table is full, no empty slot exists, so insertion cannot proceed and must fail or trigger resizing externally.

3. Final Answer:

   The insertion fails because no empty slot is available -> Option B

4. Quick Check:

   Full table means no free slot, insertion fails [OK]

Hint: Full table means no free slot, insertion fails [OK]

Common Mistakes:

• Assuming automatic resizing always happens
• Thinking keys get overwritten silently
• Ignoring infinite loop possibility