Java常用类源码——ArrayList源码解析

ArrayList

ArrayList是我们经常使用的一个类了，是属于List接口的那一块,那么，我们就来看这个类的源码吧！

ArrayList签名

public class ArrayList<E> extends AbstractList<E>
       implements List<E>, RandomAccess, Cloneable, java.io.Serializable

从上面我们知道ArrayList是实现了List、RandomAccess ，Cloneable，Serializable接口的一个类。

那么它的成员属性有哪些呢？如下的源码：

// 默认初始化对的容量是10
 private static final int DEFAULT_CAPACITY = 10;
 
 // 当初始化容量为0 时，构造一个这样的空的Object类型的数组，下面的构造方法中会有提到
   private static final Object[] EMPTY_ELEMENTDATA = {};
 /**
     * 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.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
     //真正存储元素的容器，就是一个Object类型的数组，当
    transient Object[] elementData; // non-private to simplify nested class access
    // 标识数组的大小
     private int size；

构造函数

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
     // 指定容量大小的构造函数
    public ArrayList(int initialCapacity) {
        // 大于0的时候创建新的数组对象
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
            // 指定大小为0 的时候，引用一个空数组
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
     //当没有进行初始化容量大小的时候，将引用默认的空数组
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
//传入一个集合的时候
public ArrayList(Collection<? extends E> c) {
        //将集合转变成一个数组
        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;
        }
    }

在利用Collection来构造的时候，有一个确认对象类型的检验，如果集合中的对象不为Object类型，那么就利用Array类的静态方法进行拷贝，这个给出的注释是调用toArray()方法时可能出现问题。看来API开发人员想的还是比较的细致的。当转换的数组为空的时候，ArrayList并没有使用转换的空结果，而是依然使用自己构造的空数组。

主要方法

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;
   }

ArrayList的添加元素，是添加到数组的末尾的，并且是永远返回一个true, 这是说明这个向容器中添加的时候是永远不会出现错误的了哦！
再来看add（）方法中的ensureCapacityInternal

private void ensureCapacityInternal(int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           //将默认的容量大小和向里面再添加一个元素是的大小进行比较，选择其中较大的。
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       ensureExplicitCapacity(minCapacity);
   }

这个方法是非常重要的，这里面是确保ArrayList容量能否再增加一个，那里面是怎么做的呢？ 通过上面的代码知道ensureCapacityInternal 这个方法中首先是判断当前的对象数组是不是默认的空数组，如果是的话，就在默认容量（10）和需要的容量中取一个最大值，然后把得到的这个值传递给下一个函数ensureExplicitCapacity,所以在这里就可以解答上面 transient Object[] elementData上面的解释了，在创建一个空TreeMap，如果使用的默认的构造方法，那么elementData就是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA,当首次插入对象的时候，最大值的时候一定是10，实际上就相当于构造了一个长度为10的对象的数组。

private void ensureExplicitCapacity(int minCapacity) {
       modCount++;
       // overflow-conscious code
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
   }

ensureExplicitCapacity这个方法第一行先不管是干什么的，看后面的，就是判断需要的容量和现在用来存储的对象的数组(elementData)哪个更大，如果现在已经有的不够大了，那就扩容！

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 进行扩容  是的变为原来的1.5倍
    int newCapacity = 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);
}

   private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

上面的这段代码进行了扩容的操作，可以看出扩容是通过newCapacity = oldCapacity + (oldCapacity >> 1); 这段代码实现的，这段代码实际是上就是将原来的容量变为原来的1.5倍。

但是要对扩容后的容量进行检验，共有两种可能：

1. 得到的容量比需要的容量小，为什么会出现这样的情况呢，溢出了呗
2. 得到的容量超过了规定的最大容量，进入hugeCapacity如果需要的容量小于0，抛出内存溢出异常，如果需要的容量比规定的最大容量大，那么最大容量只能是 Integer.MAX_VALUE.

最后将elementData通过Array的复制拷贝方法进行了扩容。以上就是整个添加新的元素的过程。从这个过程可以看出，ArrayList也并不是无限大的，他指定了最大容量是Interger.MAX_VALUE-8，再大的话，实际最大只能是Integer.MAX_VALUE这个值了。

add(int, E)

这个方法是在指定的位置上插入元素element

/**
   * Inserts the specified element at the specified position in this
   * list. Shifts the element currently at that position (if any) and
   * any subsequent elements to the right (adds one to their indices).
   *
   * @param index index at which the specified element is to be inserted
   * @param element element to be inserted
   * @throws IndexOutOfBoundsException {@inheritDoc}
   */
  public void add(int index, E element) {
      //检查边界
      rangeCheckForAdd(index);
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      System.arraycopy(elementData, index, elementData, index + 1,
                       size - index);
      elementData[index] = element;
      size++;
  }
     /**
   * A version of rangeCheck used by add and addAll.
   */
  private void rangeCheckForAdd(int index) {
      if (index > size || index < 0)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }

