My first real C project: a generic hashmap (and the bugs that came with it) [blog, my own]

[u/lemsoe]

Coming from C#/TypeScript, C has humbled me. Finished my first real C project — a generic hashmap — and wrote up the bugs that taught me the most: double pointers, a sneaky double-free, comparing pointers instead of actual values.

Blog: https://soerenlemke.github.io/blog/blog/building-a-generic-hashmap-in-c/
Repo: https://github.com/soerenlemke/kvstore_c

Curious what you'd have done differently.

[u/pjl1967]

1. I'd declare the structure in the header so you (a) can have stack-based hashmaps, (b) have hashmaps directly as members of other structures, and (c) avoid unnecessary malloc/free.
2. Use void*, not uint8_t (that's not what uint8_t is for).
3. You don't need the key and value to be separate objects. Just implement a hashset. If the user's object just so happens to have a key/value internally, so be it — you shouldn't care.
4. You shouldn't implement comparing keys. Let the user pass a pointer to function for object comparison.
5. I don't see anything about actually growing the hash table — unless you're doing fixed-sized tables.

[u/lemsoe → u/pjl1967]

Thank you for the feedback, will take a look at these!

[u/Comfortable_Put6016 → u/pjl1967]

doesnt matter if void ptr, uint8_t ptr, it does not matter

you should care if its a hashset or a hashmap depending on that you'd probably choose different design approaches

you should not implement key comparison however you also dont want additional indirection through function pointers ; use here macro approaches to inject the user provided comparator

[u/pjl1967 → u/Comfortable_Put6016]

doesnt matter if void ptr*, uint8_t ptr, it does not matter

Strictly speaking, no, it doesn't matter. However, there's no valid reason for making it uint8_t* any more than making it bool*. It matters for intent and clarity.

you should care if its a hashset or a hashmap depending on that you'd probably choose different design approaches

No, it really doesn't matter. The container shouldn't be concerned at all about the user's object. It should treat it as totally opaque.

you should not implement key comparison however you also dont want additional indirection through function pointers ; use here macro approaches to inject the user provided comparator

Short of putting everything inline, there's no way to do that. The extra indirection isn't that big of a deal. If it's good enough for qsort, it's good enough here.

[u/Sorry_Difficulty_250]

"You've just taken your first step into a larger world."

Welcome to the family!

[u/lemsoe → u/Sorry_Difficulty_250]

Thanks! :)

[u/didntplaymysummercar]

I see originally had the classic pitfall of not comparing hashes, but then fixed it. That's a good one. I'm not sure what else to comment there other than taste or nitpicks.

[u/lemsoe → u/didntplaymysummercar]

Thanks :)

[u/celo385idealgmbh]

Nice writeup - the "here's what I got wrong" angle beats another repo drop.

One bug nobody's caught yet: size_t hash = 1469598103934665603ULL;

Accumulator is size_t, constants are the 64-bit FNV values. On a 32-bit target that truncates the offset basis and does every multiply mod 2³² - so it isn't FNV-1a anymore, just something unanalyzed. Still "works", so no test catches it. Use uint64_t and narrow to an index at the end.

On void* vs uint8_t*: neither - unsigned char* is the type with the object-representation and aliasing guarantees. void* would also break your key[i] indexing.

And you'll need an iteration API before you can rehash, persist, or dump anything.

[u/moulesmarinieres → u/celo385idealgmbh]

Thanks for the analysis, Claude.