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.
3
