1. 首页
  2. 问答
  3. 超高性能C/C++哈希映射（表，字典）

超高性能C/C++哈希映射（表，字典）

2010-07-21 33 views
66

我需要将原始键（int，也许是long）映射到高性能哈希映射数据结构中的结构值。超高性能C/C++哈希映射（表，字典）

我的程序会有几百张这样的地图，每张地图通常最多会有几千个条目。然而，地图会不断“清爽”或“搅动”想象一下每秒处理数百万个add和delete消息。

C或C++中的哪些库具有适合此用例的数据结构？或者，你会如何建议自己创建？谢谢！

来源

2010-07-21 Haywood Jablomey

+1

您是否需要使用密钥来处理您的数据？ – 2010-07-21 14:51:11

+3

更新或检索更频繁？ （添加/删除，或读/更新不会改变密钥） – falstro 2010-07-21 14:52:06

+0

http://stackoverflow.com/questions/266206/simple-hashmap-implementation-in-c。这可能是一个开始的好地方。 – DumbCoder 2010-07-21 14:56:36

回答

27

我会建议您尝试Google SparseHash（或C11版本Google SparseHash-c11），看看它是否适合您的需求。它们具有高效的内存实现以及针对速度优化的实现。 很久以前，我做了一个基准测试，它是速度方面最好的哈希表实现方式（不过有缺点）。

来源

2010-07-21 14:53:12 Scharron

+9

你能详细说明这些缺点吗？ – 2010-07-21 15:05:35

+0

IIRC，这是一个内存问题，当删除一个元素时，元素被破坏了，但是它的内存仍然存在（我想用作缓存）。 – Scharron 2010-07-21 15:14:01

+3

@Haywood Jablomey：主要缺点是它需要你分离一个或两个（如果你擦除了元素）值并且从不使用这些值。在某些情况下，这很容易做到，例如负面整数或类似的，但在其他情况下并不是这样。 – doublep 2010-07-21 20:06:47

11

C或C++中的哪些库具有适合此用例的数据结构？或者，你会如何建议自己创建？谢谢！

查看LGPL'd Judy arrays。从来没有用过我自己，但几次被广告给我。

你也可以尝试对STL容器（std :: hash_map等）进行基准测试。根据平台/实现和源代码调整（尽可能预先分配动态内存管理费用昂贵），它们可能具有足够的性能。另外，如果最终解决方案的性能超过了解决方案的成本，那么您可以尝试使用足够的RAM对系统进行排序，以将所有内容都放入普通数组中。按索引访问的性能是无与伦比的。

添加/删除操作比get操作更频繁（100倍）。

这提示您可能需要专注于先改进算法。如果数据只写入，不读取，那为什么要写它们呢？

来源

2010-07-21 16:24:16 Dummy00001

11

默认使用boost::unordered_map（或tr1等）。然后分析你的代码，看看代码是否是瓶颈。只有这样我才会建议精确分析您的要求以找到更快的替代品。

来源

2010-07-21 18:03:26

+8

它是。 VS2013的'std :: unordered_map'占我整个执行时间的90％以上，尽管我只使用地图来处理相对较小的一部分。 – Cameron 2015-04-16 14:45:42

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/

如果这还不够好，你可以滚动哈希模块e自己解决了你用你测试过的STL容器看到的问题，以及上面的一个哈希算法。请务必在某处发布结果。

哦，它的有趣的是，你有多个地图......也许你可以有一个64位NUM与用于区分高位，其映射属于并添加所有键值对，以一个巨型的关键简化哈希值。我已经看到了具有几十万个符号的散列在基本的素数散列算法上工作得非常好。

你可以检查解决方案如何执行相比数百地图..我认为这可能是更好的从内存分析的角度来看...如果你需要做这个练习，请张贴结果在某处

我相信超过散列算法也可能是恒定的添加/删除的内存（能不能避免？）那可能是你的应用程序

好运的表现更关键的CPU缓存使用配置文件

来源

2010-07-21 18:33:00 computinglife

2

从Miscellaneous Container Templates尝试哈希表。其closed_hash_map的速度与Google的dense_hash_map大致相同，但更易于使用（对包含的值不加限制），并且还具有其他一些优点。

来源

2010-07-21 20:03:59 doublep

1

http://incise.org/hash-table-benchmarks.html GCC有一个非常非常好的实现。但是，记住，它必须尊重一个非常糟糕的标准决定：

如果一个翻版发生，所有迭代器失效，但引用和 指针个别元素仍然有效。如果没有发生实际的重复冲突 ，则不会更改。

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

这意味着基本标准指出，实现必须基于链表。 它可以防止有更好性能的开放寻址。

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

来源

2014-05-29 01:43:59

2

我会建议uthash。只需包括#include "uthash.h"，然后将UT_hash_handle添加到结构中，并选择结构中的一个或多个字段作为关键字。关于表现的字眼here。

来源

2015-02-16 06:31:00 sjain

相关问题

 相关问题