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

Question

我一直在对我开发的软件进行性能分析，发现全局URL字典的查找占应用程序“加载”阶段时间的约10％。该字典实现为C++ STL std :: map，具有O（lg n）查找。我将把它移动到hash_map中，它具有大致固定的查找时间。STL字符串类没有哈希代码属性，当然也不会缓存哈希代码。这意味着每次查找都需要重新生成哈希代码。

我怀疑缓存哈希代码是否值得努力。这意味着更改许多代码行以使用具有缓存哈希代码属性的新字符串类。鉴于当前实现在每次查找时执行log（n）个完整的字符串比较，我认为将其减少到基本上每次查找一个字符串遍历（通过哈希函数）是一个巨大的胜利。

有人有缓存字符串哈希代码的经验吗？它是否曾经证明过值得努力？

- David Gladfelter

---

哈希需要很少的时间。你打算如何保持这些字符串哈希的缓存？我的意思是，如果你保留一个已经有哈希值的字符串，为什么不直接保留与该哈希值相关联的对象呢？ - GManNickG

不要使用hash_map，那是一个老的扩展。相反，使用TR1或Boost中的unordered_map。 - GManNickG

缓存哈希只对不可变对象安全，而字符串不是。除此之外，这是一个重大的复杂性，因为您必须存储将哈希与已哈希的元组相结合。除非您正在哈希某些真正大的东西，并且在现实条件下对代码进行了基准测试并发现差异很重要，否则我不建议使用它。 - Steven Sudit

@David：从STL类派生是一个不好的想法；它们并不是为此而设计的。 - GManNickG

快速问题：我们正在谈论O(lg n)，但在这种情况下，“n”是什么？ - Steven Sudit

Answer 1

需要注意的一点。

虽然哈希表可以实现固定时间的查找，但有时也可能出现O(N)的查找情况。尽管这并不常见，但确实会发生。

因此，在使用哈希表时，你总是要付出O(log N)的时间代价，但同时也保证它不会更差。

- R Samuel Klatchko

---

关于由猴子乱敲键盘编写的实现。 - GManNickG

@GMan：我猜很多猴子已经找到了程序员和莎士比亚鬼写手的有益就业，因为我见过一些非常糟糕的哈希。 - Steven Sudit

@GMan：他们并不是自己编写哈希算法，而是随意选择一个已知的但实际上很糟糕的算法。在真实代码中有很多哈希算法分布很差，或者至少在特定范围的输入下存在巨大的弱点。因此，我通常同意我们应该信任可靠库中的哈希算法，因为也有很多算法对于几乎任何输入都能产生良好的结果。 - Steven Sudit

如果您真的关心哈希表的最坏情况性能，您可以将其限制为O(log N)而不是O(N)（对于哈希冲突使用树而不是列表）。@R Samuel Klatchko - Jerry Coffin

@Jerry - 有趣的想法。你知道有没有使用它的unordered_map实现吗？ - R Samuel Klatchko

Answer 2

我没有缓存哈希码的经验，但最近我做了一些工作，将std::map转换为std::tr1::unordered_map。有两个想法。首先，请尝试首先对这个相对简单的更改进行分析，因为它有时会使情况变得更糟，这取决于您的代码在做什么。在您尝试进一步优化之前，它可能已经为您自己提供了足够的加速。其次，您的性能分析器对初始化时间的其他90％有何看法？即使您将全局字典内容优化到0时间，您也最多只能将性能提高10％。

- Michael Kristofik

---

嗨，Kristo，感谢你的建议。回答你的问题，我已经减少了大约40％的加载时间，并且我已经没有更多简单的优化点可做了。那剩下的10％相对来说比较重要，但也在我的能力范围内。 - David Gladfelter

Answer 3

当你将哈希映射与映射进行比较时，还应该尝试使用Trie或相关数据结构（无论您能从哪里获取）：

Trie实现

不幸的是，您可能会花费很多时间担心缓存友好性。在这方面，Trie类似于您已经拥有的树，而哈希映射可能比天真分配的树更好地行为良好。

此外，我对问题有点困惑。如果您多次查找相同的字符串对象，以使缓存其哈希值值得，那么您不应该只缓存查找结果吗？哈希表的整个重点在于，具有相等值的不同对象哈希到相同的值。如果您没有从包含相同字符的不同字符串多次计算相同的哈希值，则您的哈希表可能无法正常工作。

