ArrayList 的扩容机制

ArrayList 的扩容机制 ArrayList 的扩容机制

1，无参构造方法刚刚开始构造的时候

    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    
     // 第一种构造方法
    public ArrayList() {
    	// 这边其实指向的是一个空的数组
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    private static final Object[] EMPTY_ELEMENTDATA = {};

	// 第二种构造方法 带参的构造方法
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
        	 // 完成数组的构建
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        	// 如果等于0则指向空的数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        // 如果是负数 则抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

	
    public ArrayList(Collection 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;
       }
   }

2，添加方法

    
    private int size;
    
    
     // 当前不是线程安全的
    public boolean add(E e) {
     // 执行添加元素之前，会进行一个扩容的处理，判断是否要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

3，来到ensureCapacityInternal方法细看

    private void ensureCapacityInternal(int minCapacity) {
    // 判断是否等于空，此时的elementData 满足条件，因为elementData
    // 就是空，Math.max 取出最大值 DEFAULT_CAPACITY = 10
    // 而minCapacity = 1 所有最终返回10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 所以现在的minCapacity 等于10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

4,往下追 ensureExplicitCapacity方法

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++; // 修改次数加加

        // overflow-conscious code
        // 10 - 0 > 0  true
        if (minCapacity - elementData.length > 0) // 满足条件
            grow(minCapacity);// 调用扩容的方法
    }

5，最后一步grow方法

    
    private void grow(int minCapacity) {
        // overflow-conscious code
        // oldCapacity = 0, 因为elementData 数组为空
        int oldCapacity = elementData.length;
        // 这边会进行一个1.5倍扩容
        // 下面这句话可以理解成 oldCapacity 加上 oldCapacity 除以2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // nexCapacity = 0 - 1 < 0? false 
        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:
        // 这个时候会调用一个Arrays.copyOf完成一个扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

6，图解，第一次出来后就是这个样子的

7，第二次添加的时候

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++; // 修改次数加加

        // overflow-conscious code
        // minCapacity等于2 elementData.length等于10 
        // 2-10 = -8 ，-8 不大于0 所以不满足条件
        if (minCapacity - elementData.length > 0) // 不满足条件
           // 则不会再调用当前方法
            grow(minCapacity);
    }

8，假设当前的元素位子用完啦，需要进行扩容

    private void grow(int minCapacity) {
        // overflow-conscious code
        // elementData.length = 10 所以oldCapacity 等于10
        int oldCapacity = elementData.length;
        // int newCapacoty =  10 + (10 / 2);
        // 结果为15
        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:
        // 将新的newCapacity（新的容量）和之前的数组 放入后进行扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

9，图示意

10，以此内推，每次增加则为1.5倍的速度进行增加