哪種數據結構最好？

在我的應用程序，我們已經有哪種數據結構最好？

Map<String, List<String>>

現在我們得到了另一個用例，其中需要找到被映射到列表中的特定字符串的關鍵。

我下面想寫作：

string getKey(Map<String, List<String>> m, String str) { 
    for (Entry<String, List<String>> entry :m.entrySet()) { 
    if(entry.getValue().contains(str)) { 
     retrun entry.getKey(); 
    } 
    } 
    return null; 
}

Map最多可以有2000個條目。並且每個List可以具有最多500個String。

任何可能更適合的建議？我可以更改初始數據結構（Map），如果還有更好的方法可以做到這一點..

來源

2013-01-14 vikas368

您可以使用'Set '而不是'List '作爲'contains（）'方法在'Set'上快得多。如果你的地圖很大，你可以考慮添加另一個地圖。 – Shivam

我建議你添加另一個映射，給出反向映射 - 從一個字符串到鍵列表。這需要更多的工作才能與第一張地圖保持同步，但會爲您的任務提供最佳性能。

如果您認爲此類查詢的頻率相對較低，也許您的解決方案可能會更好（雖然速度較慢，但保存兩個地圖同步的時間可以彌補這一點）。

來源

2013-01-14 12:08:36

這種類型的查詢的數量可以是大約3000.如果我有另一個地圖，我將最終有100萬條條目，其中我只查詢3000次。 – vikas368

@ vikas368是的，但是對於地圖，3000個查詢中的每個查詢都可以與答案的大小成線性關係，而如果沒有這個地圖，每個查詢將關於**全部**條目是線性的。考慮到這一點，並認爲它是否值得優化。我猜測3000可能更好地使用我提出的解決方案。 –

終於我要與另一張地圖 – vikas368

您是否熟悉Guava API？如果您可以自由地添加/更改依賴關係，那麼絕對值得一試，特別是Multimap接口的實現。它完全適用於那些可以將相同密鑰映射到多個值的情況。

如果我誤解了這個問題，並且同一個鍵不會映射到多個值，那麼您可能需要重新構思/重新考慮您的問題，因爲您當前的想法Map<String, List<String>>基本上就是這樣。

來源

2013-01-14 12:14:16 posdef

我需要當前映射字符串 - >列表。除此之外，我們現在已經提到了上面提到的用例。 – vikas368

我被允許添加依賴項，但我從未使用過Guava API。你能指點我一些MultiMap的例子嗎？ – vikas368

看看我在上面給出的鏈接的文檔頁面中的例子。 'Multimap'實現很好，因爲你不必管理'List'。 – posdef

哪種數據結構最好？

回答

相關問題