Collision Handling Using Open Addressing Linear Probing in DSA Javascript

Mental Model

When two items want the same spot in a table, we look for the next empty spot in a line.

Analogy: Imagine parking cars in a row of parking spots. If your favorite spot is taken, you move forward to the next empty spot until you find one.

Table: [0] null -> [1] null -> [2] null -> [3] null -> [4] null
Hash function: key % 5
Insert 7: goes to index 2
Insert 12: index 2 taken, try 3
Insert 17: index 2 and 3 taken, try 4

Dry Run Walkthrough

Input: Insert keys 7, 12, 17 into a hash table of size 5 using linear probing

Goal: Place all keys in the table without overwriting existing keys by finding next free spot

Step 1: Insert 7 at index 7 % 5 = 2

[0] null -> [1] null -> [2] 7 -> [3] null -> [4] null

Why: Index 2 is free, so place 7 there

Step 2: Insert 12 at index 12 % 5 = 2, but index 2 is taken, try next index 3

[0] null -> [1] null -> [2] 7 -> [3] 12 -> [4] null

Why: Index 2 is occupied, so move to next index 3 which is free

Step 3: Insert 17 at index 17 % 5 = 2, indexes 2 and 3 taken, try next index 4

[0] null -> [1] null -> [2] 7 -> [3] 12 -> [4] 17

Why: Indexes 2 and 3 are occupied, so move to next free index 4

Result:

[0] null -> [1] null -> [2] 7 -> [3] 12 -> [4] 17

Annotated Code

DSA Javascript

class HashTable {
  constructor(size) {
    this.size = size;
    this.table = new Array(size).fill(null);
  }

  hash(key) {
    return key % this.size;
  }

  insert(key) {
    let index = this.hash(key);
    // linear probing to find empty slot
    while (this.table[index] !== null) {
      index = (index + 1) % this.size; // move to next index
    }
    this.table[index] = key;
  }

  print() {
    let result = '';
    for (let i = 0; i < this.size; i++) {
      result += `[${i}] ${this.table[i] === null ? 'null' : this.table[i]}`;
      if (i !== this.size - 1) result += ' -> ';
    }
    console.log(result);
  }
}

// Driver code
const ht = new HashTable(5);
ht.insert(7);  // goes to index 2
ht.insert(12); // collision at 2, goes to 3
ht.insert(17); // collision at 2 and 3, goes to 4
ht.print();

while (this.table[index] !== null) {

check if current index is occupied to handle collision

index = (index + 1) % this.size;

move to next index in circular manner for linear probing

this.table[index] = key;

insert key at found empty index

Output

[0] null -> [1] null -> [2] 7 -> [3] 12 -> [4] 17

Complexity Analysis

Time: O(n) in worst case because we may check many slots if collisions happen

Space: O(n) because we store keys in an array of size n

vs Alternative: Compared to chaining which uses linked lists, linear probing uses only the array but can have clustering causing slower insert/search

Edge Cases

Inserting into a full table

The insert loops infinitely or fails because no empty slot is found

DSA Javascript

while (this.table[index] !== null) {

Inserting duplicate keys

Duplicates are inserted in next available slot without checking for duplicates

DSA Javascript

while (this.table[index] !== null) {

Empty table insertion

Key is inserted directly at hashed index without probing

DSA Javascript

if (this.table[index] === null) this.table[index] = key;

When to Use This Pattern

When you see a hash table with collisions and need to store items in the same array without extra structures, use linear probing to find next free slot.

Common Mistakes

Mistake: Not wrapping index back to start of array causing out-of-bounds error
Fix: Use modulo operation to wrap index: index = (index + 1) % size

Mistake: Not checking if slot is occupied before inserting causing overwrite
Fix: Check if slot is null before inserting, else move to next slot

Summary

It handles collisions by moving forward to the next empty slot in the array.

Use it when you want to store keys in a fixed-size array without extra linked lists.

The key insight is to keep probing linearly until you find a free spot to insert.

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 values.

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

D. Replace the existing value in the slot with the new value.

Solution

1. Step 1: Understand collision handling methods

   Linear probing handles collisions by searching the next available slot in a sequence.

2. Step 2: Identify linear probing behavior

   When a collision happens, linear probing checks the next slot one by one until it finds an empty slot.

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 collision means resizing immediately
• Replacing existing values instead of 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 + 3) % m

D. (i + 1) % m

Solution

1. Step 1: Recall linear probing index update

   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 size, use modulo operation with table size m.

3. Final Answer:

   (i + 1) % m -> Option D

4. Quick Check:

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

Hint: Next index 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 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 (index: value)?

medium

A. 0: null, 1: null, 2: 7, 3: 12, 4: 17

B. 0: null, 1: 7, 2: null, 3: 12, 4: 17

C. 0: 7, 1: 12, 2: 17, 3: null, 4: null

D. 0: null, 1: 7, 2: 12, 3: 17, 4: null

Solution

1. Step 1: Calculate initial positions using hash function

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2. All keys initially map to index 2.

2. Step 2: Insert keys using linear probing

   Insert 7 at index 2 (empty). Insert 12: index 2 occupied, try 3 (empty), insert at 3. Insert 17: index 2 occupied, 3 occupied, try 4 (empty), insert at 4.

3. Final Answer:

   0: null, 1: null, 2: 7, 3: 12, 4: 17 -> Option A

4. Quick Check:

   Keys placed at 2, 3, 4 with probing [OK]

Hint: All keys hash to 2, probe next slots for empty [OK]

Common Mistakes:

• Placing all keys at index 2 ignoring collisions
• Skipping slots incorrectly during probing
• Miscomputing hash values

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

const size = 7;
const table = new Array(size).fill(null);
function hash(key) {
  return key % size;
}
function insert(key) {
  let index = hash(key);
  while (table[index] !== null) {
    index = (index + 1) % size;
  }
  table[index] = key;
}
insert(10);
insert(17);
insert(24);
console.log(table);

medium

A. The hash function should use key % (size - 1) instead of key % size.

B. The table array should be initialized with zeros instead of null.

C. The insert function does not handle the case when the table is full, causing an infinite loop.

D. The index update in the while loop should subtract 1 instead of adding 1.

Solution

1. Step 1: Analyze insert function loop

   The while loop probes next slots until it finds an empty slot (null).

2. Step 2: Identify missing full table check

   If the table is full, the loop cycles endlessly without exit condition, causing infinite loop.

3. Final Answer:

   The insert function does not handle the case when the table is full, causing an infinite loop. -> Option C

4. Quick Check:

   Missing full table check causes infinite loop [OK]

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

Common Mistakes:

• Thinking modulo should be size-1
• Ignoring infinite loop possibility
• Confusing null with zero initialization

5. You have a hash table of size 10 using linear probing. The table currently stores keys at indices: 2, 3, 4, 5. You want to insert key 22. The hash function is h(k) = k % 10. Which index will key 22 be inserted into?

hard

A. 2

B. 6

C. 7

D. 5

Solution

1. Step 1: Calculate initial index for key 22

   22 % 10 = 2, so initial index is 2.

2. Step 2: Apply linear probing to find empty slot

   Indices 2, 3, 4, 5 are occupied. Next index is 6, which is free.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Start at 2, probe until free slot at 6 [OK]

Hint: Probe forward from hash index until empty slot found [OK]

Common Mistakes:

• Inserting at first hashed index ignoring occupancy
• Stopping probing too early
• Choosing wrong next index