首先进行的是合法性的检查，然后再进行容量的检验并扩容。
第三行是进行元素的复制，复制的方法是一个native方法，其实原理就是将原来index位置开始的元素，依次向后移动一位，通过openjdk,可以知道是代用了C语言和C++的代码。并且System.arraycopy()方法使用的是C语言中的-------------------- 方法。这个方法是比较高效的，所以在Java的源码中，有拷贝的地方几乎都是有它的身影的。add（）方法最后将元素放入指定的位置中，元素的数量进行增加。

Remove方法

remove(int index)

从指定的位置删除元素，实现原理就是把index后面的数据都向前移动，时间复杂度为O(n)

/**
    * Removes the element at the specified position in this list.
    * Shifts any subsequent elements to the left (subtracts one from their
    * indices).
    *
    * @param index the index of the element to be removed
    * @return the element that was removed from the list
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
   public E remove(int index) {
       //边界检查
       rangeCheck(index);
       modCount++;
       E oldValue = elementData(index);
       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
       return oldValue;
   }

1. 第一行就是检验index的返回，有人会问为什么不检验负数的情况。本人亲自试验了一下，如果index是负数的话，第一行是可以正确执行的，但是在elementData(index)这样地方就会抛出java.lang.ArrayIndexOutOfBoundsException: -1即 数组越界异常，其实个人觉得，如果没有第一句 检验，仍然会抛出数组越界异常。只不过多了第一行的话，抛出的异常就是java.lang.IndexOutOfBoundsException: Index: 2, Size: 2，而且会打印出错误信息。又有哪个Java程序员不喜欢看到更详细的异常信息呢？
2. 计算移动量，如果要删除的元素不是最后以一位，就要进行移动。
3. 将移动后的数组末尾赋值null。这里有一句注释，让GC去回收，这个是一种释放内存的方式。赋值为null，的确是不做任何的处理更加的有效，因为Java的垃圾回收机制是通过一些垃圾回收方法来确定对象是否回收，其中的一个算法是”可达性分析”，如果没有其他的引用，即到”Root”不可达的话，是非常容易被垃圾回收机制回收的（这里大概讲一下Java的垃圾回收机制，更详细的请看我的关于Java垃圾回收机制原理的博客）。

remove(Object o)

删除指定的元素，仅仅删除符合条件的第一个元素，如果不存在，返回false即删除失败

/**
    * Removes the first occurrence of the specified element from this list,
    * if it is present.  If the list does not contain the element, it is
    * unchanged.  More formally, removes the element with the lowest index
    * <tt>i</tt> such that
    * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
    * (if such an element exists).  Returns <tt>true</tt> if this list
    * contained the specified element (or equivalently, if this list
    * changed as a result of the call).
    *
    * @param o element to be removed from this list, if present
    * @return <tt>true</tt> if this list contained the specified element
    */
   public boolean remove(Object o) {
       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;
   }

分析这段代码，首先对o进行了非空处理。如果不进行这样的处理，将会引发o.equals的空指针异常。这个是非常常见的处理方式在这if else语句块中，都用了fastRemove（index） 听上去挺高大上的，快速删除的，其实看了源码就知道，很简单。

/*
   * Private remove method that skips bounds checking and does not
   * return the value removed.
   */
  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
  }

这不就是remove(index)方法的后半部分吗？为何不直接调用这个方法呢？肯定是为了提交一点点效率嘛，这毕竟是Java API嘛.

removeAll(Collection<?> c)

在集合中，删除与Collection中元素相等的元素

public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
        }

第一行是java1.7新出的工具类，用于检验非空的，如果为空，抛出空指针异常。
接下来就来看下面的这个方法:

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

