Hashmaps in C

A hashmap is where DSA-in-C hurts the most and pays off the most. In Python d = {} is a hashmap; in C, someone has to build one. Once you have, you’re forever unafraid of open-addressing, load factors, and hash-function choice — things Python users can go a whole career without confronting. This file gives you three tiers of hashmap: the one LeetCode ships (uthash), the modern high-performance choice (khash/khashl), and a from-scratch open-addressing implementation you should write once by hand.

The Landscape in Mid-2026

The C hashmap ecosystem shifted noticeably between 2023 and 2026. The community consensus, verified across recent r/C_Programming threads and Jackson Allan’s benchmark:

• uthash — the most widely known. Ships with LeetCode’s C environment. Ergonomic macro-heavy API. Slow by modern standards; the khash author (attractivechaos) explicitly recommends against it in 2025. Use it for LeetCode because it’s there, not because it’s fast.

• khash — attractivechaos/klib. Single-header, ~500 LOC, fast, generic via macros. The workhorse for a decade. Now superseded by its own author’s follow-up, khashl, but still perfectly usable.

• khashl / CC / M*LIB / STC / Verstable — the modern-fast tier. “A few times faster AND a few times less memory than uthash” per attractivechaos (khashl’s author). Overkill for study problems; worth knowing for production.

• Rolling your own — open-addressing with linear probing, ~100 lines, no dependencies. What you’ll actually put in libprep.

For LeetCode: use uthash.h because it’s already there and you don’t have to paste 500 lines of khash.h. For your own projects and libprep: write your own open-addressing table. For production: link khashl or CC or, honestly, use C++’s absl::flat_hash_map (yes, this is a C course, but honesty first).

uthash (LeetCode-Ready)

uthash.h is macro-heavy: you add a UT_hash_handle hh; field to your struct and use macros to add/find/delete. It works.

#include "uthash.h"

typedef struct {
    int key;                // key can be any type
    int val;
    UT_hash_handle hh;      // makes this struct hashable
} Entry;

Entry *table = NULL;

void put(int key, int val) {
    Entry *e;
    HASH_FIND_INT(table, &key, e);
    if (e) { e->val = val; return; }
    e = malloc(sizeof *e);
    e->key = key; e->val = val;
    HASH_ADD_INT(table, key, e);
}

int get(int key, int *out) {
    Entry *e;
    HASH_FIND_INT(table, &key, e);
    if (!e) return 0;
    *out = e->val;
    return 1;
}

void destroy(void) {
    Entry *e, *tmp;
    HASH_ITER(hh, table, e, tmp) {
        HASH_DEL(table, e);
        free(e);
    }
}

String keys: use HASH_FIND_STR and HASH_ADD_STR. The key field must be a char*; uthash copies the string internally if you want (there’s a variant), otherwise the caller keeps it alive.

Performance: uthash is chained hashing with per-entry malloc — every insert allocates. For a leetcode problem with 10⁵ entries this is fine; for a real workload, it’s the reason people benchmark it as the slowest option.

khash (Klib) — The Middle Path

Single-header. KHASH_MAP_INIT_INT(name, val_type) generates all the functions.

#include "khash.h"
KHASH_MAP_INIT_INT(int2int, int)

int main(void) {
    khash_t(int2int) *h = kh_init(int2int);
    int absent;
    khint_t k = kh_put(int2int, h, 42, &absent);   // insert key
    kh_value(h, k) = <phone_number_or_numberic_id_or_random_id_18>;                      // set value

    k = kh_get(int2int, h, 42);                    // lookup
    if (k != kh_end(h)) printf("%d\n", kh_value(h, k));

    kh_destroy(int2int, h);
}

The API is code-generation via macros, which means great performance (open addressing, contiguous storage) at the cost of readability. Once you learn its idioms it’s not bad. For production C code that needs a hashmap and can’t drag in a whole library, khash and its successor khashl are the gold-standard single-header options.

Rolling Your Own (Open Addressing, Linear Probing)

Here’s the hashmap you should write by hand once, put in libprep, and reuse for the rest of the year. int → int with linear probing:

typedef struct {
    int key;
    int val;
    unsigned char state;   // 0=empty, 1=filled, 2=tombstone
} Slot;

typedef struct {
    Slot *slots;
    size_t cap;      // always a power of two
    size_t size;     // filled entries
} IntMap;

