Java迭代器需要知道的事儿

摘要

Java集合框架总览

Collection

List

ArrayList、Vector、LinkedList

Set

LinkedHashSet、TreeSet

Map

HashTable、HashMap、TreeMap、LinkedHashMap、ConcurrentHashMap
Iterator源码分析
- 实现Iterable接口可以使用foreach，Iterable接口主要提供一个返回Iterator的方法。
- Iterator提供HasNext、next、remove等遍历容器方法，其实现由子类(ArrayList、AbstractList等)实现。
- ListIterator接口是Iterator的子接口，在原来迭代器接口的基础上又增加了一些新的方法，允许向前、向后两个方向遍历
foreach和迭代器

foreach是java的语法糖，其实现是通过Iterator和wile实现的。
for循环和foreach
- 这两个都是遍历数据容器的方式，但两者有根本性的差别：for循环是通过循环的方式去遍历数据，而foreach是通过while循环+迭代器的方式遍历数据。
- foreach遍历容器的时候，如果对容器进行了add/remove操作，会抛出ConcurrentModificationException异常。但也不是所有容器，Java提供的fail-safe(java.util.concurrent包下的容器都是fail-safe)机制的容器就可以在遍历的时候add/remove。
ConcurrentModificationException异常出现的原因
- 为什么foreach遍历ArrayList的时候，remove元素会抛出异常？
  
  ArrayList中有类变量modCount记录了ArrayList变化的次数，每次在add/remove的时候会自增，当调用ArrayList.iterator()方法的时候会new一个内部类Itr，并在初始化Itr的时候赋值expectedModCount=modCount。
  
  当ArrayList再调用add/remove方法的时候modCount会再次自增，但expectedModCount并不会随之改变。最终在遍历时调用Itr.next()校验modCount是否等于expectedModCount时抛出异常。
- 为什么用迭代器遍历时，remove元素就不会抛出异常？
  
  迭代器遍历时，调用Itr.remove()时会再次令expectedModCount=modCount，所以在Itr.next()判断时会通过校验。

前言

集合是Java语言里的重要部分，面试时必定会问的问题，都知道集合会问 ArrayList、LinkedList、HashMap等，但有时看的博客太过片段，没有对整个集合框架有较完整的认知，本文是Java集合部分的前序，包含以下几个部分：

介绍Java集合框架中重要的接口和类。
对迭代器接口Iterator进行源码分析。
对接口Collection和Map进行源码分析。

Java集合框架总览

集合框架主要3个：List、Set、Map，看一下类图（图中红框框出的是在面试中最多问到的和平时使用最多的类）

Collection和Map都是在java.util包下的，而ConcurrentHashMap是在并发包java.util.concurrent下。

Map和List、Set不同，不是Collection的实现类，并且也没有实现Iterable，这也是为什么不能直接通过foreach的方式去遍历Map的原因

接口Iterator源码分析

我们知道集合是用来存放数据的容器，我们经常也需要去遍历整个容器，去获取数据，操作数据，这就有了迭代器的意义。

Collection接口是Iterable的子接口，Iterable这个接口的作用在其类声明中也可以看到，也就是实现了这个接口的类可以使用for-each的循环。

那么为什么实现了这个接口就可以遍历了呢？

其实这个接口最主要的方法是返回一个Iterator接口，在Iterator接口中，主要方法是我们熟悉的hasNext() next() remove()。

Iterable 可遍历，Iterator遍历器

1.8之后Iterator接口中新增了一个forEachRemaining方法，方法作用是将每个元素作为参数发给action来执行特定操作

既然这个迭代器是接口，那么其具体实现是怎么实现的呢？我们以ArrayList为例，在ArrayList中重写了Iterator()方法（如下），可以看到new了一个Itr对象，这个Itr是ArrayList的内部类，并实现了Iterator接口。

public Iterator<E> iterator() {
  return new Itr();
}

/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
  int cursor;       // index of next element to return
  int lastRet = -1; // index of last element returned; -1 if no such
  int expectedModCount = modCount;
  Itr() {}
  public boolean hasNext() {
    return cursor != size;
  }
  public E next() {
   ...
  }
  public void remove() {
   ...
  }
  public void forEachRemaining(Consumer<? super E> consumer) {
    ...
  }
}

有了上面的源码分析，当试着去看LinkedList的迭代器实现，会发现其iterator()方法调用的是父抽象类AbstractList的iterator()方法。原来在抽象类AbstractList中也重写了iterator()方法，并定义了一个Itr()的内部类，跟ArrayList很相似（还不知道为什么要在ArrayList中又重写一次）。这里整理了一下Java集合框架迭代器的实现。

类	迭代器实现	说明
ArrayList	ArrayList定义的内部类
LinkedList	AbstractList中定义的内部类
Vector	Vector定义的内部类	方法级synchronized
Set	map.keySet().iterator()	TreeSet、LinkedHashSet同样
Map	Key、value、entry继承AbstractSet，有实现iteratable接口

对于List其实现较为相似，都是会在内部定义一个Itr的类，然后iterator()方法是返回一个Itr内部类的实例对象，但Set的iterator()方法实现令人惊讶，并且Map没有继承Iterable接口，却也有iterator()方法（是在Map的内部类keySet等中有），这部分的源码会在后面对List、Set、Map的深入分析中展开。

ListItr

在List中，无论是AbstractList还是ArrayList、Vector都有一个ListItr的内部类。

private class ListItr extends Itr implements ListIterator<E> {
  ListItr(int index) {
    cursor = index;
  }
  ...
}

