JDK源码之ArrayList-Iterator

之前写过一篇ArrayList源码的博客 https://www.cnblogs.com/zumengjie/p/13538394.html 其中遗留了一个问题,ArrayList添加元素和删除元素或者清空元素时都会有一个操作 modCount++;当时并没有将死磕到底的精神进行到底。这两天在一本源码书籍里边提到了这个变量,看完后决定记录下来。这本书我也介绍大家去读《Java修炼指南-高频源码解析》是开课吧组编的书,这本书四个字形容,开卷有益。

下文带//为个人注释。源代码使用这个颜色

迭代集合引发的问题

Itr迭代器

ListItr迭代器继承自Itr

ListItr的特色功能

Fail-Fast机制

一些有趣的方法

  • forEach

  • trimToSize

  • subList

  • 为什么说增强for就是迭代器？

  • Arrays.asList

迭代集合引发的问题

首先先看一段代码。这段代码就是在for循环中使用集合本身的remove方法删除元素。结果大家也都知道因为删除了元素,size减去1,变量i又自增1。最终导致被元素后边的一个没有被遍历到。B被删除了,C顶替了B它的index是2但是变量i已经是3了所以跳过。

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

        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        list.add("E");

        // 结果是 A D E
        for (int i = 0; i < list.size(); i++) {
            if (i == 1) {
                list.remove(i);
            } else {
                System.out.println(list.get(i));
            }
        }

View Code

接着再看这一段代码。看这段代码主要就是要知道在迭代器中使用集合本身的删除,新增都会报错。ConcurrentModificationException。

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

        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        list.add("E");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String next = iterator.next();
            if (next.equals("B")) {
                list.remove("B");// 报错 java.util.ConcurrentModificationException
                list.remove(1);// 报错 java.util.ConcurrentModificationException
                list.add("F");// 报错 java.util.ConcurrentModificationException
            } else {
                System.out.println(next);
            }

        }

View Code

但是可以使用迭代器自己的新增或者删除元素的方法。

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

        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        list.add("E");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String next = iterator.next();
            if (next.equals("B")) {
                iterator.remove();
            } else {
                System.out.println(next);
            }

        }

View Code

Itr迭代器

//它返回的是一个Iterator对象是ArrayList中的一个内部类,Iterator<E> iterator()其实是List接口的一个抽象方法。

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

int cursor;//指向下一个元素的下标，默认是0。
int lastRet = -1;//上一个被迭代的下标。
int expectedModCount = modCount;//这个变量在集合长度变化时会自增1

public boolean hasNext() {
return cursor != size;//判断有没有下一个元素的依据是cursor的size!=size,cursor默认是0。如果size是3,cursor也是3那就没有下一个元素了。
}

//在迭代器里抛出的异常就是它做的,当迭代器创建后expectedModCount==modCount,但如果我们使用集合本身的方法改变了集合的长度modCount就会增加而expectedModCount不会增加。

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

@SuppressWarnings("unchecked")
public E next() {//获取集合内的下一个元素

checkForComodification();//进来后就走了判断,如果通过迭代器以外的方法修改了集合的长度,那这个方法就直接异常了。
int i = cursor;//默认是0
if (i >= size)//这里也是健壮性的判断,和hasNext()起到同样的效果。
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;//拿到ArrayList中的数组。
if (i >= elementData.length)//健壮性的判断
throw new ConcurrentModificationException();
cursor = i + 1;//cursor+1,这表示下一个被读取的元素的下标。
return (E) elementData[lastRet = i];//获取当前元素,并且把下标赋值给lastRet,也就是说这个变量的意思是上一个被迭代的下标。
}

