如何将具有单独链接的哈希表存储在磁盘上的文件中?
在运行时生成存储在哈希表中的数据很昂贵,从磁盘加载 HT 会更快……如果我能弄清楚如何去做的话。
编辑:查找是在内存中加载的 HT 完成的。我需要找到一种方法将哈希表(在内存中)以某种二进制格式存储到文件中。这样下次程序运行时,它就可以将 HT 从磁盘加载到 RAM 中。
我正在使用 C++。
如何将具有单独链接的哈希表存储在磁盘上的文件中?
在运行时生成存储在哈希表中的数据很昂贵,从磁盘加载 HT 会更快……如果我能弄清楚如何去做的话。
编辑:查找是在内存中加载的 HT 完成的。我需要找到一种方法将哈希表(在内存中)以某种二进制格式存储到文件中。这样下次程序运行时,它就可以将 HT 从磁盘加载到 RAM 中。
我正在使用 C++。
您使用什么语言?常见的方法是进行某种二进制序列化。
好的,我看到您已编辑添加语言。对于 C++,有几个选项。我相信Boost序列化机制是相当不错的。此外,Boost 的序列化库页面也描述了替代方案。链接在这里:
http://www.boost.org/doc/libs/1_37_0/libs/serialization/doc/index.html
假设 C/C++:使用数组索引和固定大小的结构而不是指针和可变长度分配。您应该能够直接将数据结构写入()到文件中以供以后读取()。
对于任何更高级别的东西:许多高级语言 API 都具有序列化功能。Java 和 Qt/C++ 都有可以立即想到的方法,所以我知道其他人也这样做。
您可以通过使用序列化(例如在 Java 中)将整个数据结构直接写入磁盘。但是,您可能被迫将整个对象读回内存以访问其元素。如果这不切实际,那么您可以考虑使用随机访问文件来存储哈希表的元素。您只需使用文件中的字节位置,而不是使用指针来表示链中的下一个元素。
这有点类似于构建磁盘上的DAWG,这是我不久前所做的。让它如此美妙的是它可以直接用 mmap 加载,而不是读取文件。如果哈希空间是可管理的,比如 2 16或 2 24个条目,那么我想我会做这样的事情:
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.
也许DBM可能对您有用。
如果您的哈希表实现很好,那么只需存储哈希和每个对象的数据 - 考虑到哈希,将对象放入表中不应该很昂贵,并且不直接序列化表或链可以让您在保存之间改变确切的实现并加载。