Quadratic Probing

Quadratic probing is an open addressing scheme in computer programming for resolving the hash collisions in hash tables. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found. An example sequence using quadratic probing is:

H + 1², H + 2², H + 3², H + 4², H + 5² .... H + k²

Quadratic probing can be a more efficient and optimal algorithm in an open addressinng table, since it avoids the clustering problem that can occr with linear probing, alghtough it is not immune. It also provides good memory caching because it preserves some locality of reference; however, linear probing has greater locality and, thus, better cache performance.

Quadratic Hash Function

Let h(k) be a hash function that maps an element k to an integer in [0, m-1], where m is the size of the table.

Let the i^th probe position for a value k be given by the function,

h(k, i) = h(k) + c₁i + c₂i² (mod m)

where c₂ ≠ 0 as if c₂ = 0, then h(k, i) degrades to a linear probe.

Procedure of Quadratic Probing

Let hash(x) be the slot index computed using the hash function and m be the size of the hash table.

If the slot hash(x) % m is full, then we try (hash(x) + 1²) % m.
If (hash(x) + 1²) % m is also full, then we try (hash(x) + 2²) % m.
If (hash(x) + 2²) % m is also full, then we try (hash(x) + 3²) % m.

This process is repeated for all the values of i until an empty slot is found.

Example for Quadratic Probing

Let us take an example where the keys or the numbers given are as follows; [2, 12, 22, 32], for linear probing hash function be h₁(x) = x (mod 10), and for quadratic probing hash function be h₂(x) = x+i² (mod 10); where i is from 1, 2, 3,...

hash value of keys from h₁; [2, 2, 2, 2]
hash value of keys from h₂; [2, 3, 6, 1]

Here in the quadratic probing, for first key, h₂(2) = 2, h₂(12) = 2 when i=1, since the hash value 2 is already there the i value will get incremented by 1, thus h₂(12) becomes 3 (12 + (2)² (mod 10)) and so on h₂(22) = 6, h₂(32) = 1. Since, we can clearly see in linear probing, there is clustering while that clustering problem is resolved by doing the quadratic probing.
The clustering problem will still arise when we will try to add 42, 52, and 62, as no matter what i is, the hash value of 62 will always be already there. But before some number of duplicate hash values, quadratic probing is more efficient than linear probing.

Implementation in Python

def print_array(arr):
     
    # Unpacking and printing the array elements
    print(*arr)
     
# Function to implement the quadratic probing
def hashing(table, table_size, arr, N):
     
    # Iterating through the array
    for i in range(N):
         
        # Computing the hash value
        hash_value = arr[i] % table_size
 
        # Insert in the table if there is no collision
        if (table[hash_value] == -1):
            table[hash_value] = arr[i]
             
        else:
             
            # If there is a collision iterating through all possible quadratic values
            for j in range(table_size):
                 
                # Computing the new hash value
                new_hash = (hash_value + j * j) % table_size
                 
                if (table[new_hash] == -1):
                     
                    # Break the loop after inserting the value in the table
                    table[new_hash] = arr[i]
                    break
 
    print_array(table)
    
arr = [ 50, 700, 76, 85, 92, 73, 101 ]
N = 7
 
# Size of the hash table
L = 7
 
# Hash table bucket
hash_table = [0] * 7
 
# Initializing the hash table
for i in range(L):
    hash_table[i] = -1
     
# Quadratic probing
hashing(hash_table, L, arr, N)

Output :

700 50 85 73 101 92 76

Advantages of Quadratic Probing

It is used to resolve collisions in hash tables.
It is an open addressing scheme in computer programming.
It is more efficient for a closed hash table.

Disadvantage of Quadratic Probing

It has secondary clustering. Two keys have the same probe sequence when they hash to the same location.

Compared to other hash methods

In linear probing, when collision occurs, we linearly probe for the next bucket and we keep probing until an empty bucket is found. In quadratic probing, we probe for the i^{2 th} bucket in i^th iteration and we keep probing until an empty bucket is found. In double hashing, we use another hash function hash₂(x) and look for i * hash₂(x) bucket in i^th iteration. It requires more computation time as two hash functions need to be computed.

This concludes that linear probing has the best cache performance but suffers from clustering, quadratic probing lies between the two in terms of cache performance and clustering while double caching has poor cache performance but no clustering.

Hashing

Hash Function