4

我正在开发一个需要始终保持高效的低延迟应用程序。

我需要根据字符串查找一些索引，所以我使用的是 c++ unordered_map。约束： - 仅插入和查找，没有删除 - 键是字符串，值是 int - 预计将不超过 100 万个条目添加到 unordered_map

  • 我将 unordered_map 保留设置为 100 万，这很好还是我应该保留比预期条目多 % 的订单以避免重新散列？我可以将其设置为 100 万，还是应该设置为接近 100 万或 2 次方的大素数。

  • 我在 c++ std lib 中使用默认字符串哈希函数，它恰好是 murmur2。我的键介于 - 25 到 50 个字符之间，并且都是包含数字、大写英文字母和 _ 字符的唯一键。这个散列函数是否足以均匀分布密钥，还是我需要为 unordered_map 提供更好的散列函数？

  • unordered_map 是否会为 100 万个键、值对以及大小为 100 万的数组分配空间，当我调用保留或保留时，仅创建该大小的数组并在插入时动态分配键、值对？

  • 插入时堆上的键、值对的动态分配会有多大的阻力？特别是因为这是一个包含许多条目的大哈希表。

  • 出于性能原因，实现我自己的哈希表并在堆栈上或初始化期间为 100 万个条目预分配内存是个好主意，或者上述 unordered_map 的优化是否足够接近？

  • 有没有办法提前为 unorderd_map 中的预期条目数分配内存以避免插入时的动态分配？

4

1 回答 1

1

让我们尝试用代码回答其中的一些问题。我没有粘贴整个东西，因为它有点长。请在此处找到所有代码。我在这里粘贴了部分输出：

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 个元素，即使有 50 万个存储桶是空的。
  • 如果没有初始reserve，沿途大约有 15 次重新分配，但生成的地图的桶数较少。
  • 随着足够大，reserve根本没有重新分配。
  • 当然，您可以滚动自己的哈希表。例如，您可以为所有键保留一个连续的空间块，因为它们每个不超过 50 个字节，并且一个块用于值。但我敢肯定，这将是一项相当大的工作，可能没有很好的好处。在您开始重新实现可能不需要的内容之前，分析并记录您的内存分配。
于 2013-10-21T18:40:08.327 回答