Double Hashing
Advanced open addressing collision resolution using two hash functions: h1(key) determines initial position, h2(key) determines probe step size. This eliminates primary clustering (linear probing's main weakness) while maintaining open addressing's cache benefits. The probe sequence depends on the key, spreading collisions more uniformly. Widely used in high-performance hash tables where load factors approach 0.9.
Visualization
Interactive visualization for Double Hashing
Double Hashing:
- • idx = (h1(k) + i*h2(k)) % m
- • Reduces clustering vs linear probing
- • Time: O(1) average
Interactive visualization with step-by-step execution
Implementation
1class DoubleHashing {
2 private keys:(string|number|null)[]; private values:(any|null)[]; private n=0; constructor(private capacity=17){ this.keys=Array(capacity).fill(null); this.values=Array(capacity).fill(null); }
3 private h1(k:any){ return (Math.abs(String(k).split('').reduce((a,c)=>((a*31+c.charCodeAt(0))|0),0))%this.capacity) }
4 private h2(k:any){ return 1 + (Math.abs(String(k).split('').reduce((a,c)=>((a*131+c.charCodeAt(0))|0),0)) % (this.capacity-1)) }
5 put(k:any,v:any){ if(this.n/this.capacity>0.7) this.resize(this.capacity*2+1); let i=0, idx=(this.h1(k)+i*this.h2(k))%this.capacity; while(this.keys[idx]!=null && this.keys[idx]!==k){ i++; idx=(this.h1(k)+i*this.h2(k))%this.capacity; } if(this.keys[idx]==null) this.n++; this.keys[idx]=k; this.values[idx]=v; }
6 get(k:any){ let i=0, idx=(this.h1(k)+i*this.h2(k))%this.capacity; while(this.keys[idx]!=null){ if(this.keys[idx]===k) return this.values[idx]; i++; idx=(this.h1(k)+i*this.h2(k))%this.capacity; } return undefined; }
7 private resize(nc:number){ const ok=this.keys, ov=this.values; this.capacity=nc; this.keys=Array(nc).fill(null); this.values=Array(nc).fill(null); this.n=0; for(let i=0;i<ok.length;i++) if(ok[i]!=null) this.put(ok[i], ov[i]); }
8}Deep Dive
Theoretical Foundation
Double hashing probe sequence: h(key, i) = (h1(key) + i × h2(key)) mod m for i = 0,1,2,... **Key requirement**: h2(key) must be coprime with m (gcd(h2(key), m) = 1) to guarantee full table traversal. Common choice: m = prime, h2(key) = 1 + (hash(key) mod (m-1)). This ensures h2 ∈ [1, m-1], all coprime with prime m. **Advantage over linear probing**: different keys have different probe sequences, eliminating primary clustering. Performance: expected probes ≈ 1/(1-α) for success, similar to linear probing but without clustering degradation. Works well even at α ≈ 0.9.
Complexity
Time
O(1)
O(1)
O(n)
Space
O(n)
Applications
Industry Use
Python's old dictionary implementation (pre-3.6)
Language runtime symbol tables
High-load hash tables in databases
Embedded systems with memory constraints
Compiler hash tables
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.