Linear Probing

Linear Probing

Linear probing is a collision resolution technique used in hash tables to handle collisions. When a collision occurs, linear probing searches for the next available slot in the hash table by incrementing the index sequentially until an empty slot is found.

Example

Let's consider a similar example with a hash function "key mod 5" and a sequence of keys: 12, 25, 37, 46, 58, 61, 72.

In this case, the table size (S) is 5, and the hash function calculates the hash value by taking the key modulo 5.

Let's follow the steps of inserting these keys into the hash table using linear probing collision resolution:

hash(12) = 12 % 5 = 2

The slot at index 2 is empty, so we insert key 12 at index 2.


hash(25) = 25 % 5 = 0

The slot at index 0 is empty, so we insert key 25 at index 0.


hash(37) = 37 % 5 = 2

The slot at index 2 is already occupied by key 12.

We increment the index by 1 and try (hash(37) + 1) % 5 = (38) % 5 = 3.

The slot at index 3 is empty, so we insert key 37 at index 3.


hash(46) = 46 % 5 = 1

The slot at index 1 is empty, so we insert key 46 at index 1.


hash(58) = 58 % 5 = 3

The slot at index 3 is already occupied by key 37.

We increment the index by 1 and try (hash(58) + 1) % 5 = (59) % 5 = 4.

The slot at index 4 is empty, so we insert key 58 at index 4.


hash(61) = 61 % 5 = 1

The slot at index 1 is already occupied by key 46.

We increment the index by 1 and try (hash(61) + 1) % 5 = (62) % 5 = 2.

The slot at index 2 is already occupied by key 12.

We increment the index by 1 and try (hash(61) + 2) % 5 = (63) % 5 = 3.

The slot at index 3 is already occupied by key 37.

We increment the index by 1 and try (hash(61) + 3) % 5 = (64) % 5 = 4.

The slot at index 4 is already occupied by key 58.

We increment the index by 1 and try (hash(61) + 4) % 5 = (65) % 5 = 0.

The slot at index 0 is empty, so we insert key 61 at index 0.


hash(72) = 72 % 5 = 2

The slot at index 2 is already occupied by key 12.

We increment the index by 1 and try (hash(72) + 1) % 5 = (73) % 5 = 3.

The slot at index 3 is already occupied by key 37.

We increment the index by