Rehashing Collision Resolution

Rehashing is the process of resizing a hash table and redistributing all existing elements into the new, larger table. It is performed when the hash table becomes too full, causing performance to degrade due to excessive collisions.

Think of it like moving to a bigger house when your family grows. You don't just add rooms to your current house; you find a larger house and move all your belongings there, organizing them in the new space more efficiently.

Why is Rehashing Necessary?

• Performance Degradation: As the hash table fills up, collisions become more frequent, increasing search and insertion times.
• Load Factor Exceeds Threshold: The load factor (α = n/m) becomes too high, making operations slower.
• Maintain O(1) Performance: Rehashing ensures that the average-case time complexity remains constant O(1).

Load Factor (α)

The load factor is the ratio of the number of elements stored in the hash table to the total number of slots.

Load Factor (α) = n / m

Where:

• n = Number of elements currently stored
• m = Total number of slots (table size)

Typical Thresholds

Note: When α exceeds these thresholds, performance degrades significantly, and rehashing should be triggered.

The Rehashing Process

Step 1: Check Load Factor

When inserting a new element, calculate the new load factor. If it exceeds the threshold, trigger rehashing.

Step 2: Create a New Table

• Create a new hash table of larger size.
• The new size is typically double the old size (or the next prime number greater than double).

Step 3: Choose a New Hash Function

• Since the table size changes, the hash function must also change.
• For example, if the old hash function was h(key) = key % old_m, the new function becomes h'(key) = key % new_m.

Step 4: Re-insert All Elements

• Traverse the old hash table.
• For each occupied slot, compute the new hash using the new hash function.
• Insert the element into the new table using the same collision resolution technique.

Step 5: Free the Old Table

• Release the memory occupied by the old table.
• Update the table pointer to point to the new table.

Detailed Example of Rehashing

Initial hash table:

• Size (m): 5
• Hash Function: h(key) = key % 5
• Collision Resolution: Separate Chaining
• Load Factor Threshold: α > 0.75

Insert the following keys in order: 1, 6, 11, 16, 21

Step 1: Insert Key 1

• h(1) = 1 % 5 = 1
• Insert at index 1.
• n = 1, m = 5, α = 0.2

Index 0: NULL
Index 1: 1 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL

Step 2: Insert Key 6

• h(6) = 6 % 5 = 1
• Collision! Insert at index 1 (chaining).
• n = 2, m = 5, α = 0.4

Index 0: NULL
Index 1: 6 → 1 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL

Step 3: Insert Key 11

• h(11) = 11 % 5 = 1
• Collision! Insert at index 1 (chaining).
• n = 3, m = 5, α = 0.6

Index 0: NULL
Index 1: 11 → 6 → 1 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL

Step 4: Insert Key 16

• h(16) = 16 % 5 = 1
• Collision! Insert at index 1 (chaining).
• n = 4, m = 5, α = 0.8

Load factor (0.8) exceeds threshold (0.75)! Trigger rehashing.

Index 0: NULL
Index 1: 16 → 11 → 6 → 1 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL

Step 5: Perform Rehashing

