How Quadratic Probing is Done
Understanding how Quadratic Probing is done is key to grasping its efficiency in collision resolution in hash tables. It's like finding a parking spot in a crowded lot; if your usual spot is taken, you try the next one a little further away, then maybe one further still, but in a predictable pattern. Here's the step-by-step breakdown.
Initial Hash Calculation
First, we calculate the initial hash of the item (let's call this hash_value). This is often done using a simple modulo operation with the hash table size. Think of this as your first choice for a parking spot.
Collision Detection
We check the slot at hash_value. If it's empty, great! We insert the item there. If not, it means there's a collision, just like if your parking spot was already taken.
Quadratic Probing
This is where Quadratic Probing comes into play. We don't just move to the next slot. Instead, we add a quadratic function of the number of tries to the original hash_value. So, for the 1st collision, we check hash_value + 1^2, for the 2nd, hash_value + 2^2, and so on.
Finding a Free Slot
We repeat step 3 until we find an empty slot or realize the table is full (like circling the parking lot until you find a spot or realize it's completely full).
Insertion
Once a free slot is found, the item is inserted into that slot.
This method ensures that we spread out the items evenly across the hash table, reducing the likelihood of clustering and thus maintaining efficient access times.
It's important to note that the size of the hash table should be chosen carefully to ensure that it can accommodate the quadratic probing sequence without too many overlaps, much like a parking lot needs to be big enough to handle the cars coming in at peak times.
For a more practical understanding, let's go through a coding example that demonstrates the execution of Quadratic Probing when handling collisions in a hash table. We'll extend our previous Python example to include a method for searching elements, which will also utilize Quadratic Probing.
- Python
- C++
- C#
- JavaScript
- Java
Python
class QuadraticProbingHashTable:
def __init__(self, capacity=10):
self.capacity = capacity
self.table = [None] * self.capacity
self.size = 0
def hash(self, key):
return key % self.capacity
def quadratic_probe_for_insert(self, key):
original_hash = self.hash(key)
hash_value = original_hash
i = 1
while self.table[hash_value] is not None:
hash_value = (original_hash + i ** 2) % self.capacity
i += 1
if i > self.capacity:
raise Exception("Hash table is full")
return hash_value
def quadratic_probe_for_search(self, key):
original_hash = self.hash(key)
hash_value = original_hash
i = 1
while self.table[hash_value] is not None and self.table[hash_value] != key:
hash_value = (original_hash + i ** 2) % self.capacity
i += 1
if i > self.capacity:
return None
return hash_value if self.table[hash_value] == key else None
def insert(self, key):
if self.size == self.capacity:
raise Exception("Hash table is full")
hash_value = self.quadratic_probe_for_insert(key)
self.table[hash_value] = key
self.size += 1
print(f"Inserted {key} at index {hash_value}")
def search(self, key):
hash_value = self.quadratic_probe_for_search(key)
if hash_value is not None:
print(f"{key} found at index {hash_value}")
else:
print(f"{key} not found in the hash table")
# Example usage
hash_table = QuadraticProbingHashTable(10)
hash_table.insert(23)
hash_table.insert(33)
hash_table.insert(43)
hash_table.search(33)
hash_table.search(44)

You can also try this code with Online Python Compiler
Run Code
C++
#include <iostream>
#include <vector>
using namespace std;
class QuadraticProbingHashTable {
private:
vector<int> table;
int capacity;
int size;
int hash(int key) {
return key % capacity;
}
int quadraticProbeForInsert(int key) {
int originalHash = hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue] != -1) {
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) throw runtime_error("Hash table is full");
}
return hashValue;
}
int quadraticProbeForSearch(int key) {
int originalHash = hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue] != -1 && table[hashValue] != key) {
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) return -1;
}
return table[hashValue] == key ? hashValue : -1;
}
public:
QuadraticProbingHashTable(int cap) : capacity(cap), size(0), table(cap, -1) {}
void insert(int key) {
if (size == capacity) throw runtime_error("Hash table is full");
int hashValue = quadraticProbeForInsert(key);
table[hashValue] = key;
size++;
cout << "Inserted " << key << " at index " << hashValue << endl;
}
void search(int key) {
int hashValue = quadraticProbeForSearch(key);
if (hashValue != -1) {
cout << key << " found at index " << hashValue << endl;
} else {
cout << key << " not found in the hash table" << endl;
}
}
};
// Example usage
int main() {
QuadraticProbingHashTable hashTable(10);
hashTable.insert(23);
hashTable.insert(33);
hashTable.insert(43);
hashTable.search(33);
hashTable.search(44);
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
C#
using System;
public class QuadraticProbingHashTable
{
private int?[] table;
private int capacity;
private int size;
public QuadraticProbingHashTable(int capacity = 10)
{
this.capacity = capacity;
table = new int?[capacity];
size = 0;
}
private int Hash(int key)
{
return key % capacity;
}
private int QuadraticProbeForInsert(int key)
{
int originalHash = Hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue].HasValue)
{
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) throw new Exception("Hash table is full");
}
return hashValue;
}
private int? QuadraticProbeForSearch(int key)
{
int originalHash = Hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue].HasValue && table[hashValue] != key)
{
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) return null;
}
return table[hashValue] == key ? hashValue : (int?)null;
}
public void Insert(int key)
{
if (size == capacity) throw new Exception("Hash table is full");
int hashValue = QuadraticProbeForInsert(key);
table[hashValue] = key;
size++;
Console.WriteLine($"Inserted {key} at index {hashValue}");
}
public void Search(int key)
{
int? hashValue = QuadraticProbeForSearch(key);
if (hashValue.HasValue)
{
Console.WriteLine($"{key} found at index {hashValue}");
}
else
{
Console.WriteLine($"{key} not found in the hash table");
}
}
}
// Example usage
public class Program
{
public static void Main()
{
QuadraticProbingHashTable hashTable = new QuadraticProbingHashTable(10);
hashTable.Insert(23);
hashTable.Insert(33);
hashTable.Insert(43);
hashTable.Search(33);
hashTable.Search(44);
}
}
JavaScript
class QuadraticProbingHashTable {
constructor(capacity = 10) {
this.capacity = capacity;
this.table = Array(this.capacity).fill(null);
this.size = 0;
}
hash(key) {
return key % this.capacity;
}
quadraticProbeForInsert(key) {
const originalHash = this.hash(key);
let hashValue = originalHash;
let i = 1;
while (this.table[hashValue] !== null) {
hashValue = (originalHash + i ** 2) % this.capacity;
i++;
if (i > this.capacity) throw new Error("Hash table is full");
}
return hashValue;
}
quadraticProbeForSearch(key) {
const originalHash = this.hash(key);
let hashValue = originalHash;
let i = 1;
while (this.table[hashValue] !== null && this.table[hashValue] !== key) {
hashValue = (originalHash + i ** 2) % this.capacity;
i++;
if (i > this.capacity) return null;
}
return this.table[hashValue] === key ? hashValue : null;
}
insert(key) {
if (this.size === this.capacity) throw new Error("Hash table is full");
const hashValue = this.quadraticProbeForInsert(key);
this.table[hashValue] = key;
this.size++;
console.log(`Inserted ${key} at index ${hashValue}`);
}
search(key) {
const hashValue = this.quadraticProbeForSearch(key);
if (hashValue !== null) {
console.log(`${key} found at index ${hashValue}`);
} else {
console.log(`${key} not found in the hash table`);
}
}
}
// Example usage
const hashTable = new QuadraticProbingHashTable(10);
hashTable.insert(23);
hashTable.insert(33);
hashTable.insert(43);
hashTable.search(33);
hashTable.search(44);

