博客

Iterator是Java中常用的接口，在Iterable接口中有一个iterator()方法，它返回一个Iterator对象。集合框架中的迭代器就是来源与此。

Iterator()的功能简单，只能单向移动：
1.调用iterator()方法返回一个Iterator对象。
2.第一次调用Iterator的next()方法，返回序列的第一个元素。此后每调用一个next(),会返回序列的下一个元素。调用next()方法前最好先调用hasNext()方法，判断序列后面是否还有元素。
3.remove()删除上次next()返回的对象，remove()只能在next()之后使用，并且一个remove()匹配一个next().
4.使用hasNext()判断序列中是否还有元素

ArrayList继承AbstractList类，在AbstractList类中定义了一个实现了Iterator接口的内部类：

private class Itr implements Iterator<E> {
  /**
   * Index of element to be returned by subsequent call to next.
   */
  int cursor = 0;

  /**
   * Index of element returned by most recent call to next or
   * previous. Reset to -1 if this element is deleted by a call
   * to remove.
   */
  int lastRet = -1;

  /**
   * The modCount value that the iterator believes that the backing
   * List should have. If this expectation is violated, the iterator
   * has detected concurrent modification.
   */
  int expectedModCount = modCount;

Itr是一个内部类，上述代码一共定义了3个变量，cursor表示遍历的当前序号，lastRet 表示上次遍历的序号，expectedModCount是用来快速失败的。cursor初始值为0，lastRet 初始为-1，expectedModCount在创建迭代器时被复制为AbstractList类中的遍历modCount。某个线程对ArrayList进行add、remove等操作时，会导致自身的modCount+1，这样就和迭代器中的expectedModCount 不同，当检测到二者不同时，意味着有其他线程修改了ArrayList对象，此线程退出，快速失败机制。

  public boolean hasNext() {
    return cursor != size();
  }

如果cursor不等于序列大小，后面肯定存在对象，否则表示全部遍历完，后面没有对象了。

  public E next() {
    checkForComodification();
    try {
      int i = cursor;
      E next = get(i);
      lastRet = i;//最近一次调用next()方法返回的元素的下标。
      cursor = i + 1;//下一次调用next()方法返回的元素的下标。
      return next;
    } catch (IndexOutOfBoundsException e) {
      checkForComodification();
      throw new NoSuchElementException();
    }
  }

迭代器先检查对象是否被修改，使用主类的get()方法得到目标值，然后更新lastRet和cursor，最后返回结果。迭代器的next()方法虽然跟指针有点型似，但是底层时完全不同的。迭代器并没有指向序列内部，而是每次都调用get方法获得对象，并跟新 lastRet和cursor索引。

PS：如果使用LinkedList的iterator的话，那么使用next()的成本很高。因为get()每次都从头开始遍历，速度很慢。

  public void remove() {
    if (lastRet < 0)
      throw new IllegalStateException();//所以，调用remove()前必须先调用next()
    checkForComodification();

    try {
      AbstractList.this.remove(lastRet);
      if (lastRet < cursor)
        cursor--;//因为移除了一个元素
      lastRet = -1;//所以，不能连续调用两次remove()方法
      expectedModCount = modCount;
    } catch (IndexOutOfBoundsException e) {
      throw new ConcurrentModificationException();
    }
  }

调用remove()方法，先判断lastRet，若没调用next()或者已经remove()，lastRet会为-1直接报错。检查对象是否被修改，然后调用主类的remove移除对象。此时序列的对象减少一个，被删对象之后的对象标号整体减1，所以cursor–，同时将lastRet置为-1，若不再次调用next()方法，lastRet不会更新，将不能执行remove().

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