超高性能C/C++哈希映射（表、字典）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3300525/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Super high performance C/C++ hash map (table, dictionary)
提问by Haywood Jablomey
I need to map primitive keys (int, maybe long) to struct values in a high-performance hash map data structure.
我需要将原始键（int，可能是 long）映射到高性能哈希映射数据结构中的结构值。
My program will have a few hundred of these maps, and each map will generally have at most a few thousand entries. However, the maps will be "refreshing" or "churning" constantly; imagine processing millions of addand deletemessages a second.
我的程序将有几百张这样的地图，而每张地图通常最多只有几千个条目。但是，地图会不断“刷新”或“搅动”；想象处理数以百万计add和delete消息的第二。
What libraries in C or C++ have a data structure that fits this use case? Or, how would you recommend building your own? Thanks!
C 或 C++ 中的哪些库具有适合此用例的数据结构？或者，您会如何推荐自己构建？谢谢！
回答by Scharron
I would recommend you to try Google SparseHash(or the C11 version Google SparseHash-c11) and see if it suits your needs. They have a memory efficient implementation as well as one optimized for speed. I did a benchmark a long time ago, it was the best hashtable implementation available in terms of speed (however with drawbacks).
我建议您尝试使用Google SparseHash（或 C11 版本Google SparseHash-c11），看看它是否适合您的需求。它们具有内存高效的实现方式以及针对速度进行了优化的实现方式。很久以前我做了一个基准测试，它是速度方面最好的哈希表实现（但是有缺点）。
回答by Dummy00001
What libraries in C or C++ have a data structure that fits this use case? Or, how would you recommend building your own? Thanks!
C 或 C++ 中的哪些库具有适合此用例的数据结构？或者，您会如何推荐自己构建？谢谢！
Check out the LGPL'd Judy arrays. Never used myself, but was advertised to me on few occasions.
查看 LGPL 的Judy 数组。从来没有用过自己，但有几次向我做广告。
You can also try to benchmark STL containers (std::hash_map, etc). Depending on platform/implementation and source code tuning (preallocate as much as you can dynamic memory management is expensive) they could be performant enough.
您还可以尝试对 STL 容器（std::hash_map 等）进行基准测试。根据平台/实现和源代码调整（预分配尽可能多的动态内存管理是昂贵的），它们的性能可能足够高。
Also, if performance of the final solution trumps the cost of the solution, you can try to order the system with sufficient RAM to put everything into plain arrays. Performance of access by index is unbeatable.
此外，如果最终解决方案的性能胜过解决方案的成本，您可以尝试订购具有足够 RAM 的系统以将所有内容放入普通数组中。按索引访问的性能无与伦比。
The add/delete operations are much (100x) more frequent than the get operation.
添加/删除操作比获取操作更频繁（100 倍）。
That hints that you might want to concentrate on improving algorithms first. If data are only written, not read, then why write them at all?
这暗示您可能希望首先专注于改进算法。如果只写数据，不读数据，那为什么还要写呢？
回答by Mark B
Just use boost::unordered_map(or tr1etc) by default. Then profile your code and see if that code is the bottleneck. Only then would I suggest to precisely analyze your requirements to find a faster substitute.
默认情况下只需使用boost::unordered_map（或tr1等）。然后分析您的代码并查看该代码是否是瓶颈。只有这样，我才会建议精确分析您的需求以找到更快的替代品。
回答by Pavel Davydov
If you have a multithreaded program, you can find some useful hash tables in intel thread building blocks library. For example, tbb::concurrent_unordered_map has the same api as std::unordered_map, but it's main functions are thread safe.
如果你有一个多线程程序，你可以在intel thread building blocks library 中找到一些有用的哈希表。例如，tbb::concurrent_unordered_map 与 std::unordered_map 具有相同的 api，但它的主要功能是线程安全的。
Also have a look at facebook's folly library, it has high performance concurrent hash tableand skip list.
回答by sherpya
from android sources (thus Apache 2 licensed)
来自 android 源（因此 Apache 2 许可）
https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils
https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils
look at hashmap.c, pick include/cutils/hashmap.h, if you don't need thread safety you can remove mutex code, a sample implementation is in libcutils/str_parms.c
查看hashmap.c，选择include/cutils/hashmap.h，如果你不需要线程安全，你可以删除互斥代码，示例实现在libcutils/str_parms.c
回答by zhanxw
khash is very efficient. There is author's detailed benchmark: https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/and it also shows khash beats many other hash libraries.
khash 非常有效。有作者的详细基准：https: //attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/，它还显示 khash 击败了许多其他哈希库。
回答by sjain
回答by computinglife
First check if existing solutions like libmemcache fits your need.
首先检查 libmemcache 等现有解决方案是否符合您的需要。
If not ...
如果不 ...
Hash maps seems to be the definite answer to your requirement. It provides o(1) lookup based on the keys. Most STL libraries provide some sort of hash these days. So use the one provided by your platform.
哈希映射似乎是您需求的明确答案。它提供基于键的 o(1) 查找。如今，大多数 STL 库都提供某种散列。因此，请使用您的平台提供的那个。
Once that part is done, you have to test the solution to see if the default hashing algorithm is good enough performance wise for your needs.
完成该部分后，您必须测试解决方案以查看默认散列算法的性能是否足以满足您的需求。
If it is not, you should explore some good fast hashing algorithms found on the net
如果不是，您应该探索在网上找到的一些好的快速散列算法
- good old prime number multiply algo
- http://www.azillionmonkeys.com/qed/hash.html
- http://burtleburtle.net/bob/
- http://code.google.com/p/google-sparsehash/
- 好老素数乘法算法
- http://www.azillionmonkeys.com/qed/hash.html
- http://burtleburtle.net/bob/
- http://code.google.com/p/google-sparsehash/
If this is not good enough, you could roll a hashing module by yourself, that fixes the problem that you saw with the STL containers you have tested, and one of the hashing algorithms above. Be sure to post the results somewhere.
如果这还不够好，您可以自己滚动一个散列模块，它可以解决您在测试过的 STL 容器以及上述散列算法之一中看到的问题。请务必将结果张贴在某处。
Oh and its interesting that you have multiple maps ... perhaps you can simplify by having your key as a 64 bit num with the high bits used to distinguish which map it belongs to and add all key value pairs to one giant hash. I have seen hashes that have hundred thousand or so symbols working perfectly well on the basic prime number hashing algorithm quite well.
哦，有趣的是，您有多个映射……也许您可以通过将密钥作为 64 位 num 来简化，其中高位用于区分它属于哪个映射，并将所有键值对添加到一个巨大的哈希中。我已经看到具有十万左右符号的散列在基本素数散列算法上运行得非常好。
You can check how that solution performs compared to hundreds of maps .. i think that could be better from a memory profiling point of view ... please do post the results somewhere if you do get to do this exercise
您可以检查与数百张地图相比该解决方案的执行情况……我认为从内存分析的角度来看这可能会更好……如果您确实可以进行此练习，请在某处发布结果
I believe that more than the hashing algorithm it could be the constant add/delete of memory (can it be avoided?) and the cpu cache usage profile that might be more crucial for the performance of your application
我相信除了散列算法之外，它可能是内存的不断添加/删除（可以避免吗？）和 CPU 缓存使用配置文件，这可能对您的应用程序的性能更重要
good luck
祝你好运
回答by doublep
Try hash tables from Miscellaneous Container Templates. Its closed_hash_mapis about the same speed as Google's dense_hash_map, but is easier to use (no restriction on contained values) and has some other perks as well.
尝试来自Miscellaneous Container Templates 的哈希表。它closed_hash_map的速度与 Google 的 差不多dense_hash_map，但更易于使用（对包含的值没有限制）并且还有其他一些好处。
回答by v.oddou
http://incise.org/hash-table-benchmarks.htmlgcc has a very very good implementation. However, mind that it must respect a very bad standard decision :
http://incise.org/hash-table-benchmarks.htmlgcc 有一个非常好的实现。但是，请注意它必须尊重一个非常糟糕的标准决定：
If a rehash happens, all iterators are invalidated, but references and pointers to individual elements remain valid. If no actual rehash happens, no changes.
如果发生 rehash，所有迭代器都将失效，但指向单个元素的引用和指针仍然有效。如果没有实际的重新哈希发生，则没有变化。
http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/
http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/
This means basically the standard says that the implementation MUST BE based on linked lists. It prevents open addressing which has better performance.
这意味着基本上标准说实现必须基于链表。它可以防止具有更好性能的开放寻址。
I think google sparse is using open addressing, though in these benchmarks only the dense version outperforms the competition. However, the sparse version outperforms all competition in memory usage. (also it doesn't have any plateau, pure straight line wrt number of elements)
我认为 google sparse 正在使用开放寻址，尽管在这些基准测试中，只有密集版本的表现优于竞争对手。然而，稀疏版本在内存使用方面的表现优于所有竞争对手。（它也没有任何高原，纯直线wrt元素数）
