java for each loop 的实现原理

最近在leetCode上做题，参考别人的代码时，看到了如下的code:

public int removeDuplicates(int[] nums) {
    int cur = 0 ; 
    for(int n:nums)
        if(n>nums[cur])
            nums[++cur] = n;
    return cur+1;
}

 

这个函数的功能是删除一个已排序数组中的重复数字，上面这段code比我的实现简洁许多。但是我第一眼看到它时产生了一个疑问。在我的印象中，java 的for each loop中只能做读操作，不能做写操作，否则会抛出ConcurrentModificationException。但是上面的code工作的很好。我记得for each loop 会编译成iterator的操作，但是查了一下Array Class 并没有iterator的功能，array 的for each loop 又是怎么实现的呢？为了搞清楚这个问题做了如下调查。

写了一段在array上for each loop的函数

 

package test;

public class ArrayIterate {	
	public static void main(String[] args){
		int [] a = new int[]{1,2,3,4,5};
		for(int i: a){
			int b = i;
		}
	}
}

 编译后查看class 文件, 如下：

 

// Compiled from ArrayIterate.java (version 1.6 : 50.0, super bit)
public class test.ArrayIterate {
  
  // Method descriptor #6 ()V
  // Stack: 1, Locals: 1
  public ArrayIterate();
    0  aload_0 [this]
    1  invokespecial java.lang.Object() [8]
    4  return
      Line numbers:
        [pc: 0, line: 3]
      Local variable table:
        [pc: 0, pc: 5] local: this index: 0 type: test.ArrayIterate
  
  // Method descriptor #15 ([Ljava/lang/String;)V
  // Stack: 4, Locals: 7
  public static void main(java.lang.String[] args);
     0  iconst_5
     1  newarray int [10]
     3  dup
     4  iconst_0
     5  iconst_1
     6  iastore
     7  dup
     8  iconst_1
     9  iconst_2
    10  iastore
    11  dup
    12  iconst_2
    13  iconst_3
    14  iastore
    15  dup
    16  iconst_3
    17  iconst_4
    18  iastore
    19  dup
    20  iconst_4
    21  iconst_5
    22  iastore
    23  astore_1 [a]
    24  aload_1 [a]
    25  dup
    26  astore 5
    28  arraylength
    29  istore 4
    31  iconst_0
    32  istore_3
    33  goto 47
    36  aload 5
    38  iload_3
    39  iaload
    40  istore_2 [i]
    41  iload_2 [i]
    42  istore 6
    44  iinc 3 1
    47  iload_3
    48  iload 4
    50  if_icmplt 36
    53  return
      Line numbers:
        [pc: 0, line: 5]
        [pc: 24, line: 6]
        [pc: 41, line: 7]
        [pc: 44, line: 6]
        [pc: 53, line: 9]
      Local variable table:
        [pc: 0, pc: 54] local: args index: 0 type: java.lang.String[]
        [pc: 24, pc: 54] local: a index: 1 type: int[]
        [pc: 41, pc: 44] local: i index: 2 type: int
      Stack map table: number of frames 2
        [pc: 36, full, stack: {}, locals: {java.lang.String[], int[], _, int, int, int[]}]
        [pc: 47, same]
}

 嗯...... 没看懂。

 

再仔细看，main 函数的

28 arraylength

29 istore 4

这两行是取了数组长度然后存入4号变量 

44  iinc 3 1

47  iload_3

48  iload 4

50  if_icmplt 36

这四行是，

3号变量增大1

load 3号变量到栈顶

load 4号变量到栈顶

比较栈顶的两个操作数如果第一个小于第二个则跳转到36也就是循环起始的位置。

看明白这几行大概就知道是怎么执行的了，array 的for each loop会编译成一个基于array length的loop。

与写一个for(int i=0; i<array.length;i++){}具有一样的效果。

再看看List上的for each loop是怎么回事。

package test;

import java.util.ArrayList;

public class ListIterate {
	public static void main(String[] args){
		ArrayList<Integer> a= new ArrayList<Integer>();
		a.add(1);
		a.add(2);
		a.add(3);
		a.add(4);
		a.add(5);
		for(int i : a){
			int b = i;
		}
	}
}

 编译后的结果

