Extendible Hashing
Extendible hashing is a dynamic hashing algorithm that uses a directory of pointers to buckets to handle data growth and shrinkage gracefully. By decoupling the hash prefix space (global depth) from individual bucket allocation spaces (local depth), it guarantees point queries in minimal disk I/O operations while amortizing the structural reorganization cost over massive inserts. Unlike traditional static hashing or linear hashing, extendible hashing prevents performance degradation and long overflow chains by doubling its directory exponentially only when the local depth of an overflowing bucket equals the global depth.
HOW-TO IMPLEMENT & CONFIGURE
- Modern C++ compiler supporting C++20 (GCC 11+, Clang 13+, MSVC 2019+)
- Standard Template Library (STL)
- Operating System page-aligned memory allocators or direct block storage simulators
Architectural Setup & Environment Initialization
Define the memory layout constants, including fixed bucket capacity B and structural classes for Buckets and the Directory. Ensure bitwise operations can easily isolate hash prefixes.
#include <vector>
#include <memory>
#include <iostream>
#include <cstdint>
const size_t BUCKET_CAPACITY = 2;
struct Record {
uint32_t key;
uint64_t value;
};Core Algorithm / Protocol Logic Implementation
Implement the Bucket and ExtendibleHashTable classes, featuring dynamic directory doubling, local depth tracking, and bucket splitting upon overflow.
struct Bucket {
uint8_t local_depth;
std::vector<Record> records;
explicit Bucket(uint8_t depth) : local_depth(depth) {}
bool is_full() const { return records.size() >= BUCKET_CAPACITY; }
};
class ExtendibleHashTable {
private:
uint8_t global_depth;
std::vector<std::shared_ptr<Bucket>> directory;
size_t hash(uint32_t key) const {
return key;
}
size_t get_index(uint32_t key) const {
return hash(key) & ((1 << global_depth) - 1);
}
public:
ExtendibleHashTable() : global_depth(0) {
directory.push_back(std::make_shared<Bucket>(0));
}
void insert(uint32_t key, uint64_t value) {
size_t dir_idx = get_index(key);
auto target_bucket = directory[dir_idx];
for (const auto& rec : target_bucket->records) {
if (rec.key == key) return; // Update logic omitted for brevity
}
if (!target_bucket->is_full()) {
target_bucket->records.push_back({key, value});
return;
}
// Bucket Overflow & Split Logic
if (target_bucket->local_depth == global_depth) {
if (global_depth >= 32) throw std::overflow_error("Max depth reached");
size_t current_size = directory.size();
global_depth++;
directory.resize(current_size * 2);
for (size_t i = 0; i < current_size; ++i) {
directory[i + current_size] = directory[i];
}
}
uint8_t original_depth = target_bucket->local_depth;
target_bucket->local_depth++;
auto new_bucket = std::make_shared<Bucket>(target_bucket->local_depth);
std::vector<Record> old_records = target_bucket->records;
target_bucket->records.clear();
old_records.push_back({key, value});
size_t mask = 1 << (original_depth);
for (size_t i = 0; i < directory.size(); ++i) {
if (directory[i] == target_bucket) {
if ((i & mask) != 0) {
directory[i] = new_bucket;
}
}
}
for (const auto& rec : old_records) {
insert(rec.key, rec.value);
}
}
};Verification, Profiling & Unit Testing
Construct a comprehensive test suite to validate insertion mechanics, split cascades, and directory doubling invariants.
int main() {
ExtendibleHashTable htable;
htable.insert(1, 100);
htable.insert(2, 200);
htable.insert(3, 300); // Triggers split
std::cout << "Execution completed successfully.n";
return 0;
}Production Hardening & Common Failure Modes
Mitigate risks associated with skewed hash distributions causing pathological directory doubling, and ensure thread safety using fine-grained read-write latches.
// Production hardening pattern: Implement reader-writer locks per bucket and atomic directory swaps.
#include <shared_mutex>
struct ThreadSafeBucket {
std::shared_mutex mutex;
uint8_t local_depth;
std::vector<Record> records;
};Mathematical Foundation & Invariants
Extendible hashing relies on a hash function h(k) mapping keys to a uniform bitstring space of width w. The directory maintains a size of 2^g, where g is the global depth. Every bucket references an internal block containing records, characterized by a local depth l <= g. The core invariant states that all keys hashing to a bucket share a common prefix of length l. When a bucket overflows and l < g, the bucket splits into two, its local depth is incremented, and precisely half of the directory entries pointing to the old bucket are updated to point to the new bucket. If l == g, the global depth g is incremented, doubling the directory size before executing the split.
Concurrency Control & Lock Coupling
In multi-threaded database architectures, acquiring a global mutex on the entire hash table during every insertion causes severe throughput bottlenecks. Production systems implement latch crabbing or optimistic concurrency control. Readers acquire a shared lock on the directory pointer, traverse to the bucket, acquire a shared lock on the bucket, and release the directory lock. Writers acquire an exclusive lock on the bucket; if a split is required, the writer upgrades the lock to an exclusive lock on the directory structure, ensuring thread safety during pointer reallocation and directory resizing.
📚 STANDARDS & ACADEMIC RFC CITATIONS
- Fagin, R., Nievergelt, J., Pippenger, N., & Strong, H. R. (1979). Extendible Hashing—A Fast Access Method for Dynamic Files. ACM Transactions on Database Systems (TODS), 4(3), 315-344.
- Elmasri, R., & Navathe, S. B. (2015). Fundamentals of Database Systems (7th ed.). Pearson.
- Silberschatz, A., Korth, H. F., & Sudarshan, S. (2019). Database System Concepts (7th ed.). McGraw-Hill Education.