c++ - C++ Google dense_hash_set 插入的性能

Question

我有一个 C++ 程序正在插入大约。将 1800 万个 uint64_t 类型的数字放入 google dense_hash_set。

所有的数都是2^64以下的偶数，有这个性质

N >= radical(N)^4.

插入速度比插入 1800 万个随机数或 1800 万个序列号慢一个数量级。

执行插入时，代码似乎大部分时间都在执行语句

if ( test_empty(bucknum) )

将 1800 万个项目插入到 dense_hash_set 中是否合理？

有什么方法可以加快插入速度吗？

相关行是

uint64_t N;
google::dense_hash_set<uint64_t> evencandidates;
evencandidates.set_empty_key(-1);
.....
evencandidates.insert(N);

Answer 1

通过用 std::tr1::hash 替换默认哈希函数解决。密集哈希集的声明变为:

google::dense_hash_set<uint64_t, std::tr1::hash<uint64_t> > evencandidates;

选择要存储的数字的标准，

N >= radical(N)^4 and N even

存储的数字的结果有很多共同因素，特别是大多数数字的 2 次方。选择一个适用于这组数字的哈希函数可以解决性能问题。