WikiGalaxy
Double Hashing
Introduction to Double Hashing
Double hashing is a collision resolution technique in hash tables. It uses two hash functions to calculate the index for storing data, reducing the chance of collisions.
Example 1: Basic Double Hashing
Basic Concept
In double hashing, we use two hash functions: h1(key) and h2(key). The formula is: index = (h1(key) + i * h2(key)) % table_size, where i is the number of attempts.
int h1(int key) { return key % table_size; }
int h2(int key) { return 1 + (key % (table_size - 1)); }
int doubleHashing(int key, int i) {
return (h1(key) + i * h2(key)) % table_size;
}
Explanation
The first hash function h1(key) gives the initial position, while h2(key) provides the step size for probing.
Example 2: Handling Collisions
Collision Resolution
When a collision occurs, double hashing calculates a new index using the second hash function, minimizing clustering.
int findSlot(int key) {
int i = 0;
int index = doubleHashing(key, i);
while (hashTable[index] != null && hashTable[index] != key) {
i++;
index = doubleHashing(key, i);
}
return index;
}
Explanation
This method finds the next available slot by incrementing i until an empty or matching slot is found.
Example 3: Efficiency
Efficiency of Double Hashing
Double hashing offers better distribution of keys across the hash table, reducing clustering and improving efficiency.
boolean insertKey(int key) {
int index = findSlot(key);
if (hashTable[index] == null) {
hashTable[index] = key;
return true;
}
return false;
}
Explanation
This insertion method efficiently places keys into the hash table, ensuring minimal collisions.
Example 4: Real-world Application
Practical Use Case
Double hashing is used in scenarios where fast retrieval and insertion are crucial, such as caching mechanisms and database indexing.
class Cache {
int[] cacheTable;
Cache(int size) {
cacheTable = new int[size];
}
void add(int key) {
int index = findSlot(key);
cacheTable[index] = key;
}
}
Explanation
The cache class demonstrates how double hashing can be employed to manage cache entries effectively.
Example 5: Advanced Strategies
Advanced Techniques
Advanced double hashing strategies involve dynamically resizing hash tables and optimizing hash functions for specific data types.
void resizeTable() {
int newSize = table_size * 2;
int[] newTable = new int[newSize];
for (int key : hashTable) {
if (key != 0) {
int index = findSlot(key);
newTable[index] = key;
}
}
hashTable = newTable;
table_size = newSize;
}
Explanation
This resizing method ensures the hash table maintains efficiency even as it grows, by redistributing existing keys.
