调用java.util.HashMap.keySet()有多贵？

Question

我实现了一个稀疏矩阵List<Map<Integer,Double>>.
为了得到行i的所有条目,我打电话list.get(i).keySet().这次电话有多贵？

我还使用了宝库来替代实现List<TIntDoubleHashMap>.这里
的通话费用是list.get(i).keys()多少？

您对如何实现有效的稀疏矩阵有任何进一步的想法吗？
或者您可以提供Java中现有实现的列表吗？

Answer 1

取决于实现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).使用ArrayList,它将是O(1).遍历键集取决于您是使用数组支持的Map(HashMap)还是SortedMap(TreeMap).在这两种情况下,遍历将是O(n),前者明显快于后者,因为数组遍历总是比遍历指针(或Java特定情况下的引用)更快.

现在,如果你把两个 list.get(I).keySet()和设定的迭代考虑进去,用链表实现,这将是为O(n ^ 2).因此,不应该使用list.get(i).keySet(),而应使用迭代器(请参阅下面的伪代码,为了清晰起见,它避免使用通用语法)

对于未实现java.util.RandomAccess(如LinkedList)的列表,这是O(n ^ 2):

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

Answer 2

根据Java 中的稀疏矩阵/数组，Colt 库包含此功能；深入研究他们的Javadoc API，这似乎是真的，并且包括时间。

此外，您的实现似乎没有使用按列稀疏性（您只在行上有哈希图）。他们的确实如此，并且针对整数和双精度进行了优化，就像 Trove 中的情况一样（但不是标准 Java 情况，它使用具有相当大开销的对象）。我推荐柯尔特。