欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ArrayList源码万字解析!透彻易懂!

程序员文章站 2022-05-23 14:16:18
...

此文章转载于: 且听_风吟
原文链接:https://blog.csdn.net/qq_26803795/article/details/106243345

写在前面:我是「且听风吟」,目前是某上市游戏公司的大数据开发工程师,热爱大数据开源技术,喜欢分享自己的所学所悟,现阶段正在从头梳理大数据体系的知识,以后将会把时间重点放在Spark和Flink上面。

如果你也对大数据感兴趣,希望在这个行业一展拳脚。欢迎关注我,我们一起努力,一起学习。博客地址:https://ropledata.blog.csdn.net

博客的名字来源于:且听风吟,静待花开。也符合我对技术的看法,想要真正掌握一门技术就需要厚积薄发的毅力,同时保持乐观的心态。

你只管努力,剩下的交给时间!

ArrayList源码万字解析!透彻易懂!

一、前言

不管是什么样的软件岗位,想要进大厂,肯定会问到一些基础源码知识,如果我们想要从中脱颖而出,就必须要非常熟悉这些源码。本文我们结合源码用通俗易懂的语言来解析ArrayList,尽量给每一行源码都写上注释,给每一个功能加上总结,由于内容较多,强烈建议收藏,那么废话不多说,一起来见真章!
ArrayList源码万字解析!透彻易懂!

二、重新认识ArrayList

  1. 什么是ArrayList?
    ArrayList是基于数组实现的List类,封装了一个动态再分配的Object数组,以达到可以动态增长和缩减的索引序列。
  2. 长啥样?
    ArrayList源码万字解析!透彻易懂!
    如图,是一个长度为6,存储了6个6的数组,下标(index)从0开始,数组(elementData)表示存储的数据本身。
  3. 有哪些基本概念?
    • index 表示数组下标;
    • elementData 表示数组本身;
    • DEFAULT_CAPACITY 表示数组初始大小,默认是10;
    • size 表示当前数组的大小,int类型,未使用volatile修饰,非线程安全;
    • modCount 表示当前数组被修改的版本的次数,也就是说当数组结构有变动,就会+1。

三、知其所以然----撸源码

1. 从整个ArrayList.java的类注释开始入手

简单翻译总结如下:
- ArrayList允许put null值,并且会自动扩容;
- size,isEmpty,get,set,Iterator和listIterator方法的时间复杂度是O(1),add方法的复杂度根据添加元素的多少而不同,添加n个元素,时间复杂度O(n);
- 非线程安全,因此在多线程情况下,为了线程安全推荐使用(List list = Collections.synchronizedList(new ArrayList(...)););
- 支持增强for循环,但需要注意的是,由于非线程安全,所以在使用迭代器迭代过程中,如果数组大小被改变,会快速失败,并抛出异常。

