一些关于哈希表/无序映射的问题

Question

一些关于哈希表/无序映射的问题

c++hashmaphashtableunordered-maplow-latency

4

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

我需要根据字符串查找一些索引，因此我使用了c++的unordered_map。约束条件： -仅插入和查找，无删除 -键是字符串，值是整数 -不希望向unordered_map中添加超过100万条目

我将unordered_map的reserve设置为100万，这样好吗？还是应该按预期条目数量的某个百分比进行保留以避免重新哈希？我可以将其设置为100万，还是应该设置为接近100万的大质数或2的幂。
我正在使用c++ std lib中的默认字符串哈希函数，它恰好是murmur2。我的键介于25到50个字符之间，并且都是包含数字、大写英文字母和_字符的唯一键。这个哈希函数是否足以平均分配键，或者我需要提供更好的哈希函数给unordered_map使用？
当我调用reserve时，unordered_map会为100万个键值对和大小为100万的数组分配空间，还是只有该大小的数组被创建，键值对在插入时动态分配？
由于这是一个具有许多条目的大哈希表，堆上的键值对的动态分配会产生多少负担？
出于性能原因，是否实现自己的哈希表并在堆栈或初始化期间预先分配100万个条目的内存是一个好主意，或者上述unordered_map的优化足够接近？
有没有办法提前为unordered_map中预期的条目数分配内存，以避免插入时的动态分配？

(Note: 请注意保留HTML标记)

- Medicine

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- detunized · Accepted Answer

让我们通过编程来尝试回答这些问题。由于代码有点长，我不会粘贴整个代码，请在这里找到所有的代码。但我会在此处粘贴部分输出：

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就没有任何重新分配。
当然，您可以自己编写哈希表。例如，您可以为所有键预留一个连续的空间块，因为它们不超过50个字节，并为值预留一个块。但我相信这可能需要很多工作，可能没有好处。在重新实现可能不必要的内容之前，请对内存分配进行分析和记录。