Loading...
墨滴

Liftoff

2021/06/12  阅读:48  主题:橙心

ArrayList源码阅读解析

调式环境及工具: OpenJDK8 , IntelliJ IDEA

1     ArrayList 简介

1.1  ArrayList的继承结构图

1.2  ArrayList属性

  private static final long serialVersionUID = 8683452581122892189L;//序列化版本字段

    private static final int DEFAULT_CAPACITY = 10//【默认的初始化容量为:10】

    private static final Object[] EMPTY_ELEMENTDATA = {};//【当初始化容器时指定初始化容量为0时】

   
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//【当初始化容器不指定容量时】

   
    transient Object[] elementData; //【ArraysList的数据缓冲区,用于存储数据,扩容的时候会重新创建赋值】

    private int size; //【记录ArrayList的实际元素个数,并非数组的长度】
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//个人认为是为了防止某些VM发生OutOfMemoryError,建议开发者最好把长度范围控制在这个范围当中

根据ArrayList字段的定义,看得出ArrayList的底层的数据结构是数组Object[] elementData ,官方对该数组最大长度建议是MAX_ARRAY_SIZE=Integer.MAX_VALUE-8(但是该数组的长度是可以扩容至Integer.MAX_VALUE的,后续源码会详细介绍)。

数组的优缺点(决定ArrayList使用场景的一个重要因素):
  • 优点: 索引检索效率高,支持随机访问
  • 缺点: 需连续的存储空间,增删效率低(总体来说)

2   ArrayList构造方法

2.1  ArrayList()

public ArrayList() {//【不指定初始化容量大小时,默认的初始化一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA】
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

2.2  ArrayList(Collection<? extends E> c)

 public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();//【当以一个Collection类型的集合作为参数时,会将参数转化为一个Object数组】
        if ((size = a.length) != 0) {//【当参数c的数据不为空,同时会对ArrayList的size属性进行赋值】
            if (c.getClass() == ArrayList.class{//【且对象字节码类型ArrayList.class】
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.【c的数据为空,初始化为:EMPTY_ELEMEN0TDATA】
            elementData = EMPTY_ELEMENTDATA;
        }
    }

其执行流程如图:


2.3  ArrayList(int initialCapacity)

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//【指定初始化容量大于0,按initialCapacity大小创建空数组并赋值给elementData】
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//【指定初始化容量为0时】
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

3   源码解析

3.1   添加元素 add(E e) & add(int index, E element)

3.1.1    add(E e)

 public boolean add(E e) {//添加元素到容器中
        ensureCapacityInternal(size + 1);  // Increments modCount!!【确保容量足够,会进行相应的扩容】
        elementData[size++] = e;
        return true;
    }

add(E e)方法内部首先调用了ensureCapacityInternal(size + 1)确保数组的容量能够容纳新添加进来的数据(扩容就是发生在这里)。一切准备就绪后,elementData[size++] = e进行数据添加,(size是数组实际元素的个数)。接下来我们一起来看下ensureCapacityInternal方法在添加元素前做了那些准备工作,直接上源码

  • ensureCapacityInternal(int minCapacity)
private void ensureCapacityInternal(int minCapacity) {//【此时的minCapacity是接下来容器实际存储的元素个数】
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

 //计算容器要求满足的最小容器的大小
 private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//【如果容器没指定容器初始化的大小】
            return Math.max(DEFAULT_CAPACITY, minCapacity);//【默认初始化的数组容量的大小为10】
        }
        return minCapacity;
    }


 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//【这个字段很重要,后面针对并发操作时着重讲】

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)//【判断是否需要扩容,判断依据:在确保数据能够完全存储的前提下,容器当前的容量是否足够】
            grow(minCapacity);//【扩容操作】
    }
  

ensureCapacityInternal(int minCapacity)方法中涉及到两个方法的调用calculateCapacity(Object[] elementData, int minCapacity)ensureExplicitCapacity(int minCapacity),这两个方法的作用是什么?

  • calculateCapacity(Object[] elementData, int minCapacity):参数elementData就是ArrayList底层存储数据的数组;minCapcity=size+1是当新添一个元素进来时,elementData数组要满足的最小的长度。elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA,这里是指定默认初始化容器容量的大小为DEFAULT_CAPACITY(前提是第一次调用add(...)方法,不然容器的大小还是0)。到这里已经明确知道,该方法的作用就是:计算elementData数组满足最小容量要求时数组长度。
  • ensureExplicitCapacity(int minCapacity):参数minCapcityelementData数组要满足最小容量要求的长度。重头戏来了if (minCapacity - elementData.length > 0),发现minCapacity与elementData数组当前的长度比较,言下之意就是当前数组elementData的容量是否满足最小容量要求? 满足:我就不调用grow(minCapacity)进行扩容; 不满足:果断调用grow(minCapacity)进行扩容 思考?

  • 扩容grow(minCapacity)
 /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//【1.5倍进行扩容】
        if (newCapacity - minCapacity < 0)//【扩容之后容器是否能够满足最小容量的要求?】
            newCapacity = minCapacity;//【不足以存下,就把确保能够存下的容量minCapacity赋值作为容器扩容后,容器的大小】
        if (newCapacity - MAX_ARRAY_SIZE > 0)//【数据量很大时,申请一个超大的容器】
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//【扩容后重新创建一个新的数组】
    }

扩容前要明白的三个问题:

  • 1 .扩容的触发机制是什么?(上面已经解释过,minCapacity>elementData.length会触发扩容)。
  • 2.扩容的具体是怎么实现的?(重点)
  • 3.可以无限制的扩容吗?如果不可以那么容器最大的容量时多少?

