Explore open addressing in hash tables, focusing on collision resolution techniques like linear probing, quadratic probing, and double hashing, with practical JavaScript implementations.
Open addressing is a collision resolution technique used in hash tables where all elements are stored directly within the hash table array itself. Unlike separate chaining, which uses linked lists to handle collisions, open addressing finds another spot within the array to store the colliding element. This approach requires a careful balance between hash function design and probing strategy to maintain efficient operations.
In open addressing, when a collision occurs (i.e., two keys hash to the same index), the algorithm searches for the next available slot in the array according to a specific probing sequence. The main probing techniques include linear probing, quadratic probing, and double hashing. Each method has its own advantages and trade-offs, which we will explore in detail.
Linear probing is the simplest form of open addressing. When a collision occurs, the algorithm checks the next slot in the array (index + 1) until it finds an empty slot. This method is straightforward but can lead to a phenomenon known as primary clustering, where a cluster of occupied slots forms, increasing the likelihood of future collisions.
class LinearProbingHashTable {
constructor(size = 53) {
this.keyMap = new Array(size);
}
_hash(key) {
let total = 0;
let PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96;
total = (total * PRIME + value) % this.keyMap.length;
}
return total;
}
set(key, value) {
let index = this._hash(key);
while (this.keyMap[index]) {
index = (index + 1) % this.keyMap.length;
}
this.keyMap[index] = [key, value];
}
get(key) {
let index = this._hash(key);
while (this.keyMap[index]) {
if (this.keyMap[index][0] === key) {
return this.keyMap[index][1];
}
index = (index + 1) % this.keyMap.length;
}
return undefined;
}
}
Quadratic probing uses a quadratic function to compute the interval between probes. This method reduces primary clustering but can lead to secondary clustering, where keys that hash to the same initial index follow the same probe sequence.
The quadratic probing formula is:
index = (initialIndex + c1 * i + c2 * i * i) % arraySize;
Where c1 and c2 are constants, and i is the probe attempt number.
class QuadraticProbingHashTable {
constructor(size = 53) {
this.keyMap = new Array(size);
}
_hash(key) {
let total = 0;
let PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96;
total = (total * PRIME + value) % this.keyMap.length;
}
return total;
}
set(key, value) {
let index = this._hash(key);
let i = 1;
while (this.keyMap[index]) {
index = (index + i * i) % this.keyMap.length;
i++;
}
this.keyMap[index] = [key, value];
}
get(key) {
let index = this._hash(key);
let i = 1;
while (this.keyMap[index]) {
if (this.keyMap[index][0] === key) {
return this.keyMap[index][1];
}
index = (index + i * i) % this.keyMap.length;
i++;
}
return undefined;
}
}
Double hashing uses a second hash function to calculate the step size for probing. This method is more complex but effectively reduces clustering by ensuring a more uniform distribution of keys across the hash table.
The double hashing formula is:
index = (hash1(key) + i * hash2(key)) % arraySize;
The secondary hash function, hash2, must not evaluate to zero to ensure that the probing sequence covers all slots in the table.
class DoubleHashingHashTable {
constructor(size = 53) {
this.keyMap = new Array(size);
}
_hash1(key) {
let total = 0;
let PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96;
total = (total * PRIME + value) % this.keyMap.length;
}
return total;
}
_hash2(key) {
return (key % (this.keyMap.length - 1)) + 1;
}
set(key, value) {
let index = this._hash1(key);
let i = 0;
while (this.keyMap[index]) {
index = (this._hash1(key) + i * this._hash2(key)) % this.keyMap.length;
i++;
}
this.keyMap[index] = [key, value];
}
get(key) {
let index = this._hash1(key);
let i = 0;
while (this.keyMap[index]) {
if (this.keyMap[index][0] === key) {
return this.keyMap[index][1];
}
index = (this._hash1(key) + i * this._hash2(key)) % this.keyMap.length;
i++;
}
return undefined;
}
}
Each probing method has its strengths and weaknesses:
Open addressing is a powerful technique for collision resolution in hash tables, offering several methods to balance simplicity and performance. By understanding and implementing linear probing, quadratic probing, and double hashing, you can optimize hash table operations for a wide range of applications.