Hash Table Probing Technique - Quadratic Probing

Linear probing, quadratic probing, and double hashing are all subject to the issue of causing cycles, which is why probing functions used with these methods are very specific. We discussed linear probing in our last article; in this article we will cover quadratic probing.

If you would like insights on hashing and other probing techniques before starting this article, please read the following:

Hash Table - Introduction
Hash Table - Open Addressing and linear probing

Quadratic Probing

Quadratic Probing (QP) is a probing method which probes according to a quadratic formula, specifically:

P(x) = ax² + bx +c, where a, b, c are constants and a != 0 otherwise we will have linear probing.

However, not all quadratic functions are viable because they are unable to produce a cycle of order N. We need some way to handle this.

Suppose if our linear function is P(X) = 2x² + 2, H(k) = 4, and table size is 8, we end up with the following cycle occurring:

H(k) + P(0) mod N = 4
H(k) + P(1) mod N = 7
H(k) + P(2) mod N = 4
H(k) + P(3) mod N = 7
H(k) + P(4) mod N = 4
H(k) + P(5) mod N = 7
H(k) + P(6) mod N = 4
H(k) + P(7) mod N = 7

The cycle {4,7} makes it impossible to reach buckets {0,1,2,3,5,6}. This would cause an infinite loop if all the buckets {4,7} are already occupied.

There are three popular approaches to solving our problem:

Let P(x) = x², keep the table size a prime number > 3 and also α(Max load factor) <= ½.
Let P(x) = (x² + x)/2, keep the table size a power of two.
Let P(x) = (-1^x)*x², keep the table size a prime number N where N ≡ 3 mod 4.

Now let’s test one of our approaches,

Let P(x) = (x² + x)/2, keep the table size a power of two.

Here we have one empty hash table and we will go on and insert our key-value pairs (ki,vi) using QP:

Probing function: P(x) = (x² + x)/2
Table size: N = 23 = 8 (power of two)
Max load factor: α = 0.4
Threshold before resize: N * α = 3

Insert the following:

Before we insert we can see that we will exhaust our threshold, so we should resize our table, i.e, double the size to keep its power of 2. Also, copy all content from the previous table.

Table size: N = 2⁴ = 16 (power of two)
Max load factor: α = 0.4
Threshold before resize: N * α = 6

Code Implementation:

The below code uses the first approach that we listed by which we can implement QP.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;

void quadratic_hashing(vector < int > & hash_table, int table_size,
  vector < int > & kv, int N) {

  for (int i = 0; i < N; i++) {
    int hash_index = kv[i] % table_size;

    if (hash_table[hash_index] == -1)
      hash_table[hash_index] = kv[i];
    else {
      for (int j = 0; j < table_size; j++) {

        int t = (hash_index + j * j) % table_size;
        if (hash_table[t] == -1) {
          hash_table[t] = kv[i];
          break;
        }
      }
    }
  }
}

int main() {
  int n;
  cin >> n;

  vector < int > kv(n);
  for (int i = 0; i < n; i++) cin >> kv[i];

  int hash_table_size;
  cin >> hash_table_size;

  vector < int > hash_hash_table(hash_table_size, -1);

  quadratic_hashing(hash_hash_table, hash_table_size, kv, n);

  for (int i = 0; i < n; i++)
    cout << kv[i] << " ";

  return 0;
}

Input:

1
2
3
7
50 700 76 85 92 73 101
7

Output:

50 700 76 85 92 73 101

Time Complexity: O(N * TS), where N is the length of the key value and TS is the size of the hash table.

Space Complexity: O(1)