Creating a Generic Hash table in C for flexible data storage

Last update on December 20 2024 13:05:22 (UTC/GMT +8 hours)

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.