Java 容器 - ArrayList 源码分析

Java 集合中的 ArrayList 是基于数组实现的

开头

首先我们看初始化一个 ArrayList 的结构

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
    /**
     * 默认大小
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 共用的数组实例用于空的实例
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    /**
     * 默认大小的空实例所用的共用的数组实例。我们判断当一个元素被加入时数组实例该怎样扩大*/
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access
    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

大家可以发现ArrayList 继承于 AbstractList，还有 List、Clone、Serializable接口，说明它可以被克隆和序列化。
Any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY when the first element is added.说明只是DEFAULTCAPACITY_EMPTY_ELEMENTDATA类型的 ArrayList 在加入一个元素时将会被初始化为10

构造方法

/**
 *构造一个有初始大小的 list
 */
public ArrayList(int initialCapacity) {
    /*判断输入的容量是否大于0*/
    if (initialCapacity > 0) {
        /*大于0初始化一个大小为输入的容量的数组*/
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        /*如果输入的大小为0就初始化一个空数组*/
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        /*否则抛出异常*/
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
/*初始化一个默认的空数组*/
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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;
    }
}

添加方法

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

当添加的时候，首先会调用ensureCapacityInternal(int minCapacity)这个方法来扩充数组的容量，然后再把值加进数组。

扩容方法

private void ensureCapacityInternal(int minCapacity) {
        /*先判断数组时是否为空数组*/
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            /*选择 minCapacity 和10中最大的那个值*/
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        
        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // 判断minCapacity时候大于数组的容量
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    //数组的最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    private void grow(int minCapacity) {
        // 原来数组的容量
        int oldCapacity = elementData.length;
        /*新数组的容量为oldCapacity + oldCapacity/2 (右移一位为原来的数除以2)，也就是1.5倍*/
        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);
    }
    private static int hugeCapacity(int minCapacity) {
        /*传进来的参数为负数抛出异常，如果大于数组最大容量，返回 Integer 的最大值*/
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

总结

ArrayList 初始化时底层为空数组且大小为0，当有第一个元素加进去后，数组的容量为10。扩容后新容量是原来容量的1.5倍。

如果觉得我的文章对你有帮助，就赏给我这个学生党一些钱买书继续深入学习下去吧！赏

微信打赏

支付宝打赏

本文作者： 小小小maker_wei
本文链接： blog.makerwei.me/posts/63081…
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！