使用什麼數據結構來存儲<String，String>類型的鍵值對？一個鍵有很多值

我的應用程序從.txt文件讀取bigram搭配（對）。他們被認爲是鍵值對。一個單一的鍵可以有多個值（因此，排除任何種類的Map作爲數據結構）...我想按照自然字母順序排列它們。使用什麼數據結構來存儲<String，String>類型的鍵值對？一個鍵有很多值

第一個詞的搭配即鍵將一個動詞，它的價值將有助於動詞字樣的collocation..So的，樹木可以考慮

所以，基本上我想實現一個

SortedList <String, String>

樣的東西..

我所遇到以下是適合我的要求的數據結構，雖然我無法決定使用哪一個：（multimap中這裏提到的是谷歌的集合框架的一部分）

HashMultiMap
嘗試 - 我只知道這個數據結構的基礎知識。我在Java here中發現了它的一個實現。它不執行delete（）操作。
FastTreeMap
TreeMultimap
SortedSetMultimap

，或者你想推薦任何其他數據結構？我還沒有通過Java中的字典呢...請幫我決定哪一個我應該選擇...

謝謝！

編輯 - 名單預計將包含約100-200項

EDIT2：操作：如果搜索鍵 - 值映射在某一給定key..as我前面所說的，DST將存儲列表作爲鍵值條目的動詞詞組配對;它是通過讀取文件中的條目來初始化的...工作如下所示：我們首先獲取dst中的所有密鑰...讀取文件並標記它（通過OpenNLP完成，不是爲此）和然後搜索是否有任何令牌在dst中找到了密鑰（即是動詞）......一旦找到，我們將獲得給定密鑰的所有值，並搜索該組值中的下一個令牌。如果在dst中找到該值，則意味着檢測到搭配...設置適當的值然後...這是DST如何實際工作的原因...

來源

2011-03-27 Navin Israni

'地圖<字符串，列表>'會的工作，並就你想要什麼樣的操作來進行簡單的 – 2011-03-27 10:48:47

？這個集合包含多少條記錄？你打算多久執行一次操作？這些是您必須回答的問題，以便有人能夠推薦合適的數據結構。 – jmg 2011-03-27 11:08:50

我沒有看到您的編輯條目數量。用這麼小的數字，我會說具體的數據結構並不像我以前想象的那麼相關。所以，你的問題更多的是：哪個現成的庫適合你的用例？是對的嗎？ – jmg 2011-03-27 11:18:56

java.util.NavigableMap是提供地圖抽象與鍵的總排序的接口。 JavaSE 6提供java.util.TreeMap或java.util.concurrent.ConcurrentSkipListMap作爲實現。前者對你來說可能就足夠了。要清楚，我建議使用類似：

Map<String,Set<String>>具有以下具體類型TreeMap<String, ArraySet<String>>。

來源

2011-03-27 11:24:56 jmg

謝謝TON！我現在正在使用TreeMap > ..和地圖工作完美罰款...謝謝你.. :) – 2011-03-28 13:12:50

但ALAS ..實施並非100％完成即使然後..請閱讀EDIT3 – 2011-03-28 13:13:47

有一點點錯誤顯示一些值.. 。但現在不見了......再次感謝你..：D – 2011-03-28 13:42:12

僅供參考：Google Collections項目已已停產，現在是Google的Guava的一部分。

番石榴的ListMultimap將確保特定鍵內的值保持與它們在文件中出現的順序相同。但是，它不會將鍵保持與它們在文件中出現的順序相同。

來源

2011-03-27 10:51:57

對這個答案頭腦投票的人會澄清什麼是錯的嗎？ – 2011-03-27 18:17:30

不是HashMap或HashMultiMap，因爲他們不允許你迭代在順序按鍵。

不FastTreeMap或ConcurrentSkipListMap ...除非你的應用程序是多線程的。

各種TreeMap或TreeMultiMap實現都可以，但是TreeMap版本將需要將它們實例化爲Map<String,List<String>>並管理這些列表。

Tree與Trie是有點難度。我懷疑一個精心設計/實現的Trie會提供更快的查找，但我也懷疑它會佔用更多的內存。（我正在做一些假設，實際上，複雜性分析將取決於實現細節）

來源

2011-03-27 11:25:35

我們正在談論200-300個條目，所以，除非這個算法打算在Amiga上運行，否則根本就不重要 – akappa 2011-03-27 11:46:25

是的。性能不是一個大問題。 – 2011-03-27 15:07:59

如果性能（和空間利用率）不是一個問題，那麼無論你使用TreeMap，TreeMultiMap還是基於trie的替代方案......只要相應的實現類都可以工作就無關緊要了。最好的解決方案是最簡單的解決方案。 – 2011-03-28 05:44:23

我認爲如上面建議您可以使用TreeMap（取決於您的收集的大小），這將保證地圖按鍵升序排列，或者如果你想在創建TreeMap時用你自己的比較器自定義排序。

final Map<String, List<String> resultMap = new TreeMap<String, List<String>>();

地圖創建後，你會更新，進一步添加和刪除地圖？除了簡單的遍歷？我認爲如果你有很多添加，更新等等，HashMap是理想的。也許最初創建一個HaspMap然後將其轉換爲TreeMap來遍歷可能會更快一些？任何人？但是，如果您創建HaspMap考慮負載因素，請確保您具有較高的初始容量，以儘量減少重新刷新操作的次數。默認加載因子爲0.75，因此如果您的初始大小爲100，那麼當添加75元素時，地圖將被重新繪製。

啊發現另一個與HashMap負載因子HashMap initialization parameters (load/initialcapacity) stackoverflow鏈接。

來源

2011-03-27 12:50:17 MalsR

AFAIK HashMap不允許多個值的單個鍵...我不知道TreeMap ...有人可以澄清有關TreeMap .. – 2011-03-27 15:14:10

並沒有...我不會修改數據結構，一旦它已被讀取...和示例地圖聲明你給...它的wayy太複雜，我實現.. – 2011-03-27 15:19:46

使用什麼數據結構來存儲<String，String>類型的鍵值對？一個鍵有很多值

回答

相關問題