Open Addressing (Linear Probing)
Hash table collision resolution technique where collisions are resolved by probing subsequent slots linearly (index+1, index+2, ...) until an empty slot is found. Invented in the 1950s, linear probing offers excellent cache locality and simple implementation but suffers from primary clustering. Widely used in high-performance systems where cache performance is critical, including Java's IdentityHashMap and some C++ standard library implementations.
Visualization
Interactive visualization for Open Addressing (Linear Probing)
Open Addressing - Linear Probing:
- • Collision resolution by probing next slot
- • Time: O(1) average
Interactive visualization with step-by-step execution
Implementation
1class LinearProbingHash {
2 private keys: (string|number|null)[];
3 private values: (any|null)[];
4 private n = 0;
5 constructor(private capacity = 16) { this.keys = Array(capacity).fill(null); this.values = Array(capacity).fill(null); }
6 private hash(k: string|number) { const s = String(k); let h = 0; for (let i=0;i<s.length;i++) { h = (h*31 + s.charCodeAt(i))|0; } return (h>>>0) % this.capacity; }
7 private resize(newCap: number) { const oldK = this.keys, oldV = this.values; this.capacity = newCap; this.keys = Array(newCap).fill(null); this.values = Array(newCap).fill(null); this.n = 0; for (let i=0;i<oldK.length;i++) if (oldK[i]!=null) this.put(oldK[i]!, oldV[i]); }
8 put(key: string|number, value: any) { if (this.n/this.capacity > 0.7) this.resize(this.capacity*2); let i = this.hash(key); while (this.keys[i]!=null && this.keys[i]!==key) i = (i+1)%this.capacity; if (this.keys[i]==null) this.n++; this.keys[i]=key; this.values[i]=value; }
9 get(key: string|number) { let i = this.hash(key); while (this.keys[i]!=null) { if (this.keys[i]===key) return this.values[i]; i=(i+1)%this.capacity; } return undefined; }
10 delete(key: string|number) { let i = this.hash(key); while (this.keys[i]!=null) { if (this.keys[i]===key) { this.keys[i]=null; this.values[i]=null; this.n--; i=(i+1)%this.capacity; while (this.keys[i]!=null) { const k = this.keys[i]!, v = this.values[i]; this.keys[i]=null; this.values[i]=null; this.n--; this.put(k,v); i=(i+1)%this.capacity; } if (this.capacity>16 && this.n/this.capacity<0.2) this.resize(this.capacity>>1); return true; } i=(i+1)%this.capacity; } return false; }
11}Deep Dive
Theoretical Foundation
Open addressing stores all elements directly in the hash table array (no linked lists). On collision, linear probing searches sequentially: h(k), h(k)+1, h(k)+2, ... (mod m) until finding empty slot. **Primary clustering**: consecutive occupied slots form clusters that grow faster as more keys hash into or near them, degrading performance. Load factor α = n/m must stay below ~0.7 for good performance. Deletion is complex: cannot simply empty slot (breaks probe chains), must use tombstones or re-insert displaced keys. Expected probe length: ~1/(1-α) for successful search, ~1/(1-α)² for unsuccessful. Cache-friendly: linear memory access pattern.
Complexity
Time
O(1)
O(1)
O(n)
Space
O(n)
Applications
Industry Use
Java IdentityHashMap
High-performance in-memory caches
Symbol tables in compilers
Database hash indexes
Deduplication systems
Network routing 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.