unordered_map 与水桶相撞

Question

我正在使用 C++11 中的 unordered_map 库，我对存储桶的工作方式有些困惑。根据 cplusplus 网站上的文档，我很清楚它们并不像我想象的那样工作。

我希望我的密钥对中的密钥会散列到同一个桶中。例如：

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
  unordered_map<string, string> map;
  map.emplace("abc", "bca");
  map.emplace("abc", "bac");
  cout << map.bucket_size(map.bucket("abc")) << endl;
  cout << map.bucket_count() << endl;
  return 0;
}

我的预期是输出是

2
1

然而，它是

1
2

我知道输出的结果比我的预期理想得多，目标是尽可能少的链接，但出于我的目的，我希望发生这种链接和碰撞，以便我可以进行计算我需要为我的程序。我是否缺少完成此操作的步骤？

Answer 1

出现了一些情况 - 一个是您将同一个密钥输入两次。最终发生的是第二个 emplace 实际上失败了，因为对于任何地图数据结构，每个键只能获得一个值。如果您查看，您会发现包含 "abc" 的存储桶具有 "bca" 的值。

至于 bucket_count，不能保证它是任何特定值，并且很可能是实现定义的。例如，它可能是您的实现总是至少创建 2 个存储桶（如果它创建的话）。在决定丢弃该项目之前，它还可以在插入第二个项目时创建第二个存储桶。

unordered_map 与水桶相撞

unordered_map collision with buckets

hashtable

data-structures

c++11