Quadratic Probing

Problem Statement

Given a hash function, Quadratic probing is used to find the correct index of the element in the hash table. To eliminate the Primary clustering problem in Linear probing, Quadratic probing in data structure uses a Quadratic polynomial hash function to resolve the collisions in the hash table.

Example

Let there a table of size = 10 with slot position index i=0, 1, 2, 3, 4, 5 ,6 ,7,8,9 as shown below.

Let the sequence of keys = 9 ,19 ,29 ,39 ,49 ,59,71 These keys are to be inserted into the hash table.

The hash function for indexing, $H = K mod 10$, where k = key value.

If quadratic probing is used for collision resolution then find the positions of each of the key elements in the hash table.

After collision Resolution the final positions of the element in the hash table will look like this:

Let's understand how the positions of these keys are calculated and quadratic probing is used to resolve collision in the next section.

Example Explanation

Let's understand for each key how its index is calculated in the Hash table.

The hash function for indexing is $H(K)= K mod 10$. While inserting an element in the hash table if the index position in the hash table is already occupied then the collision is resolved by the quadratic hash function as :

$hi(K) = ( H(K) + i^2)$ % $10$

where $hi(K)$ is the next index for the key K. i is the collision number. For first collision i=1, For second collision i=2, For third collision, i=3, and so on. This is calculated until a space is assigned to the key element in the hash table.

Let's find the index value of each element in the sequence of key = 9, 19, 29,39, 49, 59,71

• K=9

the hash value can be calculated for this key by the hash function $H(K)= K mod 10$. $H(9) = 9$ % $10 = 9$ (available)

so, k=9 is inserted at index 9 in the hash table. as shown below

• K=19

the hash value can be calculated for this key by the hash function $H(K)= K mod 10$.

$H(19) = 19$ % $10 =9$ (First collision) As index 9 is already occupied by key = 9 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10$ (i=1 for first collision)

$h1(19) =( H(19) + 1*1 )$%$10$ $= (9 +1)$%$10 = 0$ (this index position is available in the hash table) So, K=19 is inserted at index 0 in the hash table as shown below

• K=29

the hash value can be calculated for this key by the hash function $H(K)= K mod 10$.

$H(29)=29$ % $10 = 9$(First collision)

As index 9 is already occupied by key = 9 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10$ (i=1 for first collision)

$h1(29) = ( H(29) + 1*1 )$%$10$ = $(9 +1)$%$10 = 0$ (Second collision) As index 0 is already occupied by key = 19 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10 =2$ (i=2 for second collision)

$h2(29) = (H(29) + 2*2)$ %$10 = (9+4)$%$10 = 3$ (available)

So, K=29 is inserted at index 3the in the hash table.

• K= 3the 9

the hash value can be calculated for this key by the hash function $H(K)= K mod 10$.

$H(39) = 39$ % $10 =9$(First collison)

As index 9 is already occupied by key = 9 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10$ (i=1 for first collision)

$h1(39) = ( H(39) + 1*1 )$%$10 = (9 +1)$%$10 = 0$(Second collision) As index 0 is already occupied by key = 19 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10 =2$ (i=2 for second collision)

$h2(39) = (H(39) + 2*2)=3$ (Third collision)

As index 3 is already occupied by key = 29 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10 =2$ (i=3 for third collision)

$h3(39) = (H(39) + 3*3)$ %$10 = (9+9)$%$10 = 8$(available)

So, K=39 is inserted at index 8 in the hash table

• K= the 49 the hash value can be calculated for this key by the hash function $H(K)= K mod 10$.

$H(49) = 49$ % $10 =9$(First collison)

As index 9 is already occupied by key = 9 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10$ (i=1 for first collision)

$h1(49) = ( H(49) + 1*1 )$%$10 = (9 +1)$%$10 = 0$(Second collision)

As index 0 is already occupied by key = 19 so next index is calculated by quadratic hash function $i(K) = ( H(K) + i^2)$ % $10 =2$ (i=2 for second collision)

$h2(49) = (H(49) + 2*2)=3$ (Third collision)

As index 3 is already occupied by key = 29 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10$ (i=3 for third collision)

