對java.util.HashMap.keySet（）的調用有多昂貴？

Question

我實現了一個稀疏矩陣爲List<Map<Integer,Double>>。
要獲得第i行的所有條目，我請致電list.get(i).keySet()。這個電話有多貴？

我還使用了替代實現的庫文件庫List<TIntDoubleHashMap>。
撥打list.get(i).keys()的費用是多少？

關於如何實現一個高效的稀疏矩陣，你還有什麼想法嗎？
或者你能提供一個在java中現有實現的列表？

Answer 1

根據Sparse matrices/arrays in Java，Colt庫包含此功能;潛入他們Javadoc API，這似乎是真實的，幷包括時間。

此外，您的實現似乎不使用列方式稀疏（您只有行上hashmaps）。他們的確，並且針對整數和雙精度進行了優化，就像Trove中的情況一樣（但不是標準的Java情況下，它使用的對象具有相當大的開銷）。我推薦Colt。

Answer 2

這是一樣便宜，因爲它是一個看法。

從jdk7 source line 884：

public Set<K> keySet() { 
    Set<K> ks = keySet; 
    return (ks != null ? ks : (keySet = new KeySet())); 
} 

特羅韋可能是因爲不像Java集合框架更快它可以直接與原語工作，無需昂貴的裝箱/拆箱。

Answer 3

取決於實現List和Map的類。如果您使用實現java.util.RandomAccess（即ArrayList）的List類，則get（i）的調用爲O（1）。如果它是一個LinkedList，它將是O（n）。

- 編輯，以顯示下面的代碼片段（因爲verdy_p下面沒有讀好，並且喜歡去關切線）： -

// In HashMap.java, line 867, JDK 1.6.0.24, how much more 
// constant time do we want? 

public Set<K> keySet() { 
    Set<K> ks = keySet; 
    return (ks != null ? ks : (keySet = new KeySet())); 
} 

- 編輯的結束 - -

在大多數Map實現上對keySet（）的調用將是常量時間。關於遍歷keySet（）如果使用的是數組支持的Map實現（如HashMap），keySet（）依賴於entrySet（），它返回一個由數組支持的內部迭代器。所以keySet（）的迭代是O（n）。

我也會認爲大部分（如果不是全部的話）都是由數組支持的Map實現。

對於SortedMap實現（如TreeMap），迭代其鍵值將類似於從最低鍵到最大鍵的樹上迭代。這相當於一個失敗的二進制搜索，它是O（n）。

這兩種情況似乎都是O（n）。如果你使用Eclipse，你實際上可以看看實現Java類的代碼，並更好地瞭解它們的複雜性。

對於java.util.concurrent下的類（如ConcurrentHashMap），您必須考慮其他因素以確定它們的價格。要擴展更多，如果使用鏈表，list.get（i）.keyset（）將爲O（n）。如果使用鏈表，list.get（i）.keyset（）將爲O（n）。使用ArrayList，它將是O（1）。遍歷鍵集將取決於您是使用數組支持的Map（HashMap）還是SortedMap（TreeMap）。在這兩種情況下，穿越會爲O（n）與前者比顯著更快後來因爲數組遍歷總是比通過指針遍歷更快（在此Java具體情況或引用。）現在

，如果你把都用 list.get（i）.keySet（）和迭代集合考慮進去，用鏈表實現，那就是O（n^2）。因此，而不是做list.get（I）.keySet（），你應該使用一個迭代器（見僞下面，它消除了清晰通用語法）

這是列出了爲O（n^2）不實現java.util.RandomAccess（如鏈表）：

for(int i = 0; i < list.size(); i++) 
{ 
    Set keySet = list.get(i).keySet(); 
    for(Integer key : keySet.iterator()) 
    { 
     ... stuff (assuming constant time) ... 
    } 
} 

這是其他同類型的List實現的O（N）：

for(Map m : list.iterator()) 
{ 
    for(Integer key : m.keySet()) 
    { 
     ... stuff (assuming constant time) ... 
    } 
}