5 ms·

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 impleme

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?

wichert 8y ago
You can look at the source in his github repository: https://github.com/skarupke/flat_hash_map https://github.com/skarupke/flat_hash_map
- dividuum 8y ago
  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.
- titzer 8y ago
  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.
  - Tomis02 8y ago
    To be honest, when it comes to C++ boilerplate, I've seen much, much worse. At a first glance the code looks somewhat clean.
  - jcelerier 8y ago
    > 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.
    - titzer 8y ago
      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.
      - jcelerier 8y ago
        > 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.
      - kwillets 8y ago
        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.
lentil_soup 8y ago
He mentions he'll update the blog post with a link to the talk he gave once it's online
andromeduck 8y ago
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.
redcalx 8y ago
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.

wichert 8y ago

You can look at the source in his github repository: https://github.com/skarupke/flat_hash_map https://github.com/skarupke/flat_hash_map

dividuum 8y ago
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.
titzer 8y ago
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.
- Tomis02 8y ago
  To be honest, when it comes to C++ boilerplate, I've seen much, much worse. At a first glance the code looks somewhat clean.
- jcelerier 8y ago
  > 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.
  - titzer 8y ago
    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.
    - jcelerier 8y ago
      > 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.
    - kwillets 8y ago
      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.

lentil_soup 8y ago

He mentions he'll update the blog post with a link to the talk he gave once it's online

andromeduck 8y ago

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.

redcalx 8y ago

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.