8 ms·

Write a hash table in C

189 points by jmlr 9y ago

smegel 9y ago
This might seem academic, but I actually had a real reason to hand-roll a hash table implementation that would work in process-shared memory (as an Apache module). It was based on the hash table implemented in mod_ldap, and was part of an LRU cache.
sillysaurus3 9y ago
The link at the bottom of the intro is broken: https://github.com/jamesroutley/write-a-hash-table/blob/v0.1.0/hash-table https://github.com/jamesroutley/write-a-hash-table/blob/v0.1... preventing the reader from advancing. I think the whole thing would be best as a single page, to be honest. Even if it's long, people have scroll wheels. But it's a stylistic choice.
7Anonymous 9y ago
Just go back to the table of contents. The link works from there.
nathan_long 9y ago
If you just want to see hash tables work as a data structure, here's a talk-as-blog-post I made on the subject. http://nathanmlong.com/2015/10/reimplementing-rubys-hash/ http://nathanmlong.com/2015/10/reimplementing-rubys-hash/
- igravious 9y ago
  Nathan, that was absolutely fan-fuckin-tastic. Pardon me for the potty mouthed tmesis but that was a highly highly amusing run through. How did you do the graphs? (I'm always wondering how people do graphs.) And is that really you on the sofa waking up from the dream?
- deleted 9y ago
  [deleted]
baron816 9y ago
While the reasons for this that the author gave are valid, I think it would also be valuable to do this in a high level language. I'm sure lot of people who can read C code went through a CS program, and hopefully learned how hash tables work then. People without CS degrees and who mostly write JS/Ruby/Python/etc. and use hash tables on almost every line of code they write are much less likely to know how they work. Just saying, someone should do it for other languages.
- eighthnate 9y ago
  The problem with writing hash tables or any fundamental data structures in JS/Ruby/Python/etc is that most of the hard work is done for them. The hard part is allocation memory, keeping track of the structure(array) holding the hashtable, etc. What else is there? Implementing the hash function/code? If you don't have a CS degree, you probably don't even know how lists, queues, stacks, etc really work. But the kind of programming that is done at a "high" level, you might not even need know it. Instead of saying people should implement it JS/Ruby/Python/etc ( all of whom are OOPs ), they should learn C and implement it in C.
  - pfranz 9y ago
    There's room for both. There's a reason why a lot of CS programs have shuffled from primarily C to Python (some had Java in between). Not having to deal with boilerplate and housekeeping lets you focus on learning the topic at hand. Especially in a classroom setting where you're probably focusing on the specific subject instead of real-world dirtiness. But after learning the basic concept, you do need an actual implementation if you want to do anything.
    - eighthnate 9y ago
      > There's room for both. Sure. I'm all for learning ML, Scheme, C/C++, Python, Ruby, Java/C#, etc. > There's a reason why a lot of CS programs have shuffled from primarily C to Python (some had Java in between). The reason is called dumbing down the curriculum. My fall freshman year, my college tried to switch from C to Java in order to make it easier for the general population to get into CS and there was a major pushback from the CS student body, alumni and a bunch of the CS professors. We went back to C/C++ my sophomore year. > Not having to deal with boilerplate and housekeeping lets you focus on learning the topic at hand. I disagree. Having to deal with the boilerplate and housekeeping helps you learn the topic at hand. > But after learning the basic concept, you do need an actual implementation if you want to do anything. I disagree. Giving them "training wheels" will keep them dependent on training wheels. In an idealistic world, people go from Java/Python to C/Assembly, but that's rarely the case. CS should begin with Math ( boolean algebra/logic/etc ), Assembly and C. Then go on to functional paradigms. Then to OOP. Etc ( in the language ). Of course they should also learn about OS( kernel/filesystems/etc ), networks, computation theory/etc, compilers, etc. The dumbing down of the curriculum so that music/english majors can pass CS classes doesn't do anyone any favors.
cletusw 9y ago
Link should be changed to https://github.com/jamesroutley/write-a-hash-table https://github.com/jamesroutley/write-a-hash-table
- sctb 9y ago
  OK, we've updated the link from https://github.com/jamesroutley/write-a-hash-table https://github.com/jamesroutley/write-a-hash-table.
  - fao_ 9y ago
    What's the difference in the URLs, I can't see any.
jnordwick 9y ago
Why is this extremely basic CS 101 stuff being voted up today? Definitely not HN material.
- sgslo 9y ago
  Because not everyone who reads HN went through a CS program, and may have not seen implementations of common data structures like this before. Its a well-written tutorial that conveys the topic well.
  - jnordwick 9y ago
    My advice would be to take this to another website, one specifically for introductory CS topics. I expect a higher level of discussion on HN.
    - LittlePeter 9y ago
      good for you.
    - bauerd 9y ago
      My advice would be to go to another website, one specifically for non-introductory data structures.
    - deleted 9y ago
      [deleted]
  - MandieD 9y ago
    Heck, I did go through the CS program at an infamously competitive mid-Atlantic school with decent grades, and I still liked the tutorial and am glad to have seen it on HN. We can always use a look back at what's behind the "leaky abstractions" (to quote Joel Spolsky) that make our modern software world possible.
agumonkey 9y ago
hah, just a few days ago I named a few files hshtbl.c trie.c and so on. All after a Raymond Hettinger talk about how they rethought Python 3 dicts.
jay-anderson 9y ago
This is a good mostly simple overview. The appendix should also mention robin hood hashing as a method for addressing collisions. From my understanding it is cpu cache friendly and works well in practice.
__s 9y ago
Weird there isn't a src directory collecting everything together Hashtables are one of those data structures one can easily get away with never having to write on their own, yet still use every day. In scripting languages it's impractical to roll your own, & in the more abstracted low level languages there'll usually be a pretty good generic version. Yet there's much room for variation I had the joy to be out of reach of off-the-shelf hashtables for luwa, init: https://github.com/serprex/luwa/blob/436c7271120fcd116af30e906919afe7a7e55254/rt/alloc.lua#L156 https://github.com/serprex/luwa/blob/436c7271120fcd116af30e9... get/set: https://github.com/serprex/luwa/blob/436c7271120fcd116af30e906919afe7a7e55254/rt/table.lua https://github.com/serprex/luwa/blob/436c7271120fcd116af30e9... hash: https://github.com/serprex/luwa/blob/436c7271120fcd116af30e906919afe7a7e55254/rt/obj.lua#L130 https://github.com/serprex/luwa/blob/436c7271120fcd116af30e9... Still need to implement Lua's sequential-portion-as-array logic. I do like the API not having a 'remove' method, opting intead for nil by default. nil value entries get vacuumed out when rehashing. This ends up acting as tombstone. In an earlier iteration I was using 0 as a marker distinct from nil, but an implementation detail is that nil is stored at address 0.. oops
msarnoff 9y ago
"The language doesn't come with [a hash table implementation] included" The standard library does come with a half-baked hash table implementation[1] (hcreate/hdestroy/hsearch) that only allows creation of _one_ global hash table. GNU libc[2] adds hcreate_r/hdestroy_r/hsearch_r that allows multiple tables to be created. The APIs are strange and antiquated. On the other hand, the hash table implementation described in the article presents a much nicer interface. [1] http://pubs.opengroup.org/onlinepubs/009695399/functions/hcreate.html http://pubs.opengroup.org/onlinepubs/009695399/functions/hcr... [2] http://man7.org/linux/man-pages/man3/hsearch.3.html http://man7.org/linux/man-pages/man3/hsearch.3.html
- to3m 9y ago
  The hcreate nonsense is POSIX, not C99, so a conforming C implementation might not include it.
  - twic 9y ago
    How does junk like this ever get into a standard? Didn't a whole committee of very experienced systems programmers have to sit down and say, "yes, these are routines that i think people will find generally useful"? It looks like the same header, search.h, also includes functions for working with binary trees, where the user passes in the root pointer, and so which support multiple trees: http://pubs.opengroup.org/onlinepubs/9699919799/functions/tsearch.html http://pubs.opengroup.org/onlinepubs/9699919799/functions/ts... So this committee must have signed off on the hashtable stuff even though they had an example of how to do it properly right next to it!
    - jws 9y ago
      A standards process is frequently about documenting what already exists in common implementations so that there is a specification for future implementations. POSIX was very much one of these processes.
      - to3m 9y ago
clarry 9y ago
Don't allocate these items individually; don't store pointers to such items. They're tiny, and the pointer chasing + allocator bookkeeping overhead + potential randomisation make it inefficient for no gain. Just allocate an array of items. This way you'll also deal with fewer potential errors. Speaking of errors, please handle them and fix the API so that the caller can know if there's a problem.
- pacaro 9y ago
  Yeah, reading through that jumped out at me. Also the use of strdup, while a reasonable choice, should also come with caveats about ownership and copying I stopped at the use of pow for exponentiation in the hash function. Just iteratively multiply your factor and take the modulus on each round. This would handle utf-8 just fine if characters are cast to unsigned in the hash function and a larger prime factor is used None of these are real criticisms, I'd just love to see a pointer to more in depth information on how to really write hash functions I hope that i missed it, but this definitely needs a clear statement that this is a pedagogical exercise and not a production ready implementation
benlorenzetti 9y ago
In the intro section, on extending to unicode being non-trivial...is the argument that if your input has some non-ascii data you probably have all non-ascii data and the above 127 bucket will be too full? Honest question.
dullgiulio 9y ago
If your set is known at compile time, make a Perfect Hash Table with gperf instead. It's commonly used in compilers and other software with a parsing or interpreting stage.
fizixer 9y ago
I've heard of two possibilities (as a recommendation) for using data structures in C without having to develop them: - BSD queue.h offers linked lists, queues, etc [1]. - UT-hash offers hash tables [2]. I've also read some people being frustrated with them, probably due to the quirky syntax/API. On the plus side (BSD at least) it's just a header file that you can download, include and start using. [1] http://bxr.su/OpenBSD/sys/sys/queue.h http://bxr.su/OpenBSD/sys/sys/queue.h [2] https://troydhanson.github.io/uthash/ https://troydhanson.github.io/uthash/
- dottrap 9y ago
  Also there is the header-only khash.h [3], complete with benchmarks: https://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/ https://attractivechaos.wordpress.com/2008/08/28/comparison-... (Also provides kbtree.h, ksort.h, kstream.h, kvec.h) [3] https://attractivechaos.wordpress.com/programs/ https://attractivechaos.wordpress.com/programs/ Also there are the stb header-only libraries. There is a hash table implementation buried inside stb.h [4] https://github.com/nothings/stb https://github.com/nothings/stb
- nurettin 9y ago
  I think at this point if you aren't in a very constrained platform, it doesn't really make sense to use someone else's data structure implementations unless they at least support some kind of CPU parallelism. Preferably openmp or whatever suits the algorithm at hand.
- DSMan195276 9y ago
  Definitely look into the Linux kernel data structures. Container_of is a fantastic way to do data structures in C.
- sigjuice 9y ago
  Also, BSD tree.h for red-black trees and splay trees http://bxr.su/OpenBSD/sys/sys/tree.h http://bxr.su/OpenBSD/sys/sys/tree.h
- atrn 9y ago
  Have a look for Phong Vo's CDT - container data type - library.
pieguy 9y ago
"(long)pow(a, len_s - (i+1))" is both inefficient and inaccurate. You should store the current power in a variable which you multiply by 'a' and reduce by 'm' on each iteration. Also, your double hashing scheme has a bug. You identified that it's problematic if hash_b returns 0, but adding 1 to the result doesn't actually solve anything, because now you have the same problem if hash_b returns num_buckets-1.
peterbotond 9y ago
berkeley db 185. it has served me very good over the years and it was fast enough for real time market data and indexing and many more.

189 points by jmlr 9y ago

This might seem academic, but I actually had a real reason to hand-roll a hash table implementation that would work in process-shared memory (as an Apache module). It was based on the hash table implemented in mod_ldap, and was part of an LRU cache.

sillysaurus3 9y ago

The link at the bottom of the intro is broken: https://github.com/jamesroutley/write-a-hash-table/blob/v0.1.0/hash-table https://github.com/jamesroutley/write-a-hash-table/blob/v0.1... preventing the reader from advancing. I think the whole thing would be best as a single page, to be honest. Even if it's long, people have scroll wheels. But it's a stylistic choice.

7Anonymous 9y ago

Just go back to the table of contents. The link works from there.

nathan_long 9y ago

If you just want to see hash tables work as a data structure, here's a talk-as-blog-post I made on the subject. http://nathanmlong.com/2015/10/reimplementing-rubys-hash/ http://nathanmlong.com/2015/10/reimplementing-rubys-hash/

igravious 9y ago
Nathan, that was absolutely fan-fuckin-tastic. Pardon me for the potty mouthed tmesis but that was a highly highly amusing run through. How did you do the graphs? (I'm always wondering how people do graphs.) And is that really you on the sofa waking up from the dream?
deleted 9y ago
[deleted]

baron816 9y ago

While the reasons for this that the author gave are valid, I think it would also be valuable to do this in a high level language. I'm sure lot of people who can read C code went through a CS program, and hopefully learned how hash tables work then. People without CS degrees and who mostly write JS/Ruby/Python/etc. and use hash tables on almost every line of code they write are much less likely to know how they work. Just saying, someone should do it for other languages.

eighthnate 9y ago
The problem with writing hash tables or any fundamental data structures in JS/Ruby/Python/etc is that most of the hard work is done for them. The hard part is allocation memory, keeping track of the structure(array) holding the hashtable, etc. What else is there? Implementing the hash function/code? If you don't have a CS degree, you probably don't even know how lists, queues, stacks, etc really work. But the kind of programming that is done at a "high" level, you might not even need know it. Instead of saying people should implement it JS/Ruby/Python/etc ( all of whom are OOPs ), they should learn C and implement it in C.
- pfranz 9y ago
  There's room for both. There's a reason why a lot of CS programs have shuffled from primarily C to Python (some had Java in between). Not having to deal with boilerplate and housekeeping lets you focus on learning the topic at hand. Especially in a classroom setting where you're probably focusing on the specific subject instead of real-world dirtiness. But after learning the basic concept, you do need an actual implementation if you want to do anything.
  - eighthnate 9y ago
    > There's room for both. Sure. I'm all for learning ML, Scheme, C/C++, Python, Ruby, Java/C#, etc. > There's a reason why a lot of CS programs have shuffled from primarily C to Python (some had Java in between). The reason is called dumbing down the curriculum. My fall freshman year, my college tried to switch from C to Java in order to make it easier for the general population to get into CS and there was a major pushback from the CS student body, alumni and a bunch of the CS professors. We went back to C/C++ my sophomore year. > Not having to deal with boilerplate and housekeeping lets you focus on learning the topic at hand. I disagree. Having to deal with the boilerplate and housekeeping helps you learn the topic at hand. > But after learning the basic concept, you do need an actual implementation if you want to do anything. I disagree. Giving them "training wheels" will keep them dependent on training wheels. In an idealistic world, people go from Java/Python to C/Assembly, but that's rarely the case. CS should begin with Math ( boolean algebra/logic/etc ), Assembly and C. Then go on to functional paradigms. Then to OOP. Etc ( in the language ). Of course they should also learn about OS( kernel/filesystems/etc ), networks, computation theory/etc, compilers, etc. The dumbing down of the curriculum so that music/english majors can pass CS classes doesn't do anyone any favors.

cletusw 9y ago

Link should be changed to https://github.com/jamesroutley/write-a-hash-table https://github.com/jamesroutley/write-a-hash-table

sctb 9y ago
OK, we've updated the link from https://github.com/jamesroutley/write-a-hash-table https://github.com/jamesroutley/write-a-hash-table.
- fao_ 9y ago
  What's the difference in the URLs, I can't see any.

jnordwick 9y ago

Why is this extremely basic CS 101 stuff being voted up today? Definitely not HN material.

sgslo 9y ago
Because not everyone who reads HN went through a CS program, and may have not seen implementations of common data structures like this before. Its a well-written tutorial that conveys the topic well.
- jnordwick 9y ago
  My advice would be to take this to another website, one specifically for introductory CS topics. I expect a higher level of discussion on HN.
  - LittlePeter 9y ago
    good for you.
  - bauerd 9y ago
    My advice would be to go to another website, one specifically for non-introductory data structures.
  - deleted 9y ago
    [deleted]
- MandieD 9y ago
  Heck, I did go through the CS program at an infamously competitive mid-Atlantic school with decent grades, and I still liked the tutorial and am glad to have seen it on HN. We can always use a look back at what's behind the "leaky abstractions" (to quote Joel Spolsky) that make our modern software world possible.

agumonkey 9y ago

hah, just a few days ago I named a few files hshtbl.c trie.c and so on. All after a Raymond Hettinger talk about how they rethought Python 3 dicts.

jay-anderson 9y ago

This is a good mostly simple overview. The appendix should also mention robin hood hashing as a method for addressing collisions. From my understanding it is cpu cache friendly and works well in practice.

__s 9y ago

Weird there isn't a src directory collecting everything together Hashtables are one of those data structures one can easily get away with never having to write on their own, yet still use every day. In scripting languages it's impractical to roll your own, & in the more abstracted low level languages there'll usually be a pretty good generic version. Yet there's much room for variation I had the joy to be out of reach of off-the-shelf hashtables for luwa, init: https://github.com/serprex/luwa/blob/436c7271120fcd116af30e906919afe7a7e55254/rt/alloc.lua#L156 https://github.com/serprex/luwa/blob/436c7271120fcd116af30e9... get/set: https://github.com/serprex/luwa/blob/436c7271120fcd116af30e906919afe7a7e55254/rt/table.lua https://github.com/serprex/luwa/blob/436c7271120fcd116af30e9... hash: https://github.com/serprex/luwa/blob/436c7271120fcd116af30e906919afe7a7e55254/rt/obj.lua#L130 https://github.com/serprex/luwa/blob/436c7271120fcd116af30e9... Still need to implement Lua's sequential-portion-as-array logic. I do like the API not having a 'remove' method, opting intead for nil by default. nil value entries get vacuumed out when rehashing. This ends up acting as tombstone. In an earlier iteration I was using 0 as a marker distinct from nil, but an implementation detail is that nil is stored at address 0.. oops

msarnoff 9y ago

"The language doesn't come with [a hash table implementation] included" The standard library does come with a half-baked hash table implementation[1] (hcreate/hdestroy/hsearch) that only allows creation of _one_ global hash table. GNU libc[2] adds hcreate_r/hdestroy_r/hsearch_r that allows multiple tables to be created. The APIs are strange and antiquated. On the other hand, the hash table implementation described in the article presents a much nicer interface. [1] http://pubs.opengroup.org/onlinepubs/009695399/functions/hcreate.html http://pubs.opengroup.org/onlinepubs/009695399/functions/hcr... [2] http://man7.org/linux/man-pages/man3/hsearch.3.html http://man7.org/linux/man-pages/man3/hsearch.3.html

to3m 9y ago
The hcreate nonsense is POSIX, not C99, so a conforming C implementation might not include it.
- twic 9y ago
  How does junk like this ever get into a standard? Didn't a whole committee of very experienced systems programmers have to sit down and say, "yes, these are routines that i think people will find generally useful"? It looks like the same header, search.h, also includes functions for working with binary trees, where the user passes in the root pointer, and so which support multiple trees: http://pubs.opengroup.org/onlinepubs/9699919799/functions/tsearch.html http://pubs.opengroup.org/onlinepubs/9699919799/functions/ts... So this committee must have signed off on the hashtable stuff even though they had an example of how to do it properly right next to it!
  - jws 9y ago
    A standards process is frequently about documenting what already exists in common implementations so that there is a specification for future implementations. POSIX was very much one of these processes.
    - to3m 9y ago

clarry 9y ago

Don't allocate these items individually; don't store pointers to such items. They're tiny, and the pointer chasing + allocator bookkeeping overhead + potential randomisation make it inefficient for no gain. Just allocate an array of items. This way you'll also deal with fewer potential errors. Speaking of errors, please handle them and fix the API so that the caller can know if there's a problem.

pacaro 9y ago
Yeah, reading through that jumped out at me. Also the use of strdup, while a reasonable choice, should also come with caveats about ownership and copying I stopped at the use of pow for exponentiation in the hash function. Just iteratively multiply your factor and take the modulus on each round. This would handle utf-8 just fine if characters are cast to unsigned in the hash function and a larger prime factor is used None of these are real criticisms, I'd just love to see a pointer to more in depth information on how to really write hash functions I hope that i missed it, but this definitely needs a clear statement that this is a pedagogical exercise and not a production ready implementation

benlorenzetti 9y ago

In the intro section, on extending to unicode being non-trivial...is the argument that if your input has some non-ascii data you probably have all non-ascii data and the above 127 bucket will be too full? Honest question.

dullgiulio 9y ago

If your set is known at compile time, make a Perfect Hash Table with gperf instead. It's commonly used in compilers and other software with a parsing or interpreting stage.

fizixer 9y ago

I've heard of two possibilities (as a recommendation) for using data structures in C without having to develop them: - BSD queue.h offers linked lists, queues, etc [1]. - UT-hash offers hash tables [2]. I've also read some people being frustrated with them, probably due to the quirky syntax/API. On the plus side (BSD at least) it's just a header file that you can download, include and start using. [1] http://bxr.su/OpenBSD/sys/sys/queue.h http://bxr.su/OpenBSD/sys/sys/queue.h [2] https://troydhanson.github.io/uthash/ https://troydhanson.github.io/uthash/

dottrap 9y ago
Also there is the header-only khash.h [3], complete with benchmarks: https://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/ https://attractivechaos.wordpress.com/2008/08/28/comparison-... (Also provides kbtree.h, ksort.h, kstream.h, kvec.h) [3] https://attractivechaos.wordpress.com/programs/ https://attractivechaos.wordpress.com/programs/ Also there are the stb header-only libraries. There is a hash table implementation buried inside stb.h [4] https://github.com/nothings/stb https://github.com/nothings/stb
nurettin 9y ago
I think at this point if you aren't in a very constrained platform, it doesn't really make sense to use someone else's data structure implementations unless they at least support some kind of CPU parallelism. Preferably openmp or whatever suits the algorithm at hand.
DSMan195276 9y ago
Definitely look into the Linux kernel data structures. Container_of is a fantastic way to do data structures in C.
sigjuice 9y ago
Also, BSD tree.h for red-black trees and splay trees http://bxr.su/OpenBSD/sys/sys/tree.h http://bxr.su/OpenBSD/sys/sys/tree.h
atrn 9y ago
Have a look for Phong Vo's CDT - container data type - library.

pieguy 9y ago

"(long)pow(a, len_s - (i+1))" is both inefficient and inaccurate. You should store the current power in a variable which you multiply by 'a' and reduce by 'm' on each iteration. Also, your double hashing scheme has a bug. You identified that it's problematic if hash_b returns 0, but adding 1 to the result doesn't actually solve anything, because now you have the same problem if hash_b returns num_buckets-1.

peterbotond 9y ago

berkeley db 185. it has served me very good over the years and it was fast enough for real time market data and indexing and many more.