C Hash Tables

How it works

A hash table maps a key to a starting slot, but different keys can choose the same slot. Linear probing looks at subsequent slots until it finds the key or an empty slot. Bound the probe count by capacity so a full table cannot loop forever. This demonstration has no deletion; adding deletion requires tombstones or another strategy so searches do not stop too early. Average constant-time expectations depend on hashing, load factor and input distribution, not simply on using a remainder operator.

Run it locally

Use a hosted C17 compiler in a separate lab folder. The command assumes a driver named cc; substitute gcc, clang or zig cc as appropriate. C does not currently run in Bhylu’s browser playground. Apache, PHP and MySQL are not needed for these C programs.

cc -std=c17 -Wall -Wextra -Wpedantic -Werror hash-tables.c -o lesson

On Windows, use -o lesson.exe and run .\lesson.exe in PowerShell. On Unix-like systems run ./lesson. Math-library linking differs by toolchain; GCC on many Unix systems needs -lm after the source.

Download the complete C source. File-writing labs must run in an empty private directory, away from existing reports.

Example

#include <stdio.h>
#include <stdbool.h>
#include <stddef.h>

struct Slot { bool occupied; unsigned key; int depth; };
static bool insert(struct Slot table[5], unsigned key, int depth) {
    for (size_t probe = 0; probe < 5; ++probe) {
        size_t i = (key % 5u + probe) % 5;
        if (!table[i].occupied || table[i].key == key) {
            table[i] = (struct Slot){true, key, depth}; return true;
        }
    }
    return false;
}
static bool lookup(const struct Slot table[5], unsigned key, int *out) {
    for (size_t probe = 0; probe < 5; ++probe) {
        size_t i = (key % 5u + probe) % 5;
        if (!table[i].occupied) { return false; }
        if (table[i].key == key) { *out = table[i].depth; return true; }
    }
    return false;
}

int main(void) {
    struct Slot table[5] = {{0}};
    if (!insert(table, 7, 18) || !insert(table, 12, 24)) { return 1; }
    int depth = 0;
    if (lookup(table, 12, &depth)) { printf("Station 12: %d mm\n", depth); }
    return 0;
}

Expected result

Station 12: 24 mm

Seven and twelve both start at slot two. The second key is stored in the next available slot and lookup follows the same sequence. Existing keys are updated instead of duplicated. A production table needs resizing, deletion and adversarial-input policies; this fixed example exposes the collision rule without pretending to provide a general-purpose container.