多键哈希表（无序映射）

Question

我需要使用多个键（int类型）来从哈希表中存储和检索单个值。我将使用多个键来索引单个项目。我需要快速插入和查找哈希表。顺便说一下，我不能在实现中使用Boost库。

我该怎么做？

- Ashley

---

当您说多个键时，是指每个键必须单独索引相同的项，还是指多个整数一起用于索引单个项？（即，在查找时，您是否提供一个或所有多个键？） - Jerry Coffin

感谢您的快速回复。我将使用多个键来索引单个项。 - Ashley

Answer 1

如果你的意思是两个整数组成一个键，则使用unordered_map<std::pair<int,int>, value_type>。如果你想用多个键索引相同的数据集，请查看Boost.MultiIndex。

- Yakov Galka

---

这个不起作用。我已经尝试过了。它说：哈希没有为此类型进行专门化。 - off99555

如果你定义一个自定义哈希函数，它将起作用。参见，例如，https://dev59.com/EWQn5IYBdhLWcg3wNk04 - orizon

Answer 2

如果您的容器的键由多个int组合而成，您可以使用 boost :: tuple作为您的键，将int封装起来，无需进行更多工作。 只要您的键int子组件数量固定即可。

- Steve Townsend

---

谢谢您的回复。我已经更新了我的问题，关于我不被允许使用Boost库。 - Ashley

@Ashley - 为什么不呢？如果没有 Boost，你就无法轻松使用 unordered_map。 - Steve Townsend

我认为我目前可以访问的unordered_map是来自GNU C++库的实现。 - Ashley

Answer 3

最简单的方法可能是保持一个指向列表元素的指针/索引映射。

这里需要更多的细节，你需要支持删除吗？元素如何设置？可以使用boost::shared pointers吗？（如果需要支持删除，则相当有帮助）

我假设在这种情况下值对象很大，或者由于其他原因你不能在常规映射中简单地复制值。

- jkerian

Answer 4

如果检索总是需要组合，那么最好使用多个键形成单个复合键。

您可以通过以下方式实现此操作：

1. 将键作为整数串连接字符串存储，例如

   (int1,int2,int3) => data
   

2. 使用更高的数据类型，如uint64_t，在其中可以添加单个值以形成键

   // 参见下面的注释以获取方法
   

- aeh

---

方法#2很好，更好的解释请参见http://stackoverflow.com/questions/3761914/storing-and-retrieving-multiple-keys-in-c/3762694#3762694；公式似乎不正确，可能是（假设`N`为int位宽）：`((int1 << 2*N) + (int2 << N) + int3)，前提是data至少有3*N`位。 - Arun