Introduction

A hash table is a data structure that implements an associative array, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Program Structure

The hash table program consists of the following components:

• Data Structure: A struct to represent a key-value pair and the hash table itself.
• Hash Function: A function to compute the index for a given key.
• Insertion Function: A function to insert a new key-value pair into the hash table.
• Search Function: A function to retrieve a value based on its key.
• Deletion Function: A function to remove a key-value pair from the hash table.
• Main Function: The entry point to the program that demonstrates the functionality of the hash table.

Code

#include 
#include 
#include 

#define TABLE_SIZE 10

// Structure to represent a key-value pair
typedef struct Item {
    char *key;
    int value;
    struct Item *next; // Pointer to handle collisions using chaining
} Item;

// Structure to represent the hash table
typedef struct HashTable {
    Item **items;
} HashTable;

// Hash function to calculate the index
unsigned int hash(const char *key) {
    unsigned long int hashval = 0;
    for (; *key != '\0'; key++) {
        hashval = (hashval << 5) + *key; // Shift left and add the ASCII value } return hashval % TABLE_SIZE; // Return index within table size } // Create a new hash table HashTable *create_table() { HashTable *table = malloc(sizeof(HashTable)); table->items = malloc(sizeof(Item*) * TABLE_SIZE);
    for (int i = 0; i < TABLE_SIZE; i++) { table->items[i] = NULL; // Initialize all slots to NULL
    }
    return table;
}

// Insert a key-value pair into the hash table
void insert(HashTable *table, const char *key, int value) {
    unsigned int index = hash(key);
    Item *new_item = malloc(sizeof(Item));
    new_item->key = strdup(key);
    new_item->value = value;
    new_item->next = table->items[index]; // Insert at the beginning (head) of the linked list
    table->items[index] = new_item;
}

// Search for a key in the hash table
int search(HashTable *table, const char *key) {
    unsigned int index = hash(key);
    Item *current = table->items[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value; // Return the value if key is found
        }
        current = current->next;
    }
    return -1; // Return -1 if key is not found
}

// Delete a key-value pair from the hash table
void delete(HashTable *table, const char *key) {
    unsigned int index = hash(key);
    Item *current = table->items[index];
    Item *prev = NULL;

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            if (prev == NULL) {
                table->items[index] = current->next; // Remove the item at the head
            } else {
                prev->next = current->next; // Bypass the current item
            }
            free(current->key);
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

// Free the hash table
void free_table(HashTable *table) {
    for (int i = 0; i < TABLE_SIZE; i++) { Item *current = table->items[i];
        while (current != NULL) {
            Item *to_delete = current;
            current = current->next;
            free(to_delete->key);
            free(to_delete);
        }
    }
    free(table->items);
    free(table);
}

// Main function to demonstrate hash table functionality
int main() {
    HashTable *table = create_table();

    insert(table, "key1", 1);
    insert(table, "key2", 2);
    insert(table, "key3", 3);

    printf("Value for 'key1': %d\n", search(table, "key1"));
    printf("Value for 'key2': %d\n", search(table, "key2"));
    printf("Value for 'key3': %d\n", search(table, "key3"));

    delete(table, "key2");
    printf("Value for 'key2' after deletion: %d\n", search(table, "key2"));

    free_table(table);
    return 0;
}

Explanation of the Code

The program is structured to define and implement a basic hash table with the following components:

Data Structures

• Item: A struct representing a key-value pair, which includes a key, a value, and a pointer to the next item for handling collisions using chaining.
• HashTable: A struct representing the hash table itself, which contains an array of pointers to Item.

Hash Function

The hash function takes a string key and computes an index by processing each character of the key. It shifts the hash value left and adds the ASCII value of the character to it, finally taking the modulus with the table size to ensure the index fits within the bounds of the array.

Core Functions

• create_table: Allocates memory for the hash table and initializes its items to NULL.
• insert: Adds a new key-value pair to the hash table, handling collisions by linking items in a linked list at the hashed index.
• search: Looks for a key in the hash table and returns its associated value, or -1 if the key is not found.
• delete: Removes a key-value pair from the hash table, also handling linked list adjustments for collisions.
• free_table: Frees allocated memory for the hash table and its items to avoid memory leaks.

Main Function

The main function demonstrates the use of the hash table by creating one, inserting key-value pairs, searching for values, and deleting a key. Finally, it frees the memory used by the hash table.

Conclusion

This basic implementation of a hash table in C provides a foundation for understanding how hash tables work. It demonstrates key concepts such as hashing, collision resolution, and memory management, which are crucial for building efficient data structures.