ArrayList源码分析

JAVA,javascript,集合框架

ArrayList源码分析

初始化、添加、扩容

初始化

ArrayList类有三个构造方法，分别是 ArrayList() 、ArrayList(Collection<? extends E> c) 、ArrayList(int initialCapacity) 下面逐个分析

ArrayList()

该构造方法为无参构造，源码如下：

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; 

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

从源码可以看出，午餐构造方式创建对象实际上没有执行任何操作，只是为 elementData 变量赋一个默认值。

这里 elementData 之所以没有设置为private，主要是为了方便嵌套的子类访问。

ArrayList(Collection<? extends E> c)

    public ArrayList(Collection<? extends E> c) {
        // 将集合对象c转换为数组
        Object[] a = c.toArray();
        // 获取数组的长度并判断是否为0
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                // 如果集合对象c是ArrayList类型，则直接赋值给elementData
                elementData = a;
            } else {
                // 如果集合对象c不是ArrayList类型，则使用Arrays.copyOf方法将数组a转换为Object[]类型，并赋值给elementData
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // 如果集合对象c为空，则初始化elementData为空数组
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

对于通过传入一个集合初始化ArrayList的方式，由上面的源码可知，主要内容是判断传入的集合是否为空。若传入的集合参数为空，则执行逻辑等同于调用无参构造；若传入的集合不为空且为ArrayList类型，则直接将集合赋值到当前类，否则使用数组复制的形式初始化当前集合的 elementData

ArrayList(int initialCapacity)

    // 接收一个integer类型的参数，用于指定初始容量，
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            // 如果初始容量大于0，则创建一个具有该容量的ArrayList实例；
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 如果初始容量为0，则创建一个空ArrayList实例；
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            // 如果初始容量为负，则抛出IllegalArgumentException异常。
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        }
    }

对于传入初始容量的形式，由上面代码可知，本质上就是创建了一个 initialCapacity 容量的数组用于存储数据。

添加元素

add(E e)

// 集合的容量，初始状态下为0
private int size;

// 默认集合容量
private static final int DEFAULT_CAPACITY = 10;

// 集合元素最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

public boolean add(E e) {
    // 确保集合容量足够容纳新元素，若不足则扩容
    ensureCapacityInternal(size + 1);  // 增加modCount计数器（用于跟踪修改次数）
    // 将元素添加到集合末尾
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // 确定所需的实际最小容量，并确保集合容量足够
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果当前数组为空数组，返回默认容量与所需容量中的较大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 否则，返回所需的最小容量
    return minCapacity; 
}

private void ensureExplicitCapacity(int minCapacity) {
    // 每次修改集合时，递增modCount
    modCount++; 

    // 如果所需容量大于当前数组容量，则扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // 获取当前数组的容量
    int oldCapacity = elementData.length;
    // 将当前容量增加50%
    // 这里采用移位运算，效果等同于 oldCapacity / 2，但是效率更高
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新的容量仍小于所需的最小容量，则取最小容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新的容量超过最大允许容量，则取最大允许容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 使用新的容量创建新数组，并将旧数组中的元素复制到新数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 处理超过最大数组尺寸的情况，确保容量不超过Integer.MAX_VALUE
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 溢出
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

关于数组最大容量：

由上面的代码可以看到，数组初始容量为10，最大容量为 Integer.MAX_VALUE - 8 。这里 -8 是因为HotSpot虚拟机支持最大数组容量为 Integer.MAX_VALUE 而虚拟机需要分配一些额外空间用于存储数组元数据，因此实际最大容量略小于 Integer.MAX_VALUE

add(int index, E element)

  • 方法源码
public void add(int index, E element) {
    // 检查索引是否合法（在0到size之间），如果不合法抛出IndexOutOfBoundsException
    rangeCheckForAdd(index);

    // 确保集合容量足够容纳新的元素，如果容量不足则扩容，同时增加modCount计数器（用于跟踪修改次数）
    ensureCapacityInternal(size + 1);

    // 从索引位置开始，将数组中的元素向右移动一个位置，以腾出空间插入新元素
    System.arraycopy(elementData, index, elementData, index + 1, size - index);

    // 在指定的索引位置插入新元素
    elementData[index] = element;

    // 集合的容量加1
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

从最顶层的方法源码可以看出，指定位置添加元素的方法与直接添加元素的方法相比，只新增了两行代码。主要区别在于，需要多计算一次传入的索引是否合法，以及多执行一次数组复制。

类似文章