I've noticed a recurring pattern when students first approach hash tables in C: they treat the "key" as if it were already an index. They think, "If I want to store data for user 'bob', I'll just put it in the slot for 'bob'." But 'bob' isn't a number. Even if you use the ASCII values of the characters, you'll quickly realize that you can't allocate an array large enough to hold every possible string combination. If you tried to map every possible 8-character username to a unique array index, you'd need more memory than exists on earth.

The Myth: Keys are Indices

Imagine you're building a simple phonebook. You might think you can just use the first letter of the name as the index. 'A' goes to 0, 'B' goes to 1, and so on. It seems elegant until you realize that "Alice" and "Andrew" both want to live in slot 0. If you simply overwrite the data, Andrew vanishes. If you try to make the array huge enough to give every single name its own spot, your program will crash with a segmentation fault long before it starts, because you're asking the OS for a contiguous block of memory that simply isn't available.

The Reality: Mapping and Collisions

The trick is to use a hash function. This is just a piece of logic that takes a variable-length input (like a string) and spits out a fixed-size integer. We then use the modulo operator (%) to force that integer into the bounds of our actual array size. I usually recommend the djb2 algorithm for simple projects because it's fast and distributes keys surprisingly well.

unsigned long hash_function(char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    return hash;
}

But here is the catch: no hash function is perfect. Two different strings will eventually hash to the same index. We call this a collision. Since we can't avoid them, we have to manage them. The most straightforward way in C is "Chaining." Instead of storing the value directly in the array, we store a pointer to a linked list. Each slot in our table becomes the "head" of a list of all items that happened to hash to that index.

Wiring the Chain

To build this, you need a structure for the entry and a structure for the table itself. I like to keep the entry simple: the key, the value, and a pointer to the next entry in the chain. When you insert a new item, you hash the key, go to that index, and prepended the new entry to the front of the linked list. It's O(1) for insertion, which is why hash tables are so loved.

typedef struct Entry {
    char *key;
    int value;
    struct Entry *next;
} Entry;

typedef struct HashTable {
    int size;
    Entry **buckets;
} HashTable;

HashTable* create_table(int size) {
    HashTable *table = malloc(sizeof(HashTable));
    table->size = size;
    table->buckets = calloc(size, sizeof(Entry*));
    return table;
}

When you want to retrieve a value, you hash the key again, jump to the bucket, and then walk down the linked list comparing the search key with the Entry->key using strcmp. If the list is short—which it should be if your table size is reasonable—this happens almost instantaneously.

📋 Practical Task

Exercise: Building a Case-Insensitive Word Frequency Counter

Your task is to implement a hash table that counts the occurrences of words in a provided list of strings. However, there's a twist: the counter must be case-insensitive (e.g., "Apple", "apple", and "APPLE" should all increment the same counter).

Requirements:

• Implement a insert_word(HashTable *table, char *word) function that increments the value associated with a word. If the word doesn't exist yet, create a new entry with a value of 1.
• Ensure that the hash function and the lookup process treat "Hello" and "hello" as the same key.
• Implement a print_frequencies(HashTable *table) function that iterates through every bucket and every node in the chains to print the final counts.
• Properly free all allocated memory for the entries and the table buckets before the program exits.

Starter Hint: You can use tolower() from <ctype.h> to normalize your strings before hashing or comparing them.