How do you implement a hash table in C?

Create an array of pointers (the slots), hash each key to an index with a function like djb2 modulo the table size, and handle collisions by chaining: each slot points to a linked list of nodes, and colliding keys are inserted at the head of their slot's list. Search hashes the key and walks only that one chain.

What is a hash collision and how is it handled?

A collision is two different keys hashing to the same slot — unavoidable whenever there are more possible keys than slots. Chaining stores colliding entries in a per-slot linked list; open addressing probes nearby slots instead. With a good hash function chains stay short, keeping average lookup O(1).

What is the djb2 hash function?

djb2 is a simple string hash by Dan Bernstein: start with 5381 and for each character compute hash = hash * 33 + character. It is fast, easy to memorize, and distributes typical string keys well, which makes it the standard choice for C interview implementations.

Hash Table in C — Implementation with Chaining (djb2)

A hash table maps keys to storage slots in near-constant time: run the key through a hash function, take the result modulo the table size, and that’s the index where the key lives. It’s the data structure behind Python dicts, Java HashMaps, and database indexes — and one of the most-asked interview topics in C, because C makes you build every piece yourself. This page implements a complete hash table with djb2 string hashing and collision handling by chaining (linked lists per bucket): insert, search, display, and cleanup — all in tested, warning-free C89.

How Hashing Works — Step by Step

Hash the key: a hash function turns a string into a large number. We use djb2: start at 5381, then for each character compute h = h * 33 + c. Simple, fast, and spreads real-world keys well.
Map to a slot: h % TABLE_SIZE squeezes the big number into a valid array index.
Handle collisions: two different keys can land in the same slot (with 8 keys in 7 slots it’s guaranteed — the pigeonhole principle). With chaining, each slot holds a linked list; colliding keys simply join the chain.
Search: hash the key, walk that one chain comparing with strcmp(). With a good hash function, chains stay short — that’s where O(1) average lookup comes from.

Key	djb2 % 7	Result
apple	3	slot 3
cherry	2	slot 2
fig	2	collision — chains in front of cherry

C Program to Implement a Hash Table (Chaining)

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

#define TABLE_SIZE 7             /* small on purpose, to force collisions */

struct node {
    char key[32];
    struct node *next;
};

static struct node *table[TABLE_SIZE];

/* djb2 string hash: simple, fast, and good distribution */
static unsigned long hash(const char *key)
{
    unsigned long h = 5381;
    int c;

    while ((c = (unsigned char)*key++) != 0) {
        h = h * 33 + (unsigned long)c;
    }
    return h % TABLE_SIZE;
}

static int insert(const char *key)
{
    unsigned long idx = hash(key);
    struct node *n = malloc(sizeof *n);

    if (n == NULL) {
        return 0;
    }
    strncpy(n->key, key, sizeof n->key - 1);
    n->key[sizeof n->key - 1] = '\0';
    n->next = table[idx];         /* chain: new node at the head */
    table[idx] = n;
    return 1;
}

static int search(const char *key)
{
    struct node *n = table[hash(key)];

    while (n != NULL) {
        if (strcmp(n->key, key) == 0) {
            return 1;
        }
        n = n->next;
    }
    return 0;
}

static void display(void)
{
    int i;
    struct node *n;

    for (i = 0; i < TABLE_SIZE; i++) {
        printf("  [%d]", i);
        for (n = table[i]; n != NULL; n = n->next) {
            printf(" -> %s", n->key);
        }
        printf("\n");
    }
}

static void free_table(void)
{
    int i;
    struct node *n, *next;

    for (i = 0; i < TABLE_SIZE; i++) {
        for (n = table[i]; n != NULL; n = next) {
            next = n->next;
            free(n);
        }
        table[i] = NULL;
    }
}

int main(void)
{
    const char *words[] = { "apple", "banana", "cherry", "date",
                            "fig", "grape", "kiwi", "lemon" };
    int i, count = (int)(sizeof words / sizeof words[0]);

    for (i = 0; i < count; i++) {
        if (!insert(words[i])) {
            printf("Out of memory.\n");
            free_table();
            return 1;
        }
    }

    printf("Hash table (size %d) after %d insertions:\n", TABLE_SIZE, count);
    display();

    printf("\nsearch(\"cherry\") = %s\n", search("cherry") ? "found" : "not found");
    printf("search(\"mango\")  = %s\n", search("mango") ? "found" : "not found");

    free_table();
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra -o hashing hashing.c
./hashing

Sample Output

Hash table (size 7) after 8 insertions:
  [0]
  [1] -> kiwi -> grape
  [2] -> fig -> cherry
  [3] -> apple
  [4] -> banana
  [5]
  [6] -> lemon -> date

search("cherry") = found
search("mango")  = not found

Three chains have two entries — real collisions, handled. Note that fig appears before cherry even though it was inserted later: new nodes go to the head of the chain (O(1) insertion).

Code Explanation

hash() — djb2’s magic numbers (5381, 33) come from empirical testing by Dan Bernstein; the (unsigned char) cast keeps negative char values from corrupting the arithmetic. unsigned long overflow is well-defined in C (it wraps), so this is portable.
n->next = table[idx]; table[idx] = n; — head insertion: two pointer assignments, no chain walking.
strncpy + explicit terminator — strncpy does not null-terminate when the source fills the buffer; the follow-up line is mandatory, and forgetting it is a classic interview trap in itself.
free_table() — saves n->next before freeing n. Reading n->next after free(n) would be use-after-free.
TABLE_SIZE 7 — deliberately tiny so the demo shows collisions. Real tables resize when the load factor (entries ÷ slots) passes ~0.75, and prime sizes help weak hash functions spread better.

Time and Space Complexity

Operation	Average	Worst case	Why
Insert	O(1)	O(1)	hash + head insertion
Search	O(1)	O(n)	worst case: all keys collide into one chain
Space	O(n + TABLE_SIZE)		nodes + slot array

The other classic collision strategy is open addressing (probe the next slots instead of chaining) — better cache behavior, but deletion gets tricky. Chaining is the version to know first, and the one interviewers usually mean.

What This Program Teaches

Why hash tables achieve O(1) average lookup — and when they degrade to O(n)
Collision handling with chaining, and head insertion into a linked list
The strncpy null-termination trap
Safe linked-list teardown (save next before free)

Related C Programs

Reverse a Linked List in C — the structure inside each bucket
Binary Search in C — O(log n) lookup, the sorted-array alternative
Linear Search in C — what each chain walk actually is
Use-After-Free in C — the bug free_table() is written to avoid

Test yourself: our free C Programming Quiz app for Android has 150+ questions with explanations for every answer.

Recommended Book

Section 6.6 of The C Programming Language by Kernighan & Ritchie builds exactly this structure — a chained hash table for a symbol table. We’ve solved all of the book’s exercises. Also on Amazon.com.