ArrayList自动扩容原理

一、ArrayList三种初始化

1、默认的构造器，将会以默认的大小来初始化内部的数组

public ArrayList();
 

2、用一个ICollection对象来构造，并将该集合的元素添加到ArrayList

public ArrayList(Collection<? extends E> c)
 

3、用指定的大小来初始化内部的数组

public ArrayList(int initialCapacity)
 

二、扩容概括

     扩容概括为两步：

     1、扩容---把原来的数组复制到另一个内存空间更大的数组中

     2、添加元素---把新元素添加到扩容以后的数组中

下面详细介绍扩容代码的实现原理和方法之间的调用关系

三、自动扩容从ArrayList初始化开始

1、无参构造方法：创建一个空数组

  

   

    

     

    
    

     

      transient Object[] elementData;
     
    
   

    

     

    
    

     

      private static final Object[] EMPTY_ELEMENTDATA = {};
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       *无参构造方法实现创建一个空数组，并且为这个数组赋一个空值
     
    
   

    

     

    
    

     

       *
     
    
   

    

     

    
    

     

      */
     
    
   

    

     

    
    

     

      public ArrayList() {
     
    
   

    

     

    
    

     
        super();
     
    
   

    

     

    
    

     
        //为数组赋空值
     
    
   

    

     

    
    

     
        this.elementData = EMPTY_ELEMENTDATA;    
     
    
   

    

     

    
    

     

          }
     
    
  
 

2、扩容从add( )开始

  

   

    

     

    
    

     
 /**
     
    
   

    

     

    
    

     

       *1、 ArrayList 扩容从add()开始
     
    
   

    

     

    
    

     

       *2、add方法有两条语句如下：
     
    
   

    

     

    
    

     

       * ensureCapacityInternal(size + 1); 判断是否需要调用扩容方法
     
    
   

    

     

    
    

     

       * elementData[size++] = e; 调用add方法添加的值赋值给数组。
     
    
   

    

     

    
    

     

       * 
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     
    public boolean add(E e) {
     
    
   

    

     

    
    

     

              ensureCapacityInternal(size + 1);  // Increments modCount!!
     
    
   

    

     

    
    

     

              elementData[size++] = e;
     
    
   

    

     

    
    

     
        return true;
     
    
   

    

     

    
    

     

          }
     
    
  
 

3、ensureCapacityInternal：判断是否需要扩容

  

   

    

     

    
    

     
    //1、add方法调用ensureCapacityInternal方法
     
    
   

    

     

    
    

     

      private void ensureCapacityInternal(int minCapacity) {
     
    
   

    

     

    
    

     
    //2、判断当前数组是否为空
     
    
   

    

     

    
    

     
        if (elementData == EMPTY_ELEMENTDATA) {
     
    
   

    

     

    
    

     

                  minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
    //3、调用扩容判断的方法，将当前最小扩容值传进去。
     
    
   

    

     

    
    

     

              ensureExplicitCapacity(minCapacity);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    private void ensureExplicitCapacity(int minCapacity) {
     
    
   

    

     

    
    

     

              modCount++;
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
     /**
     
    
   

    

     

    
    

     

       * 4、minCapacity：最小扩容值
     
    
   

    

     

    
    

     

       *elementData.length：数组空间长度
     
    
   

    

     

    
    

     

       * 判断是否扩容原理：
     
    
   

    

     

    
    

     

       * （最小扩容值 - 数组空间长度 > 0）则调用扩容方法grow(minCapacity);
     
    
   

    

     

    
    

     

       * 举例：第一次调用add方法，最小扩容值为11，数组长度为10 那么(11- 10 > 0)调用扩容，扩容后是当 
     
    
   

    

     

    
    

     

       *前值的1.5倍=15。 
     
    
   

    

     

    
    

     

       * 第二次调用add方法，最小扩容值+1是12，数组长度为15那么(12- 15 > 0)不大于0，不调用扩容方法
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     
        // overflow-conscious code
     
    
   

    

     

    
    

     
        if (minCapacity - elementData.length > 0)
     
    
   

    

     

    
    

     

                  grow(minCapacity);
     
    
   

    

     

    
    

     

          }
     
    
  
 

4、grow(minCapacity) ：计算扩容空间大小，并调用复制数组方法。

  

   

    

     

    
    

     
    private void grow(int minCapacity) {
     
    
   

    

     

    
    

     
        // overflow-conscious code
     
    
   

    

     

    
    

     
    //1、获取现在数组的长度
     
    
   

    

     

    
    

     
        int oldCapacity = elementData.length;
     
    
   

    

     

    
    

     
    //2、扩容后的数组长度
     
    
   

    

     

    
    

     
    // oldCapacity >> 1 右移运算符 原来长度的一半 再加上原长度也就是每次扩容是原来的1.5倍
     
    
   

    

     

    
    

     
        int newCapacity = oldCapacity + (oldCapacity >> 1);
     
    
   

    

     

    
    

     
    //3、判断扩容后的长度是否小于需要的最小扩容
     
    
   

    

     

    
    

     
        if (newCapacity - minCapacity < 0)
     
    
   

    

     

    
    

     

                  newCapacity = minCapacity;
     
    
   

    

     

    
    

     
    //4、判断扩容后的长度是否超过规定的最大值
     
    
   

    

     

    
    

     
        if (newCapacity - MAX_ARRAY_SIZE > 0)
     
    
   

    

     

    
    

     

                  newCapacity = hugeCapacity(minCapacity);
     
    
   

    

     

    
    

     
        // minCapacity is usually close to size, so this is a win:
     
    
   

    

     

    
    

     
    //5、调用复制数组方法，将老的数组复制到新的数组中，并将需要添加的元素加到数组最后一位
     
    
   

    

     

    
    

     

              elementData = Arrays.copyOf(elementData, newCapacity);
     
    
   

    

     

    
    

     

          }
     
    
  
 

文章来源: brucelong.blog.csdn.net，作者：Bruce小鬼，版权归原作者所有，如需转载，请联系作者。

原文链接：brucelong.blog.csdn.net/article/details/94012710