In this article, we will discuss about quadratic probing, a solution for hash collisions in hash tables.
What we will see,
- Hash function
- Quadratic Probing
- Quadratic Hash Function
- Procedure of Quadratic Probing
- Explained through an example
- Implementation in python
- Compared to other hash methods
HashingHashing 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 FunctionHash 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.
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 =  * 7 # Initializing the hash table for i in range(L): hash_table[i] = -1 # Quadratic probing hashing(hash_table, L, arr, N)
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.