Hash Table Operations with Collision Handling

The collision is part of the design

A hash table uses a key to select a bucket. In our implementation, an unsigned integer key selects one of eight buckets using its remainder on division by eight. Keys 1, 9, and 17 therefore select the same bucket. They are different keys, so the table must retain all three.

We’ll resolve that collision with separate chaining: each array element points to the head of a linked list. To find a key, examine only its bucket’s list, comparing stored keys, not values. To insert a new key, link a node into that list. To delete one, unlink and free its node.

Watch the chaining portion of Jacob Sorber’s Understanding and implementing a Hash Table (in C). It shows the array-and-list arrangement in C; our implementation will add an explicit duplicate-key and ownership contract.

For a more precise account of the three operations, read the implementation discussion in Open Data Structures. Its pseudocode stores set elements rather than our key–value pairs, but the bucket invariant is the same.

The invariant to carry into the code is simple: every stored node is in the bucket selected by its key, and each key occurs at most once. An update must preserve the node count. A failed allocation must leave the table unchanged.

A 23-minute C implementation

Use this contract:

• table_get returns whether the key exists. On success it writes the value to *out; on failure it leaves *out unchanged.
• table_put inserts a missing key or updates an existing key. It returns false only for an invalid table pointer or an allocation failure. Updating does not allocate or change size.
• table_delete returns whether it removed a key. Only a successful deletion decrements size.
• The table owns every node it allocates. Keys and values are stored directly in nodes, so neither requires a separate allocation. table_destroy is supplied.

Save the following as hash.c. Replace only the three placeholder functions during your timed run. The tests deliberately place keys 1, 9, and 17 in one bucket.

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define BUCKETS 8u

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

typedef struct {
    Node *buckets[BUCKETS];
    size_t size;
} Table;

static size_t bucket_of(uint32_t key)
{
    return (size_t)(key % BUCKETS);
}

static bool table_get(const Table *t, uint32_t key, int *out)
{
    /* Replace this placeholder. */
    (void)t;
    (void)key;
    (void)out;
    return false;
}

static bool table_put(Table *t, uint32_t key, int value)
{
    /* Replace this placeholder. */
    (void)t;
    (void)key;
    (void)value;
    return false;
}

static bool table_delete(Table *t, uint32_t key)
{
    /* Replace this placeholder. */
    (void)t;
    (void)key;
    return false;
}

static void table_destroy(Table *t)
{
    if (t == NULL)
        return;

    for (size_t i = 0; i < BUCKETS; ++i) {
        Node *node = t->buckets[i];
        while (node != NULL) {
            Node *next = node->next;
            free(node);
            node = next;
        }
        t->buckets[i] = NULL;
    }
    t->size = 0;
}

int main(void)
{
    Table t = {0};
    int value = 314;

    assert(!table_get(&t, 1, &value) && value == 314);
    assert(table_put(&t, 17, 170));
    assert(table_put(&t, 9, 90));
    assert(table_put(&t, 1, -1));
    assert(t.size == 3);

    assert(table_get(&t, 17, &value) && value == 170);
    assert(table_get(&t, 1, &value) && value == -1);

    assert(table_put(&t, 9, 900));
    assert(t.size == 3);
    assert(table_get(&t, 9, &value) && value == 900);

    assert(!table_delete(&t, 25) && t.size == 3);
    assert(table_delete(&t, 9) && t.size == 2);
    assert(!table_get(&t, 9, &value));
    assert(table_get(&t, 17, &value) && value == 170);
    assert(table_delete(&t, 1) && t.size == 1);
    assert(table_delete(&t, 17) && t.size == 0);
    assert(!table_delete(&t, 17));

    /* A separate chain tests deletion of its tail. */
    assert(table_put(&t, 18, 180));
    assert(table_put(&t, 10, 100));
    assert(table_put(&t, 2, 20));
    assert(table_delete(&t, 18) && t.size == 2);
    assert(table_get(&t, 2, &value) && value == 20);
    assert(table_get(&t, 10, &value) && value == 100);

    assert(table_put(&t, 0, -1)); /* Zero key and negative value are valid. */
    assert(table_get(&t, 0, &value) && value == -1);

    assert(!table_get(NULL, 0, &value));
    assert(!table_get(&t, 0, NULL));
    assert(!table_put(NULL, 0, 1));
    assert(!table_delete(NULL, 0));

    table_destroy(&t);
    assert(t.size == 0);
    assert(!table_get(&t, 0, &value));

    puts("hash table tests passed");
    return 0;
}

