我应该缓存用作哈希键的STL字符串的哈希码吗？

Question

我正在对我开发的软件进行一些性能分析,并且我发现URL的全局字典上的查找大约占应用程序"加载"阶段时间的10%.该字典实现为C++ STL std :: map,它具有O(lg n)查找.我要将它移动到hash_map,它具有大致固定的时间查找.stl字符串类没有哈希代码属性,它肯定不会缓存哈希代码.这意味着每次查找都需要重新生成哈希码.

我怀疑缓存哈希码是值得的.这将意味着更改许多代码行以使用具有缓存哈希代码属性的新字符串类.鉴于当前实现在每次查找时都会记录(n)完整的字符串比较,我认为每次查找将其减少到基本上一次字符串遍历(通过散列函数)是一个很大的胜利.

有没有人有缓存字符串哈希码的经验？有没有证明值得付出努力？

Answer 1

我没有缓存哈希代码的经验，但我最近做了一些转换std::map为std::tr1::unordered_map. 我想到了两个想法。首先，尝试首先分析相对简单的更改，因为它有时会使事情变得更糟，具体取决于您的代码正在做什么。在您尝试进一步优化之前，它本身可能会给您带来足够的加速。其次，您的探查器对您的其余 90%的初始化时间有何评价？即使你将全局字典的东西优化到 0 次，你最多也只能将性能提高 10%。