对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) ... 
    } 
}