Collision Handling Using Open Addressing Linear Probing in DSA Javascript - Build from Scratch

Collision Handling Using Open Addressing Linear Probing

📖 Scenario: Imagine you are building a simple phone book app that stores phone numbers by names. You want to store these entries in a small table. Sometimes, two names might want to go into the same spot in the table. To handle this, you will use a method called linear probing to find the next empty spot.

🎯 Goal: Build a simple hash table using an array and handle collisions using open addressing with linear probing. You will insert entries and then print the final state of the table.

📋 What You'll Learn

Create an array called hashTable with size 5 initialized with null values

Create a variable called tableSize and set it to 5

Write a function called hashFunction that takes a key (string) and returns an index using the sum of character codes modulo tableSize

Write a function called insert that inserts a key and value into hashTable using linear probing to handle collisions

Insert these entries in order: 'Alice': '123', 'Bob': '456', 'Charlie': '789', 'David': '101'

Print the final hashTable array showing each index and its stored entry or null

💡 Why This Matters

🌍 Real World

Hash tables are used in many apps like phone books, caches, and databases to store and find data quickly even when collisions happen.

💼 Career

Understanding collision handling in hash tables is important for software engineers working on efficient data storage, databases, and performance-critical applications.

1

Create the hash table array

Create an array called hashTable with size 5 and fill it with null values.

DSA Javascript

const hashTable = new Array(5).fill(null)
// Your code here

Hint

Use new Array(5).fill(null) to create an array of size 5 filled with null.

2

Create the table size variable

Create a variable called tableSize and set it to 5.

DSA Javascript

const hashTable = new Array(5).fill(null)
const tableSize = 5
// Your code here

Hint

Just create a constant tableSize and assign 5.

3

Write the hash function and insert function with linear probing

Write a function called hashFunction that takes a key string and returns the sum of its character codes modulo tableSize. Then write a function called insert that takes key and value and inserts them into hashTable using linear probing to find the next empty spot if there is a collision.

DSA Javascript

const hashTable = new Array(5).fill(null)
const tableSize = 5

// Write hashFunction and insert functions below
// Your code here

Hint

Use a loop to sum character codes in hashFunction. In insert, use a while loop to find the next empty spot by increasing index and wrapping around with modulo.

4

Insert entries and print the hash table

Use the insert function to add these entries in order: 'Alice': '123', 'Bob': '456', 'Charlie': '789', 'David': '101'. Then print the hashTable array showing each index and its stored entry or null.

DSA Javascript

const hashTable = new Array(5).fill(null)
const tableSize = 5

function hashFunction(key) {
    let sum = 0
    for (let i = 0; i < key.length; i++) {
        sum += key.charCodeAt(i)
    }
    return sum % tableSize
}

function insert(key, value) {
    let index = hashFunction(key)
    let startIndex = index
    while (hashTable[index] !== null) {
        index = (index + 1) % tableSize
        if (index === startIndex) {
            console.log('Hash table is full')
            return
        }
    }
    hashTable[index] = { key, value }
}

// Insert entries and print the hashTable
// Your code here

Hint

Call insert for each entry. Then use a for loop to print each index and its content or null.

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