ArrayList迭代器源码分析

时间：2022-04-07 22:21:00

集合的遍历

Java集合框架中容器有很多种类，如下图中：

ArrayList迭代器源码分析

对于有索引的List集合可以通过for循环遍历集合：

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

 ​

 list.add("aaa");

 list.add("bbb");

 list.add("ccc");

 list.add("ddd");

 ​

 for (int i = 0; i < list.size(); i++) {

     System.out.println(list.get(i));

 }

同样的对于List集合也可以用其迭代器来遍历：

 Iterator<String> iterator = list.iterator();

 ​

 while (iterator.hasNext()) {

     System.out.println(iterator.next());

 }

以及使用增强for循环，但是增强for循环还是用迭代器实现的：

 for (String s : list) {

     System.out.println(s);

 }

迭代器接口定义

首先来看下迭代器的接口定义如下：

 public interface Iterator<E> {

 ​

     boolean hasNext();

 ​

     E next();

 ​

     default void remove() {

         throw new UnsupportedOperationException("remove");

     }

 ​

     default void forEachRemaining(Consumer<? super E> action) {

         Objects.requireNonNull(action);

         while (hasNext())

             action.accept(next());

     }

 }

可以看得到迭代器中只定义了四个方法， hasNext() 判断是否有下个元素， Next() 获取下个元素， remove() 删除元素，以及 forEachRemaining() 方法对每个剩余元素都执行给定操作，直到所有元素都被处理或动作引发异常。

ArrayList迭代器源码分析

下面来看ArrayList中的迭代器实现源码：

 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

 ​

     //判断是否有下个元素就是将cursor与集合size进行比较当cursor不等size时表示有下个元素

     //hasNext()方法

     public boolean hasNext() {

         return cursor != size;

     }

 ​

     //下个元素

     public E next() {

         checkForComodification();

         //当前的游标赋给i

         int i = cursor;

         //判断i是否越界

         if (i >= size)

             throw new NoSuchElementException();

         Object[] elementData = ArrayList.this.elementData;

         //判断i是否超出elementDate

         if (i >= elementData.length)

             throw new ConcurrentModificationException();

         cursor = i + 1;

         return (E) elementData[lastRet = i];

     }

 ​

     //删除当前的元素

     public void remove() {

         if (lastRet < 0)

             throw new IllegalStateException();

         //判断集合版本号与集合迭代器版本号是否相同

         checkForComodification();

 ​

         try {

             ArrayList.this.remove(lastRet);

             cursor = lastRet;

             lastRet = -1;

             //将删除元素后的集合版本号赋给迭代器版本号

             expectedModCount = modCount;

         } catch (IndexOutOfBoundsException ex) {

             throw new ConcurrentModificationException();

         }

     }

 }

在迭代过程中对集合做出修改就会抛出异常ConcurrentModificationException，这个异常来源是 checkForComodification() 方法，这个方法的代码如下：

 final void checkForComodification() {

     if (modCount != expectedModCount)

     throw new ConcurrentModificationException();

 }

modCount是当前集合的版本号，每次对集合进行修改操作都会导致modCount加1，expectedModCount是这个集合的迭代器的版本号，在迭代器的初始话过程中可以看到

 int expectedModCount = modCount;

将集合版本号赋给集合的迭代器的版本号，之后的迭代过程中Next()和hasNext()方法都会调用checkForComodification()这个方法来判断两个版本号是否相同。所以在迭代过程中是不可以对集合进行修改的操作。但是迭代器自带的remove()方法却可以对集合进行元素删除操作，这是因为在迭代器的remove()方法中每次删除元素后都有

 expectedModCount = modCount;

这个操作来同步集合和集合的迭代器的版本号。因此，使用了迭代器的 remove() 方法对集合中的元素进行了删除操作不会导致ConcurrentModificationException错误。增强for循环是迭代器实现的，因此增强for循环和其同理。在增强for循环中修改元素一样会抛出异常。

增强for循环实现

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

 list.add("aaa");

 list.add("bbb");

 list.add("ccc");

 list.add("ddd");

 for (String s : list) {

     System.out.println(s);

 }

上面的代码对list集合用增强for循环进行遍历输出，反编译之后得到如下结果：

 List<String> list = new ArrayList();

 list.add("aaa");

 list.add("bbb");

 list.add("ccc");

 list.add("ddd");

 Iterator var2 = list.iterator();

 while(var2.hasNext()) {

     String s = (String)var2.next();

     System.out.println(s);

 }

所以可以明显的看到增强for循环实现也是通过迭代器，因此也不能在增强for循环中对集合元素进行修改，否则会抛出ConcurrentModificationException异常。

迭代中多次调用Next()

在如下这种情况中在迭代过程中调用了两次Next()方法：

 ArrayList<Integer> list1 = new ArrayList<>();

 list1.add(1);

 list1.add(2);

 list1.add(3);

 list1.add(4);

 list1.add(5);

 Iterator iter = list1.iterator();

 while (iter.hasNext()) {

     System.out.println(iter.next());  //两次迭代器next()问题

     System.out.println(iter.next());

 }

运行结果是可以打印出所有的元素，但是会抛出NoSuchElementException异常，但是如果减少一个list1中的元素就会正常输出：

 public static void main(String[] args) {

     ArrayList<Integer> list1 = new ArrayList<>();

     list1.add(1);

     list1.add(2);

     list1.add(3);

     list1.add(4);

     Iterator iter = list1.iterator();

     while (iter.hasNext()) {

         System.out.println(iter.next());

         System.out.println(iter.next());

     }

运行可以完整输出，并且不会抛出NoSuchElementException异常。这是因为在每次Next()方法中

 if (i >= elementData.length)

     throw new ConcurrentModificationException();

都会做如上的判断，来判断当前的游标是否已经在元素地址外，上面的测试代码中出现异常的代码，一共有五个元素，每次while循环都会迭代两次，所以当第三次进入循环的第一次迭代时可以正常输出的，但是第二次迭代就会出现迭代器中的游标已经等于集合的长度，所以会抛出异常。但是在没有抛出异常的代码中，一共四个元素，每次迭代都会调用两次next()方法，所以一共执行了两次while循环，最后一次循环中的最后一次迭代游标正好在 list.length - 1 处，不会抛出异常，并且下一次循环因为hasNext()方法返回false，所以也不会进入while循环中，所以并不会抛出异常。

相关文章