Quadratic Probing
Quadratic probing is an open-addressing collision resolution scheme in hash tables where the interval between probes is a quadratic function of the probe attempt counter. Formally, given a key mapped to an initial hash index h(k), the i-th probe index is defined as h(k, i) = (h(k) + c1 * i + c2 * i^2) mod m, where m is the table capacity, and c1, c2 are constants with c2 != 0. This technique effectively mitigates primary clustering—a pathological degradation pattern inherent to linear probing—by dispersing consecutive secondary collisions along a parabolic trajectory across the backing array.
HOW-TO IMPLEMENT & CONFIGURE
- Modern C++17 compliant compiler (GCC 9+, Clang 10+, MSVC 2019+)
- Standard development toolchain (CMake 3.15+, Make or Ninja)
- Understanding of modular arithmetic, prime factorization, and memory alignment
Architectural Setup & Environment Initialization
Initialize a robust project structure ensuring memory safety and deterministic cache utilization. Set up a CMake project targeting C++17.
cmake_minimum_required(VERSION 3.15)
project(QuadraticProbingEngine CXX)
set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
add_executable(hash_benchmark main.cpp)Core Algorithm Implementation
Implement a production-grade hash table leveraging quadratic probing with triangular numbers (c1 = 1/2, c2 = 1/2) over a table capacity constrained to a power of two or a prime number to guarantee cycle properties.
#include <vector>
#include <optional>
#include <stdexcept>
template <typename K, typename V>
class QuadraticHashMap {
private:
enum class State { EMPTY, OCCUPIED, DELETED };
struct Entry {
K key;
V value;
State state{State::EMPTY};
};
std::vector<Entry> table;
size_t capacity;
size_t size;
size_t hash(const K& key) const {
return std::hash<K>{}(key) % capacity;
}
void rehash() {
size_t old_capacity = capacity;
capacity *= 2;
std::vector<Entry> old_table = std::move(table);
table = std::vector<Entry>(capacity);
size = 0;
for (const auto& entry : old_table) {
if (entry.state == State::OCCUPIED) {
insert(entry.key, entry.value);
}
}
}
public:
explicit QuadraticHashMap(size_t cap = 8) : capacity(cap), size(0), table(cap) {}
bool insert(const K& key, const V& value) {
if (static_cast<double>(size) / capacity >= 0.5) {
rehash();
}
size_t h = hash(key);
size_t i = 0;
while (i < capacity) {
size_t idx = (h + i + i * i) / 2 % capacity; // Triangular probing variant
if (table[idx].state == State::EMPTY || table[idx].state == State::DELETED) {
table[idx] = {key, value, State::OCCUPIED};
++size;
return true;
}
if (table[idx].state == State::OCCUPIED && table[idx].key == key) {
table[idx].value = value;
return true;
}
++i;
}
return false;
}
std::optional<V> get(const K& key) const {
size_t h = hash(key);
size_t i = 0;
while (i < capacity) {
size_t idx = (h + i + i * i) / 2 % capacity;
if (table[idx].state == State::EMPTY) return std::nullopt;
if (table[idx].state == State::OCCUPIED && table[idx].key == key) {
return table[idx].value;
}
++i;
}
return std::nullopt;
}
};Verification and Unit Testing
Construct a test harness validating boundary conditions, insertions, updates, and rehashing behavior.
#include <iostream>
int main() {
QuadraticHashMap<int, std::string> map(4);
map.insert(1, "alpha");
map.insert(5, "beta"); // Forces collision with 1 if capacity is 4
map.insert(9, "gamma");
std::cout << "Key 1: " << map.get(1).value_or("NOT_FOUND") << "n";
std::cout << "Key 5: " << map.get(5).value_or("NOT_FOUND") << "n";
std::cout << "Key 9: " << map.get(9).value_or("NOT_FOUND") << "n";
return 0;
}Production Hardening & Failure Mode Mitigation
Protect against infinite loops during probing cycles by enforcing strict load factor caps (alpha <= 0.5) and ensuring table capacities adhere to mathematical constraints.
// Enforce load factor constraint <= 0.5 to prevent secondary clustering loops
// and guarantee that half the table remains empty for successful termination.Mathematical Foundation & Probe Sequence Generation
The core limitation of linear probing is primary clustering, where contiguous blocks of occupied slots expand monotonically, increasing average lookup times to O(n). Quadratic probing breaks this spatial dependency by generating probe sequences using a second-degree polynomial:
h(k, i) = (h(k) + c1 * i + c2 * i^2) mod m
To ensure the probe sequence examines a maximal number of unique slots before repeating, specific configurations of constants c1, c2 and table size m are required. When m is a prime congruence to 3 mod 4 and c1 = c2 = 1/2, the sequence guarantees traversal of distinct entries for the first m / 2 probes. Alternatively, setting m to a power of two requires precise tuning of c1 and c2 (such as c1 = c2 = 1/2) alongside bitwise masking to prevent infinite cycles.
Secondary Clustering Analysis
While quadratic probing completely eliminates primary clustering—keys that hash to the same initial index h(k) will follow the exact same probe sequence (termed secondary clustering)—this does not impair performance as severely as primary clustering because secondary collisions only occur for keys sharing an identical initial hash signature. However, when the load factor exceeds 0.5, quadratic probing mathematically guarantees that the probe sequence will fail to find an empty slot even if free slots exist elsewhere in the table, necessitating dynamic resizing or re-hashing.
Memory Layout & Cache Efficiency
From a hardware perspective, open addressing schemes like quadratic probing outperform pointer-heavy data structures (such as separate chaining linked lists) due to spatial locality and CPU cache line utilization. Contiguous allocation maps entries sequentially in RAM. Although quadratic jumps disrupt strict sequential prefetching, modern CPU branch predictors and instruction-level parallelism manage moderate stride variations efficiently, provided the footprint fits within L2/L3 cache hierarchies.
📚 STANDARDS & ACADEMIC RFC CITATIONS
- Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Peterson, W. W. (1957). Addressing for Random Access Storage. IBM Journal of Research and Development, 1(2), 130-146.