ListIterator接口是Iterator的子接口，在原来迭代器接口的基础上又增加了一些新的方法，允许向前、向后两个方向遍历 List

foreach和迭代器

foreach其实是Java提供的语法糖，我们看下用foreach的循环反编译之后的是如何的。

原代码：

List<String> userNames = new ArrayList<String>() {{
    add("Hollis");
    add("H");
}};

for (String userName : userNames) {
    if (userName.equals("Hollis")) {
        userNames.remove(userName);
    }
}

反编译之后的代码：

public static void main(String[] args) {
    List<String> userNames = new ArrayList<String>() {{
        add("Hollis");
        add("H");
    }};

    Iterator iterator = userNames.iterator();
    do
    {
        if(!iterator.hasNext())
            break;
        String userName = (String)iterator.next();
        if(userName.equals("Hollis"))
            userNames.remove(userName);
    } while(true);
    System.out.println(userNames);
}

原来foreach的实现是通过Iterator和wile实现的。

for循环和foreach

这两个都是可以实现遍历数据容器的方式，但两者有根本性的差别：for循环是通过循环的方式去遍历数据，而foreach是通过while循环+迭代器的方式遍历数据。

如果在遍历集合的时候，对集合进行了add/remove操作，那么for循环和foreach循环会有什么不同呢？我们看下下面这个例子：

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        new Main().run2(list);
        System.out.println(list);
    }

    private void run1(List list) {
        for (int i = 0; i < list.size(); i++) {
            list.remove(i);
        }
    }

    private void run2(List<Integer> list) {
        for (Integer i : list) {
            list.remove(i);
        }
    }
}

结果一目了然：

run1运行结果：[2, 4]

run2运行结果：Exception in thread "main" java.util.ConcurrentModificationException（记住这个异常，后文会进行分析）

上面的结果应该都没什么疑问，foreach中不要对遍历对象进行add/remove这几乎是常识了（但也不是所有的容器，fail-safe的容器就可以遍历的时候add/remove），但如果我们将输入的list的长度改为2时，输出结果是否会报异常呢？

 public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
//        list.add(3);
//        list.add(4);
        new Main().run2(list);
        System.out.println(list);
    }

    private void run2(List<Integer> list) {
        for (Integer i : list) {
            list.remove(i);
        }
    }

输出结果:[2] ， 输出结果并没有抛出ConcurrentModificationException异常

这是为什么呢？我们从源码的角度去分析一下这个问题。

ConcurrentModificationException异常出现的原因

我们用反编译之后的代码看一下：

public static void main(String[] args) {
    List<Integer> list = new ArrayList<String>() {{
        add(1);
        add(2);
    }};

    Iterator iterator = list.iterator();
    do
    {
        if(!iterator.hasNext())                  // 2
            break;
        Integer i = (Integer)iterator.next();    // 3
        list.remove(i);                           // 1
    } while(true);
    System.out.println(list);
}

在ArrayList中搜索一下ConcurrentModificationException异常，发现与上述代码相关的就是迭代器的next()方法。对于ArrayList，其迭代器是内部实现的Itr内部类，在next方法中会首先调用checkForComodification方法，代码如下：

public E next() {
  checkForComodification();
	...
}

final void checkForComodification() {
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

哦！原来modCount != expectedModCount就会抛出ConcurrentModificationException异常。

分析到这里，我们可以先回答一下上节的问题：

为什么当list的长度为2是，使用foreach遍历集合，并对集合进行remove操作，并不会抛出ConcurrentModificationException异常？

答案就是，抛出异常是在迭代器的next()方法中，会先校验modCount 是否 expectedModCount。而集合长度为2时，在第一次remove之后再调用迭代器hasNext()就直接跳出循环了。

现在我们接着将modCount和expectedModCount是什么。modCount代表对ArrayList的操作次数，每次add/remove都会使modCount++，而expectedModCount是ArrayList内部迭代器的修改次数，当调用ArrayList的iterator方法时，会new Itr，并在此时对expectedModCount赋值为modCount。

//调用ArrayList的iterator()方法会new Itr
public Iterator<E> iterator() {
  return new Itr();
}
//Itr初始化的时候，expectedModCount会赋值为modCount
private class Itr implements Iterator<E> {
  int cursor;       // index of next element to return
  int lastRet = -1; // index of last element returned; -1 if no such
  int expectedModCount = modCount;

所以，expectedModCount只在Itr初始化（也就是调用ArrayList的Iterator方法）的时候会赋值为modCount ，如果后面又对ArrayList修改了(add/remove)，那么modCount++，但expectedModCount并不会改变，所以就造成了modCount != expectedModCount

我们在看下面的代码：

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        Iterator<Integer> iterator = list.iterator();
        do{
            if(!iterator.hasNext())  {
                break;
            }
            Integer i = iterator.next();
            iterator.remove();  //和上面的代码只是改变了这行！ list换成了iterator
        }while (true);
        System.out.println(list);
    }

这是用迭代器去遍历的通常实现，结果一目了然，输出结果：[]

但为什么第12行代码，list.remove()换成iterator.remove()就不会有异常了呢？

public void remove() {
  if (lastRet < 0)
    throw new IllegalStateException();
  checkForComodification();

  try {
    ArrayList.this.remove(lastRet);
    cursor = lastRet;
    lastRet = -1;
    expectedModCount = modCount;   //LOOK AT ME！
  } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
  }
}

在代码第10行，会对再次expectedModCount赋值为modCount。所以使用iterator.remove()并不会抛出ConcurrentModificationException异常