Hacker News Reader

Comment by switch_kickflip | Hacker News Reader

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?

View on HN

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

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.

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.

To be honest, when it comes to C++ boilerplate, I've seen much, much worse. At a first glance the code looks somewhat clean.

> 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.

I understand what it is for. YMMV but for me C++ is pretty much a constant mental stack overflow when reading the guts like this. It seems like C++ libraries are getting more and more configurable in a way that hurts readability and understandability and library designers don't seem to recognize there is a fundamental tradeoff here.

> It seems like C++ libraries are getting more and more configurable in a way that hurts readability and understandability and library designers don't seem to recognize there is a fundamental tradeoff here.

well, I mean... if it was not configurable, it would not really be useful, except for toy examples, and for those the default std::unordered_map is more than sufficient. To be useful, a hash table implementation at least needs to allow to configure the hash function and the comparison operator.

I actually have separate implementations of an algorithm with and without templates; the template one is for benchmarking with different combinations of options; the non-template one is for readability, and it's only about 60 lines.

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.

Reply on news.ycombinator.com