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

Question

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

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

注意事项:

• 我知道这不是非常重要，我可以简单地不指定任何内容，它会起作用。
• 这与 What should I pass to unordered_map's bucket count argument if I just want to specify a hash function? 有关，但不是其欺骗)
• 如果对您的回答有帮助，您可以假设我想要一个介于 f_1 和 f_2 之间的负载因子(事先已知)。
• 我正在使用默认的哈希函数，我不知道输入是什么样的，但它不太可能对哈希产生敌对性..

Answer 1

根据 n4296在 23.5.4.2 [unord.map.cnstr](这是 C++14 的最终草案)默认情况下，unordered_map 的 max_load_factor 为 1.0，因此您可以将 bucket_count 设置为 n。

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

我要么不担心它，要么如果它是一个大 map ，将桶计数设置为n。然后，当分析显示您有问题时，您可以担心优化问题。

如果您知道所需的负载因子范围，则只需将桶计数设置为 std::ceil(n/(std::max(f_1,f_2))，(和在填充 map 之前设置加载因子)。