不确定unordered_map的工作原理

Question

我有点困惑,unordered_map是如何工作的,什么是桶以及如何管理它们.

在这篇博文中,unordered_map是向量的向量.

我的问题是:

• 假设桶是"内部"向量是正确的吗？
• 因为每个桶(向量)可以包含多个元素,由哈希表上的哈希冲突("外部"向量)给出,并且由于我们必须扫描这个内部向量(在线性时间内),假设我们是正确的必须在密钥类型上定义相等的方法(对哈希运算符成瘾)才能找到桶内的密钥？
• 默认情况下外部向量(哈希表)大小是多少？
• 默认情况下内部矢量大小是多少？
• 如果一个桶中的元素数量变得太大会发生什么呢？换句话说,当重新发生时？

很抱歉这些问题,但我没有找到任何详细解释这个结构是如何工作的(例如在cppreference.com上).

Answer 1

std :: unordered_map是标准的C++ 哈希表.它曾经在STL中被称为hash_map,但在1998年许多STL的接口被合并到C++中时错过了船,到2011年,很多库都有自己的hash_map,C++不得不选择另一个名称(我认为"无序"是一个很好的选择;假设哈希表中的顺序是错误的常见来源.

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

不,它都是不正确的(与迭代器无效要求不兼容)和危险(在这个假设下你最终可能会减去指向同一个桶中元素的指针).

在现实生活中,桶是链表; 例如

• LLVM libc ++ unordered_map是__hash_node的链接列表数组的unique_ptr
• GNU libstdc ++ unordered_map是指向_Hash_node的链接列表数组的指针

是否正确假设我们必须在密钥类型上定义相等的方法(对哈希运算符成瘾)才能找到桶内的密钥？

是的,在桶中定位密钥正是第4个模板参数的std::unordered_map用途(当然,不需要在字面上调用"密钥类型上的相等方法")

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

没有"外部载体".默认构造的存储桶数量std::unordered_map是实现定义的,您可以使用bucket_count进行查询.

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

没有"内部载体".任何给定存储桶的大小等于当前放置在存储桶中的元素数.您可以使用bucket_size进行查询

如果一个桶中的元素数量变得太大会发生什么呢？换句话说,当重新发生时？

如果一个桶中的元素数量变得太大,则没有任何反应.但是如果每个桶的平均元素数(也就是load_factor)超过max_load_factor,则会发生重新散列(例如插入时)

Answer 2

这可能会帮助您了解存储桶： http://www.cplusplus.com/reference/unordered_map/unordered_map/bucket_count/ http://www.cplusplus.com/reference/unordered_map/unordered_map/max_load_factor/

但一般来说，是的，桶类似于内部向量。它需要一个相等运算符（或谓词）来区分具有与您建议的相同哈希值的键。

初始桶数可能为 0。可以通过 rehash() 或 Reserve() 设置（它们的语义略有不同。）

http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/

在理想情况下，每个存储桶只会包含一个项目。您可以使用bucket_size 来检查这一点。当负载系数（总项目与存储桶计数）变高时，它会自动重新散列。

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

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

如果这些答案对您的程序很重要，您可以按照我的描述查询这些值。如果您只是想理解它，请在一些测试场景中查询它们，它可能会变得更加清晰。