ArrayList的源码

• ArrayList的底层是数组。

目前看源码，比较关心的几个问题

• ArrayList的初始化容量是10， 但是我们之前看构造方法的时候，没看到。
• 底层是怎么扩容的？是不是添加一个数据，扩容一次。

ArrayList的初始化逻辑

class ArrayList{
    
    // 这个就是ArrayList底层的数组。  
    Object[] elementData;
    
    // 底层实际存储了多少个元素的个数。
    int size;
    
    static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    private static final int DEFAULT_CAPACITY = 10;
   
    // 这个是一个空构造方法， 在空构造方法里面，啥也没做，赋了一个常量。
    // 就是个空的。{}。我替大家推测了一下， 空构造里面，啥也没赋值。 ===》  在添加方法的时候，一定得能用。 
    // 所以接下来，我们看 添加方法。 
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    // e是要添加的元素。 
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 直接往数组的size位置，赋值e。   e其实就是我们要存进去的数据。
        // 所以走到这一行，就说明一个事情， 数组已经初始化好了
        elementData[size++] = e;
        return true;
    }
    
    // minCapacity = 1
    private void ensureCapacityInternal(int minCapacity) {
        // 这里两个方法套在一起，其实是内层方法的返回值作为外层方法的输入值。 
        // 也就是先执行 calculateCapacity(elementData, minCapacity)
        // 再执行这个 ensureExplicitCapacity()
        //                     calculateCapacity它的返回值是10
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    //                                             {}                1
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 所以，先进入这个方法里。 因为elementData目前确实是它
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //   DEFAULT_CAPACITY = 10;
            // return Matn.max(10, 1);   返回的是10 
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    //               ensureExplicitCapacity()    10
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        //  10         -    0   > 0
        if (minCapacity - elementData.length > 0)
            // 索引会进入这个方法。
            grow(minCapacity);
    }
    
    //                      10
    private void grow(int minCapacity) {
        // oldCapacity = 0
        int oldCapacity = elementData.length;
        // newCapacity = 1.5 * oldCapacity = 0
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        //   0 - 10  < 0  进入
        if (newCapacity - minCapacity < 0)
            // newCapacity = minCapacity = 10；
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 拷贝 elementData.  拷贝 10个。 
        // 其实做了一个特殊处理。  如果之前有， ["zs", "ls"]  。拷贝的数目不够，会补null.
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
}

扩容逻辑

什么时候会扩容？ 所以肯定会在添加数据的时候，进行扩容。

所以要看add方法。

class ArrayList{
    
    // 这个就是ArrayList底层的数组。  
    Object[] elementData;
    
    // 底层实际存储了多少个元素的个数。
    int size;
    
    
    // 假设，底层数组是10个。我们这个e已经是第11个数据了。 
    public boolean add(E e) {
        // 扩容一定是在这一行扩的。 
        //                      10  + 1 = 11 
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;
        return true;
    }
    
    // 											11
    private void ensureCapacityInternal(int minCapacity) {
        // calculateCapacity(elementData, minCapacity) 的返回值是 11
        // ensureExplicitCapacity（11）. 入参是11.
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    // 									elementData = new Object[10];    , 11
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //     11 
        return minCapacity;
    }
    
    //                                         11
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        //    11   -  10  >  0成立。 进入，
        if (minCapacity - elementData.length > 0)
            // grow(11)
            grow(minCapacity);
    }
    
    
    //                        11
    private void grow(int minCapacity) {
        // oldCapacity = 10
        int oldCapacity = elementData.length;
        // newCapacity = 1.5 * oldCapacity = 15
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        //  15 - 11  < 0  不成立。 
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        
        // int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // elementData =  新容量是15。
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    // 总结一下： 咋扩容的。 1.5倍原始容量
}

源码属于一个提高部分。如果听得懂更好，如果听不懂，先放一放。因为不影响后面写代码。

class ArrayList{
    
    // 这个就是ArrayList底层的数组。  
    Object[] elementData;
    
    // 底层实际存储了多少个元素的个数。
    int size;
    
    
    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;
    }
    
    
}