ArrayList集合源码分析

内容如有错误或者其他需要注意的知识点，欢迎指正或者探讨补充，共同进步。

一、字段分析

//默认初始化容量。这里和Vector一样，只是Vector,没有用一个变量，而是调用无参构造函数时，直接塞了个10。
private static final int DEFAULT_CAPACITY = 10;
//这里给出了两个空数组。有两个疑问，1.为什么给空数组2.为什么还给了两个
//1。在我们创建空的ArrayList集合时，为了避免创建多个空的数组，而换成统一用这里的口空数组代替，达到了节约内存和提高效率。
//2。为了区分我们在构造集合时，是用的有参构造函数，还是无参函数。不同的构造也会带来扩容机制的不同。
//	-	无参构造函数，会使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA 数组，在第一次添加元素是，扩容后的容量是10。
//	-	有参构造函数，如果传入的是0，则是用EMPTY_ELEMENTDATA ，扩容是1.5的扩容。0->1->2->3->4->6->9->13，如果数据很少
//		少到比10还小，能够降低内存消耗的。
//所以又有了疑问，那为什么不用一个就可以了呢，第一次扩容都用容量10。
//	-	源码上面的注释是：Shared empty array instance used for default sized empty instances. 
//		We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.
//		这是用于默认大小的空实例的共享空数组实例。我们将其与EMPTY_ELEMENTDATA区分开来，以便在添加第一个元素时知道要扩充多少空间。
//		同时如果有那种添加很少元素的需求，元素数量小于10，这样做是可以减少内存消耗的，达到更适配相应需求的目的。
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//用来存储数据的数组
transient Object[] elementData;//实际存储了数据的个数
private int size;

二、构造方法分析

• 从构造方法可以看出，我们在创建 ArrayList 时，并没有更新容量，就是用的默认容量10。

