如何將散列表存儲在文件中？

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中有兆字節是可怕的，並且由於分頁，它仍然佔用比物理內存更少的空間。