扩容的具体实现:

  • 默认的扩容大小是在原数组的基础上1.5倍扩容newCapacity = oldCapacity + (oldCapacity >> 1)。
  • 如果1.5倍扩容后,数组的大小还不满足minCapacity的最小要求,那么就把minCapacity的值作为扩容后容器的大小,newCapacity = minCapacity。(当然扩容后的容器数组大小是有限制的,所以扩容后数组的大小要满足一定的要求,也就是我们的第三个问题扩容的限制)
  • 确定扩容后容器的大小newCapacity,进行实际的扩容elementData=Arrays.copyOf(elementData, newCapacity)

可能有的同学会疑问,为什么是1.5倍扩容,不是2倍,也不是minCapacity+1进行扩容???
关于这个问题我个人搜集一些比较有论证力的资料,最后我得出了自己的结论: 第一点考虑到空间利用率问题和避免过度扩容导致内存浪费,所以采用1.5的扩容因子可以提高空间利用率。第二点是1.5倍不算太小,可以避免频繁的扩容,虽然1.5倍扩容后可能有部分空间没用上,但是采用的是一种空间换时间思想,提高效率。(相关参考资料: C++ STL 中 vector 内存用尽后, 为什么每次是 2 倍的增长, 而不是 3 倍或其他值?

  • Arrays.copyOf(elementData, newCapacity)实现扩容
 //ArrayList调用的就是这个方法
 public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }
//被 copyOf(T[] original, int newLength)内部调用
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
          //创建一个新的数组这个数组就是扩容后要返回的新数组
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength)
;
          //把原来数组original的元素拷贝至新数组中,并且返回新数组copy
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

这两个方法都是Arrays类的静态方法,最重要的一步是内部调用System.arraycopy(Object src, int srcPos,Object dest, int destPos,int length)这是一个本地方法,该方法就是数组扩容创建新数组后,进行数组元素的复制核心方法,涉及到数组复制拷贝的原理和算法。要去看hotspot源码实现,现在还在研究当中,这个方法被很多jdk源码使用,后续的笔记会通过阅读hotspot的实现来单独的解读下这个方法!!!(注意:该方法不创建新的数组(临时数组倒是会创建),只是进行数组元素的复制,Arrays.copyOf(...)会创建新的数组)

  /* * @param      src      the source array.
     * @param      srcPos   starting position in the source array.
     * @param      dest     the destination array.
     * @param      destPos  starting position in the destination data.
     * @param      length   the number of array elements to be copied.
     */

    public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);
  • src : 源数组
  • srcPos : 源数组起始位置
  • dest: 目标数组
  • destPos:目标数组的起始位置
  • length: 要复制数组元素的个数

