Java集合框架：ArrayList的介绍、使用、原理与源码解析

见贤思齐

大家好，我是栗筝i，这篇文章是我的“栗筝i的Java技术栈”专栏的第013篇文章，在“栗筝i的Java技术栈”这个专栏中我会持续为大家更新Java技术相关全套技术栈内容。专栏的主要目标是已经有一定Java开发经验，并希望进一步完善自己对整个Java技术体系来充实自己的技术栈的同学。与此同时，本专栏的所有文章，也都会准备充足的代码示例和完善的知识点梳理，因此也十分适合零基础的小白和要准备工作面试的同学学习。当然，我也会在必要的时候进行相关技术深度的技术解读，相信即使是拥有多年Java开发经验的从业者和大佬们也会有所收获并找到乐趣。–本文将从介绍ArrayList开始，详细探讨其使用方法、工作原理以及背后的源码实现，帮助读者深入理解并灵活运用ArrayList，以提升编程效率和代码质量。在接下来的部分中，我们将首先概述ArrayList的基本特性及其在Java集合框架中的地位。随后，通过实际代码示例展示如何创建、操作和管理ArrayList。接着，我们会揭示ArrayList的内部工作机制，包括其底层数据结构、扩容策略和性能优化等方面的内容。最后，我们将深入分析ArrayList的源码，探讨其设计思想和实现细节，以便读者能够更全面地掌握这一重要的集合类。文章目录1、ArrayList概述1.1、ArrayList介绍1.2、ArrayList特点1.3、ArrayList使用用例1.4、ArrayList实现原理1.5、ArrayList优缺点及适用场景2、ArrayList源码2.1、数据结构2.2、构造方法2.3、元素访问2.4、添加操作2.5、扩容机制2.6、删除操作3、ArrayList知识点补充3.1、ArrayList方法概述3.2、在遍历ArrayList时移除元素时的问题3.2.1、ConcurrentModificationException3.2.2、跳过元素3.3、遍历ArrayList时移除元素时的问题解决方案3.3.1、使用迭代器的remove方法3.3.2、使用Java8的removeIf方法3.3.3、使用逆向遍历1、ArrayList概述1.1、ArrayList介绍ArrayList即动态数组，是最常用的List实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。用MSDN（MicrosoftDeveloperNetwork，微软开发者网络）中的说法，就是Array的复杂版本。ArrayList底层使用数组实现，由于数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。所以当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。ArrayList的每个实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是大于等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。此外，ArrayList在被添加大量元素前，应用程序也可以使用ensureCapacity()操作来指定ArrayList实例的容量，这可以减少递增式再分配的数量。ArrayList是非线程安全的，只能在单线程环境下使用，多线程环境下可以考虑用Collections.synchronizedList(Listl)函数返回一个线程安全的ArrayList类，也可以使用java.util.concurrent并发包下的CopyOnWriteArrayList类。1.2、ArrayList特点ArrayList是一个可变大小的数组，可以动态地调整大小。ArrayList有以下特点：动态数组：ArrayList底层是一个动态数组，能够自动调整其大小。当添加新元素时，如果内部数组空间不足，ArrayList会创建一个更大的数组并将旧数组中的元素复制到新数组中；有序：ArrayList保持元素的插入顺序，即按照元素添加到集合中的顺序来存储它们；快速随机访问：由于底层是数组，可以通过索引快速访问元素，时间复杂度为O(1)；可变大小：ArrayList的大小是动态调整的，用户不需要指定其初始大小，但可以通过构造函数指定初始容量;不保证线程安全：ArrayList不是线程安全的。如果多个线程同时访问一个ArrayList实例，并且至少一个线程修改了列表的结构，那么必须在外部实现同步；允许null元素：ArrayList允许存储null元素；频繁的增删操作效率较低：由于插入或删除元素时需要移动数组中的其他元素，频繁的插入和删除操作会导致性能下降，特别是在列表的中间位置进行操作时，时间复杂度为O(n)。1.3、ArrayList使用用例ArrayList是Java中广泛使用的集合类，适用于各种场景。以下是常见的使用用例和代码示例，创建一个ArrayList，并进行基本的增删查操作：：importjava.util.ArrayList;publicclassArrayListBasicOperations{publicstaticvoidmain(String[]args){//创建一个ArrayListArrayListfruits=newArrayList();//添加元素fruits.add("Apple");fruits.add("Banana");fruits.add("Cherry");//获取元素Stringfruit=fruits.get(1);//"Banana"System.out.println("Thesecondfruitis:"+fruit);//删除元素fruits.remove("Apple");//遍历列表for(Stringitem:fruits){System.out.println(item);}//检查列表大小intsize=fruits.size();System.out.println("Listsize:"+size);}}1234567891011121314151617181920212223242526272829301.4、ArrayList实现原理ArrayList是Java中基于动态数组实现的集合类，其实现原理主要包括以下几个方面：数据结构、扩容机制、添加和删除元素的过程，以及一些常见操作的时间复杂度。数据结构：ArrayList底层使用一个数组来存储元素。它定义了一个初始容量，当元素数量超过当前容量时，会自动扩容；扩容机制：当向ArrayList中添加元素且当前数组已满时，会触发扩容机制。扩容时，新的数组容量通常是旧容量的1.5倍；添加元素：添加元素有两种方式：在末尾添加和在指定位置添加。前者是最常见的操作，时间复杂度为O(1)；后者需要移动指定位置之后的元素，时间复杂度为O(n)；删除元素：删除元素同样有两种方式：删除指定位置的元素和删除指定元素的第一次出现。删除指定位置的元素需要移动后面的元素，时间复杂度为O(n)；删除指定元素的第一次出现则需要先查找，时间复杂度为O(n)。1.5、ArrayList优缺点及适用场景优点：动态调整大小：ArrayList可以根据需要动态调整其大小，用户不需要手动管理数组的大小；快速随机访问：由于底层是数组，ArrayList支持快速的随机访问，时间复杂度为O(1)；有序：ArrayList保持元素的插入顺序，这使得它非常适合需要保持顺序的场景；实现简单：ArrayList的实现相对简单，提供了丰富的API，使用起来非常方便；允许重复和null元素：ArrayList允许存储重复元素和null元素，增加了灵活；扩容机制：ArrayList内部的扩容机制能够有效减少扩容次数，提升性能。缺点：插入和删除效率低：在ArrayList中间插入或删除元素时，需要移动数组中的其他元素，时间复杂度为O(n)，因此在频繁插入和删除操作的场景中效率较低；非线程安全：ArrayList不是线程安全的，如果在多线程环境中使用，需要手动进行同步，或者使用Collections.synchronizedList包装；占用额外内存：ArrayList在扩容时需要分配新的数组并复制旧数组中的元素，这会占用额外的内存，并可能导致内存碎片问题；空间浪费：当ArrayList的实际元素数量远小于其容量时，会浪费内存空间；扩容时性能开销：当ArrayList扩容时，需要进行数组复制操作，会导致短暂的性能下降，特别是在大规模扩容时。适用场景：快速随机访问：如果应用程序需要频繁地通过索引访问元素，ArrayList是一个很好的选择；读取多、写入少：适用于读取操作多于写入操作的场景；存储有序数据：适用于需要保持元素插入顺序的场景。不适用场景：频繁插入和删除：不适用于频繁在中间位置插入或删除元素的场景，因为这会导致大量的数组移动操作；线程安全要求：不适用于需要线程安全的场景，除非使用同步包装。2、ArrayList源码ArrayList通过动态数组来实现，其扩容机制保证了在添加大量元素时能够自动调整容量。它提供了快速的随机访问，但在进行大量插入和删除操作时效率较低，特别是在列表中间进行操作时。这些特性使得ArrayList适用于需要频繁访问元素但插入和删除操作较少的场景。为了更好的理解ArrayList的这些特性，接下来我们以JDK1.8中的代码为例，看一下它的源码！2.1、数据结构ArrayList通过维护一个数组elementData来存储其元素，并使用两个共享的空数组实例EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA来区分不同状态下的空ArrayList。当添加第一个元素时，ArrayList会根据当前状态选择合适的扩展策略。这个设计使得ArrayList能够高效地管理其内部数组，在需要时进行动态扩展。publicclassArrayListextendsAbstractListimplementsList,RandomAccess,Cloneable,java.io.Serializable{//省略其他方法和实现细节.../***用于空实例的共享空数组实例。*/privatestaticfinalObject[]EMPTY_ELEMENTDATA={};/***用于默认大小空实例的共享空数组实例。*我们将其与EMPTY_ELEMENTDATA区分开来，以便在添加第一个元素时知道要扩充多少。*/privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};/***存储ArrayList元素的数组缓冲区。*ArrayList的容量即为此数组缓冲区的长度。*任何elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList在添加第一个元素时会扩展到DEFAULT_CAPACITY。*/transientObject[]elementData;//为简化嵌套类访问，非私有/***ArrayList的大小（它包含的元素数量）。**@serial*/privateintsize;//省略其他方法和实现细节...}123456789101112131415161718192021222324252627282930313233342.2、构造方法ArrayList提供了灵活的构造方法来初始化列表，可以指定初始容量、使用默认容量或通过集合初始化。通过这些构造方法，ArrayList能够满足不同场景下的初始化需求，并且在初始化时根据传入参数的不同进行相应的处理和优化。publicclassArrayListextendsAbstractListimplementsList,RandomAccess,Cloneable,java.io.Serializable{//省略其他方法和实现细节.../***使用指定的初始容量构造一个空列表。**@paraminitialCapacity列表的初始容量*@throwsIllegalArgumentException如果指定的初始容量为负数*/publicArrayList(intinitialCapacity){if(initialCapacity>0){this.elementData=newObject[initialCapacity];}elseif(initialCapacity==0){this.elementData=EMPTY_ELEMENTDATA;}else{thrownewIllegalArgumentException("IllegalCapacity:"+initialCapacity);}}/***构造一个初始容量为十的空列表。*/publicArrayList(){this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/***构造一个包含指定集合元素的列表，按集合的迭代器返回的顺序。**@paramc包含要放入此列表中的元素的集合*@throwsNullPointerException如果指定的集合为null*/publicArrayList(Collectionc){Object[]a=c.toArray();if((size=a.length)!=0){if(c.getClass()==ArrayList.class){elementData=a;}else{elementData=Arrays.copyOf(a,size,Object[].class);}}else{//用空数组替换。elementData=EMPTY_ELEMENTDATA;}}//省略其他方法和实现细节...}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152532.3、元素访问正因为ArrayList的底层实现是数组（一块连续的内存区域），所以可以轻松的实现快速的随机访问和按索引操作。get方法在访问或修改元素之前都会调用rangeCheck方法检查索引的有效性，而rangeCheck方法会在索引超出范围时抛出详细的错误信息。publicclassArrayListextendsAbstractListimplementsList,RandomAccess,Cloneable,java.io.Serializable{//省略其他方法和实现细节.../***在指定索引处获取元素。**@paramindex要获取元素的位置*@return指定索引处的元素*/EelementData(intindex){return(E)elementData[index];}/***获取指定索引处的元素，并进行范围检查。**@paramindex要获取元素的位置*@return指定索引处的元素*@throwsIndexOutOfBoundsException如果索引超出范围*/publicEget(intindex){rangeCheck(index);//检查索引是否在范围内returnelementData(index);//返回指定索引处的元素}/***检查索引是否在范围内。**@paramindex要检查的索引*@throwsIndexOutOfBoundsException如果索引超出范围*/privatevoidrangeCheck(intindex){if(index>=size||indexextendsAbstractListimplementsList,RandomAccess,Cloneable,java.io.Serializable{ //省略其他方法和实现细节 .../***在ArrayList末尾添加一个元素。**@parame要添加的元素*@return总是返回true*/publicbooleanadd(Ee){ensureCapacityInternal(size+1);//确保容量足够容纳新元素，增加modCountelementData[size++]=e;//将新元素添加到数组中，size自增returntrue;}/***确保ArrayList的容量足够容纳指定数量的元素。**@paramminCapacity需要的最小容量*/privatevoidensureCapacityInternal(intminCapacity){ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));}/***计算所需的容量**@paramelementData当前的数组*@paramminCapacity需要的最小容量*@return计算后的容量*/privatestaticintcalculateCapacity(Object[]elementData,intminCapacity){if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){returnMath.max(DEFAULT_CAPACITY,minCapacity);}returnminCapacity;}/***显式地确保ArrayList的容量足够。**@paramminCapacity需要的最小容量*/privatevoidensureExplicitCapacity(intminCapacity){//递增修改计数，以支持快速失败机制modCount++;//overflow-consciouscodeif(minCapacity-elementData.length>0)grow(minCapacity);//如果所需容量超过当前数组长度，则扩展数组}/***扩展数组的容量。**@paramminCapacity需要的最小容量*/privatevoidgrow(intminCapacity){//overflow-consciouscodeintoldCapacity=elementData.length;intnewCapacity=oldCapacity+(oldCapacity>>1);if(newCapacity-minCapacity0)newCapacity=hugeCapacity(minCapacity);elementData=Arrays.copyOf(elementData,newCapacity);} //省略其他方法和实现细节 ...}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374752.5、扩容机制扩容后的数组大小是原大小的1.5倍（oldCapacity+(oldCapacity>>1)）。最后将旧数组进行复制（调用Arrays.copyof()，再调用System.arraycopy()），达到扩容的目的，此时新旧列表的size大小相同，但elementData的长度即容量不同。publicclassArrayListextendsAbstractListimplementsList,RandomAccess,Cloneable,java.io.Serializable{ //省略其他方法和实现细节 .../***扩展数组的容量。**@paramminCapacity需要的最小容量*/privatevoidgrow(intminCapacity){//将数组长度赋值给oldCapacityintoldCapacity=elementData.length; //将oldCapacity右移一位再加上oldCapacity，即相当于newCapacity=1.5倍oldCapacity(不考虑精度损失)intnewCapacity=oldCapacity+(oldCapacity>>1); //如果newCapacity还是小于minCapacity，直接将minCapacity赋值给newCapacityif(newCapacity-minCapacity0)newCapacity=hugeCapacity(minCapacity);//将elementData的数据拷贝到扩容后的数组elementData=Arrays.copyOf(elementData,newCapacity);}/`*如果大于临界值，进行整型最大值的分配**@paramminCapacity需要的最小容量*/ privatestaticinthugeCapacity(intminCapacity){if(minCapacityMAX_ARRAY_SIZE)?Integer.MAX_VALUE:MAX_ARRAY_SIZE; } //省略其他方法和实现细节 ...}12345678910111213141516171819202122232425262728293031323334353637383940414243442.6、删除操作ArrayList在进行根据索引删除时，通过系统native方法System.arraycopy完成的，原理就是将删除位置后的所有元素重新复制到删除位置到原来最后元素的前一位，并使用elementData[--size]=null;清空多余的值。packagejava.util;import...publicclassArrayListextendsAbstractListimplementsList,RandomAccess,Cloneable,java.io.Serializable{ //省略其他方法和实现细节 .../***从列表中移除指定位置的元素。*将所有后续元素左移（索引减一）。**@paramindex要移除元素的索引位置*@return被移除的元素*@throwsIndexOutOfBoundsException如果索引超出范围抛出此异常*/publicEremove(intindex){rangeCheck(index);//检查索引是否在合法范围内，防止索引越界modCount++;//修改次数加一，用于实现迭代器的快速失败机制（在迭代过程中如果检测到结构变化会抛出异常）EoldValue=elementData(index);//获取并保存将要被移除的元素值intnumMoved=size-index-1;//计算从index之后需要左移的元素数量if(numMoved>0)System.arraycopy(elementData,index+1,elementData,index,numMoved);//使用系统方法arraycopy来高效地移动数组元素elementData[--size]=null;//将最后一个元素设为null，帮助垃圾收集器回收，并减少实际元素数量returnoldValue;//返回被移除的元素}/***从列表中移除第一次出现的指定元素（如果存在）。*如果列表不包含该元素，则不做改变。*更正式地说，移除满足(o==null?get(i)==null.equals(get(i)))条件的最低索引的元素。**@paramo要从列表中移除的元素*@return如果列表包含指定元素则返回true*/publicbooleanremove(Objecto){if(o==null){for(intindex=0;index0)System.arraycopy(elementData,index+1,elementData,index,numMoved);//高效地移动数组元素elementData[--size]=null;//清理引用，帮助垃圾回收} //省略其他方法和实现细节 ...}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475763、ArrayList知识点补充3.1、ArrayList方法概述ArrayList类提供了多种方法，用于元素的添加、删除、访问、修改等操作。以下是ArrayList类的方法列表，并标注了每个方法的来源（自带、接口、父类）和参数说明。add(Ee)：实现(List)，添加元素到列表末尾，返回值类型为boolean；add(intindex,Eelement)：实现(List)，在指定位置插入元素，无返回值；addAll(Collectionc)：实现(List)，添加集合中的所有元素，返回值类型为boolean；addAll(intindex,Collectionc)：实现(List)，在指定位置插入集合中的所有元素，返回值类型为boolean；clear()：自带，清空列表，无返回值；clone()：自带，克隆列表，返回值类型为Object；contains(Objecto)：实现(Collection)，检查列表是否包含指定元素，返回值类型为boolean；ensureCapacity(intminCapacity)：自带，确保列表的最小容量，无返回值；forEach(Consumeraction)：实现(Iterable)，对列表中的每个元素执行指定操作，无返回值；get(intindex)：自带，获取指定位置的元素，返回值类型为E；indexOf(Objecto)：自带，返回指定元素第一次出现的位置，返回值类型为int；isEmpty()：实现(Collection)，检查列表是否为空，返回值类型为boolean；iterator()：实现(Iterable)，返回列表的迭代器，返回值类型为Iterator；lastIndexOf(Objecto)：自带，返回指定元素最后一次出现的位置，返回值类型为int；listIterator()：自带，返回列表的列表迭代器，返回值类型为ListIterator；listIterator(intindex)：自带，返回从指定位置开始的列表迭代器，返回值类型为ListIterator；remove(intindex)：自带，移除指定位置的元素，返回值类型为E；remove(Objecto)：自带，移除首次出现的指定元素，返回值类型为boolean；removeAll(Collectionc)：自带，移除所有包含在指定集合中的元素，返回值类型为boolean；removeIf(Predicatefilter)：实现(Collection)，移除满足条件的元素，返回值类型为boolean；replaceAll(UnaryOperatoroperator)：实现(List)，替换每个元素，无返回值；retainAll(Collectionc)：自带，保留所有包含在指定集合中的元素，返回值类型为boolean；set(intindex,Eelement)：自带，替换指定位置的元素，返回值类型为E；size()：自带，返回列表的大小，返回值类型为int；sort(Comparatorc)：自带，排序列表，无返回值；spliterator()：实现(Collection)，返回列表的可拆分迭代器，返回值类型为Spliterator；subList(intfromIndex,inttoIndex)：自带，返回指定范围的子列表，返回值类型为List；toArray()：实现(Collection)，将列表转换为数组，返回值类型为Object[]；toArray(T[]a)：实现(Collection)，将列表转换为指定类型的数组，返回值类型为T[]；trimToSize()：自带，修剪列表的容量为当前大小，无返回值。3.2、在遍历ArrayList时移除元素时的问题在遍历ArrayList或其他类型的List集合时进行元素的删除，确实需要格外小心。这是因为集合的结构修改（如添加或删除元素）可能会影响遍历过程，导致ConcurrentModificationException异常或者跳过元素。这里详细解释下这两种情况：3.2.1、ConcurrentModificationExceptionConcurrentModificationException是Java在迭代器检测到除了它自身的remove()方法之外的任何修改时抛出的异常。这是Java集合框架的“fail-fast”行为的一部分，用来快速响应错误，防止未定义的行为。当你使用迭代器或者增强型for循环（本质上使用的是迭代器）遍历ArrayList时，如果在遍历过程中通过集合的直接方法（如list.remove(index)）修改集合，就会导致迭代器的内部状态与集合的状态不一致。因为迭代器内部有一个expectedModCount变量，用来记录初始化迭代器时集合的修改次数。每次迭代时，迭代器都会检查集合的当前修改次数是否仍然等于expectedModCount。如果不等，就会抛出ConcurrentModificationException。publicclassMain{publicstaticvoidmain(String[]args){Listlist=newArrayList();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);for(Integernumber:list){if(number%2==0){list.remove(number);//尝试删除元素}}}}12345678910111213141516在这个例子中，尝试删除所有偶数。因为list.remove(Object)修改了集合，而这种修改没有通过迭代器进行，所以当迭代器检测到修改时（在下一次调用next()时），它将抛出ConcurrentModificationException3.2.2、跳过元素另一个常见的问题是在使用普通的for循环遍历并同时删除元素时可能会跳过某些元素。这是因为删除元素会影响数组的索引：importjava.util.ArrayList;importjava.util.List;publicclassMain{publicstaticvoidmain(String[]args){Listlist=newArrayList();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);for(inti=0;iit=list.iterator();while(it.hasNext()){Integervalue=it.next();if(value%2==0){it.remove();//安全删除}}12345673.3.2、使用Java8的removeIf方法Java8提供的removeIf()方法可以在内部安全地修改列表，并避免ConcurrentModificationException：list.removeIf(n->n%2==0);//删除所有偶数13.3.3、使用逆向遍历使用传统的for循环时，从列表的尾部向前遍历和删除可以避免跳过元素的问题：for(inti=list.size()-1;i>=0;i--){if(list.get(i)%2==0){list.remove(i);}}12345这些方法各有优势和适用场景。选择哪种方法取决于具体的需求和环境。在多数情况下，使用迭代器的remove()方法或removeIf()方法提供了最简洁和安全的解决方案。