基于ArrayList常用方法的源码全面解析_Java教程

我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问题早已烂熟于心，前者基于数组实现，后者基于链表实现；前者随机方法速度快删除和插入指定位置速度慢，后者随机访问速度慢删除和插入指定位置速度快；两者都是线程不安全的；列表与数组之间的区别等等。

列表与数组之间很大的一个区别就是：数组在其初始化就需要给它确定大小不能动态扩容，而列表则可以动态扩容。ArrayList是基于数组实现的，那么它是如何实现的动态扩容呢？

对于ArrayList的初始化有三种方式：

对于第一种默认的构造方法，ArrayList并没有初始化容量大小，而是将列表的元素数据引用指向了一个空数组。

1 2	`private` `transient` `Object[] elementData;` `private` `static` `final` `Object[] EMPTY_ELEMENTDATA = {};`

									//1.ArrayList默认构造方法

									public ArrayList() {  

									  super();

									  this.elementData = EMPTY_ELEMENTDATA;

									}

与JDK1.6不同的是，JDK1.6即时是在调用默认的构造方法时，也会初始化容量大小，JDK1.7当然会带来一定的好处，如果初始化而不使用就白白浪费了存储空间，等到添加的时候再初始化容量大小即可。

									//JDK1.6 ArrayList

									public ArrayList() {

									  this(10);

									}

对于第二种构造方法，则直接创建一个指定大小的数组，将列表的元素数组引用指向它。

									//2.ArrayList带有初始化大小的构造方法

									public ArrayList(int initialCapacity) {

									  super();

									  if (initialCapacity < 0)

									    throw new IllegalArgumentException("Illegal Capacity: "+

									                      initialCapacity);

									  this.elementData = new Object[initialCapacity];

									}

第三种构造方法，能将一个集合作为参数传递，但集合中的元素必须继承自ArrayList中的元素。

									//3.可将一个集合作为ArrayList的参数构造成ArrayList

									public ArrayList(Collection<? extends E> c) {

									  elementData = c.toArray();  //将集合转换为数组

									  size = elementData.length;  //集合中的元素大小

									  // c.toArray might (incorrectly) not return Object[] (see 6260652) 这里是个bug，参考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652

									  if (elementData.getClass() != Object[].class)

									    elementData = Arrays.copyOf(elementData, size, Object[].class);

									}

上面提到了一个bug，也就是说将一个集合转换为数组的时候可能错误地不会返回Object[]，举例说明。

									package com.algorithm.sort;

									import java.util.ArrayList;

									import java.util.Arrays;

									import java.util.List;

									/**

									 * bug编号:6260652。toArray有可能不会返回Object[]

									 * Created by yulinfeng on 2017/6/26.

									 */

									public class Test {

									  public static void main(String[] args) {

									    correctly();

									    incorrectly();

									  }

									  /**

									   * 返回Object[]

									   */

									  private static void correctly() {

									    List<String> list = new ArrayList<String>();

									    list.add("test");

									    System.out.println(list.getClass());

									    Object[] objArray = list.toArray();

									    System.out.println(objArray.getClass());

									  }

									  /**

									   * 不返回Object[]

									   */

									  private static void incorrectly() {

									    List<String> list = Arrays.asList("test");

									    System.out.println(list.getClass());

									    Object[] objArray = list.toArray();

									    System.out.println(objArray.getClass());

									  }

									}

运行结果：

基于ArrayList常用方法的源码全面解析

上面的这个例子就说明了toArray并不一定总是返回Object[]，返回的Object[]时，Object元素就不能插入，故JDK在“6260652”中修复了这个bug。

接下来看元素插入以及删除等其它方法。

									//ArrayList#add

									public boolean add(E e) {

									  ensureCapacityInternal(size + 1); //确保容量是否充足

									  elementData[size++] = e;  //将元素添加至数组

									  return true;

									}

									//ArrayList#ensureCapacityInternal

									private void ensureCapacityInternal(int minCapacity) {

									  if (elementData == EMPTY_ELEMENTDATA) {

									    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);   //如果此时还没有初始化列表容量大小，则对其初始化，默认容量为10

									  }

									  ensureExplicitCapacity(minCapacity); //检查容量是否充足

									}

									//ArrayList#ensureEcplicitCapacity

									private void ensureExplicitCapacity(int minCapacity) {

									  modCount++;  //注意此变量

									  if (minCapacity - elementData.length > 0)

									    grow(minCapacity);  //容量不够则进行扩容

									}

在ensureEcplicitCapacity方法中有一个modCount（modify count）变量进行了自增。

1	`protected` `transient` `int` `modCount =` `0;`

这个变量不仅在add方法中会自增，只要是在增加或者删除等对ArrayList结构产生了变化都会记录加1，这样做的原因和多线程下Iterator迭代器遍历有关。在AbstractList$Itr中也有一个变量与之对应。

1 2	`//AbstractList$Itr` `int` `expectedModCount = modCount;`

在AbstractList$Itr#next中调用了checkForComodification方法。

									//AbstractList$Itr#checkForComodification

									final void checkForComodification() {

									  if (modCount != expectedModCount)

									    throw new ConcurrentModificationException();

									}

如果当前运行环境是单线程，不论对列表进行何种操作何时增加、修改、删除等，excpectedModCount总是会等于modCount，但是如果当前运行环境是多线程，很有可能一个线程在迭代遍历，而另一个线程在对其进行新增或者修改等，JDK则不允许这么做，此时则会抛出ConcurrentModificationException异常，这就是modCount变量在此起的作用。

回到ArrayList#add方法，当列表容量不足时，此时会调用grow方法进行扩容。

									//ArrayList#grow

									private void grow(int minCapacity) {

									  int oldCapacity = elementData.length;

									  int newCapacity = oldCapacity + (oldCapacity >> 1);  //扩容策略为，每次新增容量的大小为旧容量的一半。也就是说如果默认容量为10，则第一次扩容大小为10 / 2 = 5，第二次扩容大小为15 / 2 = 7。

									  if (newCapacity - minCapacity < 0)

									    newCapacity = minCapacity;  //扩容策略扩得太小

									  if (newCapacity - MAX_ARRAY_SIZE > 0)  //扩容策略扩得太大，大于最大数组大小时，最多等于Integer.MAX_VALUE

									    newCapacity = hugeCapacity(minCapacity);

									  elementData = Arrays.copyOf(elementData, newCapacity);

									}

ArrayList获取指定索引位置的元素get方法。

									public E get(int index) {

									  rangeCheck(index);  //检查索引是否越界

									  return elementData(index);

									}

由于ArrayList是由基于数组实现，故此方法较为简单，判断是否越界，没有则根据数组下标来索引返回元素即可。remove方法删除指定位置的元素。　

									//ArrayList#remove

									public E remove(int index) {

									  rangeCheck(index);  //检查索引是否越界

									  modCount++;  //记录modCount，上面已提及

									  E oldValue = elementData(index);  //取出指定索引元素

									  int numMoved = size - index - 1;  //移动的元素个数

									  if (numMoved > 0)

									    System.arraycopy(elementData, index+1, elementData, index, numMoved);

									  elementData[--size] = null; //将最后一个数组元素置为null，方便GC

									  return oldValue;

									}