c++ - STL hash_map 比简单的哈希函数慢？

Question

我正在比较我编写的一个简单的哈希函数，该函数只是将它乘以一个质数模另一个质数(表大小)，结果证明 STL 慢了 100 倍。这是我写的测试方法:

stdext:: hash_map<string, int> hashDict;
for (int l = 0; l < size; ++l){
    hashDict[arr[l]] = l;
}
long int before3 = GetTickCount();
int c = 0;
while (c < size){
    hashDict[arr[c]];
    c++;
}
long int after3 = GetTickCount();
cout << "for stl class, the time is " << (after3 - before3) / 1000.0 << '\n';
cout << "the average is " << ((after3 - before3) / 1000.0 ) /long (size) << '\n';

字典的大小大约是 200k 个元素，我写的哈希函数的表大小有 3m 个条目，所以这可能与 STL 类的表大小非常小有关。有谁知道 STL 函数的表大小和冲突率等？

Answer 1

VS2008 STL 实现对字符串使用以下哈希函数:

size_t _Val = 2166136261U;
while(_Begin != _End)
    _Val = 16777619U * _Val ^ (size_t)*_Begin++;

这并不比您的效率低，当然不会是 100 倍，而且我怀疑 Builder 版本有很大不同。区别在于测量(GetTickCount() 不是很精确)或计算哈希值以外的操作。

我不知道 C++ Builder，但一些 STL 实现在调试版本中内置了很多额外的检查和断言。您是否尝试过分析优化的发布版本？

如果您发布一个最小但完整的示例，我们可以帮助您弄清楚发生了什么，但如果没有更多代码，就真的没什么好说的了。