Quadratic Probing in Hashing
Last Updated :
04 Mar, 2025
Hashing is an improvement technique over the Direct Access Table. The idea is to use a hash function that converts a given phone number or any other key to a smaller number and uses the small number as the index in a table called a hash table.
Quadratic Probing
Quadratic probing is an open-addressing scheme where we look for the i2‘th slot in the i’th iteration if the given hash value x collides in the hash table. We have already discussed linear probing implementation.
How Quadratic Probing is done?
Let hash(x) be the slot index computed using the hash function.
- If the slot hash(x) % S is full, then we try (hash(x) + 1*1) % S.
- If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S.
- If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S.
- This process is repeated for all the values of i until an empty slot is found.
For example: Let us consider a simple hash function as “key mod 7” and sequence of keys as 22, 30 and 50.
Below is the implementation of the above approach:
C++
// C++ implementation of
// the Quadratic Probing
#include <bits/stdc++.h>
using namespace std;
// Function to print an array
void printArray(int arr[], int n)
{
// Iterating and printing the array
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}
// Function to implement the
// quadratic probing
void hashing(int table[], int tsize, int arr[], int n)
{
// Iterating through the array
for (int i = 0; i < n; i++) {
// Computing the hash value
int hv = arr[i] % tsize;
// Insert in the table if there
// is no collision
if (table[hv] == -1)
table[hv] = arr[i];
else {
// If there is a collision
// iterating through all
// possible quadratic values
for (int j = 1; j <= tsize; j++) {
// Computing the new hash value
int t = (hv + j * j) % tsize;
if (table[t] == -1) {
// Break the loop after
// inserting the value
// in the table
table[t] = arr[i];
break;
}
}
}
}
printArray(table, tsize);
}
// Driver code
int main()
{
int arr[] = { 50, 700, 76, 85, 92, 73, 101 };
int n = sizeof(arr)/sizeof(arr[0]);
// Size of the hash table
int tsize = 11;
int hash_table[tsize];
// Initializing the hash table
for (int i = 0; i < tsize; i++) {
hash_table[i] = -1;
}
// Function call
hashing(hash_table, tsize, arr, n);
return 0;
}
// Java implementation of the Quadratic Probing
class GFG {
// Function to print an array
static void printArray(int arr[])
{
// Iterating and printing the array
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
// Function to implement the
// quadratic probing
static void hashing(int table[], int arr[])
{
int tsize = table.length, n = arr.length;
// Iterating through the array
for (int i = 0; i < n; i++) {
// Computing the hash value
int hv = arr[i] % tsize;
// Insert in the table if there
// is no collision
if (table[hv] == -1)
table[hv] = arr[i];
else {
// If there is a collision
// iterating through all
// possible quadratic values
for (int j = 1; j <= tsize; j++) {
// Computing the new hash value
int t = (hv + j * j) % tsize;
if (table[t] == -1) {
// Break the loop after
// inserting the value
// in the table
table[t] = arr[i];
break;
}
}
}
}
printArray(table);
}
// Driver code
public static void main(String args[])
{
int arr[] = { 50, 700, 76, 85, 92, 73, 101 };
int tsize = 11;
int hash_table[] = new int[tsize];
// Initializing the hash table
for (int i = 0; i < tsize; i++) {
hash_table[i] = -1;
}
// Function call
hashing(hash_table, arr);
}
}
# Python3 implementation of
# the Quadratic Probing
# Function to print an array
def printArray(arr):
# Iterating and printing the array
for i in range(len(arr)):
print(arr[i], end=" ")
# Function to implement the
# quadratic probing
def hashing(table, arr):
# Iterating through the array
for i in range(len(arr)):
# Computing the hash value
hv = arr[i] % tsize
# Insert in the table if there
# is no collision
if (table[hv] == -1):
table[hv] = arr[i]
else:
# If there is a collision
# iterating through all
# possible quadratic values
for j in range(1, len(table)+1):
# Computing the new hash value
t = (hv + j * j) % tsize
if (table[t] == -1):
# Break the loop after
# inserting the value
# in the table
table[t] = arr[i]
break
printArray(table)
# Driver code
if __name__ == "__main__":
arr = [50, 700, 76,
85, 92, 73, 101]
# Size of the hash table
tsize = 11
hash_table = [0] * tsize
# Initializing the hash table
for i in range(tsize):
hash_table[i] = -1
# Function call
hashing(hash_table, arr)
// C# implementation of the Quadratic Probing
using System;
class GFG {
// Function to print an array
static void printArray(int[] arr)
{
// Iterating and printing the array
for (int i = 0; i < arr.Length; i++) {
Console.Write(arr[i] + " ");
}
}
// Function to implement the
// quadratic probing
static void hashing(int[] table, int tsize, int[] arr,
int N)
{
// Iterating through the array
for (int i = 0; i < N; i++) {
// Computing the hash value
int hv = arr[i] % tsize;
// Insert in the table if there
// is no collision
if (table[hv] == -1)
table[hv] = arr[i];
else {
// If there is a collision
// iterating through all
// possible quadratic values
for (int j = 1; j <= tsize; j++) {
// Computing the new hash value
int t = (hv + j * j) % tsize;
if (table[t] == -1) {
// Break the loop after
// inserting the value
// in the table
table[t] = arr[i];
break;
}
}
}
}
printArray(table);
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 50, 700, 76, 85, 92, 73, 101 };
int N = 7;
// Size of the hash table
int L = 11;
int[] hash_table = new int[L];
// Initializing the hash table
for (int i = 0; i < L; i++) {
hash_table[i] = -1;
}
// Function call
hashing(hash_table, L, arr, N);
}
}
// This code is contributed by Rajput-Ji
// Javascript implementation of the Quadratic Probing
// Function to print an array
function printArray(arr)
{
// Iterating and printing the array
for (let i = 0; i < arr.length; i++) {
console.log(arr[i] + " ");
}
}
// Function to implement the
// quadratic probing
function hashing(table, tsize,
arr, N)
{
// Iterating through the array
for (let i = 0; i < N; i++) {
// Computing the hash value
let hv = arr[i] % tsize;
// Insert in the table if there
// is no collision
if (table[hv] == -1)
table[hv] = arr[i];
else {
// If there is a collision
// iterating through all
// possible quadratic values
for (let j = 1; j <= tsize; j++) {
// Computing the new hash value
let t = (hv + j * j) % tsize;
if (table[t] == -1) {
// Break the loop after
// inserting the value
// in the table
table[t] = arr[i];
break;
}
}
}
}
printArray(table);
}
// Driver Code
let arr = [ 50, 700, 76, 85,
92, 73, 101 ];
let N = 7;
// Size of the hash table
let L = 11;
let hash_table = [];
// Initializing the hash table
for (let i = 0; i < L; i++) {
hash_table[i] = -1;
}
// Quadratic probing
hashing(hash_table, L, arr, N);
Output73 -1 101 -1 92 -1 50 700 85 -1 76
Time Complexity: O(N * L), where N is the length of the array and L is the size of the hash table.
Auxiliary Space: O(1)
The above implementation of quadratic probing does not guarantee that we will always be able to use a hast table empty slot. It might happen that some entries do not get a slot even if there is a slot available. For example consider the input array {21, 10, 32, 43, 54, 65, 87, 76} and table size 11, we get the output as {10, -1, 65, 32, 54, -1, -1, -1, 43, -1, 21} which means the items 87 and 76 never get a slot. To make sure that elements get filled, we need to have a higher table size.
A hash table can be fully utilized using the below idea.
Iterate over the hash table to next power of 2 of table size. For example if table size is 11, then iterate 16 times. And iterate over the hash table using the below formula
hash(x) = [hash(x) + (j + j*j)/2] % (Next power of 2 of table size)
Below is the implementation of this idea.
C++
// C++ implementation of
// the Quadratic Probing
#include <bits/stdc++.h>
using namespace std;
// Function to print an array
void printArray(int arr[], int n)
{
// Iterating and printing the array
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}
int nextPowerOf2(int m)
{
m--;
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
m |= m >> 32;
m++;
return m;
}
// Function to implement the
// quadratic probing
void hashing(int table[], int tsize, int arr[], int n)
{
// Iterating through the array
for (int i = 0; i < n; i++) {
// Computing the hash value
int hv = arr[i] % tsize;
// Insert in the table if there
// is no collision
if (table[hv] == -1)
table[hv] = arr[i];
else {
// If there is a collision
// iterating through all
// possible quadratic values
int m = nextPowerOf2(tsize);
for (int j = 1; j <= m; j++) {
// Computing the new hash value
int t = (hv + (j + j * j) / 2) % m;
if (table[t] == -1) {
// Break the loop after
// inserting the value
// in the table
table[t] = arr[i];
break;
}
if (t >= tsize)
continue;
}
}
}
printArray(table, tsize);
}
// Driver code
int main()
{
int arr[] = { 21, 10, 32, 43, 54, 65, 87, 76 };
int n = 8;
// Size of the hash table
int tsize = 11;
int hash_table[tsize];
// Initializing the hash table
for (int i = 0; i < tsize; i++) {
hash_table[i] = -1;
}
// Function call
hashing(hash_table, tsize, arr, n);
return 0;
}
import java.util.Arrays;
public class QuadraticProbing {
// Function to print an array
static void printArray(int arr[]) {
for (int i : arr) {
System.out.print(i + " ");
}
}
// Function to calculate the next power of 2 greater than or equal to m
static int nextPowerOf2(int m) {
m--;
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
return m + 1;
}
// Function to implement the quadratic probing
static void hashing(int table[], int tsize, int arr[], int n) {
for (int i = 0; i < n; i++) {
// Compute the hash value
int hv = arr[i] % tsize;
// Insert in the table if there is no collision
if (table[hv] == -1) {
table[hv] = arr[i];
} else {
// If there is a collision, iterate through possible quadratic values
int m = nextPowerOf2(tsize);
for (int j = 1; j <= m; j++) {
int t = (hv + (j + j * j) / 2) % m;
if (t < tsize && table[t] == -1) {
table[t] = arr[i];
break;
}
}
}
}
printArray(table);
}
// Main driver code
public static void main(String[] args) {
int arr[] = { 21, 10, 32, 43, 54, 65, 87, 76 };
int n = arr.length;
// Size of the hash table
int tsize = 11;
int hash_table[] = new int[tsize];
// Initialize the hash table
Arrays.fill(hash_table, -1);
// Call the hashing function
hashing(hash_table, tsize, arr, n);
}
}
# Function to print an array
def print_array(arr):
for i in arr:
print(i, end=" ")
# Function to calculate the next power of 2 greater than or equal to m
def next_power_of_2(m):
m -= 1
m |= m >> 1
m |= m >> 2
m |= m >> 4
m |= m >> 8
m |= m >> 16
return m + 1
# Function to implement the quadratic probing
def hashing(table, tsize, arr):
for num in arr:
# Compute the hash value
hv = num % tsize
# Insert in the table if there is no collision
if table[hv] == -1:
table[hv] = num
else:
# If there is a collision, iterate through possible quadratic values
m = next_power_of_2(tsize)
for j in range(1, m + 1):
t = (hv + (j + j * j) // 2) % m
if t < tsize and table[t] == -1:
table[t] = num
break
print_array(table)
# Main driver code
if __name__ == "__main__":
arr = [21, 10, 32, 43, 54, 65, 87, 76]
n = len(arr)
# Size of the hash table
tsize = 11
hash_table = [-1] * tsize
# Call the hashing function
hashing(hash_table, tsize, arr)
using System;
class QuadraticProbing
{
// Function to print an array
static void PrintArray(int[] arr)
{
foreach (var item in arr)
{
Console.Write(item + " ");
}
}
// Function to calculate the next power of 2 greater than or equal to m
static int NextPowerOf2(int m)
{
m--;
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
return m + 1;
}
// Function to implement the quadratic probing
static void Hashing(int[] table, int tsize, int[] arr, int n)
{
for (int i = 0; i < n; i++)
{
// Compute the hash value
int hv = arr[i] % tsize;
// Insert in the table if there is no collision
if (table[hv] == -1)
{
table[hv] = arr[i];
}
else
{
// If there is a collision, iterate through possible quadratic values
int m = NextPowerOf2(tsize);
for (int j = 1; j <= m; j++)
{
int t = (hv + (j + j * j) / 2) % m;
if (t < tsize && table[t] == -1)
{
table[t] = arr[i];
break;
}
}
}
}
PrintArray(table);
}
// Main driver code
static void Main()
{
int[] arr = { 21, 10, 32, 43, 54, 65, 87, 76 };
int n = arr.Length;
// Size of the hash table
int tsize = 11;
int[] hash_table = new int[tsize];
// Initialize the hash table
for (int i = 0; i < tsize; i++)
{
hash_table[i] = -1;
}
// Call the hashing function
Hashing(hash_table, tsize, arr, n);
}
}
// Function to print an array
function printArray(arr) {
console.log(arr.join(" "));
}
// Function to calculate the next power of 2 greater than or equal to m
function nextPowerOf2(m) {
m--;
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
return m + 1;
}
// Function to implement the quadratic probing
function hashing(table, tsize, arr) {
arr.forEach(num => {
// Compute the hash value
let hv = num % tsize;
// Insert in the table if there is no collision
if (table[hv] === -1) {
table[hv] = num;
} else {
// If there is a collision, iterate through possible quadratic values
let m = nextPowerOf2(tsize);
for (let j = 1; j <= m; j++) {
let t = (hv + (j + j * j) / 2) % m;
if (t < tsize && table[t] === -1) {
table[t] = num;
break;
}
}
}
});
printArray(table);
}
// Main driver code
let arr = [21, 10, 32, 43, 54, 65, 87, 76];
let n = arr.length;
// Size of the hash table
let tsize = 11;
let hash_table = Array(tsize).fill(-1);
// Call the hashing function
hashing(hash_table, tsize, arr);
Output10 87 -1 -1 32 -1 54 65 76 43 21
Similar Reads
Quadratic Probing in Python
Hashing is an improvement technique over the Direct Access Table. The idea is to use a hash function that converts a given phone number or any other key to a smaller number and uses the small number as the index in a table called a hash table. What is Quadratic Probing?Quadratic probing is a techniq
5 min read
Introduction to Hashing
Hashing refers to the process of generating a small sized output (that can be used as index in a table) from an input of typically large and variable size. Hashing uses mathematical formulas known as hash functions to do the transformation. This technique determines an index or location for the stor
7 min read
Robin Hood Hashing
Hashing is a technique that maps data to a fixed-size table using a hash function. The hash function takes an input (or key) and returns an index in the hash table, where the corresponding value is stored. A hash table uses this index to store the data, making it very efficient for searching and acc
7 min read
Mid-Square hashing
Mid-Square hashing is a hashing technique in which unique keys are generated. In this technique, a seed value is taken and it is squared. Then, some digits from the middle are extracted. These extracted digits form a number which is taken as the new seed. This technique can generate keys with high r
7 min read
Linear Probing in Python
Linear probing is a technique used in hash tables to handle collisions. When a collision occurs (i.e., when two keys hash to the same index), linear probing searches for the next available slot in the hash table by incrementing the index until an empty slot is found. What is Linear Probing?In linear
2 min read
Hashing in Competitive Programming
Hashing is a fundamental technique in competitive programming that is used to efficiently manipulate and process large amounts of data. Data Structures like Hash Maps and Hash Sets use hashing techniques to provide faster insertion, deletion and retrieval of values. Table of Content What is Hashing?
15+ min read
Practice Problems on Hashing
In this article, we will discuss the types of questions based on hashing. Before understanding this, you should have idea about hashing, hash function, open addressing and chaining techniques (see: Introduction, Separate chaining, Open addressing). These are some key points in hashing: The purpose o
8 min read
Hashing meaning in DSA
Hashing is defined as a data distribution technique that transforms given key into a different value using hash function for faster access to data. Characteristics of Hashing:Hashing maps the data object to exactly one memory bucket.It allows uniform distribution of keys across the memory.Uses diffe
2 min read
What is Hashing?
Hashing refers to the process of generating a fixed-size output from an input of variable size using the mathematical formulas known as hash functions. This technique determines an index or location for the storage of an item in a data structure. Need for Hash data structureThe amount of data on the
3 min read
Double Hashing in Python
Double hashing is a collision resolution technique used in hash tables. It works by using two hash functions to compute two different hash values for a given key. The first hash function is used to compute the initial hash value, and the second hash function is used to compute the step size for the
4 min read