ArrayList的扩容机制原理及源码分析

1.初始化ArrayList无参构造器

1.1 使用无参构造器创建ArrayList对象

List list = new ArrayList();

    源码分析：调用无参构造器，创建了一个空的elementData数组，其初始化值为{}。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
 

1.2 首次调用add(E e）方法添加数据

//首次扩容
 for (int i = 1; i <=10 ; i++) {
            list.add(i);
        }
 
//再次扩容
for (int i = 11; i <=15 ; i++) {
            list.add(i);
        }

源码分析：

boolean add(E e);
 
//执行add()方法进行添加时: （1）先确定是否需要扩容；（2）然后再执行赋值
public boolean add(E e) {
        //ensureCapacityInternal()确定内部容量值
        ensureCapacityInternal(size + 1);  
        elementData[size++] = e;
        return true;
    }
 
 
private static final int DEFAULT_CAPACITY = 10;
 
//int minCapacity首次添加数据时该值为1
//int DEFAULT_CAPACITY = 10;
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //Math.max(DEFAULT_CAPACITY, minCapacity)比较两者的值，然后取最大值
            //因此，调用无参构造器时，初始化容量为0，首次添加数据时容量变为10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //ensureExplicitCapacity()该方法确定最小容量值
        ensureExplicitCapacity(minCapacity);
    }
 
 
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        
        // overflow-conscious code
        //第一次进入时，int minCapacity = 10,elementData.length=0，调用grow()方法进行扩容
        //要想扩容必须满足minCapacity>elementData.length，才能调用grow()方法进行扩容
        //再此调用grow()时，minCapacity=size+1，elementData.length=10(每次扩容后会改变)，
        if (minCapacity - elementData.length > 0)
           // grow()进行扩容
            grow(minCapacity);
    }
 
 
  private void grow(int minCapacity) {
        // overflow-conscious code
        // 存储旧的数组长度
        int oldCapacity = elementData.length;
        // 首次扩容时oldCapacity为0 因此： oldCapacity + (oldCapacity >> 1) = 0
        //第二次扩容变为原来的容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            //首次扩容将minCapacity=10赋值给新的容量newCapacity 
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //扩容后将原先的elementData的数据放到新的数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
 
 
 

结论：使用无参构造器创建ArrayList对象，不会定义elementdata数组的长度，当第一次调用add(E e) 方法时，初始化定义底层数组的长度为10，之后调用add(E e)时，如果需需要再次扩容，则调用grow(int minCapacity) 进行扩容,长度为原来的1.5倍。

2.初始化ArrayList有参构造器

 2.1 使用无参构造器创建ArrayList对象

     List list2 = new ArrayList(2);

  源码分析：调用有参构造器，创建了一个固定大小的elementData数组。

//int initialCapacity = 2 初始化elementData数组大小为2 
 public ArrayList(int initialCapacity) {
        //initialCapacity 是否大于0
        if (initialCapacity > 0) {
        //将值的大小赋值给elementData数组的大小
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //如果initialCapacity 为0，和创建无参构造方法流程一致
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

源码分析：当数据数量超过elementData数组长度时，进行扩容

    List list2 = new ArrayList(2);
 
     for (int i=0;i<=1;i++){
          list2.add(i);
      }
    //进行数组扩容
     list2.add(3);
 
    boolean add(E e);
 
public boolean add(E e) {
        //添加3时，需要ensureCapacityInternal()确定内部容量值
        //size+1=3  
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;
        return true;
    }
 
 
 private void ensureCapacityInternal(int minCapacity) {
         // elementData 数组不为{}，不执行
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //执行该方法，确定最小容量值
        ensureExplicitCapacity(minCapacity);
    }
 
 
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //此时数据的大小minCapacity=3 大于elementData数组大小，进行扩容 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 
 
  private void grow(int minCapacity) {
        // overflow-conscious code
        //oldCapacity = 2
        int oldCapacity = elementData.length;
        //newCapacity = 2*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的数据放到新的数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

结论：调用有参构造器，创建了一个指定大小的elementData数组，如果需要再次扩容，则直接扩容elementData为原先的1.5倍。

3.总结

        1）当创建方式为 List list = new ArrayList(0)时，默认调用EMPTY_ELEMENTDATA初始化容量为0，当首次添加元素时，elementData数组长度容量扩为 10，之后再次扩容时变为原先的1.5倍；

        2）当创建方式为 List list = new ArrayList(10)时，创建了一个指定长度的elementData数组，如果需要再次扩容时，则直接扩容elementData数组长度为原先的1.5倍。

        3）使用无参构造器创建ArrayList对象，不会定义elementdata数组的长度，当第一次调用add(E e) 方法时，初始化定义底层数组的长度为10，之后调用add(E e)时，如果需需要再次扩容，则调用grow(int minCapacity) 进行扩容,长度为原来的1.5倍。