C Hash Tables

A hash table (also called a hash map) is a data structure that stores key-value pairs and lets you insert, look up, and delete them in average constant time, no matter how many items it holds. Instead of scanning a list from the front, a hash table uses a hash function to turn a key directly into an array index, jumping straight to the right slot. C has no built-in hash table type like Python’s dict or C++’s unordered_map, so building one yourself is one of the best ways to understand what every hash table is really doing underneath. This lesson builds a complete string-keyed hash table from scratch, using an array of buckets and separate chaining to resolve collisions.

Overview: How Hash Tables Work

A hash table is built from two pieces: a fixed-size array of buckets, and a hash function that converts any key into an integer. To store a value, you hash the key, reduce that hash to a valid array index with the modulo operator (hash % table_size), and place the value in that bucket. To look the value back up, you hash the same key again, land on the same index, and read the value straight out — no linear searching required, in the ideal case.

In memory, a simple hash table for string keys looks like this: a struct holding an array of pointers, Entry *buckets[TABLE_SIZE]. Each pointer is either NULL (empty bucket) or points to the first node of a linked list. Each Entry node owns a heap-allocated copy of the key string, a value, and a pointer to the next entry in the same bucket. One linked list per bucket is called separate chaining, and it’s the approach used in this lesson because it maps naturally onto C’s manual memory management.

Collisions are unavoidable: a hash function maps a huge space of possible keys onto a small array, so by the pigeonhole principle, different keys will sometimes land on the same index. What matters is how the table handles it. The two common strategies are:

Strategy	How it works	Trade-off
Separate chaining	Each bucket holds a linked list; colliding keys are appended to that list	Simple and never "fills up," but adds pointer overhead per entry
Open addressing	On collision, probe forward (linearly, quadratically, or with a second hash) for the next free slot	No extra pointers and more cache-friendly, but the array can fill up and deletion is trickier

A good hash function is deterministic (the same key always produces the same hash), fast to compute, and spreads keys uniformly across the array so buckets stay short. A weak hash function — for example, using only a string’s length, or just its first character — causes many keys to pile into the same few buckets, degrading every operation toward O(n). This lesson uses djb2, a widely used and well-distributed string hash algorithm: start with a seed value of 5381, and for every character update the running hash as hash * 33 + character.

Load Factor and Resizing

Performance also depends on the load factor: the ratio of stored entries to the number of buckets (count / table_size). A low load factor means short chains and operations close to O(1). As the load factor climbs past roughly 0.7–1.0, chains get longer and performance degrades toward a plain linked list’s O(n). Production-quality hash tables handle this with rehashing: allocating a larger bucket array (commonly double the size) and reinserting every existing entry once the load factor crosses a threshold. The examples below use a fixed table size to keep the code focused, but Practice Exercise 2 asks you to add rehashing yourself.

Operation	Average case	Worst case
Insert	O(1)	O(n)
Search	O(1)	O(n)
Delete	O(1)	O(n)

The worst case happens when every key hashes into the same bucket, turning the table into one long linked list. With a decent hash function and a reasonable load factor this is rare in practice — average-case constant time is exactly why hash tables are the go-to structure for caches, symbol tables, dictionaries, and sets.

Syntax

C doesn’t ship a hash table type, so "syntax" here means the standard shape you build by hand: a node type for entries, a table type holding the bucket array, and a small set of functions that all start the same way — hash the key, then reduce it to an index with %.

#include <stdio.h>

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

typedef struct {
    Entry *buckets[101];
    int count;
} HashTable;

unsigned long hash_string(const char *key);
void ht_init(HashTable *table);
void ht_insert(HashTable *table, const char *key, int value);
int  ht_search(HashTable *table, const char *key, int *value_out);
int  ht_delete(HashTable *table, const char *key);

int main(void)
{
    printf("Hash table skeleton compiled successfully.\n");
    return 0;
}

Output:

Hash table skeleton compiled successfully.

• Entry — one linked-list node: an owned copy of the key, the stored value, and a pointer to the next entry in the same bucket.
• HashTable — the array of bucket head pointers plus a running count of stored entries.
• hash_string — turns a const char * key into an unsigned long hash value.
• ht_init — sets every bucket to NULL and count to 0 before first use.
• ht_insert, ht_search, ht_delete — the core operations, each starting by hashing the key and reducing it to a bucket index.

Examples

Example 1: A String Hash Function in Action

