c++ - Hashmaps：节点图和平面图有什么区别？

Question

有哪些不同类型的哈希表以及它们之间的区别？

我经常看到对“节点图”和“平面图”类型的引用。Abseil 库有这两种实现，但没有解释不同的用例是什么，谷歌搜索也没有显示任何描述。

标签： c++hashmap

Answer 1

Tip #136很好地解释了它。

简而言之：Abseil 平面地图有一个桶数组，直接存储地图条目。节点映射存储指向映射条目的指针。（这两种类型显然都使用开放寻址策略。）值得注意的是，在平面地图中，即使是空桶也会占用空间。在节点映射中，它们只占用一个指针的内存。

最后，请注意，“平面映射”一词，尤其是在 C++ 世界之外，通常保留用于收集将函数应用于子序列的每个元素的结果的函数，这是一个非常不同的含义。