You can also try this code with Online Javascript Compiler
Run Code
Java
public class QuadraticProbingHashTable {
private Integer[] table;
private int capacity;
private int size;
public QuadraticProbingHashTable(int capacity) {
this.capacity = capacity;
this.table = new Integer[capacity];
this.size = 0;
}
private int hash(int key) {
return key % capacity;
}
private int quadraticProbeForInsert(int key) {
int originalHash = hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue] != null) {
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) throw new RuntimeException("Hash table is full");
}
return hashValue;
}
private Integer quadraticProbeForSearch(int key) {
int originalHash = hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue] != null && !table[hashValue].equals(key)) {
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) return null;
}
return table[hashValue] != null && table[hashValue].equals(key) ? hashValue : null;
}
public void insert(int key) {
if (size == capacity) throw new RuntimeException("Hash table is full");
int hashValue = quadraticProbeForInsert(key);
table[hashValue] = key;
size++;
System.out.println("Inserted " + key + " at index " + hashValue);
}
public void search(int key) {
Integer hashValue = quadraticProbeForSearch(key);
if (hashValue != null) {
System.out.println(key + " found at index " + hashValue);
} else {
System.out.println(key + " not found in the hash table");
}
}
public static void main(String[] args) {
QuadraticProbingHashTable hashTable = new QuadraticProbingHashTable(10);
hashTable.insert(23);
hashTable.insert(33);
hashTable.insert(43);
hashTable.search(33);
hashTable.search(44);
}
}

