C Language Data Structures: Complete Implementation of a Handwritten HashMap (Reusable + High Performance)

Understanding HashMap in One Image

The structure implemented using an array + linked list (chaining method) is shown below:Key Points Recap: HashMap uses an array (buckets), where each bucket stores a conflict linked list (or other structures). The hash function maps the key to a hash value, and then the modulus operation is used to obtain the bucket index.During resizing, it is necessary to recalculate the index and move elements to the new buckets:

1️⃣ Design Contract (Interface Specification)

Objective: Implement a HashMap that supports string keys, with the following requirements:

• • API: create, destroy, put, get, remove, foreach
• • Dynamic resizing (default load factor 0.75)
• • Replaceable hash function
• • Memory safety, avoiding memory leaksData structure contract:
• • The length of the bucket array should be capacity (preferably a power of 2)
• • Each bucket is a collection of linked list nodes

2️⃣ Key Implementation (Code)

Below is the minimal but complete implementation, with boundary checks and simple unit tests. File:<span>hashmap.h</span>

// ...existing code...
#ifndef HASHMAP_H
#define HASHMAP_H

#include <stddef.h>

typedef struct hashmap hashmap_t;

hashmap_t *hashmap_create(size_t capacity);
void hashmap_destroy(hashmap_t *m);
int hashmap_put(hashmap_t *m, const char *key, void *value);
void *hashmap_get(hashmap_t *m, const char *key);
int hashmap_remove(hashmap_t *m, const char *key);
void hashmap_foreach(hashmap_t *m, void (*fn)(const char *k, void *v, void *ctx), void *ctx);

#endif // HASHMAP_H

File:<span>hashmap.c</span>

// ...existing code...
#include "hashmap.h"
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

// Simple FNV-1a 32-bit hash implementation
static uint32_t fnv1a(const char *s) {
    uint32_t h = 2166136261u;
    while (*s) {
        h ^= (unsigned char)(*s++);
        h *= 16777619u;
    }
    return h;
}

typedef struct node {
    char *key;
    void *value;
    struct node *next;
} node_t;

struct hashmap {
    node_t **buckets;
    size_t capacity;
    size_t size;
    float max_load; // e.g., 0.75
};

static node_t *node_create(const char *k, void *v) {
    node_t *n = malloc(sizeof(node_t));
    if (!n) return NULL;
    n->key = strdup(k);
    n->value = v;
    n->next = NULL;
    return n;
}

static void node_free(node_t *n) {
    if (!n) return;
    free(n->key);
    free(n);
}

hashmap_t *hashmap_create(size_t capacity) {
    hashmap_t *m = malloc(sizeof(hashmap_t));
    if (!m) return NULL;
    if (capacity < 8) capacity = 8;
    m->capacity = capacity;
    m->size = 0;
    m->max_load = 0.75f;
    m->buckets = calloc(m->capacity, sizeof(node_t*));
    if (!m->buckets) { free(m); return NULL; }
    return m;
}

static int hashmap_resize(hashmap_t *m, size_t new_capacity) {
    node_t **newb = calloc(new_capacity, sizeof(node_t*));
    if (!newb) return -1;
    for (size_t i = 0; i < m->capacity; ++i) {
        node_t *cur = m->buckets[i];
        while (cur) {
            node_t *next = cur->next;
            uint32_t h = fnv1a(cur->key);
            size_t idx = h & (new_capacity - 1); // capacity is power of two
            cur->next = newb[idx];
            newb[idx] = cur;
            cur = next;
        }
    }
    free(m->buckets);
    m->buckets = newb;
    m->capacity = new_capacity;
    return 0;
}

int hashmap_put(hashmap_t *m, const char *key, void *value) {
    if (!m || !key) return -1;
    if ((float)(m->size + 1) / m->capacity > m->max_load) {
        if (hashmap_resize(m, m->capacity * 2) != 0) return -1;
    }
    uint32_t h = fnv1a(key);
    size_t idx = h & (m->capacity - 1);
    node_t *cur = m->buckets[idx];
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            cur->value = value; // Replace
            return 0;
        }
        cur = cur->next;
    }
    node_t *n = node_create(key, value);
    if (!n) return -1;
    n->next = m->buckets[idx];
    m->buckets[idx] = n;
    m->size++;
    return 0;
}

