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.

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.

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.

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

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.