19

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

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

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

我正在使用 C++。

4

6 回答 6

6

您使用什么语言？常见的方法是进行某种二进制序列化。

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

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

于 2009-02-07T18:57:07.783 回答
5

假设 C/C++：使用数组索引和固定大小的结构而不是指针和可变长度分配。您应该能够直接将数据结构写入（）到文件中以供以后读取（）。

对于任何更高级别的东西：许多高级语言 API 都具有序列化功能。Java 和 Qt/C++ 都有可以立即想到的方法，所以我知道其他人也这样做。

于 2009-02-07T19:02:33.357 回答
5

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

于 2009-02-07T19:06:37.420 回答
5

放弃索引的指针。

这有点类似于构建磁盘上的DAWG，这是我不久前所做的。让它如此美妙的是它可以直接用 mmap 加载，而不是读取文件。如果哈希空间是可管理的，比如 2 16或 2 24个条目，那么我想我会做这样的事情：

  • 保留免费索引列表。（如果表为空，每个链索引将指向下一个索引。）
  • 当需要链接时，请使用表中的可用空间。
  • 如果您需要将某些内容放入被擅自占地者（从其他地方溢出）占用的索引中：
  • 记录索引（我们称它为N）
  • 交换新元素和寮屋
  • 将擅自占地者放入新的免费索引中，（F）。
  • 沿着squatter哈希索引上的链，将N替换为F。
  • If you completely run out of free indices, you probably need a bigger table, but you can cope a little longer by using mremap to create extra room after the table.

This should allow you to mmap and use the table directly, without modification. (scary fast if in the OS cache!) but you have to work with indices instead of pointers. It's pretty spooky to have megabytes available in syscall-round-trip-time, and still have it take up less than that in physical memory, because of paging.

于 2009-02-07T23:09:51.580 回答
2

也许DBM可能对您有用。

于 2009-02-07T19:05:58.967 回答
1

如果您的哈希表实现很好，那么只需存储哈希和每个对象的数据 - 考虑到哈希，将对象放入表中不应该很昂贵，并且不直接序列化表或链可以让您在保存之间改变确切的实现并加载。

于 2009-02-07T20:05:31.547 回答