public void remove() {//删除当前被迭代的元素
if (lastRet < 0)
throw new IllegalStateException();//lastRet默认是-1,也就是说如果没有调用next()就调用remove()是会报错的。
checkForComodification();//检验modCount

try {
ArrayList.this.remove(lastRet);//此处调用了ArrayList自身的remove(index)
cursor = lastRet;//这里有点意思。假如调用next()获取的元素是第四个,其实cursor是5而lastRet是4,这里把lastRet赋值给cursor意味着下次next()返回的结果还是第四个。
lastRet = -1;//这里将lastRet置为-1表示如果连续调用两个remove()也会报错。
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

//这个方法其实就是用来遍历集合的,不要试图使用这个方法时改变集合长度,否则极大的几率会出现异常。

//另外这个方法中使用的cursor,lastRet和迭代器中其他方法是共用的。

@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);//断言判断
final int size = ArrayList.this.size;//当前集合的长度
int i = cursor;//cursor默认是0
if (i >= size) {//健壮性判断
return;
}
final Object[] elementData = ArrayList.this.elementData;//拿到数组
if (i >= elementData.length) {//健壮判断
throw new ConcurrentModificationException();
}

//这里就是遍历集合元素,把当前元素交给参数consumer消费。

//如果你在消费时使用集合本身的增加或者删除方法,其效果和普通for循环一样。

//如果你在消费时使用迭代器的remove(i)则会直接报错,因为lastRet默认是-1。
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}

//这里修改cursor意味着再次调用next将会返回false。
cursor = i;

lastRet = i - 1;

//这里会再次检验modCount
checkForComodification();
}

ListItr迭代器继承自Itr

public ListIterator<E> listIterator() {
return new ListItr(0);//它创建的是带参数的 Listltr(0)
}

ListItr(int index) {
super();

//传入的index赋值给了cursor,这意味着我们可以手动的指定下一次迭代的位置。

//但是需要注意cursor更改后,lastRet没有跟着更改，意味着创建listIterator调用迭代器的remove()同样会异常。
cursor = index;
}

//获取迭代器下一次迭代的下标。

public int nextIndex() {
return cursor;
}

//在Itr类中是没有add()方法的。

public void add(E e) {
checkForComodification();//进来后首先做的就是检验modCount的值。

try {
int i = cursor;//当前下标赋值变量

//调用ArrayList自己的添加元素方法。将元素添加到当前i的位置。

//如果当前next元素是1,那么next后就是2也就是在当前迭代元素后添加元素。
ArrayList.this.add(i, e);

//迭代下标+1,这个操作意味着,新添加的元素不会被迭代到。

//例如当前集合为[A,B,C,D,E]当前next指向的是B,则next后cursor就是2

//在2位置添加元素后就是[A,B,N,C,D,E]，那其实下一个next就是N但是cursor+1后下一个就是C了。
cursor = i + 1;
lastRet = -1;//添加后同样会lastRet同样是-1意味着同时调用两次add(e)也会报错。
expectedModCount = modCount;//将modCount赋值给expectedModCount。
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

//这个set方法，倒是有些多余了,因为ArrayList集合本身的set方法不会更改modCount

//因为ListItr的set方法还会检验modCount的值。

public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();//检验modCount

try {
ArrayList.this.set(lastRet, e);//ArrayList自身的set()方法。
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

ListItr的特色功能

//判断有没有上一个,默认的cursor是0,使用了next()后cursor+1。意味着有上一个元素。

public boolean hasPrevious() {
return cursor != 0;
}

//如果有上一个则调用previous获取上一个元素。

@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();//先检验modCount
int i = cursor - 1;//当前cursor左移
if (i < 0)//如果当前迭代器的cursor已经在最左边了,就要报错。
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;//拿到集合中的数组
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];//这里取得是cursor-1
}

//或者可以使用previousIndex向左移动cursor,但是总感觉这个方法使用不当会很危险。

public int previousIndex() {
return cursor - 1;
}

Fail-Fast机制

以上内容解释了modCount这个变量到底是干啥用的。但是都没有用很专业很有B格的名词唠一下。

Fail-Fast是Java中一种错误检测机制！它的触发机制是，在迭代过程中如果集合的结构发生了

变化此时迭代器并不知情或没有来得及反应就会产生Fail-Fast事件。抛出ConcurrentModificationException异常。

所以modCount和迭代器中的expectedModCount不相等就会报错这就是Fail-Fast机制。

一些有趣的方法

forEach

//这个方法是JDK8出的，为了结合拉姆达表达式使用。　

//它接收一个Consumer消费者接口，这个接口只有一个accept方法。

public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;//获取modCount
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;//获取数组
final int size = this.size;//获取集合长度
for (int i=0; modCount == expectedModCount && i < size; i++) {//循环数组
action.accept(elementData[i]);//将数组的每个元素交给Consumer的accept方法并且执行。
}
if (modCount != expectedModCount) {//此处也会判断如果modCount出现改变会报错。
throw new ConcurrentModificationException();
}
}