Before building the full table, it helps to see the hash function alone. This program hashes three words with djb2 and reduces each hash to an index for a table of size 7.

#include <stdio.h>

unsigned long hash_string(const char *str)
{
    unsigned long hash = 5381;
    int c;

    while ((c = *str++) != '\0')
        hash = ((hash << 5) + hash) + (unsigned long)c; /* hash * 33 + c */

    return hash;
}

int main(void)
{
    const char *words[] = {"cat", "dog", "bird"};
    int table_size = 7;

    for (int i = 0; i < 3; i++) {
        unsigned long h = hash_string(words[i]);
        printf("%s -> hash=%lu, index=%d\n",
               words[i], h, (int)(h % table_size));
    }

    return 0;
}

Output:

cat -> hash=193488125, index=5
dog -> hash=193489663, index=3
bird -> hash=6385080934, index=1

Notice the hash values themselves are large and look nothing alike, but hash % table_size squeezes each one down into a valid array index between 0 and 6. Different words, even short and similar-looking ones, land on different indexes here — but with only 7 buckets and enough words, some will eventually collide, which is exactly what chaining is for.

Example 2: A Complete Hash Table With Chaining

This is the full implementation: ht_init, ht_insert, ht_search, ht_delete, and ht_free, tracking a fruit-to-price table.

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

#define TABLE_SIZE 101

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

typedef struct {
    Entry *buckets[TABLE_SIZE];
    int count;
} HashTable;

unsigned long hash_string(const char *str)
{
    unsigned long hash = 5381;
    int c;

    while ((c = *str++) != '\0')
        hash = ((hash << 5) + hash) + (unsigned long)c;

    return hash;
}

void ht_init(HashTable *table)
{
    for (int i = 0; i < TABLE_SIZE; i++)
        table->buckets[i] = NULL;
    table->count = 0;
}

void ht_insert(HashTable *table, const char *key, int value)
{
    unsigned long index = hash_string(key) % TABLE_SIZE;
    Entry *cur = table->buckets[index];

    while (cur != NULL) {
        if (strcmp(cur->key, key) == 0) {
            cur->value = value; /* key already exists: update it */
            return;
        }
        cur = cur->next;
    }

    Entry *entry = malloc(sizeof(Entry));
    entry->key = malloc(strlen(key) + 1);
    strcpy(entry->key, key);
    entry->value = value;
    entry->next = table->buckets[index];
    table->buckets[index] = entry;
    table->count++;
}

int ht_search(HashTable *table, const char *key, int *value_out)
{
    unsigned long index = hash_string(key) % TABLE_SIZE;
    Entry *cur = table->buckets[index];

    while (cur != NULL) {
        if (strcmp(cur->key, key) == 0) {
            *value_out = cur->value;
            return 1;
        }
        cur = cur->next;
    }
    return 0;
}

int ht_delete(HashTable *table, const char *key)
{
    unsigned long index = hash_string(key) % TABLE_SIZE;
    Entry *cur = table->buckets[index];
    Entry *prev = NULL;

    while (cur != NULL) {
        if (strcmp(cur->key, key) == 0) {
            if (prev == NULL)
                table->buckets[index] = cur->next;
            else
                prev->next = cur->next;
            free(cur->key);
            free(cur);
            table->count--;
            return 1;
        }
        prev = cur;
        cur = cur->next;
    }
    return 0;
}

void ht_free(HashTable *table)
{
    for (int i = 0; i < TABLE_SIZE; i++) {
        Entry *cur = table->buckets[i];
        while (cur != NULL) {
            Entry *next = cur->next;
            free(cur->key);
            free(cur);
            cur = next;
        }
    }
}

int main(void)
{
    HashTable table;
    ht_init(&table);

    ht_insert(&table, "apple", 10);
    ht_insert(&table, "banana", 20);
    ht_insert(&table, "cherry", 30);
    ht_insert(&table, "date", 40);

    int value;

    if (ht_search(&table, "banana", &value))
        printf("banana -> %d\n", value);

    if (!ht_search(&table, "grape", &value))
        printf("grape not found\n");

    printf("Item count before delete: %d\n", table.count);

    ht_delete(&table, "apple");

    if (!ht_search(&table, "apple", &value))
        printf("apple not found after delete\n");

    printf("Item count after delete: %d\n", table.count);

    ht_free(&table);
    return 0;
}

Output:

