c++ - 构造 unordered_map 时需要定义桶数吗？

Question

在 的构造函数中unordered_map，我们可以定义分配的桶数。我原以为我可以用它来减少重新散列的时间。但是，在某些情况下，这也可能会损害性能。重新哈希发生在插入时

仅当新的元素数大于 时才会发生重新散列 max_load_factor()*bucket_count()。如果插入成功，则在节点句柄中保存的元素的指针和引用无效，并且在提取之前获得的对该元素的指针和引用变为有效。(C++17 起)

上面的文档来自std::unordered_map. 我猜boost是相似的？但是它的文档没有说明重新散列的条件。

如果我将存储桶计数初始化为 100，并且有一个包含所有 100 个元素的存储桶，那么在插入 101 元素之前不会发生重新散列......如果我使用默认存储桶计数，我假设它是 << 100，重新散列可以更早地发生。

如果是这样，我们什么时候要初始化桶计数？

Answer 1

如果是这样，我们什么时候要初始化桶计数？

当分析显示它有帮助。

无法给出更具体的建议，因为这取决于确切的数据以及使用的散列函数。

通常，如果默认值足够快，请使用它。

Answer 2

一个好的经验法则是哈希表应该只有大约 70% 满（70% 是负载因子）。这会导致一些冲突，但不会太多。

如果您提前知道您计划放入表中的项目数，N那么将桶数设置为((int)N/0.7)+1可能是一个不错的选择值，因为这样可以避免重新散列的需要。如果您正在试验负载因子，您会想要使用((int)N/load_factor)+1.

使表太大可能不会对速度产生太大影响：内存分配的成本在很大程度上取决于您分配的内存量，并且在一定大小之上，所有表对于随机访问的缓存性能都会很差。