// Compiled from ListIterate.java (version 1.6 : 50.0, super bit)
public class test.ListIterate {
  
  // Method descriptor #6 ()V
  // Stack: 1, Locals: 1
  public ListIterate();
    0  aload_0 [this]
    1  invokespecial java.lang.Object() [8]
    4  return
      Line numbers:
        [pc: 0, line: 5]
      Local variable table:
        [pc: 0, pc: 5] local: this index: 0 type: test.ListIterate
  
  // Method descriptor #15 ([Ljava/lang/String;)V
  // Stack: 2, Locals: 5
  public static void main(java.lang.String[] args);
     0  new java.util.ArrayList [16]
     3  dup
     4  invokespecial java.util.ArrayList() [18]
     7  astore_1 [a]
     8  aload_1 [a]
     9  iconst_1
    10  invokestatic java.lang.Integer.valueOf(int) : java.lang.Integer [19]
    13  invokevirtual java.util.ArrayList.add(java.lang.Object) : boolean [25]
    16  pop
    17  aload_1 [a]
    18  iconst_2
    19  invokestatic java.lang.Integer.valueOf(int) : java.lang.Integer [19]
    22  invokevirtual java.util.ArrayList.add(java.lang.Object) : boolean [25]
    25  pop
    26  aload_1 [a]
    27  iconst_3
    28  invokestatic java.lang.Integer.valueOf(int) : java.lang.Integer [19]
    31  invokevirtual java.util.ArrayList.add(java.lang.Object) : boolean [25]
    34  pop
    35  aload_1 [a]
    36  iconst_4
    37  invokestatic java.lang.Integer.valueOf(int) : java.lang.Integer [19]
    40  invokevirtual java.util.ArrayList.add(java.lang.Object) : boolean [25]
    43  pop
    44  aload_1 [a]
    45  iconst_5
    46  invokestatic java.lang.Integer.valueOf(int) : java.lang.Integer [19]
    49  invokevirtual java.util.ArrayList.add(java.lang.Object) : boolean [25]
    52  pop
    53  aload_1 [a]
    54  invokevirtual java.util.ArrayList.iterator() : java.util.Iterator [29]
    57  astore_3
    58  goto 77
    61  aload_3
    62  invokeinterface java.util.Iterator.next() : java.lang.Object [33] [nargs: 1]
    67  checkcast java.lang.Integer [20]
    70  invokevirtual java.lang.Integer.intValue() : int [39]
    73  istore_2 [i]
    74  iload_2 [i]
    75  istore 4
    77  aload_3
    78  invokeinterface java.util.Iterator.hasNext() : boolean [43] [nargs: 1]
    83  ifne 61
    86  return
      Line numbers:
        [pc: 0, line: 7]
        [pc: 8, line: 8]
        [pc: 17, line: 9]
        [pc: 26, line: 10]
        [pc: 35, line: 11]
        [pc: 44, line: 12]
        [pc: 53, line: 13]
        [pc: 74, line: 14]
        [pc: 77, line: 13]
        [pc: 86, line: 16]
      Local variable table:
        [pc: 0, pc: 87] local: args index: 0 type: java.lang.String[]
        [pc: 8, pc: 87] local: a index: 1 type: java.util.ArrayList
        [pc: 74, pc: 77] local: i index: 2 type: int
      Local variable type table:
        [pc: 8, pc: 87] local: a index: 1 type: java.util.ArrayList<java.lang.Integer>
      Stack map table: number of frames 2
        [pc: 61, full, stack: {}, locals: {java.lang.String[], java.util.ArrayList, _, java.util.Iterator}]
        [pc: 77, same]
}

看过main的54, 62,78发现，果真是基于Iterator实现的。

首先获取iterator,

然后调用iterator.next() 获取当前element。

接着调用iterator.hasNext()

然后判断刚才获取的值是否为真，是则跳转到61循环开始的位置。

至此基本上搞明白了java for each loop的实现原理。

 

顺便又看了一下ArrayList的javadoc,

The iterators returned by this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

 

发现不是任何写操作都会引起ConcurrentModificationException, 只有structurally modified才会。啥叫structurally modified？这个取决于list的具体实现，对ArrayList来说，iterate一个ArrayList时，对这个list增减element就是structurally modified。如果修改element的property则没有问题。