Double Probing

Double Probing

In double hashing, two hash functions are used to calculate the index for key insertion and searching in a hash table. If a collision occurs, an alternative index is calculated using the second hash function. This process continues until an empty slot is found for insertion or until the key is found during searching. It helps to distribute keys more evenly and reduce the chances of collisions.

Example

Let's consider a hash table with a length of 7 and two hash functions: hash1(key) = key % 7 and hash2(key) = 7 - (key % 7), where key is the value to be hashed.


Initially, all the slots in the hash table are empty.

hash1(73) = 73 % 7 = 3

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


hash1(96) = 96 % 7 = 5

The slot at index 5 is empty, so we insert key 96 at index 5.


hash1(40) = 40 % 7 = 5

The slot at index 5 is already occupied by key 96.

We calculate the alternative index using hash2(40) = 7 - (40 % 7) = 7 - 5 = 2.

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


hash1(10) = 10 % 7 = 3

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

We calculate the alternative index using hash2(10) = 7 - (10 % 7) = 7 - 3 = 4.

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


hash1(55) = 55 % 7 = 6

The slot at index 6 is empty, so we insert key 55 at index 6.

This is how the hash table would look after inserting the given keys using double hashing. Note that double hashing ensures that each key is inserted into a different slot and handles collisions by calculating alternative indices using the second hash function.