扩容的限制的问题(与其说限制不如说是确保能够正常添加元素防止OOM):

  • newCapacity>MAX_ARRAY_SIZE ? 判断新申请的数组容量是否大于数组最大的容量,我们就来讨论大于的情况,它会执行hugeCapacity(int minCapacity)方法
 private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0// overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
  • 当minCapacity<0也就是溢出的情况,直接OOM
  • (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE这个三目运算在判断最小容量minCapacity是否大于ArrayList的最大容量MAX_ARRAY_SIZE。大于就返回Integer.MAX_VALUE,小于就返回MAX_ARRAY_SIZE=Integer.MAX_VALUE-8,这个都不难理解。那么问题来了,一开始就定义说明数组的最大的容量是MAX_ARRAY_SIZE=Integer_MAX_VALUE-8,为什么这里却可以返回数组长度(容量)等于Integer.MAX_VALUE,也就是说数组的最大长度是可以扩容至Integer.MAX_VALUE,这不是前后矛盾吗?带着疑问去看了下MAX_ARRAY_SIZE的注释
  /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */

     //一些VM在数组中要保留header words,尝试分配更大的容量会导致OOM
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

注释意思是说之所以定义ArrayList的最大的长度为MAX_ARRAY_SIZE的原因是:有一些VM需要保留数组的header words所以设置为Integer.MAX_VALUE-8,防止OOM的发生。这时候我们需要知道header words是什么了,那么就来看下对象的内存布局吧(JDK8)。

  • 对象内存布局(工具依赖包:openJDK jol)
        <dependency>
            <groupId>org.openjdk.jol</groupId>
            <artifactId>jol-core</artifactId>
            <version>0.16</version>
            <scope>provided</scope>
        </dependency>

在提出对象内存布局之前,先给出对象内存布局的组成:对象头(Header由mark word和class pointer组成),实例数据(Instace Data)和对齐填充(Padding)这三个部分组成。具体的相关概念可以参考《深入理解Java虚拟机》这本书对象内存布局章节。

  • 通过实际代码来看下对象锁的内存布局,把下面的代码运行起来
/**
 * @author HCW
 * @className ObjectLayout
 * @data 2021/5/31 12:54
 */

public class ObjectLayout {
    @Test
    public void viewObjectLayout(){
        // 输出虚拟机与对象内存布局相关的信息
        System.out.println(VM.current().details());
        MyObject myObject = new MyObject("HCW");
        Object[] objects = new Object[5];
        //普通对象的内存布局
        ClassLayout ordinaryObject = ClassLayout.parseInstance(myObject);
        //数组对象内存布局
        ClassLayout arrayObject = ClassLayout.parseInstance(objects);
        
        System.out.println(ordinaryObject.toPrintable());
        System.out.println(ordinaryObject.toPrintable());

    }

}
class MyObject{
    private String name;

    public MyObject(String name) {
        this.name = name;
    }
    public MyObject() {
    }
}

  • 运行结果如下:

    1 . 普通对象的内布局 图中的运行结果:红框表示对象头的mark word 占用的8bytes,绿框class pointer占用4bytes,黄框表示instace Data实例数据占用4bytes,对象有header占8+4=12bytes,整个对象总共8+4+4=16bytes,刚好16bytes是8的整数倍不需要对齐填充padding。这是一个普通对象的内存布局,当然根据对象的实例数据不同占用的内存的不用.(感兴趣的小伙伴可以按照上面的代码自己调式不同的对象的内存布局及内存占用情况)

    2 . 数组对象的内布局 图中的运行结果:红框和绿框与普通对象的表示都是一样的,紫框表示的是数组的长度array length占4bytes,所以对数组对象来说,它的对象头占16bytes;橙框表示数组元素所占的内存一个Object元素占4bytes,数组长度=5,所以实例数据instace Data占用5*4=20bytes;黄框是对齐填充padding也就是不填充之前占用36bytes不是8的倍数,要填冲至8的倍数,那就是加4bytes,填充至40bytes。所以整个对象占用16(对象头)+20(实例数据)+4(对齐填充)=40bytes。
  • 回到扩容数组最大长度的问题,我们根据数组对象在hotspot虚拟机下的内存布局和MAX_ARRAY_SIZE的官方注释大概明白了,其实elementData数组的最大容量可以扩容至Integer.MAX_VALUE的,只不过部分虚拟机可能会因为扩容大于MAX_ARRAY_SIZE会OOM,因为需要需要部分内存(4bytes)保留数组的长度信息。所以MAX_ARRAY_SIZE=Integer.MAX_VALUE-8跟这个有直接联系。

3.1.2    add(int index, E element)

添加元素到指定的索引index的位置,先上源码吧


    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */

    public void add(int index, E element) {
        rangeCheckForAdd(index);//检查插入的index位置是否越界

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//插入后要对elementData数组的数据重新整理,index后的数据都要往后移一个位置,会重新得到一个新的数组
        elementData[index] = element;//再把当前的数据插入到指定的位置
        size++;
    }

其实发现它和add(E e)方法相差不大,rangeCheckForAdd(index)这个方法就是检查index是否越界的;ensureCapacityInternal(size + 1)与add(E e)都是一样的无非就是计算最小容量和扩容相关的操作不详细介绍了。 System.arraycopy(elementData, index, elementData, index + 1,size - index)这一步是关键,在index插入元素之前,我们要对原来数组的元素进行移动,为index位置腾出空间,来了解下是怎么实现的。

  @Test
    public void addElementInIndex(){
        //源数组,0表示还未被使用的空间位置,其他数字表示已被使用的空间位置
        int[]nums={2,3,4,5,6,7,8,0,0,0};
        //我们要在索引为1的位置上,插入元素,在此之前要对索引为1及后面的元素在源数组的基础上进行移动
         //此时index=1,elementData=nums,size=7,也就是数组被使用的空间位置个数
        System.arraycopy(nums,1,nums,1+1,7-1);
        System.out.println(Arrays.toString(nums));
        //对index=1的位置赋值
        nums[1]=10;
        System.out.println(Arrays.toString(nums));
    }

运行结果:
[2, 3, 3, 4, 5, 6, 7, 8, 0, 0] //调用System.arraycopy(...)方法后的执行结果
[2, 10, 3, 4, 5, 6, 7, 8, 0, 0] //在index=1索引处插入元素后的运行结果
Process finished with exit code 0
解释:
int[]nums={2,3,4,5,6,7,8,0,0,0}是源数组,0表示未被使用的位置空间,也就是我们扩容那些没被使用的位置。System.arraycopy(nums , 1 , nums , 2 , 7-1),这段代码的意思是以nums为源数组,nums也为目标数组的基础上进行数组元素的复制,其真正的含义是: 从源数组索引index=1的位置开始复制,复制的长度为size-index=7-1(7为数组有效空间位置,1是索引开始的位置)。把这些元素复制到目标数组从index+1开始的对应位置。通过一张图来理解下。


  • 总结
    至此添加元素的一切准备工作,就完成了(包括计算数组的最小容量,数组扩容的问题)。接下来就是向elementData数组中添加元素,数组元素size++,添加元素的整个过程就结束。在add(...)添加元素的过程中,我们明白了很多相关的原理,比如:扩容机制,扩容的具体实现,再通过一张流程图来回顾我们的add(...)方法的工作流程吧。

3.2     删除元素 remove(int index) & remove(Object object) & removeAll(Collection<?> c)

3.2.1     remove(int index)

 public E remove(int index) {
        rangeCheck(index);
        modCount++;//对数据的操作次数
        E oldValue = elementData(index);//返回要删除index下表对应的数据
        int numMoved = size - index - 1;//删除后要移动的元素个数
        if (numMoved > 0)//如果删除的元素不是最后的一个有效元素(有效元素:size长度中的数组元素,大于size的都是还没有被真正利用的空间)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);//向左移动元素
        elementData[--size] = null// clear to let GC do its work
        return oldValue;
    }

该方法删除指定位置index的元素,来看下它做了那些处理工作。rangeCheck(index)检查index是否越界。elementData(index)返回index位置元素的值。 numMoved=size-index-1表示删除该元素后,要向左移动的元素个数。当numMoved>0,也就是表示删除的不是最后一个元素,就需要向左移动元素,System.arraycopy(elementData, index+1, elementData, index, numMoved)表示在源数组的基础上向左移动numMoved元素,移动的起始点为index+1,类似我上面画一张图可以更好的帮助理解。element[--size]=null,元素的个数减一。最终返回删除元素的值。

移动元素原理示意图:

3.2.2     remove(Object )

从ArrayList列表中删除第一次出现的指定元素,也就是遍历列表删除第一次出现的元素。并且返回删除成功或失败的布尔值。

 public boolean remove(Object o) {
        if (o == null) {//删除的是一个空对象
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {//在size的范围内找到第一个为null的元素
                    fastRemove(index);//根据索引位置删除
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {//在size的范围内遍历寻找第一个为o的对象 
                    fastRemove(index);//删除第一个对应的元素,根据索引位置删除
                    return true;
                }
        }
        return false;
    }

该方法内部处理逻辑是把对象进行两个分支处理,当o==null时,在size的范围内遍历elementData数组找到第一个为null的元素对应的索引index,fastRemove(index)进行删除。当o!=null时,同样是在size的范围内遍历elementData数组,找到第一个为o的对象的索引index,fastRemove(index)进行删除。可想而知,从头到尾最重要的是fastRemove(int index)方法。

  • fastRemove(int index)
 /*
    * Private remove method that skips bounds checking and does not
    * return the value removed.
    */

   private void fastRemove(int index) {//不需要检查边界,因为他都是在size的有效范围内删除对应的数据,不存在越界情况
       modCount++;
       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       elementData[--size] = null// clear to let GC do its work
   }

其实不难发现其实fastRemove(int index)的内部处理逻辑和我们上面讲的remove(int index)基本上没什么区别。只不过fastRemove(int index)不需要index越界检查,因为该方法是一个内部的私有方法,index参数传进来都是在有效的范围内的。同时它也不需要任何的返回值。具体的内部删除逻辑可以参考remove(int index)的处理逻辑。

3.2.3     removeAll(Collection<?> c)

public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);//检查指定的集合c是否为空
        return batchRemove(c, false);//批量删除
    }
    
    public static <T> requireNonNull(T obj) {
        if (obj == null)
            throw new NullPointerException();
        return obj;
    }

