c++ - 将 stdext::hash_set/hash_map 与对象指针一起使用时发生冲突

Question

我目前正在使用 MS VC++ 2008 及其提供的带有扩展的标准库。我想使用散列容器来快速插入/删除/查找对象。所以我认为这应该很好用：

stdext::hash_set<MyOjbectClass*>

我发现默认哈希函数（我假设它只使用指针值）的冲突非常高。

当我在调试器中运行以下代码时：

stdext::hash_set<void*> hs;
for (int i=0; i<30; i++)
{
    hs.insert(new std::string());
}

我看到所有物品都放在同一个桶中！(facepalm) 虽然所有指针都是唯一的。所以我可以忘记 O(1)。

那么，让它高效工作的正确方法是什么？

提供自定义哈希函数？这样的指针哪个好？

注意：我需要使用 hash_map/hash_set。请不要提供使用 unordered_map/set 或 boost 等。

score 0 · Accepted Answer

经过一番搜索，我发现很少有哈希值。以下资源很有帮助：

这里有 1 个功能：http: //naml.us/blog/2012/03

经过一些测试，MurmurHash3 对我来说效果最好。它具有最佳性能。3 个散列函数的桶分布的标准差几乎相同，比使用标准散列函数的情况要好得多。

1 回答 1