banana -> 20
grape not found
Item count before delete: 4
apple not found after delete
Item count after delete: 3

Four fruits go in, so count is 4. Searching for "banana" walks its bucket’s chain until strcmp finds a match and returns its value through the value_out pointer. Searching for "grape", which was never inserted, walks its bucket’s chain (possibly empty) and returns 0 without touching value. After ht_delete(&table, "apple") unlinks and frees that node, a further search for "apple" correctly reports not found, and count drops to 3.

Example 3: A Word Frequency Counter

A very common real use of a hash table is counting how often each item appears. This program reuses the same hashing and chaining logic, but each entry stores a running count instead of a fixed value.

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

#define TABLE_SIZE 101

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

typedef struct {
    Entry *buckets[TABLE_SIZE];
} HashTable;

unsigned long hash_string(const char *str)
{
    unsigned long hash = 5381;
    int c;

    while ((c = *str++) != '\0')
        hash = ((hash << 5) + hash) + (unsigned long)c;

    return hash;
}

void ht_init(HashTable *table)
{
    for (int i = 0; i < TABLE_SIZE; i++)
        table->buckets[i] = NULL;
}

void ht_increment(HashTable *table, const char *word)
{
    unsigned long index = hash_string(word) % TABLE_SIZE;
    Entry *cur = table->buckets[index];

    while (cur != NULL) {
        if (strcmp(cur->key, word) == 0) {
            cur->count++;
            return;
        }
        cur = cur->next;
    }

    Entry *entry = malloc(sizeof(Entry));
    entry->key = malloc(strlen(word) + 1);
    strcpy(entry->key, word);
    entry->count = 1;
    entry->next = table->buckets[index];
    table->buckets[index] = entry;
}

int ht_get(HashTable *table, const char *word)
{
    unsigned long index = hash_string(word) % TABLE_SIZE;
    Entry *cur = table->buckets[index];

    while (cur != NULL) {
        if (strcmp(cur->key, word) == 0)
            return cur->count;
        cur = cur->next;
    }
    return 0;
}

int main(void)
{
    const char *words[] = {
        "the", "quick", "fox", "jumps", "over",
        "the", "lazy", "dog", "the", "fox", "runs"
    };
    int n = sizeof(words) / sizeof(words[0]);

    HashTable table;
    ht_init(&table);

    for (int i = 0; i < n; i++)
        ht_increment(&table, words[i]);

    const char *lookups[] = {"the", "fox", "dog", "cat"};
    for (int i = 0; i < 4; i++)
        printf("%-6s %d\n", lookups[i], ht_get(&table, lookups[i]));

    for (int i = 0; i < TABLE_SIZE; i++) {
        Entry *cur = table.buckets[i];
        while (cur != NULL) {
            Entry *next = cur->next;
            free(cur->key);
            free(cur);
            cur = next;
        }
    }

    return 0;
}

Output:

the    3
fox    2
dog    1
cat    0

The word list has "the" three times and "fox" twice, so ht_increment creates one entry per unique word the first time it’s seen and simply bumps count on every repeat. "cat" was never inserted, so ht_get walks its bucket’s chain, finds no match, and returns 0 — this is the same pattern databases and compilers use for symbol tables and frequency counts.

How It Works Step by Step (Under the Hood)

Here is exactly what happens when Example 2 calls ht_insert(&table, "banana", 20):

1. hash_string walks "banana" one byte at a time, updating hash = hash * 33 + c for every character, producing one large unsigned long number.
2. ht_insert reduces that number with % TABLE_SIZE, turning it into a valid array index between 0 and 100.
3. It reads table->buckets[index], which points to the head of whatever chain (possibly empty) already lives in that bucket.
4. It walks the chain with a while loop, comparing each node’s key to "banana" with strcmp. If a match is found, the existing value is overwritten and the function returns immediately — no duplicate is created.
5. If the loop reaches the end of the chain (cur == NULL) without a match, a new Entry is allocated with malloc, its key is allocated separately and copied byte-for-byte with strcpy (the table never just borrows the caller’s pointer), and its value is set.
6. The new entry is linked in at the front of the bucket’s chain (entry->next = table->buckets[index]; table->buckets[index] = entry;), which is an O(1) insert regardless of how long the chain already is.
7. table->count is incremented so the table always knows how many entries it holds, which is what makes computing the load factor cheap.