该方法的目的是从ArrayList列表中删除包含在指定集合c中的所有元素。requireNonNull(c)对集合c是否为空的检查,为空就抛出NullPointerException()异常。batchRemove(c,false)执行批量删除的操作,具体逻辑如下:

private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;//读写指针
        boolean modified = false//修改标志
        try {
            for (; r < size; r++)//获取c不包含的元素,complement=false
                if (c.contains(elementData[r]) == complement)//这里可能发生异常
                    elementData[w++] = elementData[r];//把要保留的元素放在elementData数组前面位置
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {//当c.contains(Object)发生异常导致 r!=size
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);//r及之后的元素不删除,直接追加到w后面
                w += size - r;//w指针偏移,为删除做准备
            }
            if (w != size) {//当w!=size说明有元素需要删除
                                    
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;//把要删除的元素的位置致为null
                modCount += size - w;//对元素的操作次数
                size = w;//元素的个数
                modified = true;//表示已经发生了修改
            }
        }
        return modified;
    }

该方法是以传入的参数Collection c作为删除的参照容器,当complement=false表示删除在c中出现过的元素,当complement=true表示保留在c中出现过的元素。我们这次讲的removeAll(...)所以complement=false; 在 batchRemove(Collection<?> c, boolean complement)中我们发现一些临时变量:

  • r=0 , w=0 :  r表示遍历数组的的读指针,w表示遍历数组的写指针,稍后通过画图来理解。
  • modified=false :  表示修改标志,也就是数组的数据有没有被改动过,默认为false。
  • elementData : 批量删除的源数据数组

  • batchRemove(Collection<?> c, boolean complement)内部逻辑解析
for (; r < size; r++)//获取c不包含的元素,complement=false
               if (c.contains(elementData[r]) == complement)//这里可能发生异常
                   elementData[w++] = elementData[r];//把要保留的元素放在elementData数组前面位置

前提:complement=false

for循环遍历源数组elementData的所有元素(size范围内);c.contains(elementData[r])==complement每次去判断参考集合c中是否包含源数组elementData[r]当前元素。如果包含elmentData[r],表示该元素是删除的对象之一,不用再写回源数组,继续遍历elementData的下一个元素,r++。如果不包含elementData[r],表示该元素不是删除的对象之一,elementData[w++] = elementData[r]把当前元素写回源数组中w索引对应的位置,也就是相当于把要保留的元素放到数组的前面位置去,w++。直至循环结束或者抛出异常。
原理图: for循环的结束有两种可能:r>=size或者c.conatins(Object)抛出异常,但是最终都会执行finally子句,来看下finally中做了什么。

 if (r != size) {//当c.contains(Object)发生异常导致 r!=size
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);//r及之后的元素不删除,直接追加到w后面
                w += size - r;//w指针偏移,为删除做准备
            }

r!=size,还没遍历完elementData就发生异常导致r<size,内部调用System.arraycopy(elementData, r,elementData, w,size - r)进行截断。根据传入的参数可知,从r到size-1的size-r个元素被截断放置到以w索引开始的size-r个位置,由于重新放置了size-r个元素到elementData中,所以w右移size-r个位置。 来到最后一步,也就是真正删除元素的一步,最关键的就是w了。(size对elementData说你缺w吗?这里水太深,你把握不住。既然把握不住,我们就来探个究竟吧。)

  if (w != size) {//当w!=size说明有元素需要删除
                                    
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;//把要删除的元素的位置致为null
                modCount += size - w;//对元素的操作次数
                size = w;//元素的个数
                modified = true;//表示已经发生了修改
            }
        }

