Collision Resolution Techniques
Separate Chaining vs Open Addressing: Linear Probing (primary clustering), Quadratic Probing, and Double Hashing.
Reinforce your mental model: run, pause, and inspect live pointers with our interactive visualizer:
Topics Covered:
38. Separate Chaining (Open Hashing) & Bucket Chains • 39. Open Addressing (Closed Hashing) & The Deletion Dilemma (TOMBSTONESentinel Protocol) • 40. Linear Probing & Primary Clustering • Quadratic Probing & Secondary Clustering • Double Hashing & Coprimality Constraints • Production Implementations
Because the universe of possible search keys vastly exceeds the physical capacity of any hash table, collisions are mathematically unavoidable. An effective hash table is therefore defined by the resilience and efficiency of its collision resolution mechanism. This chapter explores the two dominant architectural paradigms: Separate Chaining (storing colliding elements in external node structures) and Open Addressing (probing for open slots directly within the primary array). We analyze probe sequence mechanics, the TOMBSTONE deletion state machine, primary and secondary clustering phenomena, and coprimality constraints in double hashing.
Learning Objectives
#- Contrast the physical memory layouts, cache performance, and load factor tolerances of Separate Chaining versus Open Addressing.
- Formulate the Open Addressing deletion dilemma and implement the
TOMBSTONEsentinel protocol to preserve probe continuity. - Diagnose the physical causes of Primary Clustering in Linear Probing and Secondary Clustering in Quadratic Probing.
- Implement Double Hashing and prove why the step function must be coprime to table capacity to guarantee a complete permutation of slots.
- Construct a robust C++20 Open Addressing hash table implementing Robin Hood / Tombstone probing.
Topic 38: Separate Chaining (Open Hashing)
#1. Conceptual Architecture & Bucket Chains
In Separate Chaining, the hash table is an array of pointers (or bucket heads). Each slot points to an external linked list (or self-balancing binary search tree) containing all key-value entries that hashed to ().
Interactive Simulations:
Observe bucket node insertions live in the Interactive Separate Chaining Visualizer.
Topic 39: Open Addressing & The Deletion Dilemma
#1. Physical Memory Topology & Probing Comparison
2. Probing Mathematical Formulations
#A. Linear Probing:
- Primary Clustering: Clusters grow and merge into large blocks, increasing expected probe length.
B. Quadratic Probing:
- Jumps across primary clusters, but identical initial hashes follow identical probe paths (Secondary Clustering).
C. Double Hashing:
- To ensure full table traversal, must be coprime to () and . For prime :
3. Production Multi-Language Implementation
#C++20 Open Addressing Hash Table with TOMBSTONE Protocol
#include <vector>
#include <string>
#include <stdexcept>
#include <optional>
template <typename K, typename V>
class OpenAddressingMap {
private:
enum class State { EMPTY, OCCUPIED, TOMBSTONE };
struct Entry {
K key;
V value;
State state = State::EMPTY;
};
std::vector<Entry> table_;
size_t capacity_;
size_t size_;
size_t tombstones_;
size_t hash1(const K& key) const {
return std::hash<K>{}(key) % capacity_;
}
size_t hash2(const K& key) const {
// Must be non-zero and coprime to prime capacity
size_t h = std::hash<K>{}(key) % (capacity_ - 1);
return 1 + h;
}
public:
explicit OpenAddressingMap(size_t cap = 11)
: capacity_(cap), size_(0), tombstones_(0), table_(cap) {}
bool insert(const K& key, const V& value) {
if ((size_ + tombstones_) * 10 >= capacity_ * 7) {
rehash(capacity_ * 2 + 1); // Expand prime
}
size_t h1 = hash1(key);
size_t h2 = hash2(key);
size_t first_tombstone = capacity_;
for (size_t i = 0; i < capacity_; ++i) {
size_t idx = (h1 + i * h2) % capacity_;
if (table_[idx].state == State::EMPTY) {
size_t dest = (first_tombstone != capacity_) ? first_tombstone : idx;
table_[dest].key = key;
table_[dest].value = value;
table_[dest].state = State::OCCUPIED;
if (first_tombstone != capacity_) --tombstones_;
++size_;
return true;
}
if (table_[idx].state == State::TOMBSTONE && first_tombstone == capacity_) {
first_tombstone = idx;
}
if (table_[idx].state == State::OCCUPIED && table_[idx].key == key) {
table_[idx].value = value;
return false; // Updated existing key
}
}
return false;
}
std::optional<V> find(const K& key) const {
size_t h1 = hash1(key);
size_t h2 = hash2(key);
for (size_t i = 0; i < capacity_; ++i) {
size_t idx = (h1 + i * h2) % capacity_;
if (table_[idx].state == State::EMPTY) {
return std::nullopt; // Search terminates
}
if (table_[idx].state == State::OCCUPIED && table_[idx].key == key) {
return table_[idx].value;
}
// If TOMBSTONE, continue probing!
}
return std::nullopt;
}
bool erase(const K& key) {
size_t h1 = hash1(key);
size_t h2 = hash2(key);
for (size_t i = 0; i < capacity_; ++i) {
size_t idx = (h1 + i * h2) % capacity_;
if (table_[idx].state == State::EMPTY) {
return false;
}
if (table_[idx].state == State::OCCUPIED && table_[idx].key == key) {
table_[idx].state = State::TOMBSTONE;
--size_;
++tombstones_;
return true;
}
}
return false;
}
private:
void rehash(size_t new_cap) {
std::vector<Entry> old_table = std::move(table_);
capacity_ = new_cap;
table_.assign(capacity_, Entry{});
size_ = 0;
tombstones_ = 0;
for (auto& entry : old_table) {
if (entry.state == State::OCCUPIED) {
insert(entry.key, entry.value);
}
}
}
};4. Key Takeaways
#- Chaining vs. Open Addressing: Chaining uses external linked lists with pointer overhead; Open Addressing stores all keys directly in the array and requires .
- TOMBSTONE Necessity: Open Addressing must mark deleted slots with
TOMBSTONEto prevent search chains from severing prematurely. - Primary Clustering: Linear probing produces contiguous clumps of occupied slots, degrading average search time.
- Double Hashing Superiority: Using a key-dependent step size coprime to prime yields independent probe permutations, eliminating clustering.
Academic Attribution & References
#- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 11: Hash Tables. MIT Press.
- Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), Section 6.4: Hashing. Addison-Wesley.
- Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 3.4: Hash Tables. Addison-Wesley.