Give yourself about three minutes to state the invariant and failure behavior, fifteen minutes to implement the functions, and five minutes to compile, test, and fix the highest-priority defect. Stop at 23 minutes for the review, even if a test remains red.

gcc -std=c11 -O0 -g -Wall -Wextra -Wpedantic \
  -fsanitize=address,undefined hash.c -o hash
./hash

The tests do not force malloc to fail, so handle that path by inspection: do not change a bucket or size until allocation succeeds. A sanitizer can detect invalid accesses on paths you run, but it cannot prove the untested allocation-failure path is correct.

Review: preserve the chain before freeing a node

Compare your implementation after the timed run. These definitions replace the three placeholders:

static bool table_get(const Table *t, uint32_t key, int *out)
{
    if (t == NULL || out == NULL)
        return false;

    for (const Node *node = t->buckets[bucket_of(key)];
         node != NULL; node = node->next) {
        if (node->key == key) {
            *out = node->value;
            return true;
        }
    }
    return false;
}

static bool table_put(Table *t, uint32_t key, int value)
{
    if (t == NULL)
        return false;

    size_t i = bucket_of(key);
    for (Node *node = t->buckets[i]; node != NULL; node = node->next) {
        if (node->key == key) {
            node->value = value;
            return true;
        }
    }

    Node *node = malloc(sizeof *node);
    if (node == NULL)
        return false;

    *node = (Node){ .key = key, .value = value,
                    .next = t->buckets[i] };
    t->buckets[i] = node;
    ++t->size;
    return true;
}

static bool table_delete(Table *t, uint32_t key)
{
    if (t == NULL)
        return false;

    Node **link = &t->buckets[bucket_of(key)];
    while (*link != NULL) {
        Node *node = *link;
        if (node->key == key) {
            *link = node->next;
            free(node);
            --t->size;
            return true;
        }
        link = &node->next;
    }
    return false;
}

Lookup and insertion both compare keys, because a shared bucket is not proof that the desired key has been found. Insertion scans before allocating: an existing key needs only a value change. For a new key, the node points to the old head before the bucket head is replaced. If malloc fails, neither pointer nor count has changed.

Deletion uses Node **link to point at the pointer that currently leads to a node. At the head, that pointer is the bucket entry; farther along, it is the preceding node’s next field. Assigning *link = node->next therefore removes a head, middle, or tail node without separate cases. After free(node), the function does not access node again. This is the same pointer-lifetime discipline you used in the linked-list lesson, now applied inside a selected bucket.

For a bucket with $k$ nodes, lookup and deletion take $O(1+k)$ time. Insertion takes the same order because it first checks for an existing key. With $n$ entries and $B$ well-distributed buckets, the expected chain length is related to the load factor $\alpha =n/B$, giving expected $O(1+\alpha )$ work; if every key lands in one bucket, the worst case is $O(n)$. Our fixed eight-bucket program is an implementation exercise, not a claim of constant-time lookup as $n$ grows. A production table would choose a suitable hash function and resize and redistribute entries to control chain lengths.

Why another collision strategy changes deletion

Separate chaining is one valid answer to this learning outcome. An interviewer may instead specify open addressing, where entries occupy slots in the array itself and collisions trigger a probe through other slots. In that design, deletion cannot simply turn a slot into “never used”: doing so could cause lookup to stop before reaching a key displaced by an earlier collision.

Read this short comparison to distinguish the stopping rule from the chained-table code you just wrote.

The key distinction is that chaining deletes a node and reconnects a list, whereas linear probing preserves the search path with a deleted marker. Neither strategy removes the need to compare actual keys when collisions occur.

Key takeaways

A working hash table needs more than an index calculation. Its collision strategy determines where lookup searches, how insertion handles an existing key, and what deletion must preserve. In your chained C table, the critical guarantees are one node per key, unchanged state on allocation failure, correct unlinking before free, and a count that changes only when the number of nodes changes.

Next, you’ll use a stack or queue to solve a traversal problem under an explicit time and space bound. The same interview pattern applies: choose the representation, state its invariant, implement the operations, and test the boundary cases.