trimToSize

//这个方法用来收缩数组，当已经确认了集合内不会添加元素时，调用此方法将集合内

//的数组进行收缩，也就是说将数组内的元素拷贝到新的数组中，新的数组大小和size相同

public void trimToSize() {

//这个变量现在已经很熟悉了吧。
modCount++;
if (size < elementData.length) {

//如果size是0就把空数组赋值给elementData,如果不是就做数组拷贝。
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}

subList

看下图的执行结果截取后的小集合元素为BC,小集合添加一个元素后卫BCF。令人迷惑的是大集合的元素ABCFDE。

首先subList(int,int)是对集合做截取返回的一个List但是注意,返回的集合并不是ArrayList而是SubList。

public List<E> subList(int fromIndex, int toIndex) {

//这个方法是对入参进行限定起始位置不能小于0,结束位置不能大于大集合的size,其实位置不能大于结束位置。否则都会抛出异常。
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);

}

//这是ArrayList中的一个内部类。它继承自AbstractList也就是说它和ArrayList是兄弟关系。
private class SubList extends AbstractList<E> implements RandomAccess {

private final AbstractList<E> parent;

//这个变量和offset是一致的,要截取数组的起始位置是N那么小集合和大集合的偏移量就是N

//也就是说要获取小集合的M下标就是要到大集合中找N+M位置的元素
private final int parentOffset;
private final int offset;
int size;

//以上图为例构造函数参数分别是当前ArrayList,0,1,3

SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;//这个值是1
this.offset = offset + fromIndex;//这个值是0+1
this.size = toIndex - fromIndex;//这个值是2
this.modCount = ArrayList.this.modCount;//ArrayList里的集合操作数变量。到处都有它。

//这是AbstractList中的add方法我们调用的是这个。而它则调用自己的双参数方法也就是调用了子类自己的。

public boolean add(E e) {
add(size(), e);
return true;
}

//这是SubList里的add方法.传入的参数是自己的size也就是2

public void add(int index, E e) {

//这里进行了检验index不能小于0不能大于size

rangeCheckForAdd(index);

//这个方法依然检验的是modCount如果当前SubList的modCount和ArrayList的modCount不一样也会抛出异常。
checkForComodification();

//这里调用的是ArrayList的add(int,object)传入的第一个参数是1+2=3也就是在ArrayList集合的第三个下标处添加元素。

//也就是说添加的元素始终是在SubList的最后一个,最终的结果ABCFDE
parent.add(parentOffset + index, e);

//将ArrayList的modCount赋值给SubList的modCount
this.modCount = parent.modCount;
this.size++;
}

//获取元素

public E get(int index) {
rangeCheck(index);
checkForComodification();

//要获取的下标+偏移量
return ArrayList.this.elementData(offset + index);
} }}

为什么说增强for就是迭代器？

最后再回到forEach这个方法。SubList中本身是没有这个方法的，它来自于Iterable继承体系是

SubList->AbstractList->AbstractCollection->Collection->Iterable

这是一个默认实现的方法。这里看似很简单，无非就是循环当前对象，然后把当前元素值传递

给Consumer.accept(o)但是这么想就错了。因为当前这个this其实是SubList但是SubList里并没有

Object[]也就是它根本就没有装在元素的数组。

default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}

断点后的截图如下

走到这我就好奇了,这个this到底是怎么生成的。于是我想使用反编译工具JD-JUI看看。但是失败了。这个工具如果有拉姆达表达式就会失败。

于是我打算曲线救国，既然这个forEach使用的增强for那么我就看看增强for这个语法糖到底干了什么？

不得不喷一句这个工具太垃圾了！于是我又找到了JDK自带的工具javap

终于这就是我要的答案！它走的是迭代器！！！SubList也有自己的迭代器。这里只看next就能看出来,每次查询下一个其实就是使用了offset偏移量+index就像是get方法一样。到此结束！不过有空我还要去找一个好点

的反编译器彻底的反编译一把这个代码。

Arrays.asList

//这个方法不是ArrayList中的方法它是Arrays工具包里的方法。