下面来分析一下这段代码。首先对集合中的对象数组进行了一次复制，然后将数组中的元素依次与collection进行对比。try{}块的结果就是得到了一个数组，数组前w位元素或与collection相同（complement=true的时候)或不同（complement=false)。
下面来看finally,先来看第二个if{}代码块，它的作用就是把数组中w以后的元素全部变为null值，让gc来回收。现在回到finally的第一个if中，看条件(r != size)，似乎永远不会满足这个条件吧。上面的for循环一直r++啊，可是别忘了，c.contains(elementData[r])这句话是有可能抛出异常的，如果一旦类型不匹配，就会抛出异常 进入finally中。
这个方法，如果没有删除任何数据，那么将会返回false。

现在我们再来看return batchRemove(c,false);这行的含义吧。它指定了第二个参数为false，所以在batchRemove（）保留下来的都是与collection中不同的元素。相同的元素都被删除了。这样就达到了removeAll(Collection<?> c)的目的。

迭代器

迭代器可是操作ArrayList的神器，在ArrayList内部通过内部类的形式实现了Iterator接口，完成对ArrayList的操作，下面就看源码：

/**
    * An optimized version of AbstractList.Itr
    */
   private class Itr implements Iterator<E> {
       int cursor;       // index of next element to return
       int lastRet = -1; // index of last element returned; -1 if no such
       int expectedModCount = modCount;

       public boolean hasNext() {
           return cursor != size;
       }

       @SuppressWarnings("unchecked")
       public E next() {
           checkForComodification();
           int i = cursor;
           if (i >= size)
               throw new NoSuchElementException();
           Object[] elementData = ArrayList.this.elementData;
           if (i >= elementData.length)
               throw new ConcurrentModificationException();
           cursor = i + 1;
           return (E) elementData[lastRet = i];
       }

       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 traffic
           cursor = i;
           lastRet = i - 1;
           checkForComodification();
       }

       final void checkForComodification() {
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
       }
   }

这个类并不长，让我们来分析一下
（1） 属性
a 游标
int cursor; 我们知道iterator是始终向前走的，就是这个游标始终在++的原因
b 末尾标识
int lastRe 标识了最后一个返回的元素的索引位置，-1代表这个元素不存在
C 操作数标识
int expectedModCount = modCount; 这个非常重要，它用来校验在使用iterator期间，是否存在非Iterator的操作对ArrayList进行了修改。
（2）checkForComodification 方法
这个方法很简单，但是可以看到在这个内部类中，几乎所有方法都在调用它。它所做的工作就是校验在使用iterator期间，是否存在非Iterator的操作对ArrayList进行了修改。
在ArrayList中，有很多操作都修改了一个变量，modCount。每次进行操作，modCount都在++。前面一直不理解这个有什么用，在这看到了它的用意。Iterator的游标特性决定了它对ArrayList中元素在这一时刻的位置很敏感，如果当前游标在index位置，而有其他操作在index-1的位置上插入了一个元素，那么调用iterator的next()方法，返回的还是当前这个元素，这样就乱了。为了避免这个情况发生，需要在这个期间把ArrayList“锁住“。它并没有实现真正的锁，所以采用了这个校验的方式。
（3）next()
返回当前游标位置的元素，这里面第一个if判断的条件很有意思。因此游标前移，当移动到一个不存在数据的地方，它抛出了异常。而并没有返回null。这就是我们为什么在使用iterator的时候不能用（null==iterator.next())来判断的原因。而是在要每次循环开始的时候判断iterator.hasNext()。
（4） remove()
删除lastRe 所标识位置的元素。我们可以把它理解为当前元素。在try前面有一个校验，保证元素没有被改动过，要不就删错了。
在try{}语句块中，首先删除了lastRe标识的元素，然后让游标指向了这个位置。我们知道在删除元素以后，这个位置有了新的元素，这样再次调用next()的时候不会出现空指针异常，更不会跳过一个元素。
最后expectedModCount = modCount;这句相当于释放了锁。也是在表示，在我Iterator的地盘，只有我能够去修改mod，别人动了就不行！``

总结

1. ArrayList是用Object数组来实现的，所谓的动态扩容，实际上是不断的产生新的数组，然后进行复制。
2. 在使用ArrayList插入大量元素时，应该有选择的申请一个容量，而不是使用默认的容量，因为扩容是会消耗很多的时间的。
3. ArrayList不是线程安全的，它的操作中没有使用同步的方法，如果想使用线程安全的，可以用Vector，也可以使用Collections.synchronizedList 来创建线程安全的list。