Implementing a Hash Map from Scratch in C

A hash map stores key–value pairs and uses a hash function to locate entries quickly. Instead of scanning every record, a program converts a key into an array index, then checks only the small group of entries associated with that position. With a suitable design, insertion, lookup and deletion are usually close to O(1) on average.

Building one in C is a useful exercise because the language makes memory ownership, pointer manipulation and resizing visible. The same ideas appear in caches, symbol tables, indexes and programming interview problems. They also connect naturally with broader computing topics covered in machine learning, where dictionaries and feature maps are common implementation tools.

Choosing The Data Structure

A practical first version uses separate chaining. The main map contains an array of buckets, and each bucket points to a linked list of nodes. Every node stores a dynamically allocated key, a value, and a pointer to the next node.

This approach handles collisions without requiring immediate probing logic. If two keys produce the same bucket index, both nodes remain in that bucket's chain. Lookup compares the requested key with each node using strcmp, while insertion can either replace an existing value or add a new node.

A map structure can be declared as follows:

#include <stddef.h>

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

typedef struct {
    HashNode **buckets;
    size_t capacity;
    size_t size;
} HashMap;

The capacity field records the number of buckets, and size counts stored key–value pairs rather than individual buckets. Keeping these values separate makes load-factor calculations and resizing straightforward.

Hashing Strings Into Buckets

A hash function converts a string into an unsigned integer. It should be deterministic, reasonably fast and capable of spreading similar strings across different values. A common educational choice is the djb2-style function:

#include <stddef.h>

static size_t hash_string(const char *key) {
    size_t hash = 5381;
    int character;

    while ((character = (unsigned char)*key++)) {
        hash = ((hash << 5) + hash) ^ (size_t)character;
    }

    return hash;
}

The expression hash * 33 is written as (hash << 5) + hash, and XOR mixes each character into the running result. The bucket position is obtained with hash_string(key) % map->capacity. Modulo is easy to understand, although a power-of-two capacity with bit masking can sometimes be faster.

A hash function does not guarantee unique results. A collision is normal, not an error. Quality is judged by distribution: if many common keys land in the same bucket, linked lists become long and operations approach linear time. Cryptographic strength is unnecessary for an ordinary in-memory dictionary, but untrusted input may justify a stronger or keyed hash to reduce deliberate collision attacks.

Allocating, Inserting And Looking Up

Initialisation allocates the bucket array with calloc, ensuring every linked-list pointer starts as NULL. Each key must be copied into storage owned by the map. A portable C implementation can allocate strlen(key) + 1 bytes and copy the characters with memcpy, avoiding reliance on the non-standard strdup function.

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

bool hashmap_init(HashMap *map, size_t capacity) {
    if (capacity == 0) {
        return false;
    }

    map->buckets = calloc(capacity, sizeof(*map->buckets));
    if (map->buckets == NULL) {
        return false;
    }

    map->capacity = capacity;
    map->size = 0;
    return true;
}

static char *copy_string(const char *source) {
    size_t length = strlen(source);
    char *copy = malloc(length + 1);

    if (copy != NULL) {
        memcpy(copy, source, length + 1);
    }

    return copy;
}

Insertion first searches the selected chain. If the key already exists, it updates the value and returns. Otherwise, it allocates a node and a key copy, links the node at the front of the chain, and increments size. Inserting at the head takes constant time once the bucket has been found.

bool hashmap_put(HashMap *map, const char *key, int value) {
    size_t index = hash_string(key) % map->capacity;

    for (HashNode *node = map->buckets[index]; node; node = node->next) {
        if (strcmp(node->key, key) == 0) {
            node->value = value;
            return true;
        }
    }

    HashNode *node = malloc(sizeof(*node));
    if (node == NULL) {
        return false;
    }

    node->key = copy_string(key);
    if (node->key == NULL) {
        free(node);
        return false;
    }

    node->value = value;
    node->next = map->buckets[index];
    map->buckets[index] = node;
    map->size++;
    return true;
}

A lookup function returns success through a Boolean result and writes the value through an output parameter. This avoids confusing a missing key with a stored value of zero.

bool hashmap_get(const HashMap *map, const char *key, int *result) {
    size_t index = hash_string(key) % map->capacity;

    for (HashNode *node = map->buckets[index]; node; node = node->next) {
        if (strcmp(node->key, key) == 0) {
            *result = node->value;
            return true;
        }
    }

    return false;
}