if(w!=size)真正的含义是:是否有需要删除的元素,之前我们注释说w是写指针。如果w==size,即源数组elementData的数据都是需要保留的,也就是elementData的所有元素都没在c中出现过,所以都写回了源数组使得w==size,就没有删除的必要了。如果w!=size,说明有元素需要需要删除,有size-w个元素需要删除。以w为开始索引,开始遍历elementData数组,并且把每个遍历的位置的数据置空,表示删除这个数据。所有需要删除的数据都删除后,修改modCount+=size-w(modCount后面会单独讲,他的重要性);size=w,表示剩下w个元素。

3.3     修改更新元素 set(int index, E element)

    3.3.1 set(int index, E element)

  /**
   * Replaces the element at the specified position in this list with
   * the specified element.
   *
   * @param index index of the element to replace
   * @param element element to be stored at the specified position
   * @return the element previously at the specified position
   * @throws IndexOutOfBoundsException {@inheritDoc}
   */

  public E set(int index, E element) {
      rangeCheck(index);//检查index是否在有效的范围内

      E oldValue = elementData(index);//把旧数据拿出来,再赋值新数据,并且把旧数据返回
      elementData[index] = element;
      return oldValue;
  }

通过源代码,发现用指定的元素替换ArrayList中指定位置的元素,其内部逻辑很简单对吧。rangeCheck(index)索引越界检查;elementData(index)先把旧数据从源数组elementData中拿出来作为返回值;elementData[index] = element更新index位置的值。比较简单不过多的赘述。

3.4     查找元素 get(int index)

   3.4.1    get(int index)

查找指定索引为index的元素

 /**
   * Returns the element at the specified position in this list.
   *
   * @param  index index of the element to return
   * @return the element at the specified position in this list
   * @throws IndexOutOfBoundsException {@inheritDoc}
   */

  public E get(int index) {
      rangeCheck(index);//检查index是否在数组的有效范围内
      return elementData(index);
  }

rangeCheck(inex)检查index是否越界;elementData(index)返回指定位置index的元素。

4   ArrayList常见问题

4.1  迭代器遍历操作列表,并发修改异常问题ConcurrentModificationException

  /**
 * @author HCW
 * @className TestArraysList
 * @data 2021/5/18 17:59
 */

public class TestArraysList {
    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<>();
      for(int i=1;i<=10;i++){
          list.add(i);
      }
       //1.迭代器遍历删除指定的元素
        Iterator<Integer> iterator = list.iterator();
        while(iterator.hasNext()){
            Integer num = iterator.next();
            if(num.equals(8)){
                list.remove(num);
            }
        }
         //2.增强for循环遍历删除指定元素
        for (Integer num : list) {
            if(num.equals(8)){
                list.remove(num);
            }
        }
    }
}

运行结果:
发现两种删除的方法都会发生并发修改异常ConcurrentModificationException,查明原因之前我们先对ArrayList的迭代器Iterator来进行个简单的了解。

  public Iterator<E> iterator() {
        return new Itr();//获取其迭代器
    }

ArrayList通过调用该方法,获取其迭代器。内部 return new Itr(),再跟进去发现Itr是ArrayList的一个内部类,Itr实现Iterator接口。

  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;//【是否还有元素要遍历就看下一个遍历的元素的索引是否等于数组的长度】
      }

      @SuppressWarnings("unchecked")
      public E next() {
          checkForComodification();//【】
          int i = cursor;
          if (i >= size)
              throw new NoSuchElementException();
          Object[] elementData = ArrayList.this.elementData;
          if (i >= elementData.length)//【并发操作异常,因为在其之前有数据被删除导致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();
          }
      }

      @Override
      @SuppressWarnings("unchecked")
      public void forEachRemaining(Consumer<? super E> consumer) {
          Objects.requireNonNull(consumer);
          final int size = ArrayList.this.size;
          int i = cursor;
          if (i >= size) {
              return;
          }
          final Object[] elementData = ArrayList.this.elementData;
          if (i >= elementData.length) {
              throw new ConcurrentModificationException();
          }
          while (i != size && modCount == expectedModCount) {
              consumer.accept((E) elementData[i++]);
          }
          // update once at end of iteration to reduce heap write traffic
          cursor = i;
          lastRet = i - 1;
          checkForComodification();
      }

      final void checkForComodification() {
          if (modCount != expectedModCount)//【检查对数据的实际操作次数modCount是否等于预期的操作次数expectedModCount】
              throw new ConcurrentModificationException();
      }
  }
  • cursor:  返回即将遍历的元素的索引。
  • lastRet:  返回上一个刚遍历过的元素的索引,没有的话就返回-1,lastRet=corsor-1。
  • expectedModCount = modCount:  预期的操作次数,发现expectedModCount默认通过modCount赋值,这个modCount就是我们讲的在remove(...)和add(...)多次出现modCount成员变量。再跟进去发现modCount变量其实继承自AbstrctList,来看下对modCount的注解。
/**
   * The number of times this list has been <i>structurally modified</i>.
   * Structural modifications are those that change the size of the
   * list, or otherwise perturb it in such a fashion that iterations in
   * progress may yield incorrect results.
   *
   * <p>This field is used by the iterator and list iterator implementation
   * returned by the {@code iterator} and {@code listIterator} methods.
   * If the value of this field changes unexpectedly, the iterator (or list
   * iterator) will throw a {@code ConcurrentModificationException} in
   * response to the {@code next}, {@code remove}, {@code previous},
   * {@code set} or {@code add} operations.  This provides
   * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
   * the face of concurrent modification during iteration.
   *
   * <p><b>Use of this field by subclasses is optional.</b> If a subclass
   * wishes to provide fail-fast iterators (and list iterators), then it
   * merely has to increment this field in its {@code add(int, E)} and
   * {@code remove(int)} methods (and any other methods that it overrides
   * that result in structural modifications to the list).  A single call to
   * {@code add(int, E)} or {@code remove(int)} must add no more than
   * one to this field, or the iterators (and list iterators) will throw
   * bogus {@code ConcurrentModificationExceptions}.  If an implementation
   * does not wish to provide fail-fast iterators, this field may be
   * ignored.
   */

  protected transient int modCount = 0;

