Skip to content
Home » Python Programs » Quadratic Probing Program in Python

Quadratic Probing Program in Python

Basic quadratic probing program in python. Hashing is a step forward from the Direct Access Table. The concept is to utilise a hash function to convert a given phone number or other key to a smaller number, which is then used as the index in a hash table. 

Hashing Function in Python

A hash function is a function that turns a large number into a little integer value. In the hash table, the mapped integer value is utilised as an index. A hash function, in simple words, converts a large number or string into a small integer that can be used as an index in a hash table. 

The collision approach, quadratic probing, is covered in this article.If the given hash value x collides in the hash table, quadratic probing is an open-addressing strategy in which we look for i2’th slot in i’th iteration.

Quadratic Probing Definition in Python

The best cache performance comes from Linear Probing, however it suffers from clustering. In terms of cache performance and clustering, quadratic probing falls somewhere in the middle. Cache performance is terrible with double caching, but there is no clustering. Here we have executed the quadratic probing program in python.

Quadratic Probing Program in Python

def printArray(arr, n):
    for i in range(n):
        print(arr[i], end = " ")
def hashing(table, tsize, arr, N):
    for i in range(N):
        hv = arr[i] % tsize
        if (table[hv] == -1):
            table[hv] = arr[i]
        else:
            for j in range(tsize):
                t = (hv + j * j) % tsize
                if (table[t] == -1):
                    table[t] = arr[i]
                    break
    printArray(table, N)
arr = [ 334, 5, 761,
        43, 922, 735, 1 ]
N = 7
L = 7
hash_table = [0] * 7
for i in range(L):
    hash_table[i] = -1
hashing(hash_table, L, arr, N)

Output:

922 43 761 1 735 334 5