集合篇-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这些数字就会去调用上面的方法。

最后编辑于：2020.05.14 16:08:42