如果您的意思是缓存已经在哈希表中的键的值，则由哈希表决定。

- Steve Jessop

Answer 4

当然，你需要使用分析工具来检查你的结果。将其更改为哈希映射，然后查看大部分时间花在哪里。除非你一直在散列键，否则我不认为你会花费大部分时间在那里。哈希旨在成为一种快速操作，否则哈希映射将没有有序容器的优势。

编译器本身会知道字符串是否未更改，并且可能会为您缓存结果（在同一范围内）。也就是说，你不想继承 std::string；STL类并非用于此目的。

相反，创建一个 std::pair 并传递它：

std::pair string_hash_pair;

然后，您需要为您的类型重载（按照 Boost 的方式，而不是 TR1；我不知道它们有多相似）hash_value 函数，在与 pair 定义相同的命名空间中。

size_t hash_value(const string_hash_pair& pPair)
{
    return pPair.second; // don't actually hash
}

就是这样。请注意，在这个对中，string和size_t都是不可变的。这是因为如果string改变了，你的哈希值就会变得不正确。所以我们将其设为const，同时也可以将哈希值设为const。

你需要一个辅助函数：

string_hash_pair make_string_hash(const std::string& pStr)
{
    return std::make_pair(pStr, boost::hash_value(pStr));
}

现在，如果您要使用字符串进行查找，只需将其制成一对即可获得常量时间的哈希值。

话虽如此，我真的怀疑有必要做这么多工作。哈希函数通常非常简单。另外，不要自己制作哈希函数。使用预先存在的经过测试的哈希函数；制作低质量哈希函数相当容易。

- GManNickG

---

如果我理解正确，键的哈希在查找期间只计算一次，无论表有多大，因此缓存它不应该有太大帮助。哈希在插入期间计算，但每个项只插入一次。 - Steven Sudit

@Steven：每次查找时只计算一次。但是，如果您多次使用相同的键进行查找，则可能会多次计算哈希值。我认为他想避免这种情况。 - GManNickG

没错。从原始帖子中我无法判断是否会多次查找同一个键，但如果确实如此，那么这样做是有道理的。当然，也可能有重新组织代码的方法，使得值不会被查找超过绝对必要的次数。 - Steven Sudit

Answer 5

我在我的字典中比较了一个带有4k-64k个字符串的set和unordered_set。

我发现，由于unordered_set的hash_value计算大约占运行时间的80％，所以在我的情况下，std :: set和unordered_set具有相同的运行时。

它使查找节省（对于std :: string FWIW使用boost :: hash_value）微不足道。

YMMV，对于一般情况，我会说进行分析，并不要被理论上未考虑CPU架构等因素的缩放所迷惑。哈希映射可能会由于哈希成本而运行更慢，并且将消耗更多内存。

我的用例是我长时间存储信息，并经常更新它，但不更改information_id哈希的信息，但可能更改其他内容。

然后，每次更新都会传递给我的查找函数，以决定是否需要为此更新向外部通知。

要通知的information_ids列表在此查找中，并且可以独立于信息更改。

通过缓存information_id的哈希值，它很可能在信息的生命周期内被重复使用10次以上。

我对缓存哈希的两行更改将unordered_set的运行时间改善了> x8

测试集：在MSVC 2012更新4上进行基准测试。每个条目在4k和64k字典中查找10次：

除了10个检查在4k中全部未命中，64k中有500个命中（更多的土豚：）

set：1373毫秒/1938毫秒

multiset：1376毫秒/1913毫秒

unordered_set初始64k桶/0.5负载因子：168毫秒/362毫秒

unordered_set 4k / 1.0：331毫秒/452毫秒

c.f预缓存

unordered_set 64k / 0.5：1519毫秒/1881毫秒

FWIW相同的事情针对MinGW 4.9.1 -O3运行

set：2003毫秒/2490毫秒

multiset：1978毫秒/2306毫秒

unordered_set初始64k桶/0.5负载因子：140毫秒/605毫秒

unordered_set 4k / 1.0：318毫秒/683毫秒

c.f预缓存

unordered_set 64k/0.5: 1619毫秒 / 2455毫秒

- Paul