Double Hashing Collision Resolution

Double Hashing is a collision resolution technique used in open addressing hash tables. It is considered one of the best open addressing techniques because it eliminates both primary and secondary clustering.

When a collision occurs, Double Hashing uses a second hash function to determine the probe step size. Unlike linear probing (step size = 1) and quadratic probing (step size = i²), the step size in double hashing varies depending on the key itself. This means that different keys will follow completely different probe sequences, even if they hash to the same initial index.

Think of it like finding a parking spot in a huge, multi-level garage. Your first hash tells you which floor to go to. If that spot is taken, your second hash tells you exactly how many spots to skip before checking the next one. Since this "skip number" is different for every car, cars don't form long chains.

The Probing Sequence

The formula for Double Hashing is:

h'(key) = (h1(key) + i * h2(key)) % Table_Size

Where:

• h1(key) is the primary hash function (gives the initial index).
• h2(key) is the secondary hash function (determines the step size).
• i is the probe number (0, 1, 2, 3,...).
• Crucial Rule: h2(key) must never be 0, and ideally should be relatively prime to the table size.

Choosing h2(key)

A good secondary hash function should:

1. Never return 0.
2. Be fast to compute.
3. Produce values that are relatively prime to the table size.

A very common and effective choice is:

h2(key) = 7 - (key % 7)

or more generally:

h2(key) = R - (key % R)

where R is a prime number smaller than the table size.

How Double Hashing Works?

Let's use a hash table of size 11 (m = 11). We'll use:

• Primary hash function: h1(key) = key % 11
• Secondary hash function: h2(key) = 7 - (key % 7)

Insert the following keys in this exact order 14, 25, 36, 47, 58.

Step 1: Initialize the Hash Table

We start with an empty table of size 11.

Index:  0  1  2  3  4  5  6  7  8  9  10
       [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]

Step 2: Insert Key 14

• Calculate h1(14) = 14 % 11 = 3.
• Calculate h2(14) = 7 - (14 % 7) = 7 - 0 = 7.
• Check index 3 (i=0). It is empty.
• Insert 14 at index 3.

Index:  0  1  2  3  4  5  6  7  8  9  10
       [ ][ ][ ][14][ ][ ][ ][ ][ ][ ][ ]

Step 3: Insert Key 25

• Calculate h1(25) = 25 % 11 = 3.
• Calculate h2(25) = 7 - (25 % 7) = 7 - 4 = 3.
• Check index 3 (i=0). It is occupied (by 14). Collision!
• Probe Sequence:
  • i = 1: (3 + 1 * 3) % 11 = 6. Check index 6. It is empty.
• Insert 25 at index 6.

Index:  0  1  2  3  4  5  6  7  8  9  10
       [ ][ ][ ][14][ ][ ][25][ ][ ][ ][ ]

Step 4: Insert Key 36

• Calculate h1(36) = 36 % 11 = 3.
• Calculate h2(36) = 7 - (36 % 7) = 7 - 1 = 6.
• Check index 3 (i=0). It is occupied (by 14). Collision!
• Probe Sequence:
  • i = 1: (3 + 1 * 6) % 11 = 9. Check index 9. It is empty.
• Insert 36 at index 9.

Index:  0  1  2  3  4  5  6  7  8  9  10
       [ ][ ][ ][14][ ][ ][25][ ][ ][36][ ]

Step 5: Insert Key 47

• Calculate h1(47) = 47 % 11 = 3.
• Calculate h2(47) = 7 - (47 % 7) = 7 - 5 = 2.
• Check index 3 (i=0). It is occupied (by 14). Collision!
• Probe Sequence:
  • i = 1: (3 + 1 * 2) % 11 = 5. Check index 5. It is empty.
• Insert 47 at index 5.

Index:  0  1  2  3  4  5  6  7  8  9  10
       [ ][ ][ ][14][ ][47][25][ ][ ][36][ ]

Step 6: Insert Key 58

• Calculate h1(58) = 58 % 11 = 3.
• Calculate h2(58) = 7 - (58 % 7) = 7 - 2 = 5.
• Check index 3 (i=0). It is occupied (by 14). Collision!
• Probe Sequence:
  • i = 1: (3 + 1 * 5) % 11 = 8. Check index 8. It is empty.
• Insert 58 at index 8.

Final Hash Table

Index:  0  1  2  3  4  5  6  7  8  9  10
       [ ][ ][ ][14][ ][47][25][ ][58][36][ ]

Observation: Notice how the keys are spread out beautifully. Even though all keys had the same primary hash (3), they followed different probe sequences (step sizes 7, 3, 6, 2, 5). There is no clustering at all.

Algorithm for Double Hashing

Insertion Algorithm

Algorithm: DoubleHashInsert(T, key)
Input:  T - Hash table of size m
        key - Key to insert
Output: None (or error if table is full)

Step 1: START
Step 2: index = h1(key)        // Primary hash
Step 3: step = h2(key)         // Secondary hash (step size)
Step 4: i = 0
Step 5: WHILE i < m DO
Step 6:     probe = (index + i * step) % m
Step 7:     IF T[probe] is empty THEN
Step 8:         T[probe] = key
Step 9:         RETURN (Success)
Step 10:    ELSE
Step 11:        i = i + 1
Step 12: END WHILE
Step 13: RETURN (Table Full Error)
Step 14: END

Search Algorithm

Algorithm: DoubleHashSearch(T, key)
Input:  T - Hash table of size m
        key - Key to search
Output: Index of the key if found, otherwise -1

