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

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.