注解对modCount的字段描述大致意思:modCount记录的是列表(ArrayList)被结构修改的次数,结构修改是指修改列表的大小,或者以一种迭代的方式扰乱列表。 modCount由iterator()方法和listIterator()方法返回的迭代器实现使用,如果modCount被意外修改将会抛出ConcurrentModificationException使用modCount实现fail-fast快速失败机制(一种错误检测机制),当使用迭代器迭代遍历列表,列表的结构发生改变就可能触发快速失败机制,抛出ConcurrentModificationException。所以说我们终于明白,为什么之前我们用迭代器遍历列表同时删除指定元素时,抛出ConcurrentModificationException了。有的同学可能会疑问,第一个用迭代器遍历删除抛出ConcurrentModificationException我可以理解,第二个使用增强for循环为什么还抛出ConcurrentModificationException,带着个问题我们去看了下相关代码的字节码class文件。
发现在字节码当中,增强for循环遍历其实也是使用了iterator迭代器进行遍历列表的,所以为什么增强for循环会触发快速失败机制的问题也就不难理解了。既然是fail-fast触发导致抛出ConcurrentModificationException,那么什么时候触发fail-fast呢?带着这问题我们继续来看内部类Itr的源码。

 public boolean hasNext() {
          return cursor != size;//【是否还有元素要遍历,就看下一个遍历的元素的索引是否等于数组的长度】
      }

hasNext()返回的是一个布尔值,其作用是用来判断是否还有元素需要遍历,cursor代表的是下一个即将遍历的元素的索引,如果说cursor=size也就代表遍历到末尾了。

 public E next() {
          checkForComodification();//【检查modCount是否等于expectedModcount】
          int i = cursor;
          if (i >= size)//多线程操作的情况下会出现此情况
              throw new NoSuchElementException();
          Object[] elementData = ArrayList.this.elementData;
          if (i >= elementData.length)//【多线程操作的情况下会出现此情况】
              throw new ConcurrentModificationException();
          cursor = i + 1;//【遍历的索引往后移一个位置,指向下一个要遍历的元素的索引】
          return (E) elementData[lastRet = i];//【把遍历到的数据返回】
      }
  //fail-fast的实现,检查modCount是否等于expectedModCunt
  final void checkForComodification() {
          if (modCount != expectedModCount)//【检查对数据的实际操作次数modCount是否等于预期的操作次数expectedModCount】
              throw new ConcurrentModificationException();
      }

在next()内部第一步是先调用checkForComodification()。看了checkForComodification()的源码,发现它是单线程情况下抛出ConcurrentModificationException的关键,也就是fail-fast的具体实现,通过比较modCount是否等于expectedModCount来决定是否抛出ConcurrentModificationException。既然是通过比较modCount和expectedModCount是否相等来决定抛出异常,但是除了获取迭代器对象时expectedModCount=modCount进行赋值,在之后的hasNext()和next()方法都没有对expectedModCount和modCount进行赋值操作,怎么就在迭代遍历删除的过程中就导致modCount!=expectedModCount而抛出ConcurrentModificationException呢?回想起当时每次讲到add(...)和remove(...),add(...)和remove(...)方法中都有对modCount操作的逻辑,每当删除减少一个元素,size--同时modCount++。当modCount++时,modCount的值发生了变化,但是没有expectedModCount=modCount的操作逻辑(expectedModCount是内部类Itr的成员变量),此时modCount>expectedModCount的。导致下次迭代器遍历列表,在next()执行 checkForComodification()方法时modCount!=expectedModCount,直接抛出ConcurrentModificationException。原来是我们在迭代遍历列表删除元素时,调用ArrayList的remove(...)成员方法,而该方法涉及到modCount变量的赋值操作,但是没有对expectedModCount=modCount的赋值操作。导致下次迭代遍历的时expectedModCount!=modCount,而直接抛出ConcurrentModificationException。

解决单线程情况下迭代遍历列表删除指定元素的ConcurrentModificationException问题

既然我们知道了迭代遍历删除指定元素抛出ConcurrentModificationException的具体原因了,那么我们怎么去解决这个问题呢?(也就是每次在迭代器遍历过程中,我们如果向列表中增添或删除元素,我们要执行expectedModCount=modCount的赋值操作,保证下一次遍历时执行checkForComodification()时expectedModCount=modCount)

  • 第一种解决方法,普通for循环(不推荐使用)

抛出异常的原因是我们在使用迭代器遍历列表进行删除和增添元素,每次遍历都要执行checkForComodification()检查modCount是否等于expectedModCount。那么我们可不可以不使用迭代器去遍历列表,就可以避免每次去执行checkForComodification()去检查modCount是否等于expectedModCount使用普通的for循环遍历列表,在循环过程中增添或删除元素。

 for(int i=0;i<list.size();i++){
           if(i==2){
               //list.add(20);
               list.remove(3);
               i--;
           }
       }
                                
  • 第二种解决方法,迭代器Itr的remove()方法
  public void remove() {
           if (lastRet < 0)//多线程执行情况下会发生此情况
               throw new IllegalStateException();
           checkForComodification();//检查modCount!=expectedCount?

           try {
               ArrayList.this.remove(lastRet);//调用ArrayList的remove(int index)成员方法
               cursor = lastRet;//由于lastRet指向的元素被删除,导致后面的元素都向前移动了一个位置
               lastRet = -1;//lastRet指向的元素被删除,所以他没有指向的了。所以赋值-1
               expectedModCount = modCount;//这就可以避免ConcurrentModificationException
           } catch (IndexOutOfBoundsException ex) {
               throw new ConcurrentModificationException();
           }
       }

