Basic Hash table implementation in C: Insertion, deletion, and retrieval

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

Write a C program that implements a basic hash table with functions for insertion, deletion, and retrieval of key-value pairs.

Sample Solution:

C Code:

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

// Define a structure to represent key-value pairs
struct KeyValuePair {
    char key[50];
    int value;
    struct KeyValuePair* next;
};

// Define a structure to represent the 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;
}

// Function to calculate the hash value of a key
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);
    struct KeyValuePair* newPair = createKeyValuePair(key, value);
    newPair->next = hashTable->table[index];
    hashTable->table[index] = newPair;
}

// Function to retrieve the value associated with a key from the hash table
int retrieve(struct HashTable* hashTable, const char* key) {
    unsigned int index = hashFunction(key, hashTable->size);
    struct KeyValuePair* current = hashTable->table[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }
    return -1; // Return -1 if the key is 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;

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            if (previous == NULL) {
                hashTable->table[index] = current->next;
            } else {
                previous->next = current->next;
            }

            free(current);
            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() {
    // Create a hash table with a size of 10
    struct HashTable* hashTable = createHashTable(10);

    // Insert key-value pairs into the hash table
    insert(hashTable, "Alaric", 35);
    insert(hashTable, "Faustus", 28);
    insert(hashTable, "Wilbur", 30);
    insert(hashTable, "Melcha", 31);

    // Display the initial state of the hash table
    printf("Initial Hash Table:\n");
    displayHashTable(hashTable);
    printf("\n");

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

    // Remove a key-value pair and display the updated hash table
    printf("Deleting key 'Faustus'\n");
    removeKey(hashTable, "Faustus");
    displayHashTable(hashTable);
    printf("\n");

    // Free the memory allocated for the hash table
    freeHashTable(hashTable);

    return 0;
}

Output:

Initial Hash Table:
[0] -> NULL
[1] -> (Faustus, 28) -> NULL
[2] -> NULL
[3] -> NULL
[4] -> NULL
[5] -> (Melcha, 31) -> NULL
[6] -> NULL
[7] -> NULL
[8] -> (Wilbur, 30) -> NULL
[9] -> (Alaric, 35) -> NULL

Value for key 'Alaric': 35
Value for key 'Faustus': 28
Value for key 'Cambria': -1

Deleting key 'Faustus'
[0] -> NULL
[1] -> NULL
[2] -> NULL
[3] -> NULL
[4] -> NULL
[5] -> (Melcha, 31) -> NULL
[6] -> NULL
[7] -> NULL
[8] -> (Wilbur, 30) -> NULL
[9] -> (Alaric, 35) -> NULL

Explanation:

In the exercise above,

• Structures:
• KeyValuePair: Represents a key-value pair with a key (string) and a value (integer), and a pointer to the next pair in case of collision.
• HashTable: Represents a hash table with a specified size and an array of pointers to KeyValuePair.
• Functions:
• createKeyValuePair: Allocates memory for a new key-value pair and initializes its values.
• createHashTable: Allocates memory for a new hash table with a specified size and initializes its array of pointers.
• hashFunction: Calculates the hash value of a given key using a simple hashing algorithm.
• insert: Inserts a new key-value pair into the hash table using the calculated hash value.
• retrieve: Retrieves the value associated with a key from the hash table.
• removeKey: Removes a key-value pair from the hash table.
• displayHashTable: Displays the contents of the hash table, including chains in case of collisions.
• freeHashTable: Frees the memory allocated for the hash table, including all key-value pairs.
• Main Function:
• Creates a hash table with a size of 10.
• Inserts several key-value pairs into the hash table.
• Displays the initial state of the hash table.
• Retrieves and prints values for specific keys.
• Removes a key-value pair and displays the updated hash table.
• Frees the memory allocated for the hash table.

Flowchart:

C Programming Code Editor:

Previous: C Program: Hash Table Implementation and Operations Home.
Next: Hash Table in C with collision Handling: Insertion, deletion, retrieval.