Hashmaps: What's the Difference Between a Node Map and a Flat Map?
What Are the Different Types of Hashtables and the Difference Between Them? I Often See References to "Node Map" and "Flat Map" Types. Abseil Library Has Both...
What are the different types of hashtables and the difference between them?
I often see references to "node map" and "flat map" types. Abseil library has both implementations, but doesn't explain what the different use cases are, and neither does a Google search reveal any description.
1 Answer
Tip #136 explains it pretty well.
In short: An Abseil flat map has a bucket array that directly stores map entries. A node map stores pointers to map entries. (Both types apparently use open addresing strategy.) Notably, in a flat map, even empty buckets take up space; in a node map, they only take up a pointer's worth of memory.
Finally, note that the term "flat map" is, especially outside of the C++ world, usually reserved for a function that collects results of applying a function to each element of a subsequence, a very different meaning.
Marcus Vance is a cybersecurity auditor and technology writer dedicated to educating the public about online safety, data privacy regulations, enterprise security, and emerging cyber threats.
