c++ - 如果我知道映射键的预期数量，我应该使用什么 bucket_count 值？

Question

我正在创建一个std::unordered_map，我将立即用 n 个键值对填充它——我知道 n. 之后将不再添加任何元素 - 我只会执行查找。

因此，我应该将什么传递bucket_count给构造函数？

笔记：

• 我知道这不是非常关键，我可以简单地不指定任何东西，它会起作用。
• 这与但不是欺骗有关，如果我只想指定哈希函数，我应该将什么传递给 unordered_map 的存储桶计数参数？)
• 如果它有助于您的回答，您可能会假设我希望在 f_1 和 f_2 之间有一个负载因子（提前知道）。
• 我使用的是默认的散列函数，我不知道输入是什么样的，但它不太可能与散列对抗..

Answer 1

根据23.5.4.2 [unord.map.cnstr] 中的 n4296（这是 C++14 的最终草案），默认情况下max_load_factorfor anunordered_map为 1.0，因此您只需将 bucket_count 设置为n.

显然，在增加桶数以提高速度和减少桶数（并提高最大负载因子）以改善空间之间存在时空权衡。

我要么不担心，要么如果它是一张大地图，请将桶数设置为n. 然后，您可以在分析显示您有问题时担心优化。

如果您知道所需的负载因子范围，那么您只需将存储桶计数设置为std::ceil(n/(std::max(f_1,f_2)),（并在填充地图之前设置负载因子）。

Answer 2

鉴于您的负载系数有一个范围，唯一缺少的信息是碰撞率。您可以简单地使用nb_buckets = n / f_2，并且一定会获得小于或等于f_2. 确保正确性f_1需要有关碰撞率的数据。