我正在开发一个需要始终保持高效的低延迟应用程序。
我需要根据字符串查找一些索引，所以我使用的是 C++ unordered_map。 约束: -只有插入和查找，没有删除 -key为字符串，值为int - 期望添加到 unordered_map 的条目不超过 100 万
我将 unordered_map 预留设置为 100 万，这样好还是我应该预留比预期条目多 % 的订单以避免重新散列？ 我可以将它设置为 100 万，还是应该设置为接近 100 万或大约 2 次幂的大质数。
我在 c++ std lib 中使用默认的字符串哈希函数，它恰好是 murmur2。 我的 key 介于 - 25 到 50 个字符之间，并且都是包含数字、大写英文字母和 _ 字符的唯一 key 。这个哈希函数是否足以均匀分布 key ，或者我是否需要为 unordered_map 提供更好的哈希函数？
当我调用 reserve 或在 reserve 时，unordered_map 是否会为 100 万个键、值对以及大小为 100 万的数组分配空间，仅创建该大小的数组并动态分配键、值对插入时？
插入时在堆上动态分配键值对会有多大阻力？特别是因为这是一个包含许多条目的大哈希表。
出于性能原因，实现我自己的哈希表是否是个好主意，在堆栈上或在初始化期间为 100 万个条目预分配内存，或者上述对 unordered_map 的优化是否足够接近？
有没有办法提前为 unorderd_map 中预期的条目数分配内存，以避免插入时动态分配？
最佳答案
让我们试着用代码来回答其中的一些问题。我没有粘贴整个东西，因为它有点长。请找到所有代码 here 。不过，我在这里粘贴了部分输出:
Map without reserve
size: 0
bucket_count: 23
load_factor: 0
Allocation count: 0
...
about 15 reallocations deleted
...
Allocation count: 1000015
size: 1000000
bucket_count: 1236397
load_factor: 0.808802
0: 550454
1: 445645
2: 180174
3: 48593
4: 9708
5: 1568
6: 231
7: 22
8: 2
Map with reserve
size: 0
bucket_count: 23
load_factor: 0
Allocation count: 1
size: 0
bucket_count: 2144977
load_factor: 0
Allocation count: 1000000
size: 1000000
bucket_count: 2144977
load_factor: 0.466205
0: 1346008
1: 626748
2: 146625
3: 22663
4: 2669
5: 248
6: 15
7: 1
- 如您所见，当您为 1m 的元素保留空间时，只会发生一次分配。我想那是用来装水桶的。
- 保留的桶数远高于 1m。
- 分配的数量与插入的元素数量完全相同。
- 您可以看到每种情况下的散列分布:有很多冲突。有时每个桶最多 8 个元素，即使有一百万个桶是空的。
- 如果没有初始
reserve，整个过程中大约有 15 次重新分配，但生成的映射具有更少的桶。 - 有了足够大的
reserve，根本就没有重新分配。 - 当然，您可以推出自己的哈希表。例如，您可以为所有键保留一个连续的空间 block ，因为每个键的长度不超过 50 个字节，并且为值保留一个 block 。但我敢肯定，这将是一项相当大的工作，可能没有什么好处。在开始重新实现可能不需要的内容之前，分析并记录您的内存分配。
关于c++ - 一些哈希表/unordered_map 问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19499719/