1

我想根据它们的散列索引一系列奇异值或结构/类（意味着一次散列多个值）。

我已经对哈希函数进行了编码，因此为任何值或结构或类提供摘要都没有问题，问题是：

  • C++ 中是否真正支持基于散列的数据结构？我的意思是，如果有一个更好的替代方法来替代std::map例如的琐碎使用，以及为此设计的具有超过 2 个字段的容器 （我还没有决定我的数据结构中真正需要多少个字段）。
  • 由于我计划轻松达到 10^5 条记录，因此管理零散的数据结构对我来说很重要的是避免直接处理内存中的巨大数据结构并分配结构的无用部分。
  • 如果我想将此结构保存在磁盘上，序列化是唯一的选择吗？

假设我的哈希函数是hash::digest()我将欣赏对实际代码的最小参考，并提供有关使用适当数据结构的示例。

谢谢。

编辑：

我想避免无序的数据结构，因为：

  • 错误的分支预测
  • 因为它们没有被排序，所以它们不能以有效的方式被分割
  • 我的主要关注点是管理这种结构及其碎片化。
4

2 回答 2

2

我将把这个写成答案，因为我不认为评论真的能让我们走到任何地方：

首先，我认为你要么找错了树，要么你需要坐下来为我们画一个小图表，这样我们就明白你在问什么。

一般来说，我和许多其他人都遵循“在工作时使用 std::vector 的原则（索引是合理的类型/范围），直到证明它不够好。如果索引不适用于向量，请使用 std ::map，除非证明这不是一个合适的解决方案”。但更重要的是，无论您使用什么存储，都应该对主代码隐藏。你应该有访问器函数来获取数据，如果你使用向量、映射、trie、B-tree、堆、堆栈、队列等都没有关系。只要你的程序需要的功能可以由您的界面，应该可以将数据存储在任何类型的容器类中。有了这个原则，您可以在需要时/根据需要更改实际的存储容器，而不必担心使用容器的代码是否会中断。

至于存储数据结构，任何不只是 POD 的东西都需要序列化，无论您使用什么形式的容器。所以如果你存储任何类，例如std::string，那么你必须序列化数据，因为内部结构不能仅仅存储在文件中。

于 2012-12-25T01:09:16.893 回答
1

在您的描述中，您声明您想要使用“散列”函数（有时称为“摘要”）的东西，这似乎表明您想要使用某种散列容器。散列容器本质上是无序的，但您也声明您不想使用像标准库这样的无序容器std::unordered_map<...>。您想要散列函数是什么？

您还声明您希望您的容器“碎片化”，但我很不清楚您对这种碎片化的含义。从它的声音来看，您似乎暗示您的容器实际上部分保存在磁盘上，并且由于其大小而仅引入内存。但是请注意，10^5 并不是一个很大的尺寸，实际上是一个相当小的尺寸！

如果您的意思是您的“散列”函数实际上提供了一个顺序，即它提供了严格的键弱顺序，并且您的内容可以呈现为字节序列（例如，使用适当的序列化和反序列化），您可能会寻找b 树：基于数据段的数据结构。虽然我确信这个数据结构有 C++ 实现，但标准 C++ 库中没有。我也没有可用的代码，创建 b-tree 也不是一件容易的事。

于 2012-12-25T01:58:49.480 回答