使用Boost无序地图

Question

伙计们，我正在使用动态编程方法来解决问题。这是该方法的简要概述

1. 使用25个唯一键标识了生成的每个值。
2. 我用 boost :: hash_combine 生成 种子 对于哈希表，使用这25个键。

3. 我将这些值存储在宣布为的哈希表中

   boost::unordered_map<Key_Object, Data_Object, HashFunction> hashState;

4. 我在算法上进行了时间分析，发现几乎 95% 运行时间用于将数据检索/插入哈希表。

5. 这些是我的哈希表的细节

   hashState.size() 1880

   hashState.load_factor() 0.610588

   hashState.bucket_count() 3079

   hashState.max_size() 805306456

   hashState.max_load_factor() 1

   hashState.max_bucket_count() 805306457

我有以下两个问题

1. 我能做些什么来提高哈希表插入/检索操作的性能？

2. C ++ STL具有HASH_MULTIMAP，这也适合我的要求。升级图书馆如何 unordered_map 与之比较 hash_multimap 按照 插入/检索性能.

Answer 1

如果您的哈希功能不是罪魁祸首，那么您可以做的最好的方法就是使用其他地图实现。由于您的钥匙很大，因此使用 unordered_map 从 boost。库图书馆 可能是最好的选择。另外，您可以尝试封闭的哈希： Google Sparsehash 或者 MCT, ，尽管当然需要进行分析，因为当元素足够小时，建议进行封闭的哈希。 （Sparserhash的确定性更高，测试得很好，但是MCT不需要这些 set_empty()/set_deleted() 方法）。

编辑：

我只是注意到我提到的Boost库中没有侵入性地图，仅设置和多插图。不过，您可以尝试两个封闭的哈希库。

编辑2：

Stl hash_map 不是标准的，它可能是一定的扩展名，而不是跨编译器的便携式。

Answer 2

您确定使用的哈希功能不是瓶颈吗？哪个时间百分比具有哈希功能？您能否进行相同的测试，并通过简单的调用来替换插入/检索。