$h3(49) = (H(49) + 3*3)$ %$10 = (9+9)$%$10 = 8$(Fourth collsion)

As index 8 is already occupied by key = 39 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10$ (i=4 for fourth collision)

$h4(49) = (H(49)+4*4)$%$10 = (9+16)$%$10 =5$ (available)

So,K=49 is inserted at index 5 in the hash table

• K=59

the hash value can be calculated for this key by the hash function $H(K)= K mod 10$.

$H(59) = 59$ % $10 =9$(First collison)

As index 9 is already occupied by key = 9 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10$ (i=1 for first collision)

$h1(59) = ( H(59) + 1*1 )$%$10 = (9 +1)$%$10 = 0$(Second collision)

As index 0 is already occupied by key = 19 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10 =2$ (i=2 for second collision)

$h2(59) = (H(59) + 2*2)=3$ (Third collision)

As index 3 is already occupied by key = 29 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10$ (i=3 for third collision)

$h3(59) = (H(59) + 3*3)$ %$10 = (9+9)$%$10 = 8$(Fourth collsion)

As index 8 is already occupied by key = 39 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10$ (i=4 for fourth collision)

$h4(59) = (H(59)+4*4)$%$10 = (9+16)$%$10 =5$ (Fifth collsion)

As index 5 is already occupied by key = 49 so next index is calculated by quadratic hash function $hi(K) = ( H(K) + i^2)$ % $10$ (i=5 for fourth collision)

$h5(59) = (H(59)+5*5)$%$10 = (9+25)$%$10 = 4$ (available)

So, K=59 is inserted at index 4 in the hash table

• K=71 $H(71)= 71$ % $10 =1$ (available)(No collision) So, K=71 is inserted at index 1the the in hash table

The final Key allocation in the hash table is

Constraints

The only constraint is number of Keys should be less than the hash table size.

For example, if the number of keys = 8 and Size of hash table = 5

After filling in the 5 positions in the hash table the collision problem for the rest of the 3 elements will never be resolved so the collisions will never be resolved.

How Quadratic Probing is Done?

While allocating the position to the element or key in the hash table firstly the index position is calculated using the hash function $H(K) = K$ % $S$ where , S = size of hash table

Now, if the slot calculated by the hash function H(k) is full then a collision occurs and the collision is resolved by $( H(K) + 1*1 )$%$S$ for the first collision.

If slot calculted by $( H(K) + 1*1 )$%$S$ is also full then again collsion is resolved by $(H(K) + 2 * 2)$%$S$ for second collsion.

If the slot calculated by $( H(K) + 2*2 )$%$S$ is also full then again collision is resolved by $( H(K) + 3 * 3 )$%$S$ for the third collision.

This process of resolving collision is continued until a vacant slot is calculated for the key.

Approach

Algorithm :

• Iterate over the given array of key
• Calculate the hash value with the help of the hash function.
• If there is no collision then insert the key at that hash value index in the hash table.
• If there is a collision iterate through all possible quadratic values.
• Compute the new hash value using the Quadratic hash function.
• Insert the key if the empty slot is found else again calculate the hash value with the quadratic hash function.

Implementation in C++:

Implementation in Java:

Implementation in Python:

• Output for the program will be:

• Time complexity of Quadratic probing algorithm :

The time complexity of the quadratic probing algorithm will be $O(N * S)$. where N is the number of keys to be inserted and S is the size of the hash table.

Best case - when there are no collisions in the insertion of all the keys in the hash table then all the elements will be inserted in one single insertion.

Worst Case - In worst case occurs when there is collision in insertion of every other element after the first element is inserted then for each of the other element the hash value for quadratic probing need to be calculated each time collision occurs.

• Space Complexity :

The space complexity of the quadratic probing algorithm will be $O(1)$ as no extra space is being used in the algorithm.

In both best case and worst case no extra space is required other than the hash table which is already given in the problem requirement so the space complexity remains $O(1)$ in both best abd worst case.

Learn More

You can learn more about hashing in data structure before understanding quadratic probing in data structure refer to this article

• Hashing in data structure