Hacker News new | ask | show | jobs
by mrazomor 882 days ago
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

1 comments

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.