public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {//如果初始容量为0，则空数组代替，size = 0this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}public ArrayList() {//如果没有指定容量，则用默认的空数组代替this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}public ArrayList(Collection<? extends E> c) {//toArray()通常会将泛型擦除掉，比如应该是List<Integer> 会变成 Objects[];//为何这样做呢？即便你不擦除掉，在代码编译时也会将泛型擦除掉，所以为了提高效率，加快编译速度。elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)//这里为什么要加这样的判断呢？因为通常来说c.toArray();已经返回了Object[],但如果这个是个人实现的//比如里面调用了c.toArray(Integer[]);则会返回Integer[],所以这里额外判断下//为了确保elementData 为Object数组，如果使用系统提供的toArray()方法，会返回if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}

三、方法分析

• 添加元素 方法，是非线程安全的方法。并且在添加元素的时候会校验是否需要扩容。

//向已有元素的末尾添加元素
public boolean add(E e) {//判断是否需要扩容，所需容量最少为：已有元素数量 + 1//但里面其实会判断，存储数据的数据是否为空，空则需最小容量为 DEFAULT_CAPACITY //否则取Math.max（已有元素数量 + 1，DEFAULT_CAPACITY ），可向下看ensureCapacityInternal(size + 1);  // Increments modCount!!//已有元素的末尾添加上新元素elementData[size++] = e;//添加成功return true;}private void ensureCapacityInternal(int minCapacity) {//判断扩容之前，判断所需的最小容量，而calculateCapacity(elementData, minCapacity) 就是判断//所需的容量，然后拿这个所需的最少容量去判断是否需要扩容。ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {//正如上面所说的，如果数组为空，则所需取其中较大值，这不难理解//这里也是第一次扩容采用什么决策作出了判断，如果是调用无参构造函数，第一次扩容是10。//如果是有参，且参数0，则1.5倍扩容，具体原因，上面参数介绍时详细说了。if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}
//这时候我们拿到了我们所需要的最小容量，来判断是否需要扩容了
private void ensureExplicitCapacity(int minCapacity) {//从Vector源码中我们之前到，这个是继承自Abastrack，用来记录版本号，防止迭代过程中集合被修改了，因为迭代器创建时，//会保存创建那一时刻集合的版本号，迭代的过程的会比较自己保存的版本号和集合的版本号，从而判断跌倒过程中是否被修改。//这里的作用是一样的。modCount++;// overflow-conscious code//如果我们所需要的最小容量比elementData数组长度还大，那必须要扩容了，不然要下标越界了。//如果是我们第一次添加元素，从构造函数可以，elementData是个空数组，这里也会扩容。 10 - 0 > 0// ！！！从这里可以看出，在添加元素时，如果元素数量大于数组长度 才会触发扩容，就是数组已经被塞满了，不是说达到数组//容量的百分之多少。if (minCapacity - elementData.length > 0)grow(minCapacity);}//到这里就是确定要扩容了，并且我们拿到了所需的最小容量，用来判断该如何扩容
private void grow(int minCapacity) {// overflow-conscious code//记录当前数组长度int oldCapacity = elementData.length;//记录扩容后的数组长度，先按1.5倍来扩容//oldCapacity >> 1 相当于 oldCapacity / 2//那自己的一般 + 自己，不就是自己原来的1.5倍。//至于最后是否会用这个值了，还需后面判断。int newCapacity = oldCapacity + (oldCapacity >> 1);//如果扩容后的容量还是不够，则先用所需的最小容量最为新容量的值。//你可能会疑问，我们添加元素都是一个一个添加的，按理说不可能扩容后容量还达不到需要的呀。//然后确实可能达不到，如果使用的有参构造函数，且参数为0，那么第一次添加元素，这里传入的值就是1，//但是初始容量为0，1.5扩容后还是0，显然不够的，这是后就会扩容成容量为1的数组。其实第二次添加元素，//扩容还是会不够，注意我说的是开始调用有参构造函数且参数0，因为无参构造，第一次扩容为10，这里不会触发。//还有一个可能是newCapacity 溢出了变成负数。则 新容量就是 minCapacity 了，即数组扩容到length + 1；if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//如果新容量值要溢出了，注意是快要溢出，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;if (newCapacity - MAX_ARRAY_SIZE > 0)//这时候我们继续确定新容量到底该多少newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win://到这里新容量就去确定好了，去做扩容啦。//这个方法会创建一个新的数组，将旧的数组按索引依次赋值到新数组上，未填充到的为数据类型的默认值，//如 int 为0，Object 为 null.//同时这是消耗新能的操作，涉及到新数组的创建和所有元素的赋值。elementData = Arrays.copyOf(elementData, newCapacity);}
//和 Vecotor.class 源码一样的，如果快要溢出了，则直接给所能给的容量的极限。
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}//向指定索引位置添加元素
public void add(int index, E element) {rangeCheckForAdd(index);//判断是否需要扩容，上面分析过了ensureCapacityInternal(size + 1);  // Increments modCount!!//上面已经进行过扩容动作了，这段代码看起来好像没必要。//上面看见的Arrays.copyOf 其实底层最终调用就是这个方法，达到扩容的目的。//难道这也是扩容？？此不是多此一举//首先依次介绍下这个方法参数含义//src：源数组，要将其内容复制到目标数组中。//srcPos：源数组中开始复制的位置。//dest：目标数组，源数组的内容将复制到该数组中。//destPos：目标数组中开始复制的位置。//length：要复制的元素个数。//知道了含义就很好理解了，是把将要插入的位置，把该位置以及之后的所有元素往后移动一格。。。//从这里也可看出，ArrayList 向指定下标插入元素效率低下，时间复杂度O(n),并且并不是覆盖掉//该位置原先的元素，而是统统靠后移。System.arraycopy(elementData, index, elementData, index + 1,size - index);//好了，这个位置被腾出位置了，可以插了。elementData[index] = element;size++;}

• 获取元素方法：这个方法没啥好说的。

  //根据索引获取元素
  public E get(int index) {//检查索引是否越界rangeCheck(index);//返回该位置值return elementData(index);}
  //检查索引是否越界
  private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
  //返回index索引位置的值
  E elementData(int index) {return (E) elementData[index];}
  

• 扩容方法：介绍添加元素方法时说过了。

• 移除元素方法：可以根据下标位置移除元素，也可根据元素值移除元素。和Vector源码很相似

//根据索引位置删除元素(可以发现，这里和Vector 的源码一模一样)
public E remove(int index) {//检查索引是否越界rangeCheck(index);//版本号+1modCount++;//得到该索引位置的值E oldValue = elementData(index);//需要移动的元素数量，就是你讲index位置的元素删了，那这个元素后院的所有的元素都要前移，这个值就是需要//移动的元素数量即index后面元素的数量int numMoved = size - index - 1;//判断index后面是否有值if (numMoved > 0)//将要移动的元素前移，其实是吧那个要删除的元素覆盖了从而达到了删除元素的目的。System.arraycopy(elementData, index+1, elementData, index,numMoved);//为什么要删除末尾元素呢，因为如果index 是最后以为元素，那么就不会触发元素前移，所以这里//多一步，将末尾元素设置为null，就是为了处理这一特殊情况。所以如果index 后面有值，这一步是//多余的，末尾已经是null了。                     elementData[--size] = null; // clear to let GC do its work//返回被删除的元素元素值return oldValue;}//根据元素值删除元素
public boolean remove(Object o) {//从这里也可看出,ArrayList是允许删除null元素值的，同时有相同值元素是，删除的是最靠前的那个。//我们在分析Vector删除源码时，在获取o的下标位置时，会调用indexOf方法，和这里的判断是一样的。//同时有个疑问？这个难道不可以统一写成elementData[index].equals(o)不就行了吗，就可以处理o是null或不是null的情况，//且不会报错,且能达到相同效果，那这个判断不是冗余了嘛。你在说什么胡话？刚刚才说的ArrayList是允许添加null的，如果//遍历获取到的元素如果是null那不就是报错了吗？所以这里这样写，才可以避免传入的o是null，同时遍历获取到的//值也是null，从而判断报错的情况。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++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;}//和上面根据索引删除元素逻辑一样的，从这里可以看出，代码冗余了(*￣︶￣)
private void fastRemove(int index) {modCount++;int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its work}

• 迭代器设计：和Vector的一样，提供了两种的迭代器。Itr 和 ListItr。
  • 不同的是，ArrayList 的迭代器在迭代过程中是不上锁的，但是Vector上锁，所以是线程不安全的。
  • 相同是的都有版本号坚持机制，Itr迭代过程中不允许集合修改，而Listitr 允许修改。

//这里和Vector几乎相同，这里只标注不同的地方。
private class Itr implements Iterator<E> {int cursor;       // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no suchint expectedModCount = modCount;Itr() {}public boolean hasNext() {return cursor != size;}@SuppressWarnings("unchecked")public E next() {//和Vector 不同的是这里Vector会上锁，保证线程安全。checkForComodification();int i = cursor;if (i >= size)throw new NoSuchElementException();//这里和Vector不太一样。Vector 是没有这个判断的，感觉有个疑问，上面都判断了 i >= size 了，//那么能到这里 i 肯定 < size 了， 而size是实际存储数据的个数，即便数组塞满了，那也是 size = length，//怎么可能   i < size 却 i >= length，所以感觉这里判断多此一举了。//要知道，ArrayLIst是非线程安全的，你在迭代的过程中，是可能有并发操作，修改了容量了，而这里做了这样的判断//就是防止并发操作下，做下检查。//而这种机制就是fail_fast(快速失败，敲黑板)。这里也是做了双重检查，checkForComodification也是检查是否被修改//这里拿到 elementData 之后再次检查，尽量避免迭代过程中集合被修改。而Vector是加了锁的，锁的还是class对象//所以检查一次即可。//这里双重检查就可避免非线程安全问题了吗，但是不是，比如Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();//---------------------------------------------------    //比如你两次都检查过后，到了这里发生了修改，还是还会带来问题，不过概率降低了。cursor = i + 1;return (E) elementData[lastRet = i];}//这里逻辑 和 Vecotr的迭代器一样的，唯一区别少了把锁public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.remove(lastRet);cursor = lastRet;lastRet = -1;expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}@Override@SuppressWarnings("unchecked")public void forEachRemaining(Consumer<? super E> consumer) {Objects.requireNonNull(consumer);final int size = ArrayList.this.size;int i = cursor;if (i >= size) {return;}final Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length) {throw new ConcurrentModificationException();}while (i != size && modCount == expectedModCount) {consumer.accept((E) elementData[i++]);}// update once at end of iteration to reduce heap write trafficcursor = i;lastRet = i - 1;checkForComodification();}//检查版本是否发生变化final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}private class ListItr extends Itr implements ListIterator<E> {ListItr(int index) {super();cursor = index;}public boolean hasPrevious() {return cursor != 0;}public int nextIndex() {return cursor;}public int previousIndex() {return cursor - 1;}@SuppressWarnings("unchecked")public E previous() {checkForComodification();int i = cursor - 1;if (i < 0)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;//这里同样多了此检查结构是否变化if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i;return (E) elementData[lastRet = i];}//和Vector比少了把锁，逻辑一样的public void set(E e) {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.set(lastRet, e);} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}//这个也是一样的，同样少了把锁。public void add(E e) {checkForComodification();try {int i = cursor;ArrayList.this.add(i, e);cursor = i + 1;lastRet = -1;expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}}

四、总结

• ArraList 底层使用数组存储结构，删除或添加元素的效率时间复杂度O（n），效率低下。查找元素快 O（1）。
• 是线程不安全的数据结构，并发场景下可能带来非线程安全的问题。
• 扩容是按1.5来进行扩容，当然不是绝对的，比如第一次添加元素时，会判断调用的是那种构造函数，无参第一次扩容为10，有参且为0，扩容后为1。还有就是快要溢出的情况，当需要的容量 > MAX_ARRAY_SIZE,则新容量为Integer.MAA_VALUE。