遍历集合的最有效方法是什么?

List<Integer>  a = new ArrayList<Integer>();
for (Integer integer : a) {
  integer.toString();
}

or

List<Integer>  a = new ArrayList<Integer>();
for (Iterator iterator = a.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   integer.toString();
}

请注意,这不是这个,这个,这个或这个的精确副本,尽管最后一个问题的答案之一很接近。这不是一个骗局的原因是,其中大多数是比较循环,在循环中调用get(i),而不是使用迭代器。

根据Meta上的建议,我会把我对这个问题的答案贴出来。


当前回答

Foreach在底层使用迭代器。它真的只是语法糖。

考虑下面的程序:

import java.util.List;
import java.util.ArrayList;

public class Whatever {
    private final List<Integer> list = new ArrayList<>();
    public void main() {
        for(Integer i : list) {
        }
    }
}

我们用javac编译, 并读取main()的分解字节码,使用javap -c Whatever:

public void main();
  Code:
     0: aload_0
     1: getfield      #4                  // Field list:Ljava/util/List;
     4: invokeinterface #5,  1            // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
     9: astore_1
    10: aload_1
    11: invokeinterface #6,  1            // InterfaceMethod java/util/Iterator.hasNext:()Z
    16: ifeq          32
    19: aload_1
    20: invokeinterface #7,  1            // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
    25: checkcast     #8                  // class java/lang/Integer
    28: astore_2
    29: goto          10
    32: return

我们可以看到foreach编译成一个程序:

使用List.iterator()创建迭代器 If Iterator.hasNext():调用Iterator.next()并继续循环


至于“为什么这个无用的循环没有从编译的代码中得到优化?”我们可以看到它没有对列表项做任何事情”:好吧,你可以对你的iterable进行编码,使.iterator()产生副作用,或者使. hasnext()产生副作用或有意义的结果。

您可以很容易地想象,表示来自数据库的可滚动查询的迭代器可能会在. hasnext()上做一些戏剧性的事情(比如联系数据库,或者因为到达结果集的末尾而关闭游标)。

因此,即使我们可以证明在循环体中没有发生任何事情,但要证明在迭代时没有发生任何有意义的/结果性的事情是更昂贵的(棘手的?)编译器必须在程序中保留这个空循环体。

我们所能希望得到的最好结果是一个编译器警告。有趣的是,javac -Xlint:all Whatever.java没有警告我们这个空循环体。不过IntelliJ IDEA可以。诚然,我已经将IntelliJ配置为使用Eclipse Compiler,但这可能不是原因所在。

其他回答

Iterator是Java Collections框架中的一个接口,它提供了遍历或遍历集合的方法。

当您的动机只是遍历一个集合以读取其中的元素时,迭代器和for循环的作用是相似的。

for-each只是遍历集合的一种方法。

例如:

List<String> messages= new ArrayList<>();

//using for-each loop
for(String msg: messages){
    System.out.println(msg);
}

//using iterator 
Iterator<String> it = messages.iterator();
while(it.hasNext()){
    String msg = it.next();
    System.out.println(msg);
}

for-each循环只能用于实现迭代器接口的对象。

现在回到for循环和iterator的例子。

当您尝试修改一个集合时,区别就出现了。在这种情况下,迭代器更有效,因为它的快速失败属性。ie。在遍历下一个元素之前,它检查底层集合结构中的任何修改。如果发现任何修改,它将抛出ConcurrentModificationException。

(注意:迭代器的这个功能只适用于java中的集合类。util包。它不适用于并发收集,因为它们本质上是故障安全的)

如果您只是在集合中漫游以读取所有值,那么使用迭代器或新的for循环语法之间没有区别,因为新的语法只是在水下使用迭代器。

然而,如果你说的循环是旧的“c风格”循环:

for(int i=0; i<list.size(); i++) {
   Object o = list.get(i);
}

然后,新的for循环或迭代器可以更高效,这取决于底层数据结构。这样做的原因是,对于某些数据结构,get(i)是一个O(n)操作,这使得循环是O(n2)操作。传统链表就是这种数据结构的一个例子。所有迭代器都有一个基本要求,即next()应该是一个O(1)操作,使循环为O(n)。

要验证新的for循环语法是否在水下使用了迭代器,请比较以下两个Java代码段生成的字节码。首先是for循环:

List<Integer>  a = new ArrayList<Integer>();
for (Integer integer : a)
{
  integer.toString();
}
// Byte code
 ALOAD 1
 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator;
 ASTORE 3
 GOTO L2
L3
 ALOAD 3
 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object;
 CHECKCAST java/lang/Integer
 ASTORE 2 
 ALOAD 2
 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String;
 POP
L2
 ALOAD 3
 INVOKEINTERFACE java/util/Iterator.hasNext()Z
 IFNE L3

第二,迭代器:

List<Integer>  a = new ArrayList<Integer>();
for (Iterator iterator = a.iterator(); iterator.hasNext();)
{
  Integer integer = (Integer) iterator.next();
  integer.toString();
}
// Bytecode:
 ALOAD 1
 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator;
 ASTORE 2
 GOTO L7
L8
 ALOAD 2
 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object;
 CHECKCAST java/lang/Integer
 ASTORE 3
 ALOAD 3
 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String;
 POP
L7
 ALOAD 2
 INVOKEINTERFACE java/util/Iterator.hasNext()Z
 IFNE L8

正如您所看到的,生成的字节代码实际上是相同的,因此使用这两种形式都没有性能损失。因此,您应该选择最吸引您的循环形式,对于大多数人来说,这将是for-each循环,因为它具有较少的样板代码。

区别不在于性能,而在于能力。当直接使用引用时,你有更多的权力显式使用迭代器类型(例如List.iterator() vs. List.listIterator(),尽管在大多数情况下它们返回相同的实现)。您还可以在循环中引用迭代器。这允许你在不获得ConcurrentModificationException的情况下从集合中删除项目。

e.g.

这是可以的:

Set<Object> set = new HashSet<Object>();
// add some items to the set

Iterator<Object> setIterator = set.iterator();
while(setIterator.hasNext()){
     Object o = setIterator.next();
     if(o meets some condition){
          setIterator.remove();
     }
}

这不是,因为它会抛出一个并发修改异常:

Set<Object> set = new HashSet<Object>();
// add some items to the set

for(Object o : set){
     if(o meets some condition){
          set.remove(o);
     }
}

为了扩展Paul自己的答案,他已经证明了字节码在特定的编译器(想必是Sun的javac?)上是相同的,但是不同的编译器不能保证生成相同的字节码,对吗?要了解两者之间的实际区别,让我们直接查看源代码,并查看Java语言规范,特别是14.14.2,“增强的for语句”:

增强的for语句相当于如下形式的基本for语句:

for (I #i = Expression.iterator(); #i.hasNext(); ) {
    VariableModifiers(opt) Type Identifier = #i.next();    
    Statement 
}

换句话说,JLS要求两者是等价的。理论上,这可能意味着字节码的边际差异,但在现实中,增强的for循环需要:

调用.iterator()方法 使用.hasNext () 通过.next()使局部变量可用

因此,换句话说,出于所有实际目的,字节码将是相同的,或几乎相同。很难想象任何编译器实现会在两者之间产生任何显著差异。

在使用集合时,应该避免使用传统的for循环。 我要给出的简单原因是for循环的复杂度是O(sqr(n))阶,而Iterator甚至是增强的for循环的复杂度只有O(n)阶。 所以它会带来性能上的差异。 只需要拿出一个包含1000个项目的列表,并用两种方式打印出来。并打印执行时的时间差。你可以看到其中的区别。