Step 1: START
Step 2: index = h1(key)
Step 3: step = h2(key)
Step 4: i = 0
Step 5: WHILE i < m DO
Step 6:     probe = (index + i * step) % m
Step 7:     IF T[probe] == key THEN
Step 8:         RETURN probe
Step 9:     IF T[probe] is empty THEN
Step 10:        RETURN -1     // Key not present
Step 11:    i = i + 1
Step 12: END WHILE
Step 13: RETURN -1
Step 14: END

Implementation in C Programming

#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 11
#define EMPTY -1

int hashTable[TABLE_SIZE];

// Initialize hash table
void initialize() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = EMPTY;
    }
}

// Primary hash function
int h1(int key) {
    return key % TABLE_SIZE;
}

// Secondary hash function (must never return 0)
int h2(int key) {
    return 7 - (key % 7);  // Returns values from 1 to 7
}

// Insert using Double Hashing
void insert(int key) {
    int index = h1(key);
    int step = h2(key);
    int i = 0;
    
    while (i < TABLE_SIZE) {
        int probe = (index + i * step) % TABLE_SIZE;
        
        if (hashTable[probe] == EMPTY) {
            hashTable[probe] = key;
            printf("Inserted %d at index %d (step=%d, i=%d)\n", key, probe, step, i);
            return;
        }
        i++;
    }
    
    printf("Hash table is full! Could not insert %d\n", key);
}

// Search using Double Hashing
int search(int key) {
    int index = h1(key);
    int step = h2(key);
    int i = 0;
    
    while (i < TABLE_SIZE) {
        int probe = (index + i * step) % TABLE_SIZE;
        
        if (hashTable[probe] == key) {
            return probe;  // Found
        }
        
        // If we find an empty slot, key is not present
        if (hashTable[probe] == EMPTY) {
            return -1;
        }
        i++;
    }
    return -1;  // Not found
}

// Display the table
void display() {
    printf("\nHash Table (Double Hashing):\n");
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("Index %d: %d\n", i, hashTable[i]);
    }
}

int main() {
    initialize();
    
    int keys[] = {14, 25, 36, 47, 58};
    int n = sizeof(keys) / sizeof(keys[0]);
    
    for (int i = 0; i < n; i++) {
        insert(keys[i]);
    }
    
    display();
    
    int key = 47;
    int result = search(key);
    if (result != -1) {
        printf("\nElement %d found at index %d.\n", key, result);
    } else {
        printf("\nElement %d not found.\n", key);
    }
    
    return 0;
}

Output:

Inserted 14 at index 3 (step=7, i=0)
Inserted 25 at index 6 (step=3, i=1)
Inserted 36 at index 9 (step=6, i=1)
Inserted 47 at index 5 (step=2, i=1)
Inserted 58 at index 8 (step=5, i=1)

Hash Table (Double Hashing):
Index 0: -1
Index 1: -1
Index 2: -1
Index 3: 14
Index 4: -1
Index 5: 47
Index 6: 25
Index 7: -1
Index 8: 58
Index 9: 36
Index 10: -1

Element 47 found at index 5.

Complexity Analysis

Time Complexity

Explanation: Double hashing provides the best average-case performance among open addressing techniques because it eliminates clustering. With a good secondary hash function and a load factor below 0.7, performance is excellent.

Space Complexity

• O(1) – Only constant extra memory is used.

Advantages of Double Hashing

1. No Primary Clustering: Since the step size is not fixed, keys don't form long contiguous blocks.
2. No Secondary Clustering: Keys with the same primary hash follow different probe sequences (because their step sizes are different).
3. Excellent Performance: Provides the best distribution among open addressing techniques.
4. More Uniform Distribution: Keys are spread evenly across the table.

Disadvantages of Double Hashing

1. Slightly Slower: Requires computing two hash functions, which takes a bit more time (but the difference is negligible compared to the time saved by reduced clustering).
2. More Complex: Slightly more complex to implement than linear or quadratic probing.
3. Requires Careful Design: The secondary hash function must never return 0 and should produce values relatively prime to the table size.
4. Table Size Restriction: For best results, the table size should be prime, and the secondary hash function should produce values less than the table size.

Comparison of Open Addressing Techniques

When to Choose Double Hashing?

Choose Double Hashing when:

• You want the best performance among open addressing techniques.
• You want to completely eliminate clustering.
• You can afford to compute two hash functions.
• You can choose a prime table size and design a good secondary hash function.

Practice Questions

1. Insert the following keys using double hashing into a table of size 11 and Secondary hash R = 7. Keys {10, 22, 31, 4, 15, 28, 17, 88, 59, 3, 6, 12, 32}. Use the given hash functions and resolve collisions using double hashing.
2. Insert the following keys using Double Hashing into a table of size 23 with Secondary Hash R = 9. Keys: {5, 14, 27, 41, 52, 66, 70, 85, 90, 102, 111, 120, 133, 145, 151}
   • h1(key) = key mod  23
   • h2(key) = 9−(key mod  9)
3. Insert the following keys using Double Hashing into a table of size 13 and Secondary Hash R = 5. Keys: {25, 38, 44, 59, 77, 91, 33, 50, 67, 29, 81}
   • h₁(key) = key mod  13
   • h₂(key) = 5−(key mod  5)
4. Insert the following keys using Double Hashing into a table of size 17 with Secondary Hash R = 7. Keys: {10, 21, 35, 48, 62, 70, 81, 93, 104, 119, 131, 144}
   • h₁(key) = key mod  17
   • h₂(key) = 7−(key mod  7)
5. Insert the following keys using Double Hashing into a table of size 19 and Secondary Hash R = 11. Keys: {22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132}
   • h₁(key) = key mod  19
   • h₂(key) = 11−(key mod  11)