在Itr的remove()方法中,调用了ArrayList的remove(int index)成员方法删除lastRet索引对应的元素,该方法会导致modCount的值发生变化。

  • cursor=lastRet和lastRet=-1这两个可能不好理解。cursor=lastRet是由于lastRet指向的元素被删除,导致cursor及后面的元素都向前移动一个位置,而且lastRet=cursor-1,所以cursor的索引变成了cursor=lastRet。lastRet=-1是因为,lastRet索引指向的元素被删除了,所以说lastRet=-1,表示没有指向的了。
  • expectedModCount = modCount这是为什么Itr的remove()单线程情况下不会发生ConcurrentModificationException的关键核心,因为在ArrayList的remove(int index)改变了modCount的值,但是在这里又重新对expectedModCount赋值,使得expectedModCount等于modCount,在下一次迭代遍历的时候,就不会触发fail-fast机制。

具体用法如下:

  ArrayList<Integer> list = new ArrayList<>();
    for(int i=1;i<=10;i++){
        list.add(i);
    }
 //1.迭代器遍历删除指定的元素
      Iterator<Integer> iterator = list.iterator();
      while(iterator.hasNext()){
          Integer num = iterator.next();
          if(num.equals(7)){
              //Itr的remove()方法                                    
              iterator.remove();
          }
      }
  • 第三种解决方法,迭代器ListItr的add(E e)方法

在迭代遍历的时候,使用Itr的remove()方法删除一个元素单线程的情况下是不出触发fail-fast机制的。但是有没有在使用迭代器迭代遍历的时候增添元素也不会触发fail-fast机制呢?接下来介绍另一个迭代器ListItr,先来看下ListItr的部分源码吧。

  private class ListItr extends Itr implements ListIterator<E{
        ListItr(int index) {
            super();
            cursor = index;
        }
        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

ListItr是ArrayList的一个内部类,它继承Itr类同时又实现了ListIterator接口。对于remove()方法继承自Itr在此不重复介绍,也说明这个迭代器在迭代遍历时不仅可以删除元素还可以增添元素。仔细看了下add(E e)源码,发现和remov()的逻辑很类似,具体看下它的内部是实现的。 在其内部通过调用ArrayList的add(int index,E e)方法进行元素的添加。index=cursor,也就是说在lastRet后面添加元素,因为lastRet代表的是刚遍历过的元素的索引(lastRet=cursor-1)。添加完成后cursor指向的元素及后面的元素的都向后移动一个位置,所以cursor+1,最后expectedModCount = modCount这是避免fail-fast机制触发的关键。

具体用法如下:


   ArrayList<Integer> list = new ArrayList<>();
    for(int i=1;i<=10;i++){
        list.add(i);
    }
                                                    
 ListIterator<Integer> listIterator = list.listIterator();
      while(listIterator.hasNext()){
          Integer num = listIterator.next();
          if(num.equals(7)){
              //在7之后添加元素11
              listIterator.add(11);
          }
      }

解决多线程情况下ConcurrentModificationException问题

在此之前,要提出的一个观点是ArrayList并不是线程安全的。
线程安全概念:当多个线程访问某一个类(对象或方法)时,对象对应的公共数据区始终都能表现正确,那么这个类(对象或方法)就是线程安全的。下面通过代码去证明ArrayList不是线程安全的。

class ArrayListConcurrentModification {
 private static ArrayList<Integer> list=new ArrayList<>();
 public static void main(String[] args) throws InterruptedException {
      //启动多个线程对list列表进行增添元素操作
     for(int i=0;i<10;i++){
         new Thread(new Runnable() {
             @Override
             public void run() {
                 work();
             }
         },"Thred"+i).start();
     }
     TimeUnit.SECONDS.sleep(5);
     System.out.println("列表的大小:"+list.size());
 }

 public static  void work(){
     for(int i=0;i<1000;i++){
         list.add(i+1);
     }
 }
}

运行结果

如果ArrayList是线程安全的,在并发执行的情况下,它能够保证数据的正确性。也就是说按照上面的执行列表的大小应该是10000,但是执行的最终结果是9881,由此证明了 ArrayList并不是线程安全的。

我们来看下Itr的remove()方法,在多线程的情况下是否依然能够保证不出现并发修改异常,我们来看段代码吧!!!

    class ArrayListConcurrentModification {
    private static ArrayList<Integer> list=new ArrayList<>();
    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i <500 ; i++) {
            list.add(i+1);
        }
        //A 线程去遍历列表的每一个元素
        Thread A = new Thread(new Runnable() {
            @Override
            public void run() {
             Iterator<Integer> iterator = list.iterator();
                while (iterator.hasNext()) {
                    Integer num = iterator.next();
                    System.out.println(num);
                }
            }
        });
          //B线程去删除指定的元素
        Thread B = new Thread(new Runnable() {
            @Override
            public void run() {
               Iterator<Integer> iterator = list.iterator();
                while (iterator.hasNext()) {
                    Integer num = iterator.next();
                   if(num%8==0){
                       iterator.remove();
                   }
                }
            }
        });
        A.start();
        B.start();
        TimeUnit.SECONDS.sleep(2);
    }
}

