超高性能的C / C ++哈希映射(表,字典)

我需要将原始键(int,也许long)映射到高性能哈希映射数据结构中的结构值。

我的程序将有几百个这样的地图,每张地图通常最多有几千个条目。 不过,地图会不断“清爽”或“搅动” 想象一下,处理数百万次adddelete消息。

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

  1. 好的老素数乘以algorithm
  2. http://www.azillionmonkeys.com/qed/hash.html
  3. http://burtleburtle.net/bob/
  4. 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/

这基本上意味着标准说实现必须基于链表。 它防止了具有更好性能的开放寻址。

我认为谷歌稀疏是使用开放寻址,但在这些基准只有密集版本胜过竞争。 但是,稀疏版本胜过所有内存使用竞争。 (也没有任何高原,纯粹的直线和数量的元素)