ArrayList源码分析

1、java.util.ArrayList<E> : List 接口的大小可变数组的实现类

• ArrayList 内部基于 数组 存储 各个元素。
• 所谓大小可变数组，是指当 数组容量不足以存放新的元素时，创建新数组，并将原数组中的内容复制过来。

2、ArrayList底层实现原理

• 构造方法源码分析
  1.  
     //对象数组：ArrayList的底层数据结构，transient表示该字段不进行序列化操作
  2.  
     transient Object[] elementData;
  3.  
     //实例化一个空数组
  4.  
     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  5.  
     //实例化一个空数组
  6.  
     private static final Object[] EMPTY_ELEMENTDATA = {};
  7.  
      
  8.  
     /**
  9.  
     *指定初始容量的有参构造
  10.  
      */
  11.  
      public ArrayList(int initialCapacity) {
  12.  
      //如果初始容量大于0就，对象数组就指向到一个新的数组，大小为所指定的大小
  13.  
      if (initialCapacity > 0) {
  14.  
      this.elementData = new Object[initialCapacity];
  15.  
      } else if (initialCapacity == 0) {
  16.  
      //如果大于0就指向一个空数组
  17.  
      this.elementData = EMPTY_ELEMENTDATA;
  18.  
      } else {
  19.  
      throw new IllegalArgumentException("Illegal Capacity: "+
  20.  
      initialCapacity);
  21.  
      }
  22.  
      }
  23.  
      /**
  24.  
      * 无参构造
  25.  
      */
  26.  
      public ArrayList() {
  27.  
      //对象数组就指向到一个空数组
  28.  
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  29.  
      }

  ArrayList基于数组实现，构造方法有有参构造和无参构造如果指定了初始容量且大于0就将对象数组指定到一个新的数组，大小为所指定的大小。如果调用无参构造就将对象数组指定到一个空的数组。

