如何在文件中存储哈希表？

Question

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

在运行时生成存储在哈希表中的数据是昂贵的,从磁盘加载HT会更快......如果我能弄清楚如何做到这一点.

编辑:查找是在内存中加载的HT完成的.我需要找到一种方法将哈希表(在内存中)以某种二进制格式存储到文件中.因此,下次程序运行时,它可以将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

您可以使用序列化(例如在Java中)将整个数据结构直接写入磁盘.但是,您可能被迫将整个对象读回内存以访问其元素.如果这不可行,那么您可以考虑使用随机访问文件来存储哈希表的元素.您只需使用文件中的字节位置,而不是使用指针来表示链中的下一个元素.

Answer 4

放弃索引指针。

这有点类似于构建磁盘DAWG，我之前做了。如此甜蜜的是，可以直接用mmap加载而不是读取文件。如果哈希空间是可管理的，比如说2 ¹⁶或2 ²⁴个条目，那么我想我会做这样的事情：

• 保留免费索引列表。（如果表为空，则每个链式索引都将指向下一个索引。）
• 需要链接时，请使用表中的可用空间。
• 如果您需要将某些内容放入擅自占地者的索引（其他位置的溢出）：
  • 记录索引（将其称为N）
  • 交换新元素和擅自占地者
  • 将擅自占地者置于新的自由指数F中。
  • 遵循擅自占地者哈希索引上的链，将N替换为F。
• 如果完全用完了空闲索引，则可能需要一个更大的表，但是可以通过使用mremap在表后创建额外的空间来处理更长的时间。

这将使您无需修改​​即可直接映射并使用该表。（如果在OS缓存中，速度很快）！但是您必须使用索引而不是指针。在syscall往返时间内有兆字节可用，而且由于分页而占用的内存仍然少于物理内存中的内存，这是非常诡异的。