一、ArrayList认识
概念
概念：ArrayList是一个其容量能够动态增长的动态数组。但是他又和数组不一样，下面会分析对比。它继承了AbstractList，实现了List、RandomAccess, Cloneable, java.io.Serializable。
RandomAccess接口，被List实现之后，为List提供了随机访问功能，也就是通过下标获取元素对象的功能。
实现了Cloneable, java.io.Serializable意味着可以被克隆和序列化。
最主要的还是看我化圈的部分
ArrayList的数据结构
分析一个类的时候，数据结构往往是它的灵魂所在，理解底层的数据结构其实就理解了该类的实现思路，具体的实现细节再具体分析。
ArrayList的数据结构是：
说明：底层的数据结构就是数组，数组元素类型为Object类型，即可以存放所有类型数据。我们对ArrayList类的实例的所有的操作底层都是基于数组的。
ArrayList源码分析
继承结构和层次关系
我们看一下ArrayList的继承结构：
- ArrayList extends AbstractList - AbstractList extends AbstractCollection
所有类都继承Object 所以ArrayList的继承结构就是上图这样
思考 为什么要先继承AbstractList，而让AbstractList先实现List？而不是让ArrayList直接实现List？
这里是有一个思想，接口中全都是抽象的方法，而抽象类中可以有抽象方法，还可以有具体的实现方法，正是利用了这一点，让AbstractList是实现接口中一些通用的方法，而具体的类， 如ArrayList就继承这个AbstractList类，拿到一些通用的方法，然后自己在实现一些自己特有的方法，这样一来，让代码更简洁，就继承结构最底层的类中通用的方法都抽取出来，先一起实现了，减少重复代码。所以一般看到一个类上面还有一个抽象类，应该就是这个作用
RandomAccess这个接口
我点进去源码发现他是一个空的接口，为啥是个空接口呢
RandomAccess接口是一个标志接口（Marker）
ArrayList集合实现这个接口，就能支持快速随机访问
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); } 复制代码
通过查看源代码，发现实现RandomAccess接口的List集合采用一般的for循环遍历，而未实现这接口则采用迭代器。 ArrayList用for循环遍历比iterator迭代器遍历快，LinkedList用iterator迭代器遍历比for循环遍历快， 所以说，当我们在做项目时，应该考虑到List集合的不同子类采用不同的遍历方式，能够提高性能！ 然而有人发出疑问了，那怎么判断出接收的List子类是ArrayList还是LinkedList呢？ 这时就需要用instanceof来判断List集合子类是否实现RandomAccess接口！
总结：RandomAccess接口这个空架子的存在，是为了能够更好地判断集合是否ArrayList或者LinkedList，从而能够更好选择更优的遍历方式，提高性能
ArrayList 类中的属性
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { // 版本号 private static final long serialVersionUID = 8683452581122892189L; // 缺省容量 private static final int DEFAULT_CAPACITY = 10; // 空对象数组 private static final Object[] EMPTY_ELEMENTDATA = {}; // 缺省空对象数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 元素数组 ArrayList中有扩容这么一个概念，正因为它扩容，所以它能够实现“动态”增长 transient Object[] elementData; // 实际元素大小，默认为0 private int size; // 最大数组容量 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; } 复制代码
构造方法
无参构造
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } 复制代码
此时ArrayList的size为空，但是elementData的length为1。第一次添加时，容量变成初始容量大小10（默认无参构造的容量就是10）
int参数构造
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); } } 复制代码
这个比较简单 进来判断是否大于0，如果大于0 就创建一个传进来大小的一个数组， 如果为0就是空数组
collection参数构造函数
public ArrayList(Collection<? extends E> c) { // 指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排 // 这里主要做了两步：1.把集合的元素copy到elementData中。2.更新size值。 elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } } 复制代码
把集合的元素重新放到新的集合里面，然后更新实际容量的大小
具体方法
add方法
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { // 扩容操作，稍后讲解 ensureCapacityInternal(size + 1); // Increments modCount!! // 将元素添加到数组尾部 elementData[size++] = e; return true; } 复制代码
第一步 扩容操作 第二步 往尾部添加一个元素 跟着往下看
ensureCapacityInternal(xxx); 确定内部容量的方法
private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { //看，判断初始化的elementData是不是空的数组，也就是没有长度 //因为如果是空的话，minCapacity=size+1；其实就是等于1，空的数组没有长度就存放不了，所以就将minCapacity变成10，也就是默认大小，但是带这里，还没有真正的初始化这个elementData的大小。 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //确认实际的容量，上面只是将minCapacity=10，这个方法就是真正的判断elementData是否够用 ensureExplicitCapacity(minCapacity); } 复制代码
ensureExplicitCapacity(xxx)；
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code //minCapacity如果大于了实际elementData的长度，那么就说明elementData数组的长度不够用，不够用那么就要增加elementData的length。这里有的读者就会模糊minCapacity到底是什么呢，这里给你们分析一下 /*第一种情况：由于elementData初始化时是空的数组，那么第一次add的时候，minCapacity=size+1；也就minCapacity=1，在上一个方法(确定内部容量ensureCapacityInternal)就会判断出是空的数组，就会给   将minCapacity=10，到这一步为止，还没有改变elementData的大小。  第二种情况：elementData不是空的数组了，那么在add的时候，minCapacity=size+1；也就是minCapacity代表着elementData中增加之后的实际数据个数，拿着它判断elementData的length是否够用，如果length 不够用，那么肯定要扩大容量，不然增加的这个元素就会溢出。 */ if (minCapacity - elementData.length > 0) //arrayList能自动扩展大小的关键方法就在这里了 grow(minCapacity); } 复制代码
grow(xxx); arrayList核心的方法，能扩展数组大小的真正秘密。
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //将扩充前的elementData大小给oldCapacity int newCapacity = oldCapacity + (oldCapacity >> 1);//newCapacity就是1.5倍的oldCapacity if (newCapacity - minCapacity < 0)//这句话就是适应于elementData就空数组的时候，length=0，那么oldCapacity=0，newCapacity=0，所以这个判断成立，在这里就是真正的初始化elementData的大小了，就是为10.前面的工作都是准备工作。 newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0)//如果newCapacity超过了最大的容量限制，就调用hugeCapacity，也就是将能给的最大值给newCapacity newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: //新的容量大小已经确定好了，就copy数组，改变容量大小咯。 elementData = Arrays.copyOf(elementData, newCapacity); } 复制代码
hugeCapacity();
//这个就是上面用到的方法，很简单，就是用来赋最大值。 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); //如果minCapacity都大于MAX_ARRAY_SIZE，那么就Integer.MAX_VALUE返回，反之将MAX_ARRAY_SIZE返回。因为maxCapacity是三倍的minCapacity，可能扩充的太大了，就用minCapacity来判断了。 //Integer.MAX_VALUE:2147483647 MAX_ARRAY_SIZE：2147483639 也就是说最大也就能给到第一个数值。还是超过了这个限制，就要溢出了。相当于arraylist给了两层防护。 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } 复制代码
总结一下扩容过程
- 1.判断是否需要扩容，如果需要，计算需要扩容的最小容量
- 2.如果确定扩容，就执行grow(int minCapacity)，minCapacity为最少需要的容量
- 3.第一次扩容是的容量大小是原来的1.5倍
- 4如果第一次 扩容后容量还是小于minCapacity,那就扩容为minCapacity
- 5.最后，如果minCapacity大于最大容量，则就扩容为最大容量
