快速搜索字典

我需要在數據結構中存儲幾百個字符串。每個字符串都有兩個與它相關的字段，就像說出字的含義和它的起源一樣。我可以以任何方式存儲字，比如排序，反向排序或任何你喜歡的字。快速搜索字典

我只需要儘快搜索字典中的字符串並獲取兩個相關字段。如果可能的話，我希望我的搜索比二進制搜索更好。

我正在使用Java。我應該使用哪個data structure或Collection Class？

注意：我不想在此使用數據庫。

來源

2012-09-24 OneMoreError

您尋找完全匹配或尋找類似於'foo'的東西也會返回'foobar'的條目嗎？ – Stephan

嗯，我正在尋找完全相同的東西。但是，如果後者可以完成，我希望它.. – OneMoreError

您可以使用HashMap<String,MyDataObject> - 這將是最快和最簡單的使用。

平均尋道時間是O(|S|)，其中|S|是字符串的長度。

您也可以嘗試和使用trie或radix tree，但在開始使用該解決方案之前，請確保您想通過分析HashMap解決方案來給它時間。

來源

2012-09-24 08:07:46 amit

你是什麼意思，他應該使用'HashSet '？它有一個'contains'方法，但不是'get'。他說他需要存儲鍵值對。 – maba

@maba：你是對的，我想他也想檢查一個Set是否適合存在。從第二次閱讀 - 這肯定不是問題。編輯工作。 – amit

你應該實現接口 – ramsinb

使用HashTable或HashMap

您的結構應該是這個樣子HashMap<String,Bookcontent>

其中BookContent是屬性詞的含義和由來類

來源

2012-09-24 08:08:43 premprakash

答案顯然是「使用HashMap」，但這不是沒有警告。您搜索的每個字符串都需要計算其哈希碼。如果您每次使用新對象，則每次支付O（s是此例中的字符串長度），再加上另一個O（s）以檢查equals。

解決這個問題的一個方法是用intern所有用於搜索的字符串。這將確保一次計算的哈希碼被重複使用，並且還會使後續的檢查短路。

另一種選擇是使用trie。它的優點是您最多支付O（s），但通常較少—這是一個基於前綴的搜索，因此只要您遍歷到前綴唯一的位置，就會得到結果。總之，如果您可以安排重複使用interned字符串，那麼基於哈希碼的解決方案是最佳選擇;如果您可以安排重複使用interned字符串，如果不是的話，一個trie是一個很好的選擇。

其他常見的選項將是一個跳過列表（在Lucene中使用）和B-tree（在數據庫索引中通用）。

來源

2012-09-24 08:10:33

糾正我，如果我錯了，但發現哈希匹配後應該仍然應用「equals（）」方法 - 除非存儲的String和查找的String是*完全相同的對象*無論如何它都是'O（| S |）'。 – amit

@amit如果密鑰被實施，那就會發生 - 將使用完全相同的對象。 –

我建議你使用Trie數據結構。我已經完成了一項類似於此的任務。此link可幫助您實施Trie DS。

來源

2012-09-24 08:11:25 Amarnath

快速搜索字典

回答

相關問題