Creating a Generic Hash table in C for flexible data storage

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

Write a C program that modifies a hash table to handle a generic data type, allowing it to store and retrieve data of any type.

Sample Solution:

C Code:

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

#define TABLE_SIZE 10

// Forward declarations
struct HashTable;
typedef void (*FreeFunction)(void*);

// Function pointer type for a hash function
typedef unsigned long (*HashFunction)(const void* key);

// Structure for a key-value pair
struct KeyValuePair {
    void* key;
    void* value;
    struct KeyValuePair* next;
};

// Structure for the hash table
struct HashTable {
    int size;
    struct KeyValuePair** table;
    HashFunction hashFunction;
    FreeFunction keyFreeFunction;
    FreeFunction valueFreeFunction;
};

// Hash function for strings (djb2 algorithm)
unsigned long stringHashFunction(const void* key) {
    unsigned long hash = 5412;
    const char* str = (const char*)key;

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

    return hash;
}

// Hash function for integers
unsigned long intHashFunction(const void* key) {
    return *(const int*)key; // Simple hash for integers
}

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

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

// Function to insert a key-value pair into the hash table
void insert(struct HashTable* hashTable, const void* key, const void* value) {
    unsigned long index = hashTable->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;
}

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

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

// 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;

            if (hashTable->keyFreeFunction != NULL) {
                hashTable->keyFreeFunction(temp->key);
            }

            if (hashTable->valueFreeFunction != NULL) {
                hashTable->valueFreeFunction(temp->value);
            }

            free(temp);
        }
    }

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

int main() {
    // Example usage with string keys and integer values
    struct HashTable* stringIntTable = createHashTable(TABLE_SIZE, stringHashFunction, free, free);

    insert(stringIntTable, "Red", (const void*)malloc(sizeof(int))); // Inserting integer value
    insert(stringIntTable, "Green", (const void*)malloc(sizeof(int)));
    insert(stringIntTable, "Blue", (const void*)malloc(sizeof(int)));

    // Retrieving and printing values
    printf("Value for key 'Red': %p\n", retrieve(stringIntTable, "Red"));
    printf("Value for key 'Green': %p\n", retrieve(stringIntTable, "Green"));
    printf("Value for key 'Blue': %p\n", retrieve(stringIntTable, "Blue"));

    // Free allocated memory
    freeHashTable(stringIntTable);

    return 0;
}

Output:

Value for key 'Red': 00000000000C1470
Value for key 'Green': 00000000000C14B0
Value for key 'Blue': 00000000000C14F0

Explanation:

In the exercise above,

• Hash Function and Key-Value Pair Structures:
• Two hash functions ("stringHashFunction()" and "intHashFunction()") are defined for string and integer keys.
• The 'KeyValuePair' structure represents a key-value pair with void* pointers for generic data.
• Hash Table Structure:
• The 'HashTable' structure contains information about the hash table, including size, an array of key-value pair pointers, and function pointers for hash, key-free, and value-free functions.
• Functions:
• createKeyValuePair: Creates a new key-value pair.
• createHashTable: Creates a new hash table with specified size and function pointers.
• insert: Inserts a key-value pair into the hash table.
• retrieve: Retrieves the value associated with a key from the hash table.
• freeHashTable: Frees the memory allocated for the hash table.
• Main Function:
• Creates a hash table (stringIntTable) for string keys and integer values.
• Inserts key-value pairs into the hash table.
• Retrieves and prints values associated with specific keys.
• Frees the allocated memory for the hash table.
• Example Usage:
• The main function demonstrates the generic hash table with string keys and integer values.
• Memory allocation is done for integer values, and the free function is used to release memory when freeing the hash table.

Flowchart:

C Programming Code Editor:

Previous: C Program: Collision Resolution Performance Analysis.
Next: Creating a spell checker in C using Hash table.