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

根据 Sparse matrices / arrays in Java Javadoc API ,这似乎是真的,时间也包括在内。

此外,您的实现似乎没有使用逐列稀疏性(您只有行上的哈希映射)。它们是这样的,并且针对int和double进行了优化,就像在Trove中一样(但在标准Java案例中不是这样的,因为标准Java案例使用了具有相当大开销的对象)。我推荐柯尔特。

取决于实现列表和映射的类。如果您使用的是实现java.util.RandomAccess的列表类(即ArrayList),那么对get(i)的调用就是O(1)。如果是LinkedList,则为O(n)。

// 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()));
}

--编辑结束--

关于遍历keySet(),如果您使用的是基于数组的映射实现(如HashMap),keySet()依赖于entrySet(),entrySet()返回由数组支持的内部迭代器。所以keySet()的迭代是O(n)。

我还假设大多数(如果不是所有)由数组支持的Map实现都是这样。

对于SortedMap实现(如TreeMap),对其键的迭代类似于对树从最小键到最大键的迭代。这相当于失败的二进制搜索,即O(n)。

两种情况似乎都是O(n)。如果使用Eclipse,实际上可以查看实现java类的代码,更好地了解它们的复杂性。

为了进一步扩展,如果使用链表,list.get(i).keyset()将是O(n)。对于ArrayList,它将是O(1)。遍历键集将取决于您是使用基于数组的映射(HashMap)还是使用SortedMap(TreeMap)。在这两种情况下,遍历都是O(n),前者是 比后者快,因为数组遍历总是比通过指针(或在这种Java特定情况下的引用)遍历快

现在,如果你 二者都 将是O(n^2)。因此,不必执行list.get(i).keySet(),而应该使用迭代器(请参见 伪码

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

对于同一类型的列表实现,这是O(n):

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

既然是风景,那就便宜多了。

从 jdk7 source line 884

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

Trove可能更快,因为与Java集合框架不同,它可以直接处理原语,而无需昂贵的装箱/拆箱。