Hopscotch Hashing
Hopscotch Hashing is an open-addressing hash table algorithm that combines the cache-efficiency of linear probing with the bounded lookup worst-case performance of chaining. By maintaining a neighborhood invariant where every key must reside within a fixed distance H of its initial hashed bucket, the algorithm uses a bitmask at each bucket to track neighborhood occupancy. This structural constraint guarantees that lookups require examining at most H locations while permitting extremely high load factors (up to 90%+) without performance degradation.
HOW-TO IMPLEMENT & CONFIGURE
- Modern C++ compiler supporting C++17 or higher (GCC 9+, Clang 10+, MSVC 2019+)
- Standard Template Library (STL)
- Atomic operations library (std::atomic) for concurrent variants
- Memory alignment primitives (alignas)
Architectural Setup & Environment Initialization
Define the table structures, memory alignment, and fundamental constants including neighborhood size H (typically 32 to match register or word width) and maximum probing limits.
#include <vector>
#include <cstdint>
#include <optional>
#include <array>
#include <stdexcept>
template<typename K, typename V, size_t H = 32>
class HopscotchHashTable {
private:
struct Bucket {
K key;
V value;
uint32_t neighborhood_bitmap;
bool occupied;
};
std::vector<Bucket> table;
size_t capacity;
size_t num_elements;
public:
explicit HopscotchHashTable(size_t initial_capacity)
: capacity(initial_capacity), num_elements(0) {
if ((H & (H - 1)) != 0 && H > 32) {
throw std::invalid_argument("Neighborhood size H must be <= 32 for standard bitmask operations.");
}
table.resize(capacity);
for (auto& b : table) {
b.occupied = false;
b.neighborhood_bitmap = 0;
}
}
};Core Algorithm / Protocol Logic Implementation
Implement the core lookup, hash function, and the complex displacement mechanism required for insertions when a bucket's neighborhood is saturated.
size_t hash_key(const K& key) const {
return std::hash<K>{}(key) % capacity;
}
bool insert(const K& key, const V& value) {
if (num_elements >= capacity / 2) {
resize_and_rehash();
}
size_t initial_hash = hash_key(key);
size_t curr = initial_hash;
// Step 2a: Find an empty bucket using linear probing
while (table[curr].occupied) {
if (table[curr].key == key) {
table[curr].value = value;
return true;
}
curr = (curr + 1) % capacity;
if (curr == initial_hash) return false; // Table full
}
size_t empty_bucket = curr;
// Step 2b: Relocate empty bucket within H distance of initial_hash
while (empty_bucket >= initial_hash + H - 1 && empty_bucket - initial_hash >= capacity - H + 1) { // simplified boundary check
// Find a closer bucket to swap with
size_t probe = empty_bucket - (H - 1);
bool moved = false;
for (size_t i = 0; i < H - 1; ++i) {
size_t candidate = (probe + i) % capacity;
uint32_t mask = table[candidate].neighborhood_bitmap;
// Find if any bit set can be shifted
// ... execution of hopscotch displacement logic ...
}
if (!moved) break;
}
// Final placement
table[empty_bucket].key = key;
table[empty_bucket].value = value;
table[empty_bucket].occupied = true;
size_t dist = (empty_bucket >= initial_hash) ?
(empty_bucket - initial_hash) :
(capacity - initial_hash + empty_bucket);
if (dist < H) {
table[initial_hash].neighborhood_bitmap |= (1U << dist);
}
num_elements++;
return true;
}Verification, Profiling & Unit Testing
Write rigorous test assertions validating neighborhood invariants, correct bitmask updates on deletion, and collision resolution.
void run_tests() {
HopscotchHashTable<int, std::string, 32> map(1024);
assert(map.insert(1, "one") == true);
assert(map.insert(33, "thirty-three") == true);
std::optional<std::string> val = map.find(1);
assert(val.has_value() && val.value() == "one");
val = map.find(33);
assert(val.has_value() && val.value() == "thirty-three");
}
int main() {
run_tests();
return 0;
}Production Hardening & Common Failure Modes
Address catastrophic failure conditions such as clustering degradation, load factor thresholds, and concurrent thread safety models using fine-grained locking or lock-free atomics.
void resize_and_rehash() {
size_t old_capacity = capacity;
auto old_table = std::move(table);
capacity *= 2;
table.clear();
table.resize(capacity);
num_elements = 0;
for (auto& b : old_table) {
if (b.occupied) {
insert(b.key, b.value);
}
}
}
std::optional<V> find(const K& key) const {
size_t initial_hash = hash_key(key);
uint32_t bitmap = table[initial_hash].neighborhood_bitmap;
while (bitmap != 0) {
int bit_index = __builtin_ctz(bitmap); // Count trailing zeros
size_t target = (initial_hash + bit_index) % capacity;
if (table[target].occupied && table[target].key == key) {
return table[target].value;
}
bitmap &= bitmap - 1; // Clear lowest set bit
}
return std::nullopt;
}Mathematical Foundations & Neighborhood Invariant
Hopscotch Hashing relies on a tight mathematical invariant: given a hash function h(k) mapping keys to the index space [0, N-1], any key k that hashes to bucket i must ultimately reside in bucket j such that (j – i) mod N < H, where H is a constant neighborhood size (typically bounded by machine word dimensions, e.g., 32 or 64). Each bucket maintains an H-bit integer mask B_i where the k-th bit is set if and only if the bucket at index (i + k) mod N contains an element whose original hash evaluated to i. Lookups check B_h(k) and use population count or bit-scan instructions (such as tzcnt or ctz) to inspect only the subset of valid candidate slots, bounding worst-case lookup operations strictly to O(H) independent of total table cardinality N.
Displacement and Robin Hood Mechanics
When an insertion targets a bucket whose neighborhood is saturated (i.e., no available slot exists within distance H), the algorithm initiates a cooperative displacement cascade. It searches outward via linear probing for a vacant slot at index x. If x is outside the neighborhood H of the original hash, the algorithm attempts to find an intermediate bucket y within H of x that can accept the element currently at y, thereby shifting the vacant slot closer to the target neighborhood. This process iterates recursively or iteratively until the empty slot is successfully relocated within the target neighborhood boundary. If no valid displacement path exists, the table triggers a structural resize and complete rehash.
Concurrency and Lock-Free Synchronization
Because hopscotch neighborhoods are localized, the data structure lends itself exceptionally well to concurrent execution models. Instead of acquiring a global mutex during modifications, threads can acquire localized fine-grained locks covering a span of H + max_displacement buckets. Furthermore, read operations are lock-free: readers inspect the neighborhood bitmask atomically and perform memory-consistent loads on the corresponding target buckets without mutating structural pointers or states. This reduces lock contention significantly compared to traditional chained hash tables or coarse-grained open-addressing designs.
📚 STANDARDS & ACADEMIC RFC CITATIONS
- Herlihy, M., Shavit, N., & Tzafrir, M. (2008). Hopscotch Hashing. Proceedings of the 22nd International Symposium on Distributed Computing (DISC), 350-364.
- Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.
- Preshing, J. (2015). The Basics of Hopscotch Hashing. Preshing on Programming.