c# - 使用排序的整数数组键快速查找整数索引值

Question

我正在寻找使用排序的整数数组键查找整数值的最快解决方案。

Keys是整型数组，长度固定为3，每个数组都是有序的。
该值是一个整数。

我的数据保证只有一个或两个排序数组具有相同的内容。每个数组都有一个唯一的索引。

我正在尝试找到匹配的数组对。

我的想法是使用字典(我正在用 C# 制作原型(prototype)并将转向 C++)

对于每个数组，我会在字典中查找它是否已经存在。如果是，我将其从字典中删除。如果我没有在字典中找到它，那么它要么是单例，要么是匹配对中的第一个，所以我会将它添加到字典中。

我的问题是 - 然后对数据提供非常具体的保证，什么是最好的容器 - 考虑到速度是我最关心的？此外，如有任何关于适当(快速)哈希函数或排序整数数组比较函数的建议，我们将不胜感激。

Answer 1

当你接触到 C++ 时，迁移到这个

http://sparsehash.googlecode.com/svn/trunk/doc/dense_hash_map.html (项目 here .)

这是我遇到过的最快的 hashmap 实现之一。

与此同时，对于 C# 来说，等效项将是这样的:http://msdn.microsoft.com/en-us/library/xfhwa508.aspx我想有更快的字典实现可用，但由于 C# 不是最终的容器，它应该可以正常工作。

您可能想考虑在您的项目中包含 berkeleydb。它非常快，并且可以在数据集增长时管理存储。它也受到各种平台的支持。