用於將數十億字典密鑰緊密映射到值的內存數據結構

Question

我想要在內存中緊湊地存儲數十億條記錄（鍵/值），並且我需要支持的唯一操作是通過查找值它的關鍵。鍵和值都是小字符串。最重要的是如何將壓縮成的數據結構;它應該比簡單的關聯數組更深入地使用鍵的內部結構。例如，應該以某種方式壓縮鍵「apple」，「apply」和「apron」到值「1」，「2」和「3」。我在找什麼數據結構？

Answer 1

這聽起來像是你想要一個trie - 它做了你所描述的那種「壓縮」，只存儲一次前綴。

我假設你有足夠的內存來存儲「數十億」的密鑰，當然，你需要在64位系統上才能夠解決如此多的項目。

Answer 2

你可以試試Trie。它從關鍵字串本身中形成一個樹形結構。不會有空位置（如在散列圖中）。

Answer 3

即使您正在處理的數據是小字符串，您是否確實您確定需要如此多的內存數據？這可能很容易達到千兆字節的內存，並且大多數數據可能不會被頻繁查詢。

一個精心設計的數據庫可能足以滿足您的需求。