Hash Table Operations in C: Insert, Delete, and Search

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

Write a C program that performs various operations on a hash table, including inserting, deleting, and searching for elements.

Sample Solution:

C Code:

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

#define TABLE_SIZE 10

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

// 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 delete a key-value pair from the hash table
void deleteKey(struct HashTable* hashTable, const char* key) {
    unsigned long index = hashFunction(key) % hashTable->size;
    struct KeyValuePair* current = hashTable->table[index];
    struct KeyValuePair* prev = NULL;

    // Traverse the linked list at the index
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            // Key found, delete the key-value pair
            if (prev == NULL) {
                // If the key is in the first node of the linked list
                hashTable->table[index] = current->next;
            } else {
                // If the key is in the middle or end of the linked list
                prev->next = current->next;
            }

            // Free the memory allocated for the key-value pair
            free(current);
            return;
        }

        // Move to the next node in the linked list
        prev = 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, %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);
}

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 initial hash table
    printf("Initial Hash Table:\n");
    displayHashTable(hashTable);
    printf("\n");

    // Retrieve and print 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");

    // Delete a key-value pair
    deleteKey(hashTable, "Green");

    // Display the hash table after deletion
    printf("Hash Table after Deleting 'Green':\n");
    displayHashTable(hashTable);
    printf("\n");

    // Free allocated memory
    freeHashTable(hashTable);

    return 0;
}

Output:

[1] -> (Orange, #FFA500) -> (Blue, #0000FF) -> NULL
[2] -> NULL
[3] -> NULL
[4] -> NULL
[5] -> NULL
[6] -> NULL
[7] -> NULL
[8] -> (Red, #ff0000) -> NULL
[9] -> (Yellow, #FFFF00) -> NULL

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

Hash Table after Deleting 'Green':
[0] -> NULL
[1] -> (Orange, #FFA500) -> (Blue, #0000FF) -> NULL
[2] -> NULL
[3] -> NULL
[4] -> NULL
[5] -> NULL
[6] -> NULL
[7] -> NULL
[8] -> (Red, #ff0000) -> NULL
[9] -> (Yellow, #FFFF00) -> NULL

Explanation:

In the exercise above,

Structures:

KeyValuePair: Represents a key-value pair and is used to create nodes in the linked list.
HashTable: Represents the hash table, containing a size, an array of linked lists (KeyValuePair** table), and an item count.

Hash Function (hashFunction):

Implements the djb2 algorithm to calculate the hash value of a string.

Functions:

createKeyValuePair: Allocates memory for a new key-value pair and initializes its values.
createHashTable: Allocates memory for a new hash table and initializes its size, item count, and table.
insert: Inserts a new key-value pair into the hash table, handling collisions using separate chaining. Resizes the table if needed based on the load factor threshold.
retrieve: Retrieves the value associated with a given key from the hash table.
deleteKey: Deletes a key-value pair from the hash table based on the provided key.
displayHashTable: Displays the contents of the hash table, showing the linked list structure at each index.
freeHashTable: Frees the memory allocated for the hash table and its key-value pairs.