Avoid collision using linear probing

Collision

While hashing, two or more key points to the same hash index under some modulo M is called as collision.

In this tutorial, we will learn how to avoid collison using linear probing technique.



Linear Probing

Calculate the hash key. key = data % size;

If hashTable[key] is empty, store the value directly. hashTable[key] = data.

If the hash index already has some value, check for next index.

key = (key+1) % size;

If the next index is available hashTable[key], store the value. Otherwise try for next index.

Do the above process till we find the space.



Linear Probing Procedure

Initial Hash Table

Hash Bucket

Insert 13

Linear Probing Example 1

insert 1

Linear Probing Example 2

Insert 6

Linear Probing Example 3

1 % 5 = 1.

6 % 5 = 1.

Both 1 and 6 points the same index under modulo 5.

So that we have placed 6 in arr[2] which is next available index.


Insert 11

Linear Probing Example 4

1 % 5 = 1.

6 % 5 = 1.

11 % 5 = 1.

Both 1, 6 and 11 points the same index under modulo 5.

So that we have placed 11 in arr[4] which is next available index.


Insert 10

Linear Probing Example 5

Insert 15

Linear Probing Example 6

15 % 5 = 0.

Hash table don't have any empty index. So, we can't insert the data.