How to implement a hash table in C (2021)

Enjoyable article and thorough run through. I didn't read all of it, but it really took me back to learning 'C' in comp sci in the early 90s. Great times.

I really like the API design of libjudy for general hash table like interfaces. It prevents you from having to hash a key twice just to do "check if key is not present, then set value, otherwise leave original value in hash." The pattern also meshes better with the way iterators naturally work.

Also, in terms of this table, if you add the computed key hash value to the stored hash entry, you can check that the value of the hashes match before you do the full strcmp. If you have a weak hash you might also get a benefit from checking that the first characters match before calling the full strcmp.

It would also make rehashing easier since you already have the full key available to you and don't have to use your internal set function to move entries into the new table. In the posted implementation the big-O semantics of a rehash are worst case.

Anyways.. "man hsearch.3" if you want something cheap and easy.

might be neat if there were acceleration wins to be had with instructions for computing hash ints from machine ints and strings.

or even better, a full fledged linear probing hash lookup instruction.

There was a fantastic benchmark of C and C++ hash tables doing the rounds a few weeks ago, it's pretty fun reading: https://jacksonallan.github.io/c_cpp_hash_tables_benchmark/.

Unless I really didn't want to introduce dependencies, or reduce code size, I think I'd use an off the shelf hash table implementation these days. It's still a fun exercise building your own though.

This is a bit of a pet peeve with anonymous Internet writing, but: are we supposed to know when you were at university? Do you know when I was? Why not state something like the number of decades or whatever?

And yeah, a void * is how you express pointer to data of unknown type in C.