我需要在內存中的集合類結構中存儲數百萬個帶有公共前綴（它們不對應於文件系統路徑）的字符串，並查詢集合以查看是否存在一條路徑。具有公共前綴的字符串的空間高效集合 - Java實現
例如
/path
/path/1
/path/2
/path/1/a
/path/1/b
我想盡可能高效地存儲這些地（他們會在內存中），因爲會有對所有涉及將一個特里是一個合理的候選串許多共同的前綴？
我正在尋找一個推薦的實現在Java中的合適的數據結構。
A Trie看起來像你需要的結構。 Radix Tries也是類似的結構，與嘗試不同，使用字符序列來標記邊緣。在簡單的嘗試中，邊緣用單個字符標記，我相信它們在你的情況下表現得更好，其中字符串共享相當多的前綴。
也見...
這看起來像一個很好的候選執行：https://github.com/rkapsi/patricia-trie
你可以使用一個樹形結構，就像它會在磁盤上。但是，您需要記住，樹結構可以在開銷時使用盡可能多或更多的內存。即它們並非真正用於節省內存。
也許你可以使用磁盤子系統的緩存，如果這些文件存在。它可能會更快。
我會檢查你真的需要這樣做，因爲你可以非常舒適地在JVM中存儲一百萬個條目。 ;）
如果您想最大限度地減少內存消耗，您可以壓縮內存中的數據。這可能比任何其他選項都小得多，但要做到高效率則要複雜得多。
我會用什麼：
讓我們在提出任何建議之前考慮權衡。
你說你需要存儲「數百萬」的路徑。我假設一百萬，因爲它使計算更容易（甚至在服務器上，我沒有看到超過一百萬個目錄）。
這些路徑有多長？您已經展示了一個非常短路徑的示例，因此我們正在研究可能有一百兆字節來存儲這些百萬條路徑。我沒有最大路徑長度的參考，但我腦海中有256個字符。所以你的路徑最多需要512Mb的內存。你有那麼多的記憶？
路徑名是如何均勻分佈的？換句話說，你是否遵循80:20的規則，在20％的目錄中找到80％的路徑？我問的原因是因爲一個特里結構需要某種形式的層次索引。如果你有很多目錄下面只有一些路徑，那麼維護一個trie會有很多開銷。
建議：如果我有足夠的內存，我會使用HashSet<String>並完成它。
如果我沒有很多內存，並遵循80:20規則（或更可能是95：5）的目錄結構，我會想到一個HashMap<String,Set<String>>。這張圖的關鍵是具有「合理」重複量的最長的主要路徑字符串，並且這些值將是剩餘的字符串。你會用逐漸縮短的主要組件探測這張地圖，直到你找到一個匹配，然後探索其餘部分。
這留下了「合理」重複的問題。這是通過減少重複來克服兩件式數據結構的開銷的重複數量。例如，/usr/bin/可能是有效的（因爲它包含數千個文件，並且每個文件保存9個字符或18個字節），但/usr/local/bin/可能不會（至少在我的系統上，它只保存單個文件）。
相似http://stackoverflow.com/questions/2218905/need-memory-efficient-way-to-store-tons-of-strings-was-hat-trie-pleplementation – Joel 2011-04-09 12:02:30