• 添加方法源码分析
  1.  
     //elementData中已存放的元素的个数，注意：不是elementData的容量
  2.  
     private int size;
  3.  
     //elementData的默认容量为10
  4.  
     private static final int DEFAULT_CAPACITY = 10;
  5.  
     //对象数组：ArrayList的底层数据结构，transient表示该字段不进行序列化操作
  6.  
     transient Object[] elementData;
  7.  
     //实例化一个空数组
  8.  
     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  9.  
     //实例化一个空数组
  10.  
      private static final Object[] EMPTY_ELEMENTDATA = {};
  11.  
       
  12.  
      protected transient int modCount = 0;
  13.  
       
  14.  
      @Native public static final int MAX_VALUE = 0x7fffffff;
  15.  
       
  16.  
      private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  17.  
       
  18.  
      /**
  19.  
      * 向elementData末尾中添加元素
  20.  
      */
  21.  
      public boolean add(E e) {
  22.  
      //确保对象数组elementData有足够的容量，可以将新加入的元素e加进去
  23.  
      ensureCapacityInternal(size + 1);
  24.  
      //加入新元素e，size加1
  25.  
      elementData[size++] = e;
  26.  
      return true;
  27.  
      }
  28.  
       
  29.  
      // minCapacity = seize+1，即表示执行完添加操作后，数组中的元素个数
  30.  
      private void ensureCapacityInternal(int minCapacity) {
  31.  
      //判断是否是空数组
  32.  
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  33.  
      //用最小容量和10进行比较，取最大值赋值给最小容量
  34.  
      minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  35.  
      }
  36.  
       
  37.  
      ensureExplicitCapacity(minCapacity);
  38.  
      }
  39.  
       
  40.  
      /**
  41.  
      *确保数组的容量足够存放新加入的元素，若不够，要扩容
  42.  
      */
  43.  
      private void ensureExplicitCapacity(int minCapacity) {
  44.  
      modCount++;
  45.  
      //如果数组个数minCapacity （size+1）大于数组长度就需要进行扩容
  46.  
      if (minCapacity - elementData.length > 0)
  47.  
      grow(minCapacity);
  48.  
      }
  49.  
       
  50.  
      private void grow(int minCapacity) {
  51.  
      int oldCapacity = elementData.length;
  52.  
      // 将旧的数组容量增加为原来的1.5倍作为新的容量
  53.  
      int newCapacity = oldCapacity + (oldCapacity >> 1);
  54.  
      //如果新的容量小于数组个数，将数组个数赋值给新容量
  55.  
      if (newCapacity - minCapacity < 0)
  56.  
      newCapacity = minCapacity;
  57.  
      // 如果新的容量大于最大容量，就根据数组个数来决定新的容量大小
  58.  
      if (newCapacity - MAX_ARRAY_SIZE > 0)
  59.  
      newCapacity = hugeCapacity(minCapacity);
  60.  
      // 根据新的容量，将数组拷贝到新的数组并赋值给数组
  61.  
      elementData = Arrays.copyOf(elementData, newCapacity);
  62.  
      }
  63.  
       
  64.  
      private static int hugeCapacity(int minCapacity) {
  65.  
      // 如果数组个数小于0抛出OutOfMemoryError异常
  66.  
      if (minCapacity < 0) // overflow
  67.  
      throw new OutOfMemoryError();
  68.  
      // 如果最数组个数大于最大容量 就返回最大值，否则返回最大容量
  69.  
      return (minCapacity > MAX_ARRAY_SIZE) ?
  70.  
      Integer.MAX_VALUE :
  71.  
      MAX_ARRAY_SIZE;
  72.  
      }
  73.  
      /**
  74.  
      * 向elementData指定位置添加元素
  75.  
      */
  76.  
      public void add(int index, E element) {
  77.  
      //指定位置检查
  78.  
      rangeCheckForAdd(index);
  79.  
      // 扩容检查
  80.  
      ensureCapacityInternal(size + 1); // Increments modCount!!
  81.  
      //通过拷贝使数组内位置为 index 到 （size-1）的元素往后移动一位
  82.  
      System.arraycopy(elementData, index, elementData, index + 1,
  83.  
      size - index);
  84.  
      // 找到位置添加元素
  85.  
      elementData[index] = element;
  86.  
      // 元素个数加一
  87.  
      size++;
  88.  
      }
  89.  
      // 判断指定位置是否超出数组个数
  90.  
      private void rangeCheckForAdd(int index) {
  91.  
      if (index > size || index < 0)
  92.  
      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  93.  
      }
  94.  
      /**
  95.  
      * @param src 原数组.
  96.  
      * @param srcPos 原数组的起始位置.
  97.  
      * @param dest 目标数组.
  98.  
      * @param destPos 目标数组的起始位置.
  99.  
      * @param length 拷贝长度.
  100.  
       */
  101.  
       public static native void arraycopy(Object src, int srcPos,
  102.  
       Object dest, int destPos,
  103.  
       int length);

  ArrayList在无参的add方法中，每次插入新的元素时，先判断是否需要扩容，判断数组是否为空，为空则建默认的容量10赋值给minCapacity，判断是否要扩容，第一次添加，数组的size是10，之后添加元素时，在ensureExplicitCapacity方法中判断数组元素个数即size+1（形参minCapacity）是否超过数组长度，超过则需要进行扩容操作，扩容是将旧的容量扩大到1.5倍，然后将数组拷贝到新的数组完成扩容操作。最后将元素添加，并size+1。ArrayList在指定位置添加元素时，是先检查指定位置是否在数组范围内，即数组中元素个数是1，则index得小于或者低于1。然后通过拷贝使数组内位置为 index 到 （size-1）的元素往后移动一位，腾出位置之后放入元素，数组个数加一。

• 删除方法源码分析
  1.  
     public E remove(int index) {
  2.  
     //指定位置检查
  3.  
     rangeCheck(index);
  4.  
     modCount++;
  5.  
     //保留要删除的值
  6.  
     E oldValue = elementData(index);
  7.  
     //要移动元素个数
  8.  
     int numMoved = size - index - 1;
  9.  
     if (numMoved > 0)
  10.  
      //通过拷贝使数组内位置为 index+1到 （size-1）的元素往前移动一位
  11.  
      System.arraycopy(elementData, index+1, elementData, index,
  12.  
      numMoved);
  13.  
      //清除末尾元素让GC回收
  14.  
      elementData[--size] = null; // clear to let GC do its work
  15.  
      //返回删除的值
  16.  
      return oldValue;
  17.  
      }

  删除指定位置的元素，先对index进行检查，在将要删除的值保留，计算出需要移动元素个数，再通过拷贝使数组内位置为 index+1到 （size-1）的元素往前移动一位，最后将末尾元素清理让GC回收返回删除值。由于List接口继承了Collection，因此ArrayList还有一个来自Collection接口定义的删除对象boolean remove( Object o ) ，而ArrayList自定义的remove方法是T remove(int index)删除的是下标位置的对象并返回值。