我对 unordered_map 的工作原理、存储桶是什么以及如何管理它们有点困惑。
From 这篇博文 http://codeforces.com/blog/entry/21853, unordered_map 是向量的向量。
我的问题是：
- 假设桶是“内部”向量是否正确？
- 由于每个存储桶（向量）可以包含多个元素，由哈希表（“外部”向量）上的哈希冲突给出，并且由于我们必须扫描这个内部向量（以线性时间），因此假设我们是否正确必须在键类型上定义 equal 方法（除了哈希运算符之外）才能找到存储桶内的键？
- 默认情况下外部向量（哈希表）大小是多少？
- 默认情况下内部向量大小是多少？
- 如果一个存储桶中的元素数量变得太大会发生什么？换句话说，当重新散列发生时会发生什么？
对于这些问题，我很抱歉，但我没有找到任何详细解释此结构如何工作（例如在 cppreference.com 上）。
std::unordered_map http://en.cppreference.com/w/cpp/container/unordered_map是标准的C++哈希表 https://en.wikipedia.org/wiki/Hash_table。它曾经被称为hash_map https://www.sgi.com/tech/stl/hash_map.html在 STL 中，但是当 1998 年 STL 的许多接口被合并到 C++ 中时错过了机会，到 2011 年，很多库都有自己的 hash_map，C++ 不得不选择另一个名称（我认为“无序”是一个很好的选择；假设顺序哈希表中的内容是错误的常见来源）。
假设桶是“内部”向量是否正确？
不，它既不正确（与迭代器失效要求不兼容）又危险（在这种假设下，您最终可能会减去指向同一存储桶中元素的指针）。
在现实生活中，桶是链表；例如
- LLVM libc++
unordered_map is a unique_ptr 到数组 https://github.com/llvm-mirror/libcxx/blob/master/include/__hash_table#L946的链表的__哈希_节点 https://github.com/llvm-mirror/libcxx/blob/master/include/__hash_table#L70s
- GNU libstdc++
unordered_map is a 指向数组的指针 https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/hashtable.h#L312的链表的_哈希_节点 https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L227s
假设我们必须在键类型上定义 equal 方法（除了哈希运算符）才能找到存储桶中的键，是否正确？
是的，在存储桶中定位密钥正是第 4 个模板参数std::unordered_map是 for （当然，不需要从字面上调用“键类型上的相等方法”）
默认情况下外部向量（哈希表）大小是多少？
不存在“外部向量”。默认构造的桶数std::unordered_map is 实现定义的 http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map，您可以使用以下方式查询桶数 http://en.cppreference.com/w/cpp/container/unordered_map/bucket_count.
默认情况下内部向量大小是多少？
不存在“内部向量”。任何给定存储桶的大小等于当前放置在存储桶中的元素数量。您可以使用以下方式查询桶大小 http://en.cppreference.com/w/cpp/container/unordered_map/bucket_size
如果一个存储桶中的元素数量变得太大会发生什么？换句话说，当重新散列发生时会发生什么？
如果元素数量达到，则不会发生任何事情one水桶变得太大。但是如果每个桶的平均元素数（又名负载系数 http://en.cppreference.com/w/cpp/container/unordered_map/load_factor) 超过最大负载系数 http://en.cppreference.com/w/cpp/container/unordered_map/max_load_factor，重新散列发生（例如insert http://en.cppreference.com/w/cpp/container/unordered_map/insert)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
