Quadratic Probing

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we will discuss about quadratic probing, a solution for hash collisions in hash tables.

What we will see,

Hashing

Hashing is an improvement over Direct Access Table. The idea is to use a hash function that converts a given key number to a smaller number and uses the small number as the index in a table called a hash table.

Hash Function

Hash function is a function that converts a given big number to a small practical integer value. The mapped integer value is used as an index in the hash table. In simple terms, a hash function maps a large string or big number to a small integer that can be used as an index in the hash table.

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 + 12, H + 22, H + 32, H + 42, H + 52 .... H + k2

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 ith probe position for a value k be given by the function,

h(k, i) = h(k) + c1i + c2i2 (mod m)

where c2 ≠ 0 as if c2 = 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) + 12) % m.
  • If (hash(x) + 12) % m is also full, then we try (hash(x) + 22) % m.
  • If (hash(x) + 22) % m is also full, then we try (hash(x) + 32) % 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 h1(x) = x (mod 10), and for quadratic probing hash function be h2(x) = x+i2 (mod 10); where i is from 1, 2, 3,...

  • hash value of keys from h1; [2, 2, 2, 2]
  • hash value of keys from h2; [2, 3, 6, 1]

Here in the quadratic probing, for first key, h2(2) = 2, h2(12) = 2 when i=1, since the hash value 2 is already there the i value will get incremented by 1, thus h2(12) becomes 3 (12 + (2)2 (mod 10)) and so on h2(22) = 6, h2(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 i2 th bucket in ith iteration and we keep probing until an empty bucket is found. In double hashing, we use another hash function hash2(x) and look for i * hash2(x) bucket in ith 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.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.