4 ms·
I was looking for something like this a few months ago and found this which also may be of interest: https://news.ycombinator.com/item?id=26590234 https://news
by version_five 3y ago
I was looking for something like this a few months ago and found this which also may be of interest:
https://news.ycombinator.com/item?id=26590234 https://news.ycombinator.com/item?id=26590234
How to implement a hash table in C (benhoyt.com)
302 points by benhoyt on March 26, 2021, 158 comments
- benhoyt 3y agoThanks for sharing! I do like the OP's article, but the more the merrier! My "How to implement a hash table in C" article [1] is for whatever reason one of my most popular articles. If only C had a slightly better standard library. :-) In my article I use "open addressing" [2] instead of linked lists for collisions, as 1) it tends to be simpler, as you only have one data structure to manage (array, rather than array and linked list), and 2) it tends to be faster, as linked lists are slow on modern CPUs because they require jumping around in memory. [1] https://benhoyt.com/writings/hash-table-in-c/ https://benhoyt.com/writings/hash-table-in-c/ [2] https://en.wikipedia.org/wiki/Open_addressing https://en.wikipedia.org/wiki/Open_addressing
- version_five 3y agoHey, thanks for writing it up! Like I said, I was looking for exactly this a few months ago, and between the explanation and the code it was a big help.
- marginalia_nu 3y agoYeah I think open addressing with linear probing is definitely the paradigm I'd choose if I wanted to build a "simple" hash table for educational purposes. It well enough and is conceptually probably the easiest approach to grok with relatively few pitfalls.