×

Search anything:

#### Algorithms Hashing Get this book -> Problems on Array: For Interviews and Competitive Programming

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 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.

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.

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.

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 =  * 7

# Initializing the hash table
for i in range(L):
hash_table[i] = -1

hashing(hash_table, L, arr, N)
``````

Output :

700 50 85 73 101 92 76

• 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.

• 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. 