Comment by switch_kickflip
8 years ago
I am essentially a hash table fetishist, and I'm a little bummed out that this doesn't go into more detail about how the damn thing works. How do you do implement a chaining hash table that uses a single flat array?
Like a FAT format but with relative indices. It should be pretty trivial pointer arithmetic.
Edit: bytell_hash_map.cpp:464 bytell_hash_map.cpp:58
Apparently there's one extra layer of indirection via a lookup table to get the final offset.
So basically the metadata byte is a bitfield union of + status flag + status code (not sure it's actually required) or offset enum. The offset enum then indexes into a look up table, the result of which is the relative offset from the current index.
He mentions he'll update the blog post with a link to the talk he gave once it's online
You can look at the source in his github repository: https://github.com/skarupke/flat_hash_map
I looked through the code and o_O there is a lot of C++ boilerplate. The core part of it is not really documented well, and there is this mysterious jump bits array...if I had more time, I could figure out it. But that's the point of a writeup, explaining things with a diagram, etc.
> I looked through the code and o_O there is a lot of C++ boilerplate.
This boilerplate allows me to choose between std::unordered_map and flat_hash_map in my whole code just by toggling a compile time switch in my code. It ensures that the data structures has the same API than all other C++ containers.
3 replies →
To be honest, when it comes to C++ boilerplate, I've seen much, much worse. At a first glance the code looks somewhat clean.
That's not the same as having a high level description of the concepts used. For details I can still dive into the details later.
You do hash % bucketCount to find your bucket/slot. Each array element is also a linked list node (with a next pointer), thus if the slot is populated you follow the linked list until an empty slot is found and attach to the end of the linked list.
I figure it works best if you over allocate slots, so that on average you only have to do very few hops on each linked list walk (or no walk at all).
Aside: This is the method employed by .NET's Dictionary<K,V> class.
Further - it's generally faster to use structure of arrays rather than array of structures, thus in the above scheme the dictionary items/payloads and the linked list pointers could be in separate arrays.