2. 初始化

  1. 三种初始化方式,源码分析

    1. 无参数初始化
      //  无参数构造器,默认是空数组
        public ArrayList() {
      	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
      
      • 1
      • 2
      • 3
      • 4
    2. 指定初始容量大小的初始化
      // 构造一个具有指定初始容量的空列表
        public ArrayList(int initialCapacity) {
      	if (initialCapacity > 0) {
      	  this.elementData = new Object[initialCapacity];
      	} else if (initialCapacity == 0) {
      	  this.elementData = EMPTY_ELEMENTDATA;
      	} else {
      	  throw new IllegalArgumentException("Illegal Capacity: "+
                                      		 initialCapacity);
      	}
        }
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
    3. 指定初始数据初始化
        //指定初始数据初始化
        public ArrayList(Collection<? extends E> c) {
      	//elementData 是保存数组的容器,默认为 null
      	elementData = c.toArray();
      	//如果给定的集合(c)数据有值,则进行拷贝赋值操作
      	if ((size = elementData.length) != 0) {
      	  // c.toArray might (incorrectly) not return Object[] (see 6260652)
      	  //如果集合元素类型不是 Object 类型,才开始拷贝,否则不执行
      	  if (elementData.getClass() != Object[].class) {
      		elementData = Arrays.copyOf(elementData, size, Object[].class);
      	  }
      	} else {
      	  // 给定集合(c)无值,则默认空数组
      	  this.elementData = EMPTY_ELEMENTDATA;
      	}
        }
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
  2. 需要注意的地方

    1. 使用无参数构造器初始化时,默认容量时0,而不是传统印象里的10,只有接着对其进行add时才会变成10;
    2. 通过观察ArrayList的无参构造器,会发现当它进行初始化时,默认大小是空数组;
    3. 可以发现在指定初始数据初始化这种方式里,有一个see 6260652的注释,这是一个1.8版本的bug,在1.9版本的到了解决。解释是(toArray方法可能不会返回Object数组),也就是说当我们有一个ArrayList,里面的元素不是Object类型,比如是String,然后当我们调用toArray方法,得到一个Object数组后,再往这个String类型的Object数组赋值时,就会触发这个BUG,报错。官方查看文档地址:https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652

3. 新增元素及扩容

  1. 先来看下新增元素核心源码
      public boolean add(E e) {
    	//确保数组大小足够,不够需要扩容
    	ensureCapacityInternal(size + 1);  // Increments modCount!!
    	//直接赋值,非线程安全
    	elementData[size++] = e;
    	return true;
      }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    通过源码,我们可以知道新增就是往数组中添加元素,主要分为两步:
    • 判断是否需要扩容,如需要就执行扩容操作
    • 直接赋值(非线程安全)
  2. 接着看下扩容源码的实现
      private void ensureCapacityInternal(int minCapacity) {
    	//如果是空数组,就从最小容量和默认容量10之间取最大值
    	//反之如果初始化时给定了初始值,就按照给定的大小为准,不走if逻辑
    	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    	  minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    	}
    	//确保容积足够
    	ensureExplicitCapacity(minCapacity);
      }
      private void ensureExplicitCapacity(int minCapacity) {
    	//记录数组被修改
    	modCount++;
    	// 如果我们希望的最小容量大于目前数组的长度,那么就扩容
    	if (minCapacity - elementData.length > 0)
    	  grow(minCapacity);
      }
      //扩容,最后把现有数据拷贝到新的数组里面去
      private void grow(int minCapacity) {
    	// overflow-conscious code
    	int oldCapacity = elementData.length;
    	// oldCapacity >> 1 右移运算符,是把 oldCapacity / 2 的意思
    	int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    <span class="token comment">// 如果扩容后的新的容量值 &lt; 我们的期望容量值,那么就取我们的期望容量值</span>
    <span class="token comment">// 也就是扩充的容量至少要满足我们的期望,宁多勿少</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>newCapacity <span class="token operator">-</span> minCapacity <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
      newCapacity <span class="token operator">=</span> minCapacity<span class="token punctuation">;</span>
    
    <span class="token comment">// 如果扩容后的值 &gt; jvm 所能分配的数组的最大值,那么就取Integer 的最大值</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>newCapacity <span class="token operator">-</span> MAX_ARRAY_SIZE <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
      newCapacity <span class="token operator">=</span> <span class="token function">hugeCapacity</span><span class="token punctuation">(</span>minCapacity<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">// minCapacity is usually close to size, so this is a win:</span>
    <span class="token comment">// 通过复制进行扩容</span>
    elementData <span class="token operator">=</span> Arrays<span class="token punctuation">.</span><span class="token function">copyOf</span><span class="token punctuation">(</span>elementData<span class="token punctuation">,</span> newCapacity<span class="token punctuation">)</span><span class="token punctuation">;</span>
    

}
//获取Integer的最大值
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 扩容的本质就是数组的拷贝
    我们通过源码可以发现,扩容的核心是一行代码:elementData = Arrays.copyOf(elementData, newCapacity);扩容会首先创建一个符合要求容量的新数组,然后把老数组的数据拷贝过去;我们一层层的点进去,会发现更底层的操作是通过System.arraycopy这个native方法进行拷贝的。
    /**
     * @param src     被拷贝的数组
     * @param srcPos  从数组那里开始
     * @param dest    目标数组
     * @param destPos 从目标数组那个索引位置开始拷贝
     * @param length  拷贝的长度 
     * 此方法是没有返回值的,通过 dest 的引用进行传值
     */
    public static native void arraycopy(Object src,  int  srcPos,
                                    		Object dest, int destPos,
                                    		int length);
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
  • 总结一波
    • 根据扩容的算法,扩容后的大小是原始容量的1.5倍;
    • ArrayList 中的数组容量的最大值是Integer 的最大值(Integer.MAX_VALUE);
    • 新增过程中,没有对值进行严格校验,所以ArrayList允许null值。
    • 新增元素操作很简单,elementData [size++] = e,因此非线程安全。
  • 4. 删除

    1. 删除元素的方式有很多,不过代码和思路类似,这里选取删除值的方式来分析
        // 根据值去删除
        public boolean remove(Object o) {
      	// 如果值是空的,找到第一个值是空的删除
      	if (o == null) {
      	  for (int index = 0; index < size; index++)
      		if (elementData[index] == null) {
      		  fastRemove(index);
      		  return true;
      		}
      	} else {
      	  // 值不为空,找到第一个和所要删除的值相等的删除
      	  for (int index = 0; index < size; index++)
      		// 注意这里是根据  equals 来判断值相等的
      		if (o.equals(elementData[index])) {
      		  fastRemove(index);
      		  return true;
      		}
      	}
      	return false;
        }
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
    2. 通过第一步,已经找到了要删除元素的索引,接下来就是根据索引位置来删除元素
        private void fastRemove(int index) {
      	// 记录数组的结构变化次数
      	modCount++;
      	// 减 1 的原因,是因为 size 从 1 开始算起,index 从 0开始算起
      	// numMoved 用来表示,在删除 index 位置的元素后,需要从 index 后移动多少个元素到前面去
      	int numMoved = size - index - 1;
      	if (numMoved > 0)
      	  // 从 index +1 位置开始被拷贝,拷贝的起始位置是 index
      	  System.arraycopy(elementData, index+1, elementData, index, numMoved);
      	//给最后一个元素重新赋值为null,然后让GC来对其进行清除
      	elementData[--size] = null; 
        }
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
    3. 总结一波
      1. 由于新增元素时允许null值,因此删除的时候也允许删除null值;
      2. 在数组中找到目标值的索引位置过程是通过equals来判断的,因此使用非基本类型数组元素的时候需要注意;
      3. 当某一个元素被删除后,后面的元素会往前移动,以便于维护数组的结构。

    5. 迭代器

    1. 由于ArrayList是通过实现java.util.Iterator 类来实现自己的迭代器,因此我们先来了解迭代器的源码
      1. 迭代器的几个主要参数及常用方法

        • 3个重要参数:
          // 索引,用来在next里取对应下标的数据
          int cursor;       // index of next element to return
          // 很巧妙的一个值
          // 每次next都会把当前元素的下标赋值给lastRet,如果进行删除操作的话,会用这个值覆盖cursor,使得下一次next依然取这个删除的索引位置上的数据!由于删除元素后,后面的元素会自动前移,那么这个操作就能保证不会漏掉任何一个数据。
          int lastRet = -1; // index of last element returned; -1 if no such
          // 迭代过程中期望数组修改版本号
          int expectedModCount = modCount;
          
          • 1
          • 2
          • 3
          • 4
          • 5
          • 6
          • 7
        • 3个基本方法:
          hasNext 还有没有值可以迭代
          next 如果有值可以迭代,迭代的值是多少
          remove 删除当前迭代的值
      2. hashNext源码解析

        public boolean hasNext() {
          return cursor != size;//cursor 表示下一个元素的位置,size 表示实际大小,如果两者相等,说明已经没有元素可以迭代了,如果不等,说明还可以迭代
        }
        
        • 1
        • 2
        • 3
      3. next源码解析
        迭代器的next和remove是相互联动的,代码层层关联,可谓精妙。通过next方法之后,会把当前遍历的元素的下标索引赋值给lastRet,一方面是可以在remove时删除这个索引的元素,另一方面可以作为已经执行next的证据,通过remove方法内部的的校验。 下面我将逐行去解析,大家多留意lastRet和cursor的变化:

        public E next() {
          //迭代过程中,根据modCount 和 expectedModCount是否相等,判断版本号有无被修改,有被修改,抛 ConcurrentModificationException 异常
          checkForComodification();
          //本次迭代过程中,元素的索引位置
          int i = cursor;
          if (i >= size)
            throw new NoSuchElementException();
          Object[] elementData = ArrayList.this.elementData;
          if (i >= elementData.length)
            throw new ConcurrentModificationException();
          // 下一次迭代时,元素的位置
          cursor = i + 1;
          // 返回元素值,并把当前元素的位置赋值为lastRet,这样有两个作用:
          // 1、可以对应删除这个索引位置的元素
          // 2、在迭代器的remove时,可以通过if判断,相当于想要使用迭代器的remove,必须先使用next
          return (E) elementData[lastRet = i];
        }
        
        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 8
        • 9
        • 10
        • 11
        • 12
        • 13
        • 14
        • 15
        • 16
        • 17
      4. remove源码解析
        首先我们要明确一点,就是由于ArrayList每次删除数据后,会把后面的数据前移。而通过上一节next的解析,我们知道了next最终会把当前元素的索引赋值给lastRet。其实remove会根据lastRet删除这个索引的元素,然后后面的数据会前移,所以为了防止下一次next时遍历下一个索引进而漏掉元素,所以在remove后,会把当前索引赋值给cursor,让next继续遍历这个位置的元素。而且为了防止迭代器重复的remove这个索引的元素,因此一会大家可以看到,在remove方法的最后lastRet会被重新赋值1。

        public void remove() {
          // 如果没有使用next,此时lastRet是-1,不支持删除数据(由于删除后,这个被删除数据的索引还有从后面移上数据,这样可以防止不小心重复删除某一索引的数据)
          if (lastRet < 0)
            throw new IllegalStateException();
          //迭代过程中,判断版本号有无被修改,有被修改,抛 ConcurrentModificationException 异常
          checkForComodification();
        

    try {
    // 调用ArrayList的remove(int index)删除数据
    ArrayList.this.remove(lastRet);
    // 在进行remove之前,已经进行了next,由于此时lastRet就是被删除元素的索引,删除之后,这个索引后面的数据会前移,所以这里把lastRet赋值给cursor,使下一次next继续遍历这个位置的元素,这样就不会漏数据了。
    cursor = lastRet;
    // 继续让lastRet变为-1,这样如果不进行next,就不会进行下一次的remove
    lastRet = -1;
    // 删除元素时 modCount 的值已经发生变化,再此赋值给 expectedModCount,用以在next时通过checkForComodification校验
    expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
    }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
  • Iterator源码小结一波

    • next方法主要完成两件事,首先检验能不能继续迭代,然后找到并返回迭代的值,并为下一次迭代做准备;
    • lastRet在next场景下表示上一次迭代的元素下标,在remove场景下表示-1,用来防止重复删除元素;
    • 如果删除成功,数组当前的modCount就会发生变化,这里会把expectedModCount重新赋值,下次迭代时两者的值就一致了。
  • 四、线程是否安全

    由于ArrayList自身的elementData、size、modCount在进行各种操作时,都没有加锁,并且这些变量都是非volatile类型的,所以如果多个线程对这些变量进行操作时,可能会有值被覆盖的情况。
    所以,结合源码我们可以发现当ArrayList作为共享变量时,会有线程安全问题;当ArrayList是方法内的局部变量时,就不存在线程安全问题了。
    最开始通过看类注释,我们知道他们推荐我们使用List list = Collections.synchronizedList(new ArrayList(...));来保证线程安全,源码解析如下:

    public boolean add(E e) {
        synchronized (mutex) {// synchronized 是一种轻量锁,mutex 表示一个当前 SynchronizedList
            return c.add(e);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5

    因此,SynchronizedList 其实是通过在每个方法上面加上锁来实现,虽然实现了线程安全,但是性能大大降低。

    五、总结

    通过上面的源码解析,我们对ArrayList有了更深入的了解,下面总结一些常见的考察点,便于记忆。

    1. ArrayList大小和容量

    • 如果使用无参构造函数创建ArrayList,大小size和初始容量都是0;
    • 如果使用有参构造函数:当指定初始容量,就按照指定的初始容量;如果没有指定初始容量传递值进去,就根据实际size的大小为初始容量;
    • 在无参构造函数初始化的ArrayList进行第一次add操作时,第一次会最少扩容10,如果第一次add进去的数值size大于10,就按照这个size扩容。

    2. ArrayList扩容总结

    当我们使用无参构造函数创建了一个ArrayList时,初始容量为0。当我们add进一个值时,此时的容量为10,size为1。然后接着添加数据时,扩容有两个情况要考虑:

    • 当我们接着add进入10个值时,此时需要扩容,首先根据公式计算1.5倍是15,然后发现15已经可以容纳11个值了,就选择15作为扩容的容量;

    • 当我们接着add进入15个值时,此时需要扩容,首先根据公式计算1.5倍是15,然后发现15无法容纳16个值,就会选择我们期望的容量16作为扩容的容量,这里的判断代码如下:

      // newCapacity 本次扩容的大小,minCapacity 我们期望的数组最小大小
      // 如果扩容后的值 < 我们的期望值,我们的期望值就等于本次扩容的大小
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
      
      • 1
      • 2
      • 3
      • 4

    而且需要注意的是,扩容会消耗性能,因为扩容底层使用的是 System.arraycopy 方法,会把原数组的数据全部拷贝到新数组上,所以性能消耗比较严重。

    3. ArrayList删除总结

    3.1、为什么普通for循环无法删除干净(漏掉要删除的数据)?

    普通for循环调用ArrayList的remove删除数据后,后面的数据会自动向前移。比如一个1,2,3,3,4的ArrayList,我们使用普通for循环,在删除下标为2的元素3后,原本下标为3、4的元素会前移一位,下次循环时我们再遍历下标3时,这时候下标3对应的元素已经是4了,相当于漏掉了一个要删除的元素。

    3.2、为什么增强for循环删除数据会报错?

    因为增强 for 循环过程其实调用的就是迭代器的 next () 方法,当你调用 lArrayList的remove 方法进行删除时,modCount 的值会 +1,而这时候迭代器中的 expectedModCount 的值却没有变,导致在迭代器下次执行 next () 方法时,首先调用checkForComodification()判断时,会由于expectedModCount != modCount 报 ConcurrentModificationException 的错误。

    3.3、为什么迭代器封装的remove方法可以删干净,且不报错?

    这个问题,在网上总结或者回答的是为什么不报错,我没有找到有人解释为什么可以删干净,我们先看为什么不报错:
    因为 Iterator.remove 方法在执行的过程中,会把最新的 modCount 赋值给 expectedModCount,这样在下次循环过程中,modCount 和 expectedModCount 两者就会相等,就能通过checkForComodification判断。
    那么究竟为什么迭代器封装的remove方法就可以删除干净,不会漏数据呢?
    首先,需要肯定的是迭代器封装的remove方法依然是调用的ArrayList的remove(int index)索引删除方法;
    下面让我们忽略其它逻辑,把next和remove放在一起从头到remove结束好好看一下:

    private class Itr implements Iterator<E> {
        // 索引,用来在next里取对应下标的数据
        int cursor;       // index of next element to return
        // 很巧妙的一个值
        // 每次next都会把当前元素的下标赋值给lastRet,如果进行删除操作的话,会用这个值覆盖cursor,使得下一次next依然取这个删除的索引位置上的数据!由于删除元素后,后面的元素会自动前移,那么这个操作就能保证不会漏掉任何一个数据。
        int lastRet = -1; // index of last element returned; -1 if no such
        // 迭代过程中期望数组修改版本号
        int expectedModCount = modCount;
    
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">hasNext</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">return</span> cursor <span class="token operator">!=</span> size<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    <span class="token keyword">public</span> E <span class="token function">next</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">//迭代过程中,根据modCount 和 expectedModCount是否相等,判断版本号有无被修改,有被修改,抛 ConcurrentModificationException 异常</span>
      <span class="token function">checkForComodification</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token comment">//本次迭代过程中,元素的索引位置</span>
      <span class="token keyword">int</span> i <span class="token operator">=</span> cursor<span class="token punctuation">;</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator">&gt;=</span> size<span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">NoSuchElementException</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      Object<span class="token punctuation">[</span><span class="token punctuation">]</span> elementData <span class="token operator">=</span> ArrayList<span class="token punctuation">.</span><span class="token keyword">this</span><span class="token punctuation">.</span>elementData<span class="token punctuation">;</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator">&gt;=</span> elementData<span class="token punctuation">.</span>length<span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">ConcurrentModificationException</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token comment">// 下一次迭代时,元素的位置</span>
      cursor <span class="token operator">=</span> i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
      <span class="token comment">// 返回元素值,并把当前元素的位置赋值为lastRet,这样有两个作用:</span>
      <span class="token comment">// 1、可以对应删除这个索引位置的元素</span>
      <span class="token comment">// 2、在迭代器的remove时,可以通过if判断,相当于想要使用迭代器的remove,必须先使用next</span>
      <span class="token keyword">return</span> <span class="token punctuation">(</span>E<span class="token punctuation">)</span> elementData<span class="token punctuation">[</span>lastRet <span class="token operator">=</span> i<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">remove</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">// 如果没有使用next,此时lastRet是-1,不支持删除数据(由于删除后,这个被删除数据的索引还有从后面移上数据,这样可以防止不小心重复删除某一索引的数据)</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>lastRet <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalStateException</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token comment">//迭代过程中,判断版本号有无被修改,有被修改,抛 ConcurrentModificationException 异常</span>
      <span class="token function">checkForComodification</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    
      <span class="token keyword">try</span> <span class="token punctuation">{</span>
      	<span class="token comment">// 调用ArrayList的remove(int index)删除数据</span>
        ArrayList<span class="token punctuation">.</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span>lastRet<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">// 在进行remove之前,已经进行了next,由于此时lastRet就是被删除元素的索引,删除之后,这个索引后面的数据会前移,所以这里把lastRet赋值给cursor,使下一次next继续遍历这个位置的元素,这样就不会漏数据了。</span>
        cursor <span class="token operator">=</span> lastRet<span class="token punctuation">;</span>
        <span class="token comment">// 继续让lastRet变为-1,这样如果不进行next,就不会进行下一次的remove</span>
        lastRet <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token comment">// 删除元素时 modCount 的值已经发生变化,再此赋值给 expectedModCount,用以在next时通过checkForComodification校验</span>
        expectedModCount <span class="token operator">=</span> modCount<span class="token punctuation">;</span>
      <span class="token punctuation">}</span> <span class="token keyword">catch</span> <span class="token punctuation">(</span><span class="token class-name">IndexOutOfBoundsException</span> ex<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">ConcurrentModificationException</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    结合前面的解析以及这段完整的代码,相信大家已经知道了为什么同样是remove,而且迭代器的remove只是在原有基础上封装了一次,就能够避免遗漏数据了,这是因为对下标索引进行了巧妙的处理。next和remove在不漏掉数据这方面的大致联动过程如下:
    1. next遍历数组,并把当前元素的索引cursor赋值给lastRet;
    2. 这时候如果执行remove,由于lastRet不再是-1,顺利向下执行,调用ArrayList.this.remove(lastRet)删除当前元素;
    3. 删除之后,用lastRet覆盖cursor,使得下一次遍历,不漏掉元素;
    4. 覆盖之后,重新给lastRet赋值为-1,避免重复删除数据。

    到这里,ArrayList的源码已经总结完毕了,相信和ArrayList相关的所有问题都能从中得到答案。

                                    </div>