[ww520]

This looks very good. The idea of using a subnet-mask style to compute the prefix of a node is pretty novel. I haven't seen anything like it. The choice of span factor of 16 is a good compromise between node size and tree depth. The node slot packing is amazing. Actually if you relax the restriction on 64-byte node to 128-byte node, you can get 64 bits per slot and will get a much higher limit for the item count. Newer CPU's are starting to support 128-byte cache line.

[mrazomor]

If I understood it correctly, it's not much different from what `absl::flat_hash_map` does.

Look for "Metadata information"/control bits at https://abseil.io/about/design/swisstables

[ww520]

I believe it's quite different. If I'm not mistaken, flat_hash_map is a typical hash table, with a hash function to map the key to a bucket. Its novel part is using the 7 lower bits of the hashed value as a bit mask against the control bits to check the presence of the item. It's like a mini-Bloom-Filter where a false query means the item definitely not in the bucket while a positive query means the item might be in the bucket. A subsequent search through the bucket can confirm the existence of the item.

This int map is a trie with an integer based key.