You can also try this code with Online Java Compiler
Run Code
Output
Inserted 23 at index 3
Inserted 33 at index 4
Inserted 43 at index 7
33 found at index 4
44 not found in the hash table
Explanation
In this example:
- The quadratic_probe_for_insert method is used for finding a free slot for insertion using Quadratic Probing.
- The quadratic_probe_for_search method utilizes Quadratic Probing to search for an existing key in the hash table.
- The insert method inserts a key using Quadratic Probing to resolve collisions.
- The search method searches for a key in the hash table, again using Quadratic Probing to navigate through potential collisions.
This code provides a basic framework to understand how Quadratic Probing can be implemented for both inserting and searching keys in a hash table, demonstrating its utility in managing collisions effectively.
Time & Space Complexity of Quadratic Probing
When it comes to understanding any data structure or algorithm, knowing about its time & space complexity is crucial. It's like assessing how much time & room a task will take up. For Quadratic Probing in hash tables, these complexities tell us how efficient the method is under different scenarios.
Time Complexity
The time complexity of operations in a hash table using Quadratic Probing, such as insertion, deletion, & search, can vary. Ideally, when the hash table is sparse & collisions are few, these operations can be incredibly swift, nearly O(1), meaning they take a constant amount of time regardless of the number of items in the table.
However, as the table gets filled & collisions increase, the efficiency can drop. In the worst case, where every potential slot needs to be checked, the time complexity can approach O(n), where n is the number of slots in the table. But remember, due to the systematic nature of Quadratic Probing, this worst-case scenario is less likely compared to other methods like linear probing.
Space Complexity
The space complexity for a hash table using Quadratic Probing is O(n), where n is the size of the table. This is because, regardless of the number of items actually stored, the table allocates space for 'n' possible entries from the get-go. It's like having a bookshelf with a fixed number of slots; the space taken up by the shelf remains the same, no matter how many books you actually put on it.
It's important to note that while Quadratic Probing improves on the clustering issue seen in simpler probing methods, it requires careful table size selection & load factor management to maintain efficiency. The load factor, which is the ratio of the number of stored entries to the table size, significantly influences performance. Keeping the load factor below a certain threshold (often around 0.5 to 0.7) helps in keeping operations efficient.
Frequently Asked Questions
What makes Quadratic Probing better than Linear Probing?
Quadratic Probing reduces clustering, a common issue in Linear Probing where a group of consecutive slots gets filled, slowing down the performance. By jumping over slots in a quadratic sequence, it spreads out the entries more evenly, leading to better performance in many cases.
How does the size of the hash table affect Quadratic Probing?
The size of the hash table is crucial for Quadratic Probing. Ideally, the table size should be a prime number to maximize the efficiency of the probing sequence. A prime number size helps ensure that all slots can be probed, reducing the chance of an unresolvable collision.
Can Quadratic Probing lead to infinite loops?
If not implemented correctly, especially in a full or nearly full table, Quadratic Probing can lead to infinite loops. To prevent this, it's important to ensure the table size is appropriate and to include a mechanism to stop the probe after a certain number of attempts, signaling the table is full or needs resizing.
Is quadratic probing faster than linear probing?
Quadratic probing can be faster than linear probing in certain cases because it reduces clustering by spreading out the probe sequence. However, its performance depends on factors like load factor and hash table size. Linear probing can suffer more from primary clustering.
What is probing in DSA?
Probing in Data Structures and Algorithms (DSA) refers to the technique used to resolve collisions in hash tables. When two keys hash to the same index, probing helps find the next available slot using methods like linear, quadratic, or double hashing.
Conclusion
In this article, we learned about Quadratic Probing in hash tables. We explored what Quadratic Probing is and how it works. Later, we discussed how Quadratic Probing is done, with a brief explanation of the required steps. We also looked at its implementation in multiple languages and concluded by understanding the time and space complexities of Quadratic Probing.