Resizing And Memory Ownership

A map becomes less efficient as its load factor rises. The load factor is size / capacity. With separate chaining, a threshold around 0.75 is a sensible starting point. When the threshold is reached, allocate a larger bucket array and reinsert every node according to the new capacity.

Rehashing is essential because the bucket index depends on the capacity. Simply copying old bucket positions would leave keys in the wrong places. During a resize, the nodes and key strings can be reused; only their links and bucket positions need to change.

Useful ownership rules should be explicit:

• The map owns every key copied during insertion.
• hashmap_get returns borrowed data through the output argument.
• Updating a key does not allocate another key string.
• Destruction must free each key, each node and the bucket array.
• Failed allocations must leave the existing map valid.

Deletion follows the same linked-list pattern. Keep a pointer to the previous node, unlink the matching node, free its key and structure, then decrement size. If the target is the first node, update the bucket head instead of dereferencing a previous pointer.

A destructor completes the lifecycle:

void hashmap_destroy(HashMap *map) {
    for (size_t i = 0; i < map->capacity; i++) {
        HashNode *node = map->buckets[i];

        while (node != NULL) {
            HashNode *next = node->next;
            free(node->key);
            free(node);
            node = next;
        }
    }

    free(map->buckets);
    map->buckets = NULL;
    map->capacity = 0;
    map->size = 0;
}

For Australian applications, memory safety matters when a map handles customer records, payment references or contact details covered by the Privacy Act 1988. A hash map does not encrypt information or enforce access control, so it should be treated as an internal data structure rather than a privacy mechanism.

Testing Correctness And Performance

Tests should cover more than a few successful lookups. Begin with an empty map, insert one key, update it, search for a missing key and delete the only entry. Then test duplicate keys, empty strings, long strings and keys that intentionally collide.

Collision tests are especially valuable because they exercise the linked-list logic. A small capacity such as four buckets makes collisions easy to create. Sanitised builds with AddressSanitizer and UndefinedBehaviorSanitizer can identify use-after-free, invalid reads and allocation errors that ordinary output tests may miss.

Practical test cases include:

• Inserting thousands of generated keys and checking every value.
• Updating keys without increasing the element count.
• Removing head, middle and final nodes in a chain.
• Resizing repeatedly while preserving all entries.
• Calling destruction after partial allocation failures.

Average insertion and lookup are O(1) when the hash function distributes keys well and resizing keeps the load factor controlled. Worst-case lookup is O(n), where all keys occupy one chain. Initialisation is O(m) for m buckets, while resizing is O(n) because every stored node must be moved.

For a Melbourne or Sydney service processing many short identifiers, a sensible capacity and a low collision rate usually matter more than micro-optimising the hash loop. A command-line tool used by a smaller regional business may favour a simpler implementation that is easy to audit. In either case, benchmark realistic key distributions rather than relying only on random strings.

Comparing Collision Strategies

Separate chaining is generally the clearest implementation for learning C. Open addressing stores entries directly inside the bucket array and searches for another position when a collision occurs. Linear probing is cache-friendly, but deletion requires tombstone markers or cluster repair, and the table must maintain unused slots.

The right design depends on workload, key ownership and expected capacity. A map used as a compiler symbol table may prioritise predictable memory layout, while a long-running web process may value simpler deletion and robust behaviour under changing data. This is similar to choosing model constraints in regularisation methods: the implementation should reflect the expected workload rather than a universal rule.

Feature	Separate Chaining	Linear Probing	Quadratic Probing
Collision storage	Linked nodes outside the array	Additional array slots	Additional array slots
Deletion	Direct unlinking	Tombstones or shifting	Tombstones or shifting
Cache locality	Usually lower	Usually high	Usually high
Load-factor tolerance	Can exceed 1.0	Must stay below 1.0	Must stay below 1.0
Main complexity	Pointer allocation	Clustering	More complex probe behaviour

When extending the example, add automatic growth before insertion would push the load factor beyond the chosen threshold. Make resizing transactional: allocate the new bucket array first, and if allocation fails, retain the old map unchanged. A complete API can also support const keys, generic void * values, custom hash functions and user-provided destructors.

The central lesson is that a hash map is a compact combination of an array, a hash function, collision handling and disciplined ownership. Once those pieces are explicit, the implementation is easier to debug, measure and adapt to real programs across Australia, from an Adelaide utility script to a Perth backend service.