从来没想过！！！谷歌在采访中也询问了ArrayList

，转载本文请联系粥夏雪公众号。前几天，我和H同学聊起了谷歌的面试经历。让我吃惊的是谷歌还问了ArrayList？？？仔细想想也是正常的。毕竟集合是Java程序员逃不掉的金诅咒。在阅读文章之前，您可以先阅读以下问题。如果你觉得没有什么问题，可以直接跳过这篇文章，就不用浪费大家的时间了。使用无参数构造函数时ArrayList何时展开？告诉我如何在扩展ArrayList时复制数组？ArrayList遍历删除时会触发什么机制？为什么用迭代器遍历删除时不行？下来继续说ArrayList这个面试高频题。ArrayList的扩展机制//buffertransientObject[]elementData用于存储数组元素;//默认空数组元素privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};//默认初始化容量privatestaticfinalintDEFAULT_CAPACITY=10;//数组大小privateintsize;//记录个数ofmodifiedtimesprotectedtransientintmodCount=0;//数组的最大值privatestaticfinalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8ArrayList底层是使用数组实现的。如果不设置，默认初始容量为10//数组扩展方式//minCapacity=size+1privateintnewCapacity(intminCapacity){//当前数组长度intoldCapacity=elementData.length;//新数组容量=旧数组长度+旧数组长度/2//oldCapacity=10oldCapacity>>1---5//比如10的二进制值为：00001010>>1----->00000101=5intnewCapacity=oldCapacity+(oldCapacity>>1);if(newCapacity-minCapacity<=0){if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA)//如果一开始没有定义初始容量，则newCapacity=0，返回默认容量10//可以得出结论，当没有没有参数的newArrayList()，这个ArrayList()是一个空集合，大小为0MAX_ARRAY_SIZE<=0)?newCapacity//这里返回长度为原数组的1.5倍：hugeCapacity(minCapacity);}添加元素时，发现底层数组需要的容量（size+1）大于数组的容量，扩容会被触发。第一次调用add()方法后，返回一个容量为10的数组，每次扩容后，新数组的长度都会是原数组长度的“1.5”倍，调用底层nativeSystem.arraycopy将旧数组的数据拷贝到新数组中，完成整个扩容，日常开发中，知道初始值的时候先设置初始值，因为扩容比较消耗性能。》脑洞小结：第一次扩容10，之后每次扩容都是原数组的1.5倍，调用底层nativeSystem.arraycopy将旧数组的数据复制到新数组，完成整个扩容。“ArrayList添加元素和ExpandArrayList.add(Ee)源码：publicbooleanadd(Ee){ensureCapacityInternal(size+1);//IncrementsmodCount!!elementData[size++]=e;returntrue;}add()inelementData[size++]=e很好理解，就是把元素插入到size位置，然后size++，我们重点看ensureCapacityInternal(size+1)方法；privatevoidensureCapacityInternal(intminCapacity){if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);}ensureExplicitCapacity(minCapacity);}ensureCapacityInternal()方法判断缓存变量elementData是否为空，即判断是否是第一次添加元素，如果是第一次添加元素，设置初始大小为默认容量10，否则为传入参数。该方法的目的是“获取数组的初始容量”。获取初始容量后，调用ensureExplicitCapacity(minCapacity)方法；privatevoidensureExplicitCapacity(intminCapacity){modCount++;//overflow-consciouscodeif(minCapacity-elementData.length>0)grow(minCapacity);}ensureExplicitCapacity(minCapacity)方法用于判断是否需要扩容，如果是第一次添加元素此时minCapacity为10，elementData容量为0，需要扩容。调用grow(minCapacity)方法。//数组最大容量privatestaticfinalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8;privatevoidgrow(intminCapacity){//overflow-consciouscodeintoldCapacity=elementData.length;//扩展大小为原数组长度的1.5倍intnewCapacity=oldCapacity+(oldCapacity>>1);//扩展容量小于需要扩展的长度，则使用需要扩展的容量if(newCapacity-minCapacity<0)newCapacity=minCapacity;//扩展容量大于最大数组长度，然后使用最大整数长度if(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);//minCapacityisusuallyclosetosize,所以thisisawin:elementData=Arrays.copyOf(elementData,newCapacity);}grow(minCapacity)方法扩展数组，扩展大小为原数组的1.5倍，如果计算出来的扩展容量小于需要的容量，则扩展大小为需要的容量。可以看出第一次展开其实是10。如果扩展容量大于数组的最大容量，则调用hugeCapacity(minCapacity)方法将数组扩展到整数的最大长度，然后将elemetData数组指向新扩展的内存空间，并将元素复制到newspace，这里使用Arrays。copyOf(elementData,newCapacity)publicstaticint[]copyOf(int[]original,intnewLength){int[]copy=newint[newLength];System.arraycopy(original,0,copy,0,Math.min(original.length,newLength)));returncopy;}可以看到底层使用了System.arraycopy，这个复制过程比较消耗性能，所以建议在初始化的时候预估一个容量。》脑洞小结：用无参构造函数创建ArrayList后，第一次扩容容量为10，后续扩容1.5倍，底层调用System.arraycopy，这个拷贝过程很耗性能，所以是建议在初始化时预估一个容量。ArrayList删除元素ArrayList提供了两种删除元素的方式，可以通过index和element删除，两种删除方式类似，删除一个元素后，后面的元素一个一个地向前移动ArrayList.remove(intindex)source代码：publicEremove(intindex){rangeCheck(index);modCount++;EoldValue=elementData(index);intnumMoved=size-index-1;if(numMoved>0)System.arraycopy(elementData,index+1,elementData,index,numMoved);elementData[--size]=null;//cleartoletGCdoitsworkreturnoldValue;}删除元素时，会先判断索引是否大于ArrayList的大小，如果索引范围正确，则索引下一个元素position为索引位置赋值，将ArrayList的大小减-1，最后返回移除的元素。“脑补一下：删除之后，底层调用还是System.arraycopy，这个复制过程比较耗性能，所以我说尽量不要用ArrayList进行频繁的增删改查。”ArrayList遍历删除@OverridepublicvoidforEach(Consumeraction){Objects.requireNonNull(action);//预设一个expectedModCount值finalintexpectedModCount=modCount;@SuppressWarnings("unchecked")finalE[]elementData=(E[])this.elementData;finalintsize=this.size;//在遍历过程中取出来判断for(inti=0;modCount==expectedModCount&&i0)System.arraycopy(elementData,index+1,elementData,index,numMoved);elementData[--size]=null;//cleartoletGCdoitsworkreturnoldValue;}从代码中可以看出expectedModCount的一个值遍历的时候会先预置，然后判断遍历。如果不同，进程将被中断并报错。这个过程涉及一个快速失败机制。通常情况下，ArrayList是不允许遍历删除的。《脑洞小结：ArrayList通过预设值expectedModCount实现快速失败机制，避免多线程遍历删除或添加，遍历过程中增删元素》。集合的快速失败（fail-fast）是Java集合的一部分。一种错误检测机制，当多个线程对集合进行结构改变时，可能会出现fail-fast机制。迭代器在遍历时直接访问集合的内容，在遍历时使用一个modCount变量。如果在遍历过程中集合的内容发生变化，则modCount的值也会发生变化。每当迭代器在遍历下一个元素之前使用hashNext()/next()时，都会检查modCount变量是否为预期的modCount值，如果是则返回遍历；否则，将抛出异常并终止遍历。注意：这里的异常抛出条件是检测条件modCount!=expectedmodCount。如果在集合发生变化时修改后的modCount值只是设置为expectedmodCount值，则不会抛出异常。因此，您不能根据是否抛出此异常来编写并发操作。此异常仅建议用于检测并发修改错误。场景：java.util包下的集合类failfast，多线程下不能并发修改（迭代修改）。》No-brainersummary：我们每天看到的ConcurrentModificationException其实就是触发了fastfailure机制的表现，方法也很简单：遍历的时候给modCount设置一个backupexpectedModCount。如果有多个线程在运行，那么就会肯定会导致modCount被改变，所以很简单，每次遍历检查modCount变量是否为expectedModCount就可以了，如果不是就说明已经被改变了，那我不管了，我就报错了。fail-safe集合容器采用fail-safe机制，遍历时不直接访问集合内容，而是先复制原始集合内容，在复制后的集合上遍历。原理：由于迭代时遍历原始集合的副本，遍历过程中对原集合所做的修改无法被迭代器检测到，因此不会触发ConcurrentModificationException。缺点：复制内容的好处是避免了ConcurrentModificationException，但同样，迭代器无法访问修改后的内容，即迭代器遍历的是开始遍历那一刻得到的集合的副本。在遍历过程中，原始迭代器不知道集合的变化。场景：java.util.concurrent包下的容器是safetofail，可以在多线程下并发使用和修改。”没有记忆的总结：那为什么不怕并发容器呢？很简单，因为采用了安全失效机制，遍历的时候直接复制一份，这样就不会被触发。”使用ArrayList的subList()需要注意的事情publicListsubList(intfromIndex,inttoIndex){subListRangeCheck(fromIndex,toIndex,size);returnnewSubList(this,0,fromIndex,toIndex);}SubList(AbstractListparent,intoffset,intfromIndex,inttoIndex){this.parent=parent;this.parentOffset=fromIndex;this.offset=offset+fromIndex;this.size=toIndex-fromIndex;this.modCount=ArrayList.this.modCount;}subList()返回结果不能强制为ArrayList类型，因为该方法本质上是创建了内部类SubList的实例，SubList是AbstractList的实现类，并没有继承自ArrayList。从上面的源码可以看出，父类是通过parent属性指定的，直接引用原始List，返回父类的局部视图，只是指定要使用的元素范围fromIndex(包括）、endIndex（排除））。那么，如果对其原List或者子List进行数据修改，就会相互影响。如果对原有List进行结构修改，会踩到Fast-fail，报错时会抛出异常ConcurrentModificationException。ArrayListiterator看看迭代器遍历和删除相关的源码publicbooleanhasNext(){returncursor!=size;}@SuppressWarnings("unchecked")publicEnext(){//同样判断modCount!=expectedModCount，如果是不同，会报错cursor=i+1;return(E)elementData[lastRet=i];}publicvoidremove(){if(lastRet<0)thrownewIllegalStateException();checkForComodification();try{ArrayList.this.remove(lastRet);游标=lastRet;lastRet=-1;//这里删除ExpectedModCount=modCount;}catch(IndexOutOfBoundsExceptionex){thrownewConcurrentModificationException();}}通过代码我们也可以看出ArrayList的迭代器是支持遍历删除的，因为会重新赋值删除后为expectedModCount。ArrayList和LinkedList的优缺点其实就是数组和链表的优缺点。ArrayList的优点是支持随机访问，get(i)的时间复杂度为O(1)。缺点是需要扩容，复制数组，内部插入数据。数据需要移动，插入删除性能较差；对于LinkedList，优点是理论上容量是无限的，没有扩容，可以方便地插入和删除数据（性能损失在查找），缺点是不能随机访问。,get(i)需要遍历。好像是反过来的，所以在实际开发中很容易区分，是频繁查找还是频繁增删改查。频繁查找就用ArrayList，频繁增删就用LinkedList。