出于性能考虑，stdext::hash_map的替代方案是什么？

Question

我正在开发一个高性能应用程序，所有调用必须得到证明。在每个事务的开始时，我有一个地图用于查找，我希望对其进行改进。该地图在启动时加载，并且之后不会更改。

下面地图中的键是std::string，但如果需要，它可以更改为char数组。C或C ++作为解决方案都可以接受。

  typedef stdext::hash_map<std:string, int> symbols_t;

有没有其他解决方案可以消除查找或更快地完成操作？

感谢您的帮助。

编辑中的其他信息：
1. hash_map当前有350,000个元素。
2. 每个键值通常为4到10个字符长度。
3. 从第三方API的回调中接收信息。 回调给出一个符号，该符号用作进行映射查找时的键值。 其余软件由从映射查找返回的int驱动。

感谢：感谢大家的意见。 您为我提供了几种探索途径。 我一定会尝试这些方法。 我很感激您的帮助。

- skimobear

---

我非常怀疑，如果您用char*替换std::string，整体性能会有很大的不同。然而，这肯定会使代码难以维护。 - ereOn

哈希表是O(1)的，因此查找时间仅取决于计算哈希所需的时间。你有研究过这个吗？ - sbi

我在想，这是你代码中最大的瓶颈吗？感觉像是过早优化。 - Yakov Galka

如果你不知道 CPU 时间花在哪里，你如何提出找到低垂果实的建议呢？这是优化的基础。不要只是猜测，也不要盲目地检查整个代码库尝试优化所有内容：找出需要和有益于优化的地方，然后再进行优化。如果地图仅占应用程序总执行时间的 0.01%，那么对其进行优化就是完全浪费时间。 - jalf

@skimobear：你感觉错了。;) 除非你有无限的时间来进行优化，否则你花费在不影响性能的代码上进行优化的每一秒钟都是你不能用于重要部分的一秒钟少。因此，净效果是你通过在没有可测量影响的地方进行优化而使代码变慢。 - jalf

Answer 1

哈希表通常速度很快，复杂度为O(1)，如果不了解应用程序的整体结构，我们无法确定是否可以摆脱哈希表，这可能是不可能的。

我不知道stdext::hash_map<std::string,T>是如何实现的，但是前缀树可能是一个更好的解决方案。它相当于具有完美哈希函数的哈希表。

      s
      |
      t
    /   \
   o     a
   |     |
(p,42)   r
         |
       (t,69)

它将以O(1)的最大10次迭代（字符串的最大长度）为您提供与您的字符串相对应的值，并将最小化存储键的空间成本。

- log0

Answer 2

这张地图是完全不变的还是在程序调用之间会发生变化？对于常量哈希表（在编译时已知），可以使用gperf程序生成快速且保证O(1)查找表。

此外，如果您告诉我们为什么以及如何确切地使地图查找减慢代码，可能会有所帮助。

- blaze

---

hash_map的内容每天都会发生变化。它每天早上从数据库中提取出来。听起来很有趣，我会看一下 :) - skimobear

gperf 生成硬编码了您的数据的 C++ 源文件。使用 gperf 从您的数据库创建一个动态库，每天早上卸载和加载它。 - Lou Franco

Answer 3

手写一个哈希表，使其更适合您的数据。

1. 使用足够简单的哈希函数
2. 使用稀疏的 C 数组，确保足够大以避免数据冲突
3. 确保所有调用都是内联的
4. 确保永远不要复制或转换字符串

5. 编写代码生成此 C 数组的 C 源代码。它将看起来像这样（使用 0 表示没有条目）：

   int symbols[] = { 0,0,0,0,0,0,5,0,0,0,0,0,3,0,0,0,0,0,0,2 /* etc */ };
   

   你编写的代码可以搜索哈希函数，使得对于你的数据没有冲突。也许只需要使用符号的前两个字符（或前四个字符）作为 int 类型即可。如果你不关心空间，你不需要为所有可能的数据创建完美的哈希函数，只需要为你拥有的数据创建一个快速的完美哈希函数即可。

数组索引是 simple_hash(string& s)

请记住，如果您更改符号，则可能需要重写哈希并肯定需要重新生成表。

编辑：根据@blaze的答案--第5个代码已经为您编写，并称为gperf

- Lou Franco

Answer 4

如果你真的需要一个以字符串为键的哈希映射，那么你可以尝试自定义哈希函数。如果你的字符串在前四个字符中大部分是唯一的，那么可以编写一个只查看字符串前四个字符的自定义哈希函数，并让哈希映射使用它。以下是一个示例：

struct CustomStringHash: std::unary_function<std::string, size_t>
{
    size_t operator()(const std::string & s) const
    {
         switch (s.size())
         {
              case 0:
                   return 0;
              case 1:
                   return s[0] + 1;
              case 2:
                   return (s[0] << 8) + s[1];
              default: //3 or more chars long, plus a terminating null
                   return *reinterpret_cast<const uint32_t *>(s.c_str());
         }
    }

如果您的字符串平均长度为8-12个字符，并且前四个字符大多数是唯一的，那么定制哈希函数可以显著加快查找速度。

- Doug

Answer 5

这里有一篇关于哈希表性能的文章，展示了一个可以替代它并且应该会表现更好的解决方案：

http://www.codeproject.com/KB/cross-platform/BenchmarkCppVsDotNet.aspx

这里是更多性能测试的列表：

http://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/ http://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/
http://tinodidriksen.com/2009/10/04/cpp-map-speeds-msvc-edition/

经验表明，当元素超过25,000个时，std_ext::hash_map的表现较差，随着元素数量的增加，查找变得更慢。将其更改为boost::unordered_map可以解决问题。

- Rolf Kristensen

Answer 6

我认为我们在这里缺乏可靠的信息，无法告诉您该怎么做。

您可能需要更具体地说明查找的目的以及函数的整体算法成本。

如果您在代码中添加丑陋的黑客来赢取一个常数微秒，在其算法成本为O(n²)而可以是O(n)的函数中，您正在浪费时间解决错误的问题。

没有额外的细节，我们无法真正告诉您。

- ereOn

---

我添加了一些额外的信息。希望它有所帮助并且足够 :) - skimobear

Answer 7

如果您不告诉我们您要查找什么或为什么要查找，我们如何建议您如何消除您的查找？我们需要更多的算法细节。

至于性能，是否使用hash_map取决于一些复杂性。哈希映射具有（如果您有一个好的实现，实际上）O（1）查找、插入。但是常数开销可能会非常高。如果您的条目数量较少，您可能会在这里遭受损失，并且可能会从std::map中受益。如果经常访问地图的许多不同元素并且可以考虑某种排序数组，则还可能遇到缓存一致性问题。

- Puppy

---

以上添加了一些额外信息。如果不足，请告诉我。谢谢。 - skimobear