ht_search and ht_delete follow the identical first three steps — hash, reduce with %, and read the bucket — then either read a matching node’s value or unlink it from the chain by rewiring the previous node’s next pointer (or the bucket head, if the match is the first node) before freeing its memory.

Common Mistakes

Mistake 1: Comparing String Keys With ==

In C, key and cur->key are both char * pointers. Comparing them with == checks whether they point to the exact same memory address, not whether the text inside is the same. Two different char arrays holding the identical word will almost always have different addresses, so this comparison silently fails to find matches that should exist.

/* WRONG: compares pointers, not string contents */
Entry *cur = table->buckets[index];
while (cur != NULL) {
    if (cur->key == key) {   /* almost always false, even for equal strings */
        cur->value = value;
        return;
    }
    cur = cur->next;
}

The fix is to compare the characters the pointers point to with strcmp, which returns 0 only when both strings match exactly, character for character:

/* CORRECT: compares the characters inside the strings */
Entry *cur = table->buckets[index];
while (cur != NULL) {
    if (strcmp(cur->key, key) == 0) {
        cur->value = value;
        return;
    }
    cur = cur->next;
}

Mistake 2: Storing a Borrowed Pointer Instead of Copying the Key

If ht_insert stores the caller’s key pointer directly instead of copying it, the table doesn’t actually own that memory. If the caller later reuses or frees the buffer the key came from — a common case when reading input into a fixed buffer inside a loop — every entry that stored that pointer now reflects whatever the buffer currently holds, corrupting keys that looked fine when they were inserted.

/* WRONG: stores the caller's pointer, the table doesn't own this memory */
Entry *entry = malloc(sizeof(Entry));
entry->key = (char *)key;
entry->value = value;
entry->next = table->buckets[index];
table->buckets[index] = entry;

Instead, allocate fresh memory sized to the string and copy it in, so the table’s copy is independent of whatever the caller does with the original:

/* CORRECT: allocate and copy the key so the table owns its own memory */
Entry *entry = malloc(sizeof(Entry));
entry->key = malloc(strlen(key) + 1);
strcpy(entry->key, key);
entry->value = value;
entry->next = table->buckets[index];
table->buckets[index] = entry;

Best Practices

• Use a well-distributed string hash such as djb2 or FNV-1a rather than something naive like summing character codes or using only the first letter.
• Always compare full key contents with strcmp (or memcmp for fixed-size binary keys); never compare string pointers with ==.
• Deep-copy any key you don’t already own into memory the table controls, and free that copy when the entry is deleted or the table is destroyed.
• Keep the load factor (count / table_size) below roughly 0.7–1.0; rehash into a bigger array once it climbs past that threshold.
• Prefer a prime table size, or a well-mixing hash with a power-of-two size, to reduce clustering in the low bits of the hash.
• Check every malloc return value for NULL in production code (omitted here to keep the examples focused) and handle allocation failure explicitly.
• Always provide a matching ht_free/destroy function that walks every bucket and frees every node and key — hash tables are easy to leak if you forget the chains.
• Decide up front how your search/get API reports "not found" (a return code, a sentinel value, or an output parameter) and use it consistently across the whole table.

Practice Exercises

1. Using the hash table from Example 2, insert "apple" -> 10, then insert "apple" -> 99 again, then search for "apple" and print the result. Confirm the second insert updates the existing entry instead of creating a duplicate. Expected output: apple -> 99.
2. Add a ht_rehash function: when table->count reaches about 75% of TABLE_SIZE, allocate a new bucket array double the size, walk every bucket in the old array, reinsert each entry using the new size (hash % new_size), and free the old array. This is what keeps a hash table’s performance close to O(1) as it grows.
3. Write a function ht_print(HashTable *table) that loops over every bucket, walks its chain, and prints each key and value it finds. Run it after inserting the four fruit prices from Example 2 and confirm all four entries show up, in whatever bucket order they happen to land.

Summary

• A hash table maps keys to array indexes with a hash function, giving average O(1) insert, search, and delete.
• C has no built-in hash table type — you build the bucket array, hash function, and collision handling yourself.
• Collisions are unavoidable; separate chaining resolves them by giving each bucket its own linked list.
• Always compare string keys with strcmp, never with ==, and always deep-copy keys the table doesn’t already own.
• Load factor and hash quality drive real-world performance; rehash into a larger table once the load factor gets too high.
• Free every allocated key and node when deleting entries or destroying the table to avoid memory leaks.