3 ms·
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/a
by mrazomor 3y 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 https://abseil.io/about/design/swisstables
- ww520 3y agoI 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.