• New Size: 10 (double the old size, next prime is 11, but we'll use 10 for simplicity)
• New Hash Function: h'(key) = key % 10

Step 6: Re-insert All Elements

Traverse the old table and re-insert each key:

Step 7: New Table After Rehashing

Index 0: NULL
Index 1: 11 → 1 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL
Index 5: NULL
Index 6: 16 → 6 → NULL
Index 7: NULL
Index 8: NULL
Index 9: NULL

Step 8: Continue Inserting Key 21

Now insert the remaining key 21 into the new table:

• h'(21) = 21 % 10 = 1
• Insert at index 1 (chaining).
• n = 5, m = 10, α = 0.5

Final Table:

Index 0: NULL
Index 1: 21 → 11 → 1 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL
Index 5: NULL
Index 6: 16 → 6 → NULL
Index 7: NULL
Index 8: NULL
Index 9: NULL

Observation: After rehashing, the elements are now more spread out. The chain at index 1 is shorter, and keys are distributed across indices 1 and 6. Performance improves significantly.

Algorithm for Rehashing

Algorithm: Rehash(T)
Input:  T - Hash table with size m and elements
Output: New hash table T' with larger size

Step 1: START
Step 2: old_m = size of T
Step 3: new_m = 2 * old_m          // Or next prime > 2*old_m
Step 4: Create new table T' of size new_m
Step 5: Choose new hash function h'(key) = key % new_m
Step 6: FOR each element key in T DO
Step 7:     new_index = h'(key)
Step 8:     Insert key into T' at new_index using same collision resolution
Step 9: END FOR
Step 10: Free memory of T
Step 11: Return T'
Step 12: END

Implementation in C Programming

#include <stdio.h>
#include <stdlib.h>
#define INITIAL_SIZE 5
#define THRESHOLD 0.75

// Node for chaining
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Hash Table structure
typedef struct {
    Node** table;
    int size;
    int count;
} HashTable;

// Create a new hash table
HashTable* createTable(int size) {
    HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
    ht->size = size;
    ht->count = 0;
    ht->table = (Node**)calloc(size, sizeof(Node*));
    return ht;
}

// Hash function
int hashFunction(int key, int size) {
    return key % size;
}

// Insert into hash table
void insert(HashTable* ht, int key) {
    int index = hashFunction(key, ht->size);
    
    // Create new node
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = key;
    newNode->next = NULL;
    
    // Insert at beginning of chain
    if (ht->table[index] == NULL) {
        ht->table[index] = newNode;
    } else {
        newNode->next = ht->table[index];
        ht->table[index] = newNode;
    }
    ht->count++;
}

// Rehash function
void rehash(HashTable** ht) {
    printf("\n*** REHASHING TRIGGERED! ***\n");
    printf("Old size: %d, Count: %d, Load Factor: %.2f\n", 
           (*ht)->size, (*ht)->count, 
           (float)(*ht)->count / (*ht)->size);
    
    // Save old table
    HashTable* oldTable = *ht;
    int oldSize = oldTable->size;
    Node** oldArray = oldTable->table;
    
    // Create new table (double the size)
    int newSize = oldSize * 2;
    HashTable* newTable = createTable(newSize);
    
    // Re-insert all elements
    for (int i = 0; i < oldSize; i++) {
        Node* current = oldArray[i];
        while (current != NULL) {
            insert(newTable, current->data);
            current = current->next;
        }
    }
    
    // Free old table memory
    for (int i = 0; i < oldSize; i++) {
        Node* current = oldArray[i];
        while (current != NULL) {
            Node* toFree = current;
            current = current->next;
            free(toFree);
        }
    }
    free(oldArray);
    free(oldTable);
    
    // Update pointer to new table
    *ht = newTable;
    
    printf("New size: %d, Count: %d, Load Factor: %.2f\n", 
           newTable->size, newTable->count, 
           (float)newTable->count / newTable->size);
    printf("*** REHASHING COMPLETE! ***\n\n");
}

// Insert with automatic rehashing
void insertWithRehash(HashTable** ht, int key) {
    // Check load factor before insertion
    float loadFactor = (float)(*ht)->count / (*ht)->size;
    
    if (loadFactor > THRESHOLD) {
        rehash(ht);
    }
    
    insert(*ht, key);
}

// Display the hash table
void display(HashTable* ht) {
    printf("Hash Table (Size: %d, Count: %d, Load Factor: %.2f):\n", 
           ht->size, ht->count, (float)ht->count / ht->size);
    for (int i = 0; i < ht->size; i++) {
        printf("Index %d: ", i);
        Node* current = ht->table[i];
        while (current != NULL) {
            printf("%d → ", current->data);
            current = current->next;
        }
        printf("NULL\n");
    }
    printf("\n");
}

int main() {
    // Create initial table
    HashTable* ht = createTable(INITIAL_SIZE);
    
    int keys[] = {1, 6, 11, 16, 21, 26, 31};
    int n = sizeof(keys) / sizeof(keys[0]);
    
    for (int i = 0; i < n; i++) {
        printf("Inserting %d\n", keys[i]);
        insertWithRehash(&ht, keys[i]);
        display(ht);
    }
    
    return 0;
}

Output (Partial):

Inserting 1
Hash Table (Size: 5, Count: 1, Load Factor: 0.20):
Index 0: NULL
Index 1: 1 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL

Inserting 6
Hash Table (Size: 5, Count: 2, Load Factor: 0.40):
Index 0: NULL
Index 1: 6 → 1 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL

Inserting 11
Hash Table (Size: 5, Count: 3, Load Factor: 0.60):
Index 0: NULL
Index 1: 11 → 6 → 1 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL

Inserting 16

*** REHASHING TRIGGERED! ***
Old size: 5, Count: 4, Load Factor: 0.80
New size: 10, Count: 4, Load Factor: 0.40
*** REHASHING COMPLETE! ***

Hash Table (Size: 10, Count: 4, Load Factor: 0.40):
Index 0: NULL
Index 1: 11 → 1 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL
Index 5: NULL
Index 6: 16 → 6 → NULL
Index 7: NULL
Index 8: NULL
Index 9: NULL

Time and Space Complexity

Time Complexity

Explanation: Rehashing is an O(n) operation, but it happens infrequently. Over a sequence of n insertions, the total cost of rehashing is O(n), making the amortized cost O(1) per insertion.

Space Complexity

• O(n) – The hash table uses space proportional to the number of elements and the table size.

Advantages of Rehashing

1. Maintains O(1) Performance: Prevents performance degradation as the table grows.
2. Dynamic Sizing: Allows the hash table to grow automatically as needed.
3. Distributes Elements Evenly: Reduces collisions by spreading keys across more slots.
4. Improves Clustering: Reduces primary and secondary clustering.

Disadvantages of Rehashing

1. Expensive Operation: Rehashing is O(n) and can be time-consuming for large tables.
2. Memory Spike: Temporarily uses twice the memory (old + new table).
3. Performance Spike: The rehashing operation causes a sudden performance delay, which can be problematic in real-time systems.
4. Complexity: Adds complexity to the implementation.

When to Use Rehashing?

• When the hash table size is dynamic (elements are added over time).
• When you want to maintain constant-time performance.
• When you can afford occasional performance spikes.
• When the load factor exceeds a threshold.

Practice Questions

1. What is rehashing and why is it necessary in a hash table?
2. Use the hash function h(k) = k % m, where m = 5. Insert the following keys:
   25, 15, 35, 45, 55 Use linear probing for collision resolution.
   1. Show the state of the hash table after all insertions.
   2. What is the load factor?
   3. Should rehashing be triggered if threshold = 0.75?
3. Use the hash function h(k) = k % 5. Insert the keys: 25, 15, 35, 45, 55
   Use linear probing.
   1. a) Show the table
   2. b) Load factor
   3. c) Rehashing?
4. Describe the steps involved in the rehashing process.