C Programming: Hash Table 🎯

Welcome to our comprehensive guide on C Programming Hash Tables! This lesson is designed to be beginner-friendly yet packed with enough depth for intermediates. Let's dive in!

What is a Hash Table? 📝

A Hash Table, also known as a Dictionary or Map, is a data structure used to implement an associative array. It allows storing data values associated with keys, providing fast lookup times and efficient storage.

Why Use Hash Tables? 💡

Hash Tables are useful when you need to perform operations like searching, inserting, and deleting data in a short amount of time. They are widely used in various real-world applications, such as:

Fast Lookup: Searching for a specific key in a Hash Table is much faster compared to other data structures like arrays and linked lists.
Database Indexing: Hash Tables are used to speed up database queries by creating indexes for frequently searched columns.
Compiler Optimization: Hash Tables are used by compilers to store symbol tables for better code optimization.

C Programming Hash Table Implementation 💡

Data Structure 📝

A Hash Table in C is implemented using an array and a linked list (or other data structures like an array of arrays). Each array index represents a slot, and the linked list in that slot contains key-value pairs.

Hash Function 💡

A Hash Function is a function that converts a key into an index that can be used to access the corresponding value in the Hash Table. The hash function should ideally distribute keys evenly across the array to minimize collisions.

Collision Resolution 💡

When multiple keys hash to the same index, a collision occurs. To resolve collisions, we use techniques like Chaining, Open Addressing, etc. This lesson will focus on Chaining, where we store each key-value pair in a linked list associated with the corresponding index.

Hash Table Example in C 💡

Here's a simple example of a Hash Table implementation in C using Chaining:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10

typedef struct HashNode {
    char *key;
    char *value;
    struct HashNode *next;
} HashNode;

HashNode *create_hash_node(char *key, char *value) {
    HashNode *node = (HashNode *)malloc(sizeof(HashNode));
    node->key = key;
    node->value = value;
    node->next = NULL;
    return node;
}

int hash_function(char *key, int table_size) {
    int hash = 0;
    for (int i = 0; i < strlen(key); i++)
        hash = (hash + key[i]) % table_size;
    return hash;
}

void insert(HashNode **table, char *key, char *value) {
    int hash = hash_function(key, TABLE_SIZE);
    HashNode *node = create_hash_node(key, value);
    if (*table == NULL)
        *table = node;
    else {
        HashNode *current = *table;
        while (current != NULL) {
            if (strcmp(current->key, key) == 0) {
                printf("Key already exists. Overwriting its value.\n");
                free(current->value);
                current->value = value;
                return;
            }
            current = current->next;
        }
        node->next = *table;
        *table = node;
    }
}

void display(HashNode *node) {
    if (node == NULL)
        printf("Hash Table is empty.\n");
    else {
        printf("Hash Table:\n");
        while (node != NULL) {
            printf("Key: %s, Value: %s\n", node->key, node->value);
            node = node->next;
        }
    }
}

int main() {
    HashNode *hash_table[TABLE_SIZE] = {NULL};

    insert(&hash_table[hash_function("key1", TABLE_SIZE)], "key1", "value1");
    insert(&hash_table[hash_function("key2", TABLE_SIZE)], "key2", "value2");
    insert(&hash_table[hash_function("key1", TABLE_SIZE)], "key1", "new_value1");
    display(hash_table[hash_function("key1", TABLE_SIZE)]);

    return 0;
}

Quiz 💡

That's it for this lesson! By now, you should have a good understanding of what a Hash Table is, why it's useful, and how to implement one in C. Happy coding! 🎉