WikiGalaxy
Collision Resolution Techniques in Hashing
Separate Chaining
Separate Chaining Overview
Separate chaining is a collision resolution technique where each bucket in the hash table points to a linked list of entries that hash to the same index.
Diagram
[0] -> (key1, value1) -> (key4, value4)
[1] -> (key2, value2)
[2] -> (key3, value3) -> (key5, value5)
import java.util.LinkedList;
class SeparateChainingHash {
private LinkedList[] table;
public SeparateChainingHash(int size) {
table = new LinkedList[size];
for (int i = 0; i < size; i++) {
table[i] = new LinkedList<>();
}
}
public void put(int key, String value) {
int index = key % table.length;
table[index].add(new Entry(key, value));
}
// Additional methods like get, remove, etc.
}
class Entry {
int key;
String value;
public Entry(int key, String value) {
this.key = key;
this.value = value;
}
}
Open Addressing: Linear Probing
Linear Probing Overview
Linear probing resolves collisions by placing the new entry in the next available position in the array, checking each subsequent index sequentially.
Diagram
[0] -> (key1, value1)
[1] -> (key2, value2)
[2] -> (key3, value3)
[3] -> (key4, value4)
class LinearProbingHash {
private Entry[] table;
public LinearProbingHash(int size) {
table = new Entry[size];
}
public void put(int key, String value) {
int index = key % table.length;
while (table[index] != null) {
index = (index + 1) % table.length;
}
table[index] = new Entry(key, value);
}
// Additional methods like get, remove, etc.
}
class Entry {
int key;
String value;
public Entry(int key, String value) {
this.key = key;
this.value = value;
}
}
Open Addressing: Quadratic Probing
Quadratic Probing Overview
Quadratic probing resolves collisions by checking indices at quadratic intervals from the original hash index, reducing clustering compared to linear probing.
Diagram
[0] -> (key1, value1)
[1] -> (key2, value2)
[4] -> (key3, value3)
[9] -> (key4, value4)
class QuadraticProbingHash {
private Entry[] table;
public QuadraticProbingHash(int size) {
table = new Entry[size];
}
public void put(int key, String value) {
int index = key % table.length;
int i = 0;
while (table[(index + i * i) % table.length] != null) {
i++;
}
table[(index + i * i) % table.length] = new Entry(key, value);
}
// Additional methods like get, remove, etc.
}
class Entry {
int key;
String value;
public Entry(int key, String value) {
this.key = key;
this.value = value;
}
}
Open Addressing: Double Hashing
Double Hashing Overview
Double hashing uses two hash functions to calculate the probe sequence, reducing clustering and providing a more uniform distribution of keys.
Diagram
[0] -> (key1, value1)
[1] -> (key2, value2)
[3] -> (key3, value3)
[6] -> (key4, value4)
class DoubleHashingHash {
private Entry[] table;
public DoubleHashingHash(int size) {
table = new Entry[size];
}
private int hash1(int key) {
return key % table.length;
}
private int hash2(int key) {
return 1 + (key % (table.length - 1));
}
public void put(int key, String value) {
int index = hash1(key);
int stepSize = hash2(key);
while (table[index] != null) {
index = (index + stepSize) % table.length;
}
table[index] = new Entry(key, value);
}
// Additional methods like get, remove, etc.
}
class Entry {
int key;
String value;
public Entry(int key, String value) {
this.key = key;
this.value = value;
}
}
Cuckoo Hashing
Cuckoo Hashing Overview
Cuckoo hashing uses two hash tables and two hash functions. If a collision occurs, the existing element is moved to its alternative position, allowing the new element to be inserted.
Diagram
Table1: [0] -> (key1, value1), [1] -> (key3, value3)
Table2: [0] -> (key2, value2), [1] -> (key4, value4)
class CuckooHashing {
private Entry[] table1, table2;
public CuckooHashing(int size) {
table1 = new Entry[size];
table2 = new Entry[size];
}
private int hash1(int key) {
return key % table1.length;
}
private int hash2(int key) {
return key % table2.length;
}
public void put(int key, String value) {
int index1 = hash1(key);
if (table1[index1] == null) {
table1[index1] = new Entry(key, value);
} else {
Entry displaced = table1[index1];
table1[index1] = new Entry(key, value);
int index2 = hash2(displaced.key);
table2[index2] = displaced;
}
}
// Additional methods like get, remove, etc.
}
class Entry {
int key;
String value;
public Entry(int key, String value) {
this.key = key;
this.value = value;
}
}
