Implementing dynamic resizing in a C Hash table

C Program to implement Hash Tables: Exercise-4 with Solution

Write a C program that implements dynamic resizing in a hash table to automatically adjust its size when the load factor exceeds a certain threshold.

Sample Solution:

C Code:

// Including necessary header files
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10
#define LOAD_FACTOR_THRESHOLD 0.7

// Forward declarations
struct HashTable* createHashTable(int size);
void resizeHashTable(struct HashTable* hashTable, int newSize);
void insert(struct HashTable* hashTable, const char* key, const char* value);
const char* retrieve(struct HashTable* hashTable, const char* key);
void displayHashTable(struct HashTable* hashTable);
void freeHashTable(struct HashTable* hashTable);

// Structure for a key-value pair
struct KeyValuePair {
    char key[50];
    char value[50];
    struct KeyValuePair* next;
};

// Structure for the hash table
struct HashTable {
    int size;
    int itemCount;
    struct KeyValuePair** table;
};
// Hash function for strings (djb2 algorithm)
unsigned long hashFunction(const char* str) {
    unsigned long hash = 5381;
    int c;

    while ((c = *str++) != '\0') {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }

    return hash;
}

// Function to create a new key-value pair
struct KeyValuePair* createKeyValuePair(const char* key, const char* value) {
    struct KeyValuePair* newPair = (struct KeyValuePair*)malloc(sizeof(struct KeyValuePair));
    if (newPair != NULL) {
        strcpy(newPair->key, key);
        strcpy(newPair->value, value);
        newPair->next = NULL;
    }
    return newPair;
}

// Function to create a new hash table
struct HashTable* createHashTable(int size) {
    struct HashTable* newTable = (struct HashTable*)malloc(sizeof(struct HashTable));
    if (newTable != NULL) {
        newTable->size = size;
        newTable->itemCount = 0;
        newTable->table = (struct KeyValuePair**)calloc(size, sizeof(struct KeyValuePair*));
    }
    return newTable;
}

// Function to insert a key-value pair into the hash table
void insert(struct HashTable* hashTable, const char* key, const char* value) {
    unsigned long index = hashFunction(key) % hashTable->size;

    // Create a new key-value pair
    struct KeyValuePair* newPair = createKeyValuePair(key, value);

    // Insert the new pair at the beginning of the linked list
    newPair->next = hashTable->table[index];
    hashTable->table[index] = newPair;

    // Update the item count
    hashTable->itemCount++;

    // Check if resizing is needed
    if ((double)hashTable->itemCount / hashTable->size > LOAD_FACTOR_THRESHOLD) {
        resizeHashTable(hashTable, hashTable->size * 2); // Resize to double the current size
    }
}

// Function to retrieve the value associated with a key
const char* retrieve(struct HashTable* hashTable, const char* key) {
    unsigned long index = hashFunction(key) % hashTable->size;
    struct KeyValuePair* current = hashTable->table[index];

    // Traverse the linked list at the index
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value; // Key found, return the value
        }
        current = current->next;
    }
    return "Key not found"; // Key not found
}

// Function to display the contents of the hash table
void displayHashTable(struct HashTable* hashTable) {
    for (int i = 0; i < hashTable->size; i++) {
        printf("[%d] -> ", i);

        struct KeyValuePair* current = hashTable->table[i];
        while (current != NULL) {
            printf("(%s, %s) -> ", current->key, current->value);
            current = current->next;
        }

        printf("NULL\n");
    }
}

// Function to free the memory allocated for the hash table
void freeHashTable(struct HashTable* hashTable) {
    for (int i = 0; i < hashTable->size; i++) {
        struct KeyValuePair* current = hashTable->table[i];
        while (current != NULL) {
            struct KeyValuePair* temp = current;
            current = current->next;
            free(temp);
        }
    }

    free(hashTable->table);
    free(hashTable);
}

// Function to resize the hash table
void resizeHashTable(struct HashTable* hashTable, int newSize) {
    // Create a new hash table with the specified size
    struct HashTable* newTable = createHashTable(newSize);

    // Rehash and insert all existing key-value pairs into the new table
    for (int i = 0; i < hashTable->size; i++) {
        struct KeyValuePair* current = hashTable->table[i];
        while (current != NULL) {
            insert(newTable, current->key, current->value);
            current = current->next;
        }
    }

    // Update the hash table with the new size and table
    hashTable->size = newSize;
    free(hashTable->table);
    hashTable->table = newTable->table;

    // Free the memory allocated for the new table structure
    free(newTable);
}

// Rest of the code...

int main() {
    // Example usage
    struct HashTable* hashTable = createHashTable(TABLE_SIZE);

    // Insert key-value pairs
    insert(hashTable, "Red", "#ff0000");
    insert(hashTable, "Green", "#008000");
    insert(hashTable, "Blue", "#0000FF");
    insert(hashTable, "Yellow", "#FFFF00");
    insert(hashTable, "Orange", "#FFA500");

    // Display the hash table
    printf("Initial Hash Table:\n");
    // Display the initial hash table
    // Display the values for specific keys
    printf("Value for key 'Red': %s\n", retrieve(hashTable, "Red"));
    printf("Value for key 'Yellow': %s\n", retrieve(hashTable, "Yellow"));
    printf("Value for key 'White': %s\n", retrieve(hashTable, "White"));
    printf("\n");

    // Free allocated memory
    freeHashTable(hashTable);

    return 0;
}

Output:

Initial Hash Table:
Value for key 'Red': #ff0000
Value for key 'Yellow': #FFFF00
Value for key 'White': Key not found

Explanation:

In the exercise above -

• Header Files and Definitions:
• The code includes standard C libraries (stdio.h, stdlib.h, string.h) and defines constants like TABLE_SIZE and LOAD_FACTOR_THRESHOLD for hash table sizing.
• Structures:
• KeyValuePair: Represents a key-value pair with fields for the key, value, and a pointer to the next key-value pair in case of collision.
• HashTable: Represents the hash table structure with fields for size, item count, and an array of pointers to key-value pairs.
• Hash Function (hashFunction):
• Implements the djb2 algorithm to generate a hash value for a given string key.
• Functions:
• createKeyValuePair: Allocates memory and creates a new key-value pair.
• createHashTable: Allocates memory and creates a new hash table with a specified size.
• insert: Inserts a key-value pair into the hash table, handling collisions using separate chaining.
• retrieve: Retrieves the value associated with a given key from the hash table.
• displayHashTable: Displays the contents of the hash table, including chained key-value pairs.
• freeHashTable: Frees the memory allocated for the entire hash table.
• resizeHashTable: Resizes the hash table when the load factor exceeds a specified threshold.
• Main Function (main):
• Illustrates an example usage of the hash table.
• Inserts key-value pairs into the hash table.
• Retrieves and prints values for specific keys.
• Displays the initial hash table and values for specific keys.
• Frees the allocated memory for the hash table.

Flowchart:

C Programming Code Editor:

Previous: C Program: String Hash function and Hash table.
Next: Hash Table Operations in C: Insert, Delete, and Search.