WikiGalaxy
Open Addressing Methods
Linear Probing
Linear Probing is a simple collision resolution method where, upon a collision, the algorithm checks the next sequential slot until an empty one is found. It is efficient but can lead to clustering.
int hash(int key) {
return key % tableSize;
}
void insert(int key) {
int index = hash(key);
while (table[index] != null) {
index = (index + 1) % tableSize;
}
table[index] = key;
}
Quadratic Probing
Quadratic Probing resolves collisions using a quadratic function. This method reduces clustering compared to linear probing by spreading out the probes.
int hash(int key) {
return key % tableSize;
}
void insert(int key) {
int index = hash(key);
int i = 0;
while (table[(index + i * i) % tableSize] != null) {
i++;
}
table[(index + i * i) % tableSize] = key;
}
Double Hashing
Double Hashing uses a second hash function to calculate the interval between probes, providing a more uniform distribution of keys.
int hash1(int key) {
return key % tableSize;
}
int hash2(int key) {
return 1 + (key % (tableSize - 1));
}
void insert(int key) {
int index = hash1(key);
int stepSize = hash2(key);
while (table[index] != null) {
index = (index + stepSize) % tableSize;
}
table[index] = key;
}
Cuckoo Hashing
Cuckoo Hashing employs two hash tables and two hash functions. If a collision occurs, the existing key is displaced and reinserted using the alternate hash function.
int hash1(int key) {
return key % tableSize;
}
int hash2(int key) {
return (key / tableSize) % tableSize;
}
void insert(int key) {
int index1 = hash1(key);
if (table1[index1] == null) {
table1[index1] = key;
} else {
int displacedKey = table1[index1];
table1[index1] = key;
int index2 = hash2(displacedKey);
if (table2[index2] == null) {
table2[index2] = displacedKey;
} else {
// Handle further displacement recursively
}
}
}
Robin Hood Hashing
Robin Hood Hashing attempts to balance the search times by ensuring that keys are moved to make room for new keys, minimizing the maximum probe distance.
int hash(int key) {
return key % tableSize;
}
void insert(int key) {
int index = hash(key);
int probeDistance = 0;
while (table[index] != null && probeDistance < maxProbeDistance) {
if (probeDistance > calculateProbeDistance(table[index])) {
swap(table[index], key);
}
index = (index + 1) % tableSize;
probeDistance++;
}
table[index] = key;
}
