logo标签列表

超高性能的C/C++哈希表（表、字典）

c++cdictionaryhashtablehashmap
99

我需要在一个高性能的哈希映射数据结构中将原始键（int，可能是long）映射为结构体值。

我的程序将有几百个这样的映射表，每个映射表通常最多只有几千个条目。但是，这些映射表将不断地“刷新”或“翻转”；想象一下每秒处理数百万条“add”和“delete”消息。

在C或C++中，有哪些库提供了适合此用例的数据结构？或者，您如何建议构建自己的数据结构？谢谢！

1
你需要对数据进行关键字搜索处理吗？ - Guillaume Lebourgeois
3
更新或检索哪个会更频繁？（添加/删除，或读取/更新，但不改变键）。 - falstro
2
@roe：添加/删除操作比获取操作频率高得多（100倍）。 - Haywood Jablomey
1
经过四年半的时间，了解哪些最符合您的需求是很有趣的。 如果当前的答案都不令人满意，您可以自己编写并接受它。 - Walter Tross
2
感谢 @StackOverflow Mods 关闭了这样一个有用的问题。 - JobHunter69
显示剩余5条评论
10个回答
32

我建议你尝试使用Google SparseHash（或C11版本的Google SparseHash-c11），看看它是否适合你的需求。它们有一个内存高效的实现，也有一个针对速度进行了优化的实现。

我很久以前进行过基准测试，这是速度方面表现最佳的哈希表实现（但有一些缺点）。

17
你能详细说明一下缺点是什么吗？ - Haywood Jablomey
如果我没记错的话，这是一个内存问题，当移除一个元素时，元素被销毁但其内存仍然存在（可能被用作缓存）。 - Scharron
4
主要缺点在于需要将一个或两个（如果您曾经删除元素）的值分离出来，并且永远不再使用它们。在某些情况下，这很容易做到，例如负整数或类似情况，但在其他情况下可能并不是那么简单。 - user319799
4
你今天是否仍然支持这项建议？ - einpoklum
12
请看C或C++中哪些库有适合这种用例的数据结构？或者，您如何建议自己构建？谢谢！
请查看LGPL的Judy数组。我自己从未使用过，但在几个场合被推荐给我。
您也可以尝试基准测试STL容器（std::hash_map等）。取决于平台/实现和源代码调整（尽可能预分配动态内存管理成本很高），它们可能足够高效。
此外，如果最终解决方案的性能胜过解决方案的成本，则可以尝试订购具有足够RAM的系统以将所有内容放入普通数组中。按索引访问的性能是无法击败的。
添加/删除操作比获取操作频率高得多（100倍）。
这暗示您可能希望首先集中改进算法。如果数据仅写入而不读取，那么为什么要写入它们呢？
11

默认情况下，只需使用 boost::unordered_map（或 tr1 等）即可。然后对代码进行剖析，查看该代码是否成为瓶颈。只有在此之后才建议精确分析您的要求，寻找更快的替代方法。

18
尽管我只在处理的相对小部分中使用映射表，但VS2013的std::unordered_map却占据了我整个执行时间的90%以上。 - Cameron
6
如果您有一个多线程程序，您可以在intel thread building blocks library中找到一些有用的哈希表。例如，tbb::concurrent_unordered_map具有与std::unordered_map相同的api，但其主要功能是线程安全的。
此外，还要查看Facebook的folly库，它具有高性能的并发哈希表和跳表。
5
3
2

首先，检查现有的解决方案，例如libmemcache是否符合您的需求。

如果不符合...

哈希映射似乎是满足您要求的明确答案。它提供基于键的o(1)查找。大多数STL库现在都提供某种哈希。因此，请使用平台提供的哈希。

完成这部分后，您必须测试解决方案，以确定默认哈希算法在性能上是否足够满足您的需求。

如果不是，则应探索一些在网络上找到的良好快速哈希算法

  1. 好的旧质数乘法算法
  2. http://www.azillionmonkeys.com/qed/hash.html
  3. http://burtleburtle.net/bob/
  4. http://code.google.com/p/google-sparsehash/

如果这还不够好，您可以自己编写哈希模块，该模块可以修复您测试过的STL容器中出现的问题，并使用上述其中一种哈希算法。请务必在某个地方发布结果。

哦，有趣的是您有多个映射...也许您可以通过将密钥作为64位数字，并使用高位来区分它属于哪个映射，并将所有键值对添加到一个巨大的哈希中来简化。我已经看到了具有十万左右符号的哈希完美地在基本质数哈希算法上运行良好。

您可以检查该解决方案与数百个映射相比的性能..我认为从内存分析的角度来看这可能更好...如果您确实进行了此练习，请在某个地方发布结果

我相信与哈希算法相比，常量添加/删除内存（是否可以避免？）和CPU缓存使用配置文件可能更关键，这对您的应用程序的性能更为重要

祝您好运

2
尝试使用杂项容器模板中的哈希表。其中的closed_hash_map速度与Google的dense_hash_map相当，但更易于使用（不限制所包含的值），而且还有其他一些好处。请注意保留HTML标签。
2
我建议使用uthash。只需包含#include "uthash.h"，然后向结构体添加一个UT_hash_handle，选择一个或多个字段作为键。关于性能的一些话在这里。
1

http://incise.org/hash-table-benchmarks.html gcc有非常好的实现。但是请注意，它必须遵守一个非常糟糕的标准决定：

如果发生重新散列，所有迭代器都将无效，但对单个元素的引用和指针仍然有效。如果没有实际重新散列发生，则不会更改。

http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/

这基本意味着标准规定实现必须基于链表。它防止了具有更好性能的开放寻址。
我认为 Google Sparse 使用了开放寻址，尽管在这些基准测试中只有密集版本胜过竞争对手。然而，稀疏版本在内存使用方面胜过所有竞争对手。（并且它没有任何平台，相对于元素数量是纯直线）
1
请参考这篇文章，其中讨论了桶接口也需要链接的问题。关于引用的观点非常好。很容易就会争辩并说这是一个有用的保证，但在许多情况下，我们只想要引用来避免再次查找元素，而通常的原因是查找太慢了...如果它不必保持引用有效，因此可以使用开放寻址！所以这似乎有点鸡生蛋的感觉。这篇文章引用了2003年的提案，明确讨论了选择的问题。 - underscore_d
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接