超高性能的C / C ++哈希映射（表，字典）
我需要将原始键（int，也许long）映射到高性能哈希映射数据结构中的结构值。
我的程序将有几百个这样的地图，每张地图通常最多有几千个条目。 不过，地图会不断“清爽”或“搅动” 想象一下，处理数百万次add和delete消息。
C或C ++中的哪些库具有符合此用例的数据结构？ 或者，你会如何build议build立自己的？ 谢谢！
我build议您尝试Google SparseHash （或C11版Google SparseHash-c11 ），看看它是否适合您的需求。 他们有一个高效的内存实施，以及一个优化的速度。 我很久以前就做了一个基准testing，这是在速度方面可用的最好的哈希表实现（不过有缺点）。
只需使用boost::unordered_map （或tr1等）默认情况下。 然后分析你的代码，看看代码是否是瓶颈。 只有这样我才能build议精确地分析你的要求，find一个更快的替代品。
C或C ++中的哪些库具有符合此用例的数据结构？ 或者，你会如何build议build立自己的？ 谢谢！
看看LGPL的Judyarrays 。 从来没有用过自己，但曾多次向我做广告。
你也可以尝试testingSTL容器（std :: hash_map等）。 根据平台/实现和源代码调整（尽可能多地预分配dynamic内存pipe理是昂贵的），它们可能具有足够的性能。
而且，如果最终解决scheme的性能胜过了解决scheme的成本，则可以尝试使用足够的RAM对系统进行sorting，以便将所有内容都放入普通数组中。 按索引访问的性能是无与伦比的。
添加/删除操作比get操作更频繁（100倍）。
这暗示你可能想要专注于改进algorithm。 如果数据只写，不读，那为什么要写呢？
如果你有一个multithreading程序，你可以在intel线程构build块库中find一些有用的哈希表。 例如，tbb :: concurrent_unordered_map与std :: unordered_map具有相同的api，但它的主要function是线程安全的。
也看看Facebook的愚蠢的库 ，它有高性能的并发哈希表和跳过列表 。
卡什是非常有效的。 有作者的详细基准： https ://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/它也显示khash击败许多其他哈希库。
首先检查像libmemcache这样的现有解决scheme是否适合您的需求。
如果不 …
哈希映射似乎是您的要求的明确答案。 它提供基于键的o（1）查找。 现在大多数STL库都提供了一些散列。 所以使用你的平台提供的那个。
一旦完成了这个部分，您就必须testing解决scheme，以查看默认的哈希algorithm是否足够满足您的性能需求。
如果不是的话，你应该研究一下在网上find的一些很好的快速哈希algorithm
- 好的老素数乘以algorithm
- http://www.azillionmonkeys.com/qed/hash.html
- http://burtleburtle.net/bob/
- http://code.google.com/p/google-sparsehash/
如果这样做不够好，你可以自己推出一个哈希模块，它解决了你用你testing过的STL容器看到的问题，以及上面的哈希algorithm之一。 请务必在某处发布结果。
哦，它有趣的是，你有多个地图…也许你可以简化你的密钥作为一个64位的数字与高位用于区分它属于哪个映射，并将所有键值对添加到一个巨大的散列。 我已经看到了具有十万个符号的散列在基本素数散列algorithm上工作的非常好。
你可以检查解决scheme如何执行相比，数百地图..我认为这可能会更好从内存分析的angular度来看…如果你做这个练习，请张贴结果的地方
我相信除了哈希algorithm，它可能是不断增加/删除内存（可以避免吗？）和cpucaching使用情况configuration文件，这对于应用程序的性能可能更为关键
祝你好运
从android源（从而Apache 2许可）
https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils
看看hashmap.c，selectinclude / cutils / hashmap.h，如果你不需要线程安全的话你可以去掉互斥量代码，样例实现在libcutils / str_parms.c
我会build议uthash 。 只需包含#include "uthash.h"然后在结构中添加一个UT_hash_handle ，并select结构中的一个或多个字段作为键。 关于这里的performance一句话。
从杂乱容器模板尝试散列表。 它的closed_hash_map与Google的dense_hash_map相同，但更容易使用（对包含值没有限制），还有一些额外的特性。
http://incise.org/hash-table-benchmarks.html gcc有非常好的实现。 但是，请记住，它必须尊重一个非常糟糕的标准决定：
如果发生重新散布，所有迭代器都将失效，但引用和指向单个元素的指针仍然有效。 如果没有发生实际的重新刷新，则不会更改。
http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/
这基本上意味着标准说实现必须基于链表。 它防止了具有更好性能的开放寻址。
我认为谷歌稀疏是使用开放寻址，但在这些基准只有密集版本胜过竞争。 但是，稀疏版本胜过所有内存使用竞争。 （也没有任何高原，纯粹的直线和数量的元素）
