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

Question

我需要将原始键(int,可能很长)映射到高性能哈希映射数据结构中的struct值.

我的程序将有几百个这样的地图,每个地图通常最多只有几千个条目.但是,地图会不断地"刷新"或"翻腾"; 想象一下处理数百万add和delete消息.

C或C++中的哪些库具有适合此用例的数据结构？或者,您会如何建议自己建造？谢谢!

Answer 1

我建议您尝试使用Google SparseHash(或C11版Google SparseHash-c11),看看它是否符合您的需求.它们具有内存有效的实现以及针对速度优化的实现.我很久以前做了一个基准测试,它是速度方面最好的哈希表实现(但有缺点).

Answer 2

C或C++中的哪些库具有适合此用例的数据结构？或者,您会如何建议自己建造？谢谢!

查看LGPL的Judy阵列.从未使用过自己,但很少有人向我做过广告宣传.

您还可以尝试对STL容器(std :: hash_map等)进行基准测试.根据平台/实现和源代码调整(预分配尽可能多的动态内存管理是昂贵的),它们可以具有足够的性能.

此外,如果最终解决方案的性能胜过解决方案的成本,您可以尝试使用足够的RAM来命令系统将所有内容放入普通阵列.索引访问的性能是无与伦比的.

添加/删除操作比get操作更频繁(100倍).

这暗示您可能希望首先专注于改进算法.如果只写入数据而不读取数据,那么为什么要写入数据呢？

Answer 3

只需默认使用boost::unordered_map(或tr1等).然后分析您的代码,看看该代码是否是瓶颈.只有这样,我才会建议您精确分析您的要求,以找到更快的替代品.

Answer 4

如果你有一个多线程程序,你可以在intel线程构建块库中找到一些有用的哈希表.例如,tbb :: concurrent_unordered_map与std :: unordered_map具有相同的api,但它的主要功能是线程安全的.

另外看看facebook的愚蠢库,它具有高性能的并发哈希表和跳过列表.

Answer 5

khash 非常高效。有作者的详细基准：https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/，它还显示 khash 击败了许多其他哈希库。