ArrayList是我们使用频率非常高的一个集合，也是集合中相对比较简单的集合。是List接口的主要实现类。一般面试的时候经常会问到ArrayList和LinkedList的区别。
ArrayList: 底层是数组实现的，查找快，增删慢。
LinkedList: 底层是链表实现的，增删快，查找慢。
一.类结构
ArrayList是集合的一种，集合的最顶端抽象接口为Collection, Collection下面又有两个子接口，一个是List,一个是Set， List和Set的区别也经常别被问到。
List: 数据是有序的，可以根据序号获取元素，List中的数据是可以重复的
Set: 数据是无序的，并且数据是不可重复的（是否重复是根据hashCode和equals方法结果决定）
List下的常用子类为： ArrayList, LinkedList, Vector.
Set下的常用子类： HashSet.
上面说的结构只是对List结构的一个简单描述。一个相对完成的类结构图如下：
这里可以更加清晰的看出ArrayList的结构，其中最主要的就是实现了List接口。那么我们简单的列一下List接口中 都有哪些方法。
intsize(); booleanisEmpty(); booleancontains(Objecto); Iterator<E>iterator(); Object[] toArray(); <T>T[] toArray(T[] a); booleanadd(Ee); booleanremove(Objecto); booleancontainsAll(Collection<?>c); booleanaddAll(Collection<?extendsE>c); booleanaddAll(intindex, Collection<?extendsE>c); booleanremoveAll(Collection<?>c); voidclear(); booleanequals(Objecto); inthashCode(); Eget(intindex); Eset(intindex, Eelement); voidadd(intindex, Eelement); Eremove(intindex); intindexOf(Objecto); intlastIndexOf(Objecto); ListIterator<E>listIterator(); ListIterator<E>listIterator(intindex); List<E>subList(intfromIndex, inttoIndex);
这你我把一些默认方法去掉了，因为看起来有点乱，其余的就是ArrayList中需要实现的方法了。这里边的大部分方法，我相信大家应该都使用过。而由于List是有序的，有序的意思就是我们可以通过编号来操作集合中的元素，所以上面有很多的方法都是可以传入 index参数的，就是直接根据编号来操作集合。
二. 构造方法
ArrayList中的构造方法总共有三个。其中两个应该是我们经常使用的。
publicArrayList(intinitialCapacity); publicArrayList(); publicArrayList(Collection<?extendsE>c);
这相当于我们可以通过三种方式来构建一个ArrayList集合
publicclassTest{ publicstaticvoidmain(String[] args){ // 无参构造List<String>list1=newArrayList<>(); // 传入初始化容量List<String>list2=newArrayList<>(3); // 传入一个集合List<String>list3=newArrayList<>(list1); } }
这里边第一种方式应该是我们最长使用的，当然也是最不负责任的。第二种方式是编码规范的要求我们这么写的，传入一个初始化的容量。这么做的目的主要是防止向集合中添加数据时，由于集合扩容导致的性能下降问题。所以建议我们在创建集合的时候，最好就根据我们的需求，合理分配出集合的容量大小。第三种是直接传入一个Collection ,要注意，是一个Collection ,也就是List也行，Set也行，这种方法会把Collection直接转为数组，存储到创建的集合中。
三. ArrayList原理
介绍完了这几个构造方法，我们先来讲讲ArrayList的原理。
Q1：ArrayList为什么可以存储元素？
其实他的本质就是一个Object[] , 我们每次向List中添加一个元素，他都会把元素存储到他的一个Object[] 中。那么问题是，我创建一个多大的数组合适呢？ 这就涉及到了一个概念叫做 容量 (Capacity) ,所以刚刚的第二种构造方法，传入一个初始化的数组容量，就是代表我的Object[] 的初始化大小是多少。比如我传入了一个10， 那就代表创建了一个10个长度的Object[].
Q2: 如果存储的数据超出了Object[]的长度范围改怎么办?
假设我们通过List list = new ArrayList(10); 指定了集合的初始化长度，那我们向里边添加的元素个数可以超过10个么。答案是肯定的，也就是我们添加超过10个元素的时候，集合也不会报错，原因是什么的，就是ArrayList的自动扩容原理。当我们向集合中添加元素的时候，集合首先会判断当前的数组容量能否容纳得下所需添加的元素，如果容纳不下，就会触发自动扩容机制。而自动扩容机制的核心原理就是创建一个更大的Object[] ,然后将原来的数组中的元素拷贝到这个更大的数组中来，而往往这个过程是比较影响性能的，尤其是集合中的数据量很大的时候，所以我们前面提到了，尽量直接指定数据的容量（在我们可以判断所需大小的时候），目的就是为了减少他的自动扩容，提升效率。
Q3: capacity和size的区别？
这个概念很重要，大家一定要搞清楚这两个概念的区别，才能够更好的理解集合。
先说capcity, 我们上面提到了，他指的就是我用来存储数据的数组的大小。而size只的是集合中存入的元素个数。
什么意思呢，比如我capacity是10，就代表我的集合中数组的长度是10个，然后我向集合中add一个元素，那么size就是1。 size代表的是集合中存储的元素的真正个数。 当集合中的size即将超过capacity的时候，就会出发集合的扩容操作，capacity会继续增大。
Q4: ArrayList的扩容机制*
这个也是面试中会经常别问到的话题，集合的默认容量是多少，什么时候触发扩容，扩成了多大等等，接下来我们就来详细的分析一下。
1. 首先介绍一下ArrayList类中的五个核心成员变量。
publicclassArrayList<E>extendsAbstractList<E>implementsList<E>, RandomAccess, Cloneable, java.io.Serializable{ privatestaticfinallongserialVersionUID=8683452581122892189L; // 默认容量privatestaticfinalintDEFAULT_CAPACITY=10; // 空数组，当capacity = 0是使用的privatestaticfinalObject[] EMPTY_ELEMENTDATA= {}; // 空数组，无参构造方法使用privatestaticfinalObject[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA= {}; // 核心数组，用于存储数据transientObject[] elementData; // non-private to simplify nested class access// 集合中实际元素个数 privateintsize; }
这几个成员变量都是非常重要的。首先我们先来介绍一下这里有两个空的Object数组。一个是EMPTY_ELEMENTDATA，还有一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
2. EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA区别
这两个都是空数组，为什么要定义两个呢，有什么区别的？其实在注解中已经给出了解释。
这里在解释一下。其实主要区别就是这样的两个集合。
Listlist1=newArrayList(0); Listlist2=newArrayList();
这两种集合，第一种情况，集合中的数组使用的就是EMPTY_ELEMENTDATA， 第二种情况使用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA。 我们也可以通过代码清晰的看出来。
主要就是对应有参构造方法中的0，和无参构造方法。
那么为什么非要用两个集合呢。主要原因在于，使用无参构造的集合（上述示例中的list2）是要扩容为默认长度（10）的数组，而指定长度的数组是不需要默认长度的。所以要用两个集合。详见计算容量的方法：
这里要注意一下，我是用的JDK8的代码和JDK7略有区别。就是数组在什么时候开辟空间。从jdk8开始，集合不是你new完了就把空间创建出来的，从代码也可以看出来，我们new完的集合（0参和无参），实际上就给了一个空数组，只有当我们向集合中添加元素的时候，才会根据长度初始化数组的长度。这样做的目的实际就是一个懒加载的思想，避免内存的浪费。
3. 扩容到底扩多大
那么接下来我们就来研究下，扩容到底扩成多大。先总结下我们创建数组的构造方法：
// 初始化了一个空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATAListlist1=newArrayList(); // 初始化了一个空数组： EMPTY_ELEMENTDATAListlist2=newArrayList(0); // 初始化了一个10个长度的数组Listlist3=newArrayList(10);
而当我们向list1中添加元素的时候，就会将其初始化成默认的长度，也就是10.
// 默认容量privatestaticfinalintDEFAULT_CAPACITY=10;
那么什么时候扩容呢: 看源码：
publicbooleanadd(Ee) { ensureCapacityInternal(size+1); // Increments modCount!!elementData[size++] =e; returntrue; }
添加元素的时候，会使用size+1的值去计算是否需要扩容：
privatevoidensureCapacityInternal(intminCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
此时的minCapacity 的值就是 size + 1; 调用calculateCapacity 得出所需容量
privatestaticintcalculateCapacity(Object[] elementData, intminCapacity) { if (elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { returnMath.max(DEFAULT_CAPACITY, minCapacity); } returnminCapacity; }
这个时候就比较重要了， 当我们的集合是通过无参构造初始化的时候，他的容量是当前size+1 和默认长度的最大值。也就是当我们向集合中添加元素的时候，如果元素个数小于10，那么这个结果就是10， 如果元素个数大于10了，就取当前的最大值。
privatevoidensureExplicitCapacity(intminCapacity) { modCount++; // overflow-conscious codeif (minCapacity-elementData.length>0) grow(minCapacity); }
如果通过上面得到的值已经大于数组的长度了，就代表数组已经装不下了，这时候就会调用grow方法进行扩容。
// 扩容核心方法privatevoidgrow(intminCapacity) { // overflow-conscious codeintoldCapacity=elementData.length; intnewCapacity=oldCapacity+ (oldCapacity>>1); if (newCapacity-minCapacity<0) newCapacity=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); }
怎么扩的呢，新的容量为 ：oldCapacity + (oldCapacity >> 1); 其实就是原长度的1.5倍，如果你原来是默认的10个长度，扩容后会变为15个。但是也不是最终结果。如果扩完的长度还不够，那么就要多长给多长了。如果扩完的长度大于 MAX_ARRAY_SIZE（这个值是int的最大值-8）,就将数组扩容为int的最大值，如果minCapacity为负就代表内存溢出了。这里可能有人想不通，就是扩容后的长度怎么可能不够呢，要注意我们的集合操作不一定都是一个一个添加的，可以通过addAll方法添加一堆元素，那么此时就可能导致你扩容后还是装不下，那就直接初始化为所需长度。
privatestaticinthugeCapacity(intminCapacity) { if (minCapacity<0) // overflowthrownewOutOfMemoryError(); return (minCapacity>MAX_ARRAY_SIZE) ?Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
最后再把原来的数组中数据拷贝到新的数组里即可。扩容操作完毕。有点复杂，没懂的多读几遍。
这里基本上就已经是ArrayList中最核心的方法了。剩下的就是一下常用的api都比较好理解了。
四. 常见Api解读
掌握了核心原理，我们就再来读读其他的方法。就比较好理解了。
1. size() 方法，获取集合中元素个数，这里一定注意和capacity的区别。
// 就是一个get方法 publicintsize() { returnsize; }
2. get方法和set方法
publicEget(intindex) { rangeCheck(index); returnelementData(index); } publicEset(intindex, Eelement) { rangeCheck(index); EoldValue=elementData(index); elementData[index] =element; returnoldValue; }
这里注意一下： 凡是跟index相关的方法，都会先校验一下index是否合法，否则会出现一个我们非常眼熟的异常：
privatevoidrangeCheck(intindex) { if (index>=size) thrownewIndexOutOfBoundsException(outOfBoundsMsg(index)); } privatevoidrangeCheckForAdd(intindex) { if (index>size||index<0) thrownewIndexOutOfBoundsException(outOfBoundsMsg(index)); }
3. addAll方法： 这个方法也涉及到扩容问题。跟上面的差不多：
publicbooleanaddAll(Collection<?extendsE>c) { Object[] a=c.toArray(); intnumNew=a.length; ensureCapacityInternal(size+numNew); // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew); size+=numNew; returnnumNew!=0; }
这里注意下，判断是否扩容的长度就是size + numNew； 单个的时候用的是 size + 1去判断是否扩容。
4. modCount解释：
我们在代码中会随处发现一个变量modCount,比如扩容的时候，remove的时候，set,clear等方法被调用的时候，都有一个modCount++；
这个变量是干什么用的呢，其实就是用来记录集合被操作的次数。记录这个东西有啥用的，主要就是在做序列化的时候，也就是往出写的时候。在ArrayList中有一个writeObject方法：
privatevoidwriteObject(java.io.ObjectOutputStreams) throwsjava.io.IOException{ // Write out element count, and any hidden stuffintexpectedModCount=modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone()s.writeInt(size); // Write out all elements in the proper order.for (inti=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount!=expectedModCount) { thrownewConcurrentModificationException(); } }
写的时候会判断前后的modCount是否一致，如果不一致代表对象被操作过，就会报ConcurrentModificationException。
5.indexOf方法： 返回对象在数组中的位置，这里是使用equals方法比较的：
publicintindexOf(Objecto) { if (o==null) { for (inti=0; i<size; i++) if (elementData[i]==null) returni; } else { for (inti=0; i<size; i++) if (o.equals(elementData[i])) returni; } return-1; }
这个应该比较好理解，就是遍历数组，查找对象，返回索引值。
6. clear方法：
publicvoidclear() { modCount++; // clear to let GC do its workfor (inti=0; i<size; i++) elementData[i] =null; size=0; }
将数组中所有元素置为null, size改为0
剩下的方法就不一一过了。 全篇代码中没有出现 synchronized关键字，也间接证明该类线程不安全
