Quadratic Probing

Quadratic Probing

Quadratic probing is a collision resolution technique used in hash tables to handle collisions. When a collision occurs, quadratic probing searches for the next available slot in the hash table by incrementing the index using a quadratic function.

The quadratic function used to increment the index during probing is typically of the form (hash(x) + c1 * i + c2 * i^2) % S, where hash(x) is the initial hash value, i is the probing step, c1 and c2 are constants, and S is the table size.

Example

Let's consider a hash table with a length of 7 and a quadratic probing function (hash(x) + i^2) % length, where length is the size of the hash table.


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


hash(76) = 76 % 7 = 6

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


hash(40) = 40 % 7 = 5

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


hash(48) = 48 % 7 = 6

The slot at index 6 is already occupied by key 76.

We increment the index by (1^2) % 7 = 1 % 7 = 1 (using the quadratic function).

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


hash(5) = 5 % 7 = 5

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

We increment the index by (1^2) % 7 = 1 % 7 = 1 (using the quadratic function).

The slot at index 6 is already occupied by key 76.

We increment the index by (2^2) % 7 = 4 % 7 = 4 (using the quadratic function).

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


hash(55) = 55 % 7 = 6

The slot at index 6 is already occupied by key 76.

We increment the index by (1^2) % 7 = 1 % 7 = 1 (using the quadratic function).

The slot at index 0 is already occupied by key 48.

We increment the index by (2^2) % 7 = 4 % 7 = 4 (using the quadratic function).

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