不确定unordered_map是如何工作的

Question

我有点搞不懂unordered_map是如何工作的，桶是什么，它们是如何管理的。

在这篇博客文章中，unordered_map是向量的向量。

我的问题是：

• 假设桶是“内部”向量是正确的吗？
• 由于每个桶(向量)可以包含多个元素，这是由哈希表(“外部”向量)上的哈希冲突给出的，而且由于我们必须扫描这个内部向量(在线性时间内)，那么假设我们必须在密钥类型(依赖哈希操作符)上定义相等的方法才能找到桶内的密钥，这样做正确吗？
• 默认情况下，外部向量(哈希表)大小是多少？
• 默认情况下，内部向量大小是多少？
• 如果一个桶中的元素数量变得太大怎么办?换句话说，当重新哈希发生时会发生什么？

对不起，这些问题，但我没有找到任何详细的解释，这个结构如何工作(例如，在cppreference.com )。

Answer 1

地图是标准的C++ 哈希表。它过去在STL中被称为地图，但是当许多STL接口在1998年被合并到C++中时，它错过了这条船。到了2011年，许多库都有了自己的hash_map，C++不得不选择另一个名称(我认为“无序”是一个很好的选择；假设哈希表中的顺序是一个常见的bug源)。

假设桶是“内部”向量是正确的吗？

不，这既不正确(与迭代器失效要求不兼容)，也很危险(在这种假设下，您可能最终会减去指向同一桶中元素的指针)。

在现实生活中，桶是链表。

• LLVM libc++ unordered_map是节点的链接列表的ptr到数组。
• libstdc++ unordered_map是节点的链接列表的指向数组的指针。

假设我们必须在密钥类型(依赖于哈希操作符)上定义相等的方法才能在桶中找到密钥，这是正确的吗？

是的，在桶中定位键正是std::unordered_map的第四个模板参数(当然，不需要按字面意思调用“键类型上的相等方法”)。

默认情况下，外部向量(哈希表)大小是多少？

没有“外部矢量”。默认构造的std::unordered_map的桶数是执行-定义，您可以使用计数查询它。

默认情况下，内部向量大小是多少？

没有“内部矢量”。任何给定桶的大小等于当前放置在桶中的元素数。您可以使用大小查询它

如果一个桶中的元素数量变得太大怎么办?换句话说，当重新哈希发生时会发生什么？

如果一个桶中的元素数量变得太大，什么都不会发生。但是，如果每个桶的平均元素数(也称为因子)超过了因子，则会发生重散列(例如在插入上)。

Answer 2

这可能有助于您理解水桶：数/数 因数/

但一般来说，是的，水桶类似于内部向量。它需要一个相等操作符(或谓词)来区分具有与您建议的相同散列的键。

桶的初始数目可能是0。它可以通过re散列()或reserve()来设置(它们的语义略有不同)。

地图/重散/

在理想的情况下，每个水桶将只有一个项目。您可以通过使用bucket_size来检查这一点。当负载因子(总项与桶数)较高时，它会自动重新散列。

默认情况下，它的目标是1:1的负载因子。如果哈希函数是好的，这可能会持续到插入max_bucket_count项为止。

请记住，这方面的具体实现可能有所不同。每个实现(例如来自不同平台或标准库)实际上只需要有正确的语义。

如果这些答案对您的程序很重要，您可以像我所描述的那样查询这些值。如果您只是试图将您的想法围绕在一起，那么在一些测试场景中查询它们，可能会变得更清楚。