static uint64_t hash_int(int x) {
    // Thomas Wang integer hash — fast, good enough for study problems
    uint64_t k = (uint64_t)(uint32_t)x;
    k = (~k) + (k << 21);
    k = k ^ (k >> 24);
    k = (k + (k << 3)) + (k << 8);
    k = k ^ (k >> 14);
    k = (k + (k << 2)) + (k << 4);
    k = k ^ (k >> 28);
    k = k + (k << 31);
    return k;
}

void map_init(IntMap *m, size_t cap) {
    // cap should be power of two
    m->slots = calloc(cap, sizeof(Slot));
    m->cap = cap;
    m->size = 0;
}

void map_put(IntMap *m, int key, int val) {
    if ((m->size + 1) * 2 > m->cap) map_resize(m, m->cap * 2);
    size_t i = hash_int(key) & (m->cap - 1);
    while (m->slots[i].state == 1 && m->slots[i].key != key) {
        i = (i + 1) & (m->cap - 1);
    }
    if (m->slots[i].state != 1) m->size++;
    m->slots[i].key = key;
    m->slots[i].val = val;
    m->slots[i].state = 1;
}

int map_get(const IntMap *m, int key, int *out) {
    size_t i = hash_int(key) & (m->cap - 1);
    while (m->slots[i].state != 0) {
        if (m->slots[i].state == 1 && m->slots[i].key == key) {
            *out = m->slots[i].val;
            return 1;
        }
        i = (i + 1) & (m->cap - 1);
    }
    return 0;
}
// map_resize: allocate new slots array, re-insert every filled slot
// map_del: mark slot as tombstone (state=2)
// map_destroy: free(m->slots)

Load factor: keep it under 0.5 for linear-probing performance. Above 0.7 and probe chains start to hurt hard. (size+1)*2 > cap triggers resize at 0.5.

Power-of-two capacity: enables the bitmask & (cap - 1) instead of % cap, which is significantly faster.

Tombstones: needed only if you support deletion. Skip them if your workload is insert-only (many study problems are).

Hash Function Choice

For integers: Thomas Wang’s mixer (above), or Murmur3’s finalizer:

uint32_t murmur3_finalizer(uint32_t k) {
    k ^= k >> 16;
    k *= 0x<phone_number_or_numberic_id_or_random_id_19>;
    k ^= k >> 13;
    k *= 0xc2b2ae35;
    k ^= k >> 16;
    return k;
}

For strings: MurmurHash3, FNV-1a, or xxHash. MurmurHash3 is the most-cited in study-related contexts:

uint32_t murmur3_str(const char *s) {
    uint32_t h = 0;
    while (*s) h = h * 31 + (unsigned char)*s++;
    return murmur3_finalizer(h);
}

(That’s Java’s String.hashCode composed with Murmur3’s finalizer. Perfectly serviceable for study problems.)

Do not use key % cap alone. That’s not a hash; that’s a modulus. If your keys have any pattern (e.g., all multiples of 4), you’ll get pathological chains. Always run a mixer.

Load Factor and Sizing Rules of Thumb

Probing scheme	Sane load factor	Notes
Linear probing	0.5	Cache-friendly. Simplest. Best for small values.
Quadratic probing	0.7	Less clustering. Slightly worse cache behavior.
Double hashing	0.7-0.8	Best distribution. Extra hash cost.
Robin Hood (linear + backshift)	0.9	State-of-the-art single-threaded. Complex.
Chaining (linked lists)	1.0+ (avg chain length)	Older style. Cache-unfriendly.

For study problems, linear probing at load-factor 0.5 is more than enough. For libprep, that’s what you ship. For production, Robin Hood or Swiss table (Google Abseil / F14 / Facebook’s F14) are what the state of the art has moved to.

String Keys: The Extra Step

With int keys, key == other_key is trivial. With char* keys, equality is strcmp(a, b) == 0. Two footguns:

1. Owning the key: if you map_put("hello", 1) with a stack string, then the stack frame ends, your key is dangling. Either copy the string on insert (strdup) and free it on delete/destroy, or document that the map borrows keys and require the caller to keep them alive.

2. Hash then compare: hash equality is not string equality. Always follow a hash match with strcmp.

What Most People Get Wrong About This

They either (a) use uthash for everything and never learn what’s underneath, or (b) roll their own but skip resizing and hit worst-case O(n) on every operation once the table fills. Write one open-addressing map, get resize + tombstones right, and never revisit this until you graduate to Robin Hood. The from-scratch version is 150 lines; that’s the price of admission.

---

Return to README.md · Next: 05_trees_and_heaps.md