- Resolution of Collisions: Collisions happen when two or more keys hash to the same index in an array. Collision resolution techniques are used to deal with these circumstances.
- Open Addressing: A sort of collision resolution method for open addressing is double hashing. If there is a collision, open addressing instructs you to insert the key-value pair in the next space in the array.
- Two Hash Functions: The two hash functions hashFunction1 and hashFunction2 are necessary for double hashing. The primary hash function, hashFunction1 should determine the key's initial index. In the event of collisions, the step size for probing the array is decided by the secondary hash function, hashFunction2.
- Double hashing with Insertion: Initially, you use hashFunction1 to get the initial index when inserting a key-value pair. HashFunction2 is used to determine the step size and probe the next slot if the initial index is filled (causing a collision). You keep probing slots until one of them is empty, and then you put the key-value pair in there.
- Search with Double Hashing: HashFunction1 is used to generate the starting index while looking for a key. The next slot is probed using hashFunction2 to calculate the step size if the key cannot be found at the first index. When you hit an empty slot (which indicates the key is not in the table), you stop exploring slots and move on.
- Initially, you use hashFunction1 to get the initial index when inserting a key-value pair.
- HashFunction2 is used to determine the step size and probe the next slot if the initial index is filled (causing a collision).
- You keep probing slots until one of them is empty, and then you put the key-value pair in there.
- HashFunction1 is used to generate the starting index while looking for a key.
- The next slot is probed using hashFunction2 to calculate the step size if the key cannot be found at the first index.
- When you hit an empty slot (which indicates the key is not in the table), you stop exploring slots and move on.
Example:
Here is an illustration of a C program that implements double hashing:
Example
#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10
// Structure to represent a hash table entry
struct HashTableEntry
{
int key;
int value;
};
// Hash table data structure
struct HashTable
{
struct HashTableEntry *table[TABLE_SIZE];
};
// Initialize the hash table
void initializeHashTable(struct HashTable* ht)
{
for (int i = 0; i < TABLE_SIZE; i++)
{
ht->table[i] = NULL;
}
}
// First hash function (for example)
int hashFunction1(int key)
{
return key % TABLE_SIZE;
}
// Second hash function (for example)
int hashFunction2(int key)
{
// Ensure it doesn't return 0 (avoiding infinite loops)
return 1 + (key % (TABLE_SIZE - 1));
}
// Insert a key-value pair into the hash table
void insert(struct HashTable* ht, int key, int value)
{
int index = hashFunction1(key);
int step = hashFunction2(key);
// Probe for an available slot using double hashing
while (ht->table[index] != NULL) {
index = (index + step) % TABLE_SIZE;
}
// Create a new entry and insert it into the table
struct HashTableEntry* entry = malloc(sizeof(struct HashTableEntry));
entry->key = key;
entry->value = value;
ht->table[index] = entry;
}
// Search for a value based on the key
int search(struct HashTable* ht, int key)
{
int index = hashFunction1(key);
int step = hashFunction2(key);
// Probe for the key using double hashing
while (ht->table[index] != NULL)
{
if (ht->table[index]->key == key)
{
return ht->table[index]->value;
}
index = (index + step) % TABLE_SIZE;
}
// Key not found
return -1;
}
int main()
{
struct HashTable ht;
initializeHashTable(&ht);
insert(&ht, 10, 42);
insert(&ht, 20, 64);
int value1 = search(&ht, 10);
int value2 = search(&ht, 20);
printf("Value for key 10: %d\n", value1); // Output: Value for key 10: 42
printf("Value for key 20: %d\n", value2); // Output: Value for key 20: 64
return 0;
}
Output:
Output
Value for key 10: 42
Value for key 20: 64
Explanation:
- In this example, we construct two structures: a HashTable structure and a HashTableEntry structure to represent key-value pairs and the hash table itself.
- The terms "hashFunction1" and "hashFunction2" refer to two hash functions.
- Using double hashing to avoid collisions, the insert function enters key-value pairs into the hash table.
- The key-value pair (10, 42) is inserted into the hash table with the syntax insert(&ht, 10, 42).
- The key-value pair (20, 64) is inserted into the hash table using the syntax insert(&ht, 20). Due to the hash functions and double hashing, it should be noted that these two keys hash to distinct locations in the table.
- The search function search(&ht, 10); looks for the value related to the key 10. Because 10 hashes to the same place as it was placed, it finds the value 42.
- The search function search(&ht, 20); looks for the value related to the key 20. Because 20 hashes to a different location than 10 does, it discovers the value 64.
- The search function uses similar double-hashing techniques to find a value based on a key.
The method of double hashing for resolving collisions involves the utilization of two separate hash functions along with open addressing to manage clashes within hash tables. When correctly executed and appropriate hash functions are chosen, this approach offers benefits such as uniform distribution of keys and efficient use of memory.