Hash Table in C with collision Handling: Insertion, deletion, retrieval

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

Implement a basic hash table in C with functions for insertion, deletion, and retrieval of key-value pairs. Write a C program that extends the above basic hash table implementation to handle collisions using techniques such as chaining or open addressing.

Sample Solution:

C Code:

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

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

// Structure to represent a hash table
struct HashTable {
    int size;
    struct KeyValuePair** table;
};

// Function to create a new key-value pair
struct KeyValuePair* createKeyValuePair(const char* key, int value) {
    struct KeyValuePair* newPair = (struct KeyValuePair*)malloc(sizeof(struct KeyValuePair));
    if (newPair != NULL) {
        strcpy(newPair->key, key);
        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->table = (struct KeyValuePair**)calloc(size, sizeof(struct KeyValuePair*));
    }
    return newTable;
}

// Hash function to calculate the index
unsigned int hashFunction(const char* key, int tableSize) {
    unsigned int hash = 0;
    while (*key) {
        hash = (hash << 5) + *key++;
    }
    return hash % tableSize;
}

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

// Function to retrieve the value associated with a key
int retrieve(struct HashTable* hashTable, const char* key) {
    unsigned int 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 -1; // Key not found
}

// Function to remove a key-value pair from the hash table
void removeKey(struct HashTable* hashTable, const char* key) {
    unsigned int index = hashFunction(key, hashTable->size);
    struct KeyValuePair* current = hashTable->table[index];
    struct KeyValuePair* previous = NULL;

    // Traverse the linked list at the index
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            if (previous == NULL) {
                hashTable->table[index] = current->next; // Update head if it's the first node
            } else {
                previous->next = current->next; // Update pointers to remove the current node
            }

            free(current); // Free memory for the removed node
            return;
        }

        previous = current;
        current = current->next;
    }
}

// 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, %d) -> ", 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);
}

// Main function
int main() {
    struct HashTable* hashTable = createHashTable(10);

    // Insert key-value pairs
    insert(hashTable, "Endymion", 35);
    insert(hashTable, "Clover", 38);
    insert(hashTable, "Khazhak", 35);
    insert(hashTable, "Melcha", 41);
    insert(hashTable, "Taqqiq", 42); // Collision with "Endymion"
    insert(hashTable, "Ufuoma", 55); // Collision with "Khazhak"
    
    printf("Initial Hash Table:\n");
    displayHashTable(hashTable);
    printf("\n");

    // Retrieve and print values for specific keys
    printf("Value for key 'Endymion': %d\n", retrieve(hashTable, "Endymion"));
    printf("Value for key 'Taqqiq': %d\n", retrieve(hashTable, "Taqqiq"));
    printf("Value for key 'Faustus': %d\n", retrieve(hashTable, "Faustus"));
    printf("\n");

    // Remove a key-value pair
    printf("Deleting key 'Clover'\n");
    removeKey(hashTable, "Clover");
    displayHashTable(hashTable);
    printf("\n");

    // Free allocated memory
    freeHashTable(hashTable);

    return 0;
}

Output:

Initial Hash Table:
[0] -> NULL
[1] -> NULL
[2] -> (Endymion, 35) -> NULL
[3] -> NULL
[4] -> NULL
[5] -> (Melcha, 41) -> NULL
[6] -> NULL
[7] -> (Ufuoma, 55) -> NULL
[8] -> (Clover, 38) -> NULL
[9] -> (Taqqiq, 42) -> (Khazhak, 35) -> NULL

Value for key 'Endymion': 35
Value for key 'Taqqiq': 42
Value for key 'Faustus': -1

Deleting key 'Clover'
[0] -> NULL
[1] -> NULL
[2] -> (Endymion, 35) -> NULL
[3] -> NULL
[4] -> NULL
[5] -> (Melcha, 41) -> NULL
[6] -> NULL
[7] -> (Ufuoma, 55) -> NULL
[8] -> NULL
[9] -> (Taqqiq, 42) -> (Khazhak, 35) -> NULL

Explanation:

In the exercise above,

• Structures:
• KeyValuePair: Represents a key-value pair with a key (string), value (integer), and a pointer to the next KeyValuePair (for handling collisions).
• HashTable: Represents a hash table with a specified size and an array of pointers to KeyValuePairs.
• Functions:
• createKeyValuePair: Creates a new key-value pair and initializes its members.
• createHashTable: Creates a new hash table and allocates memory for the array of pointers.
• hashFunction: Calculates the index for a key using a simple hash function.
• insert: Inserts a key-value pair into the hash table, handling collisions using chaining.
• retrieve: Retrieves the value associated with a given key from the hash table.
• removeKey: Removes a key-value pair from the hash table.
• displayHashTable: Displays the contents of the hash table, including linked lists for collisions.
• freeHashTable: Frees the memory allocated for the hash table.
• Main Function:
• Creates a hash table with a size of 10.
• Inserts several key-value pairs into the hash table, intentionally causing collisions.
• Displays the initial state of the hash table.
• Retrieves and prints values for specific keys.
• Deletes a key-value pair.
• Displays the updated hash table.
• Frees allocated memory.

Flowchart:

C Programming Code Editor:

Previous: Basic Hash table implementation in C: Insertion, deletion, and retrieval.
Next: C Program: String Hash function and Hash table.