最高效的Java數據結構

假設我有串的大名單（約10000個）的三倍這樣：最高效的Java數據結構

car noun yes 
dog noun no 
effect noun yes 
effect verb no

假設我提出了一個字符串雙 - 例如，（效果，動詞） - 我需要快速查看列表中的內容，看看這個對是否出現，如果是，它的值是yes還是no。（在這個例子中，double出現，值爲「no」）。

什麼是Java中用於存儲列表和最有效的搜索方式的最佳數據結構？我正在運行數十萬次這樣的搜索，所以速度是至關重要的。

謝謝！

來源

2011-10-31 Andrew

您可能會考慮使用HashMap<YourDouble, String>。搜索將是O（1）。

您可以創建一個對象，YourDouble包含前兩個值，或者將另一個附加到另一個 - 如果值仍然是唯一的 - 並使用HashMap<String, String>。

來源

2011-10-31 13:06:48

你好，你的意思是說，我應該連接前兩個字符串，使關鍵？ – Andrew

我在說這可能是你的選擇。如果您可以保證所產生的密鑰仍然是唯一的。這真的取決於你的數據。使用String來代替只允許您避免創建YourDouble對象。 –

所有的答案都有幫助，並建議一個HashMap。我將使用HashMap 。 – Andrew

我會爲您想要的每種搜索類型創建一個HashMultimap，例如，「全部三個」，「每一對」和「每個單一領域」。在生成列表時，填充所有不同的地圖，然後可以從適合您查詢的地圖中獲取。（缺點是你至少需要每個類型的類型，例如對於「單個字段」地圖只使用字符串，而對於兩場地圖使用Pair，對於三維地圖使用，野外地圖。）

來源

2011-10-31 13:06:48

我只需要在第一對上進行搜索，所以我猜想帶Pair的HashMap是最簡單的解決方案。 – Andrew

你可以使用一個HashMap其中關鍵的是前兩個字符串，您可以使用它進行查找的那些的串聯，並且該值是一個布爾值，代表yes和no字符串。

或者，看起來第二列中的詞會更少，因爲它們代表類別。你可以有一個HashMap<String, HashMap<String, Boolean>>你第一次索引的地方。「名詞」，「動詞」等，然後你通過例如「車」，「狗」，「效果」，以達到你的布爾值。這可能會更節省空間。

來源

2011-10-31 13:09:25 Vlad

爲什麼不簡單地使用HashMap，其中包含兩個第一個字符串並重新定義equals和hashCode（即Pair ）的鍵？這比連接和地圖的地圖好得多。 –

串聯可能是一個糟糕的主意，你是對的。但是，如我所說，地圖的地圖可能會帶來好處_if_，他在第二列中沒有多少不同的字符串。 – Vlad

是的，第二列只有5種可能性 – Andrew

10k對我來說似乎並不大。你有沒有試過數據庫？

需要查找此類信息的地方是Semantic Web。許多項目僅適用於Triple Stores這種類型。在Triple Store頁面底部有一個列表。

就Java而言，您的算法幾乎肯定會與語言有關，如果您發現在C中實現了一個好的算法，那麼它的Java端口也會很快。

另外，你的數據集是什麼樣的？是否有很多2個匹配，主語和動詞經常是相同的？你期望得到多少火柴？ MapReduce可以在10k中找到一個匹配的情況下工作，但如果查詢返回8k的10k查詢不容易進行分區，那麼它將無法正常工作。

還有一個針對這個問題的查詢語言：SPARQL。 bigdata blog有一些很好的見解，雖然10k似乎並不大。

來源

2011-10-31 13:17:54

最高效的Java數據結構

回答

相關問題