如何将散列表存储在文件中？

Question

如何在磁盘上的文件中存储具有单独链接的哈希表？

在运行时生成存储在散列表中的数据是很昂贵的，从磁盘加载HT会更快......如果我只能弄清楚如何去做。

编辑： 查找过程是在内存中加载HT的情况下完成的。我需要找到一种将hashtable（在内存中）以某种二进制格式存储到文件的方法。所以下一次程序运行时，它可以将HT从磁盘加载到RAM中。

我正在使用C++。

Answer 1

你使用哪种语言？常用的方法是做一些排序的二进制序列化。

好吧，我看你已编辑添加语言。对于C++有几个选项。我相信Boost序列化机制非常好。另外，Boost序列化库的页面也描述了替代方案。这里是链接：

http://www.boost.org/doc/libs/1_37_0/libs/serialization/doc/index.html

Answer 2

假定C/C++：使用阵列索引和固定尺寸结构，而不是指针和可变长度分配。您应该能够直接将（））数据结构写入文件以供稍后读取（）。

对于更高层次的任何事情：许多高级语言API都具有序列化功能。 Java和Qt/C++都有立即冲刺的方法，所以我知道其他人也是如此。

Answer 3

或许DBM可能对您有用。

Answer 4

您可以使用序列化将整个数据结构直接写入磁盘（例如in Java）。但是，您可能会被迫将整个对象读回内存以访问其元素。如果这不实用，那么你可以考虑使用random access文件来存储散列表的元素。代替使用指针来表示链中的下一个元素，您只需使用文件中的字节位置即可。

Answer 5

如果你的散列表的实现是任何好的，那么只需存储散列和每个对象的数据 - 将一个对象放入表中不应该是昂贵的散列，而不是串行化表或链直接让你改变保存和加载之间的确切实现。

Answer 6

沟指标的指针。

这有点类似于构建磁盘DAWG，我曾经做过一段时间。是什么让这个非常甜蜜，它可以直接用mmap加载而不是读取文件。如果散列空间是可管理的，说2 或2 ^24个条目，那么我想我会做这样的事情：

• 保持自由指标的列表。 （如果表为空，则每个链索引都指向下一个索引。）
• 当需要链接时，请使用表中的空闲空间。
• 如果你需要把东西，用一个棚户区（溢出从其他地方）占用的索引：
  • 记录的索引（我们称之为N）
  • 交换新的元素和棚户
  • （F）将寮屋居民置于一个新的自由指数中。
  • 遵循木屋的哈希索引链，与F.
• 代替n如果您完全耗尽自由指数，你可能需要一个更大的桌子，但你可以通过使用mremap应付长一点在桌子后面创造额外的空间。

这应该允许您直接进行mmap和使用该表，而无需修改。 （如果在OS缓存中可怕的话）！但是你必须使用索引而不是指针。在syscall-round-trip-time中有兆字节是可怕的，并且由于分页，它仍然占用比物理内存更少的空间。