哈希图：节点图和平面图有什么区别？

Question

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

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

Answer 1

提示 #136很好地解释了这一点。

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

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