performance - 使用 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 也符合我的要求。在插入/检索性能方面， boost 库unordered_map与hash_multimap相比如何。

Answer 1

如果您的哈希函数不是罪魁祸首，那么您能做的最好的事情可能就是使用不同的地图实现。由于您的密钥非常大，因此使用unordered_mapBoost.Intrusive库可能是最佳选择。或者，您可以尝试封闭散列：Google SparseHash或MCT，尽管分析肯定需要，因为当元素足够小时建议使用封闭散列。（SparseHash 更加成熟且经过良好测试，但 MCT 不需要那些set_empty()/set_deleted()方法）。

编辑：

我刚刚注意到我提到的 Boost 库中没有侵入式映射，只有 set 和 multiset。不过，您可以尝试这两个封闭的散列库。

编辑2：

STLhash_map不是标准的，它可能是一些扩展并且不能跨编译器移植。

Answer 2

您确定您使用的哈希函数不是瓶颈吗？哪个时间百分比采用哈希函数？你能做同样的测试并通过一个简单的哈希调用来替换插入/检索。