I've noticed a recurring trend when I mentor junior devs: they often treat the hash function as a magic box. The most common misconception I run into is the belief that if you just write a "good enough" hash function, you can essentially ignore collisions. You'll hear things like, "I'll just use a huge table and a complex algorithm; the odds of two keys hitting the same index are practically zero."

The Myth of the Perfect Hash

Here is why that line of thinking will crash your program in production. It's called the Pigeonhole Principle. If you have 11 pigeons but only 10 holes, at least one hole must contain two pigeons. In C, your "holes" are the indices of your array, and your "pigeons" are the possible keys (like every possible string a user could enter). Even if your table is massive, the "Birthday Paradox" tells us that collisions happen far sooner than our intuition suggests.

Let's look at a concrete example. Imagine a simple hash function that sums the ASCII values of a string and mods it by 10:

int hash(char *str) {
    int sum = 0;
    while (*str) sum += *str++;
    return sum % 10;
}

// "abc" -> 97+98+99 = 294. 294 % 10 = 4
// "cba" -> 99+98+97 = 294. 294 % 10 = 4

In this case, "abc" and "cba" collide. Even if you increase the table size to 1,000,000, there are still infinite combinations of strings that will sum to the same value. If you haven't written code to handle that collision, you'll either overwrite your data or end up with a corrupted table. You can't optimize your way out of a mathematical certainty.

Separate Chaining: The Linked List Approach

The most straightforward way to handle this is "Separate Chaining." Instead of the hash table array holding the data directly, it holds a pointer to a linked list. When a collision occurs, you just tack the new element onto the end (or the front) of the list at that index.

I generally recommend this approach when you aren't strictly limited by memory or when you don't know how many elements you'll be storing. It's robust and keeps the logic simple.

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

Node* table[100]; // An array of head pointers

void insert(char *key, int value) {
    int idx = hash(key);
    Node *newNode = malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->value = value;
    
    // Push to the front of the list at this bucket
    newNode->next = table[idx];
    table[idx] = newNode;
}

Open Addressing: Finding the Next Empty Seat

Now, linked lists involve a lot of malloc calls, which can be slow and fragment your memory. If you want something more cache-friendly, you use "Open Addressing." Specifically, "Linear Probing."

Instead of a list, if table[idx] is already taken, you just check table[idx + 1], then table[idx + 2], and so on, until you find an empty slot. It's like arriving at a movie theater and finding your assigned seat taken, so you just move down the row until you find a gap.

The catch? "Clustering." If several keys hash to the same area, you end up with a long block of occupied slots. This turns your beautiful $O(1)$ lookup into a slow $O(n)$ linear search through the array. I've seen systems crawl to a halt because a poor hash function created a "cluster" that spanned half the table.

typedef struct {
    char *key;
    int value;
    bool occupied;
} Entry;

Entry table[100];

void insert(char *key, int value) {
    int idx = hash(key);
    while (table[idx].occupied) {
        if (strcmp(table[idx].key, key) == 0) {
            table[idx].value = value; // Update existing key
            return;
        }
        idx = (idx + 1) % 100; // Wrap around the table
    }
    table[idx].key = strdup(key);
    table[idx].value = value;
    table[idx].occupied = true;
}

📋 Practical Task

Exercise: Building a Linear-Probing DNS Cache

Your task is to implement a simplified DNS cache that maps domain names (strings) to IP addresses (represented as integers for simplicity). You must use Open Addressing with Linear Probing to handle collisions.

Requirements:

• Create a hash table with a fixed size of 13 (using a prime number helps reduce collisions).
• Implement a hash() function that uses a simple polynomial rolling hash or a summation of characters.
• Implement void dns_insert(char *domain, int ip): If the slot is occupied by a different domain, probe linearly until an empty slot or the existing domain is found.
• Implement int dns_lookup(char *domain): Return the IP address if found, or -1 if the domain is not in the cache.
• Write a main()` function that inserts "google.com", "facebook.com", and "apple.com". Ensure that you test with domains that you suspect (or have forced) to collide based on your hash function.