//之所以聊到它是因为这个方法接收可变长度的数组然后返回

//一个ArrayList但是这个ArrayList可不是咱们本文的ArrayList,

//而是Arrays工具类中的内部类。

public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}

看一个有意思的代码片段。

这段代码执行是会报错的,原因就是虽然返回的也是ArrayList但是这个ArrayList只是继承了AbstractList而AbstractList类中的add方法本身

的add方法是这个样子的。

public void add(int index, E element) {
throw new UnsupportedOperationException();
}

赞 (0)

相关推荐

  • 面试官：兄弟，说说 ArrayList 和 LinkedList 有什么区别

    来自公众号:沉默王二 ArrayList 和 LinkedList 有什么区别,是面试官非常喜欢问的一个问题.可能大部分小伙伴和我一样,能回答出"ArrayList 是基于数组实现的,Lin ...

  • 探索ArrayList底层实现

    背景 想进步,想学习了,反正面试都要问的,还不如早点看了好.探索ArrayList源代码是基于JDK1.8版本的,相比以前的版本不知道有没有优化,毕竟没看过之前版本的底层代码.一般看底层代码前我都习惯 ...

  • 无语！这道迭代器笔试题，居然难倒很多人

    有位小朋友最近正在为年后换工作做准备,但是遇到一个问题,觉得很不可思议的一道笔试题.然后我把这道题发到技术群里,发现很多人居然不知道,很多都是连蒙带猜的说.感觉很有必要写一篇文章来说道说道. 涨薪必备 ...

  • 【java源码】ArrayList

    题目:[java源码]ArrayListArrayList 常用功能:构造函数.增.批量增.删.批量删.批量保留ArrayList 属性: // 默认数组长度(数组,而不是数据个数) private ...

  • 结合JDK源码看设计模式——观察者模式

    前言: 现在我们生活中已经离不开微信,QQ等交流软件,这对于我们来说不仅是交流,更有在朋友圈中或空间中进行分享自己的生活,同时也可以通过这个渠道知道别人的生活.我们在看朋友圈的时候其实我们扮演的就是一 ...

  • 结合JDK源码看设计模式——迭代器模式

    前言: Iterator翻译过来就是迭代器的意思.在前面的工厂模式中就介绍过了iterator,不过当时介绍的是方法,现在从Iterator接口的设计来看,似乎又是一种设计模式,下面我们就来讲讲迭代器 ...

  • 结合JDK源码看设计模式——组合模式

    前言: 相信大家都打开过层级很多很多的文件夹.如果把第一个文件夹看作是树的根节点的话,下面的子文件夹就可以看作一个子节点.不过最终我们寻找的还是文件夹中的文件,文件可以看做是叶子节点.下面我们介绍一种 ...

  • 结合JDK源码看设计模式——原型模式

    定义: 指原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象.不需要知道任何创建的细节,不调用构造函数 适用场景: 类初始化的时候消耗较多资源 new产生的对象需要非常繁琐的过程 构造函数比 ...

  • 结合JDK源码看设计模式——单例模式

    定义: 保证一个类仅有一个实例,并提供一个全局访问点 适用场景: 确保任何情况下这个对象只有一个实例 详解: 私有构造器 单利模式中的线程安全+延时加载 序列化和反序列化安全, 防止反射攻击 结合JD ...

  • 通达信突破孕线选股公式源码

    T1:=(REF(O,4)-REF(C,4))/REF(O,4)>=0.05; A:=HHV(C,3); B:=LLV(C,3); T2:=REF(A,1)<REF(H,4) && ...

  • Java高并发21-AQS在共享，独占场景下的源码介绍

    一.AQS--锁的底层支持 1.AQS是什么 AQS是AbstractQueuedSychronizer的简称,即抽象同步队列的简称,这是实现同步器的重要组件,是一个抽象类,虽然在实际工作中很烧用到它 ...

  • 「翔博精选指标」长线赚它几倍,长线公式（通达信公式 副图 源码 测试图）不加密没未来函数

    长线赚它几倍,长线公式 不加密没未来函数 长线买入,操作简单,赚几倍.适合新手或者上班族. EMA(L,30); EMA(L,200); 赚它几倍买:CROSS(EMA(L,30),EMA(L,200 ...