集合篇-ArrayList

ArrayList源码

ArrayList是实现了List接口的一个类，其底层是一个Object类型的数据用来存储数据，
在查找和顺序存储的时候效率高，复杂度可以达到O(1)

字段解析

//数组默认长度10
private static final int DEFAULT_CAPACITY = 10;
//空数组示例
private static final Object[] EMPTY_ELEMENTDATA = {};
//实际存储数据的数组
transient Object[] elementData;
//数据中元素的个数
private int size;
//最大数据长度 为Integer最大值-8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造器解析

public ArrayList() {
   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

这个构造器是创建一个长度为10的Object类型的数组

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

这个构造器是指定数组长度、一般推荐使用这种的。因为使用默认的数组长度会有可能进行扩容，耗费时间。

新增元素

public boolean add(E e) {
    //判断添加一个元素后是否需要进行扩容
    ensureCapacityInternal(size + 1);
    //元素e添加到数组的size处  然后size+1 代表新增一个元素
    elementData[size++] = e;
    return true;
}

//判断新增一个元素后是否需要扩容
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果当前数组中没有元素 返回默认大小和size+1中大点的
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //否则返回size + 1
    return minCapacity;
}


private void ensureExplicitCapacity(int minCapacity) {
    //数据结构变更次数+1
    modCount++;

    // size + 1 大于当前数据的话需要进行扩容  即当前数据中的元素已经满了
    if (minCapacity - elementData.length > 0)
        //扩容操作
        grow(minCapacity);
}


private void grow(int minCapacity) {
    // 获取原有的数据长度
    int oldCapacity = elementData.length;
    //新数组长度为原有数组的1.5倍  比如原有数组长度为10  现在就是 10 + 10 / 2 = 15
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    //如果原有数据长度的1.5倍小于size + 1则新数组长度为size + 1
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果原有数组的1.5倍超过了最大数组容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 使用Arrays.copyOf将旧数组的值复制到新数组中   Arrays.copyOf底层调用的是System.arraycopy  
    //这个是一个native方法
    elementData = Arrays.copyOf(elementData, newCapacity);
}

//size + 1 大于最大数组容量的话就返回Integer的最大值
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

删除元素

删除元素会进行数组的拷贝、会将index + 1 为开始位置 到数组末尾的所有元素 都向前移动一位 然后将数组末尾处的值为空
例如：数组元素为[1,2,3,4,5,6] 移除index =1的元素 会将[3,4,5,6]都向前移动一位，变成[1,3,4,5,6,6]，
然后将数组末尾的元素置空变成[1,3,4,5,6,null]

public E remove(int index) {
    //检查index范围 如果超出数组长度 会抛出异常
    rangeCheck(index);

    //数组结构变更次数+1
    modCount++;
    //获取要移除的元素
    E oldValue = elementData(index);

     //移除元素后需要复制元素的长度
    int numMoved = size - index - 1;
    
    //使用System.arraycopy进行复制
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; 

    return oldValue;
}

还有一个重载的remove方法传入元素具体的值进行删除，当集合的泛型为Integer的时候 要删除一个元素 应该传入包装类型的数据 如Integer.valueOf(element)。如果直接传入的是一个像3、5这些数字 就会去调用上面的方法。