void *hashmap_get(hashmap_t *m, const char *key) {
    if (!m || !key) return NULL;
    uint32_t h = fnv1a(key);
    size_t idx = h & (m->capacity - 1);
    node_t *cur = m->buckets[idx];
    while (cur) {
        if (strcmp(cur->key, key) == 0) return cur->value;
        cur = cur->next;
    }
    return NULL;
}

int hashmap_remove(hashmap_t *m, const char *key) {
    if (!m || !key) return -1;
    uint32_t h = fnv1a(key);
    size_t idx = h & (m->capacity - 1);
    node_t *cur = m->buckets[idx];
    node_t *prev = NULL;
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (prev) prev->next = cur->next; else m->buckets[idx] = cur->next;
            node_free(cur);
            m->size--;
            return 0;
        }
        prev = cur;
        cur = cur->next;
    }
    return -1; // not found
}

void hashmap_foreach(hashmap_t *m, void (*fn)(const char*, void*, void*), void *ctx) {
    if (!m || !fn) return;
    for (size_t i = 0; i < m->capacity; ++i) {
        node_t *cur = m->buckets[i];
        while (cur) { fn(cur->key, cur->value, ctx); cur = cur->next; }
    }
}

void hashmap_destroy(hashmap_t *m) {
    if (!m) return;
    for (size_t i = 0; i < m->capacity; ++i) {
        node_t *cur = m->buckets[i];
        while (cur) { node_t *n = cur->next; node_free(cur); cur = n; }
    }
    free(m->buckets);
    free(m);
}

3️⃣ Simple Testing (Example)

File:<span>test_hashmap.c</span>

#include "hashmap.h"
#include <stdio.h>

int main(void) {
    hashmap_t *m = hashmap_create(8);
    hashmap_put(m, "apple", "red");
    hashmap_put(m, "banana", "yellow");
    hashmap_put(m, "cherry", "red");

    printf("apple=%s\n", (char*)hashmap_get(m, "apple"));
    printf("banana=%s\n", (char*)hashmap_get(m, "banana"));

    hashmap_remove(m, "banana");
    printf("banana=%s\n", (char*)hashmap_get(m, "banana"));

    hashmap_destroy(m);
    return 0;
}

Build (PowerShell):

gcc -O2 hashmap.c test_hashmap.c -o test_hashmap
.	est_hashmap

Example Output:

apple=red
banana=yellow
banana=(null)

4️⃣ Performance and Engineering Recommendations

• • Hash Function: In production environments, it is recommended to use faster and less collision-prone functions (xxHash, MurmurHash3); FNV-1a is suitable for demonstration and small scenarios.
• • Capacity Design: Using powers of 2 allows for bitwise operations (h & (cap-1)) instead of modulus, improving speed.
• • Resizing Strategy: Default load factor is 0.75; support batch insertion with reserve(capacity) to avoid multiple resizes.
• • Collision Strategy: Linked lists degrade under severe collisions; switch to balanced trees (like Java’s implementation) when the list length exceeds a threshold.
• • Memory Allocation: Frequent malloc/free is costly; consider using memory pools or object reuse.

5️⃣ Common Pitfalls and Fixes

• • Forgetting to copy the key (strdup) can lead to invalid keys that use stack or external buffers. The implementation already copies the key.
• • Memory leaks when deleting nodes: Ensure to free the key and the node itself.
• • Concurrent Access: The current implementation is not thread-safe; it needs locks or lock-free structures to support concurrent read/write.

6️⃣ Extension Exercises (Recommendations)

1. 1. Support keys as arbitrary byte arrays (pass in length) and provide custom comparison functions.
2. 2. Implement an open addressing (linear/quadratic/double hashing) version and compare performance and memory usage.
3. 3. Implement switching from linked lists to balanced trees in high collision scenarios.

Conclusion

Writing a HashMap is not just about implementing the API; it is also a process of understanding memory, cache behavior, hash functions, and performance trade-offs. Putting the above implementation into a small library and writing benchmarks (different loads, different key distributions) will give you a deeper understanding of data structure choices and engineering compromises.