启动两个线程A和B,A线程通过迭代器遍历列表的所有的元素,B线程通过迭代器遍历删除指定的元素。
运行的结果是:出现了ConcurrentModificationException。
原因是:1. ArrayList并非线程安全,导致在多线程的环境下对modCount值的修改是混乱的。2. A线程与B线程获取的不是同一个迭代器对象,对expectedModCount值是线程私有的,但是对于modCount是两个线程共享的。当modCount修改时,对于A线程的expectedmodCount它是不会发生改变的,因为它只是遍历列表,不会去改变modCount的值,B线程删除会改变modCount的值,导致A线程再去遍历的时候expectedModCount已经不等于modCount抛出ConcurrentModificationException。

  • 第一种解决方法,加入synchronized同步锁
    class ArrayListConcurrentModification {
    private static ArrayList<Integer> list=new ArrayList<>();
    public static void main(String[] args) {
        for (int i = 0; i <20; i++) {
            list.add(i+1);
        }
        //A 线程去遍历列表的每一个元素
        Thread A = new Thread(new Runnable() {
            @Override
            public void run() {
               synchronized (list){
                   Iterator<Integer> iterator = list.iterator();
                   while(iterator.hasNext()){
                       Integer num = iterator.next();
                       System.out.println(num);
                       try {
                           TimeUnit.SECONDS.sleep(1);
                       } catch (InterruptedException e) {
                           e.printStackTrace();
                       }
                   }
               }
             }});
          //B线程去删除指定的元素
        Thread B = new Thread(new Runnable() {
            @Override
            public void run() {            
                    synchronized (list){
                        Iterator<Integer> iterator = list.iterator();
                        while (iterator.hasNext()){
                            Integer num = iterator.next();
                            if(num%8==0){
                                iterator.remove();
                            }
                        }
                    }
                }

        });
        B.start();
        A.start();
    }
}

这种方法是通过synchronized同步锁把两个线程执行的顺序变为串行执行。只有当一个线程执行完成才轮到另一个线程执行。这样就能保证一个线程执行完后对modCount值的修改会被另一个刚获得锁的线程通过获取迭代器,来获得最新的modCount值,使每个线程的expectedmodCount等于modCount值,避免ConcurrentModificationException。这样虽然能避免,但是效率很低。

  • 第二种解决方法,CopyOnWriteArrayList

CopyOnWriteArrayList是并发容器,它是ArrayList线程安全的变体。(在这里不详细解说,后续会有关于CopyOnWriteArrayList的笔记。)

    class ArrayListConcurrentModification {
    public static void main(String[] args) throws InterruptedException {
     CopyOnWriteArrayList<Integer> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
        for (int i = 0; i <100; i++) {
            copyOnWriteArrayList.add(i+1);
        }
        //A 线程去遍历列表的每一个元素
        Thread A = new Thread(new Runnable() {
            @Override
            public void run() {
               for (int i = 0; i <copyOnWriteArrayList.size() ; i++) {
                    System.out.println(copyOnWriteArrayList.get(i));
                    try {
                        TimeUnit.SECONDS.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
             }});
          //B线程去删除指定的元素
        Thread B = new Thread(new Runnable() {
            @Override
            public void run() {
                    for(int i=0;i<copyOnWriteArrayList.size();i++){
                        if(copyOnWriteArrayList.get(i)%8==0){
                             copyOnWriteArrayList.remove(copyOnWriteArrayList.get(i));
                        }
                    }
                }
        });
        B.start();
        A.start();
    }
}
    
  • 知识点补充

看下面一段代码,你认为单线程情况下会出现ConcurrentModificationException吗?

 public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    for(int i=1;i<=10;i++){
        list.add(i);
    }
      //1.迭代器遍历删除指定的元素
      Iterator<Integer> iterator = list.iterator();
      while(iterator.hasNext()){
          Integer num = iterator.next();
           //删除倒数第二个元素                
          if(num.equals(9)){
              list.remove(num);
          }
      }
  }

迭代器遍历列表,删除倒数第二个元素的时候用的是ArrayList的remove(E e)方法,果断想到的是肯定抛出ConcurrentModificationException异常,但是运行结果并非如此,大家可以试着把上面的代码运行一遍,它是可以正常运行的。
这就很奇怪了,与我们之前的结论完全不一样,明明是调用ArrayList的remove(E e)方法该方法只改变modCount的值,但是又不对expectedModCount重新赋值。下一次遍历时,执行快速失败机制检测方法checkForComodification()应该是直接抛出异常的呀。
带着这个疑问,再次去仔细看了next()和hasNext()源码

  public boolean hasNext() {
          return cursor != size;//【是否还有元素要遍历就看下一个遍历的元素的索引是否等于数组的长度】
      }

      @SuppressWarnings("unchecked")
      public E next() {
          checkForComodification();//【】
          int i = cursor;
          if (i >= size)
              throw new NoSuchElementException();
          Object[] elementData = ArrayList.this.elementData;
          if (i >= elementData.length)//【并发操作异常,因为在其之前有数据被删除导致i>=elementData.length】
              throw new ConcurrentModificationException();
          cursor = i + 1;//【遍历的索引往后移一个位置,指向下一个要遍历的元素的索引】
          return (E) elementData[lastRet = i];//【把遍历到的数据返回】
      }

我们删除的是列表的倒数第二个元素,当我们执行next()方法遍历至倒数第二个元素的时,lastRet指向的倒数第二个元素的索引,cursor指向最后一个元素的索引也就是size-1。
随后调用ArrayList的remove(E e)方法删除lastRet指向的倒数第二个元素,删除完后modCount++,列表的size--。
此时的size刚好等于cursor,当我们再进行下次遍历执行hasNext()方法时size等于cursor返回的是false,导致还没进入next()进行错误检测,已经退出迭代遍历了,所以也就不会出现ConcurrentModificationException。

Liftoff

2021/06/12  阅读:48  主题:橙心

作者介绍

Liftoff