[数据结构与算法]ArrayList源码详解

ArrayList源码详解

ArrayList作为开发最最常用的容器，了解并掌握其底层原理是每个开发人员必备的技能。

一、关键属性

/**
 * Default initial capacity.
 * 默认初始化容量
 */
private static final int DEFAULT_CAPACITY = 10;



/**
 * Shared empty array instance used for empty instances.
 * 空数组，用于空的实例化
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 空数组，用于空的实例化
* 你可能在想这个不是和 EMPTY_ELEMENTDATA  一样了吗
* 是的，它们的值是一样的，但是意义不大一样。
* 当我们使用 new ArrayList<>(); 创建容器的时候，使用的是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 
* 其目的在于：
* we distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
* 意思就是让我了解，以这种方式创建的容器，添加第一个元素的时候，到底做了哪些事情（后面会说明）。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* 存数据的。官方有个说明：

 * Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
* 
*/
transient Object[] elementData;

了解了以上属性，我们就可以回答面试官最喜欢问的面试问题了：

ArrayList的底层数据结构是什么？

显然嘛，数组。

初始化容量大小？

很多人说是10，这其实是错误的，看过源码就会知道，初始化容量是0。在新增第一个元素的时候进行扩容，容量扩容为10。这也是这个属性DEFAULTCAPACITY_EMPTY_ELEMENTDATA 存在的意义。

二、容器初始化

ArrayList 底层数据结构是数组，这个想必大家都知道。
初始化方式：

/**
 * 三种构造方法
 * 无参构造
 * 指定容量构造
 * 传入Collection 容器构造
 * 在我们能够得知容量具体大小的时候，建议指定容量大小。不然频繁的扩容还是很浪费时间的
 */
List<Integer> list = new ArrayList<>();

1. 无参构造

new ArrayList<>(); 源码很简单。

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2. 指定容量大小

也不是很复杂

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 入参大于零 初始化数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 等于0 默认{}
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 小于0 显然不行的啊 
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

3. 容器参数

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    // 集合转为数组 不会有人传null吧 
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 很多人都疑惑这一步的操作目的。问题出现在了  c.toArray();这一步，如果集合
        //  c.toArray()被重写了返回的就不一定是 Object[].class 了，这样就不是一种
        // 数据类型了。现在明白了吧。
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

三、核心add方法

整体流程图：

add()有几个重载方法，这里只对核心的add(E e)方法进行详细的介绍。
源码很简单三步：

1. 确保容量
2. 添加值
3. 返回true

public boolean add(E e) {
    // 确保容量可以进行添加
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // size 当前容量，也就是在容器最后添加元素，前提容量有这么大。所以第一步就是确保
    // 容量
    elementData[size++] = e;
    return true;
}

1. ensureCapacityInternal() 方法

作用：确保容量满足要求，不满足扩容

private void ensureCapacityInternal(int minCapacity) {
    //字面意思 确保明确的容量
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算容量 
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果是空的化 返回 默认容量10 和最小容量中的最大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

    //字面意思 确保明确的容量
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        // 容量不够 扩容 
        grow(minCapacity);
}

2. grow(int minCapacity) 扩容方法

private void grow(int minCapacity) {
    // overflow-conscious code
    // 获取旧容量
    int oldCapacity = elementData.length;
    //新容量为旧容量1.5 倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 数据copy
    elementData = Arrays.copyOf(elementData, newCapacity);
}

添加元素的流程结束了，是不是很简单。

四、核心get方法

get方法很简单，不用看源码应该就可以猜出来。get(下标) 不就是 elementData[下标] 嘛

/**
* 果然如此
*/
public E get(int index) {
    //范围检查
    rangeCheck(index);
    //获取数据
    return elementData(index);
}

五、核心remove 方法

remove 方法有不少重载方法。常用的是根据下标移除和根据元素移除。根据元素溢出，本质上还是根据下标移除，需要先定位到下标，再根据下标移除。这里只针对根据下标移除进行详细介绍。

public E remove(int index) {    
    // 范围检查
    rangeCheck(index);
    // 修改次数
    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
       // 删除（数组copy）
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // GC 清理
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

System.arraycopy()方法

此方法常用于数组copy，数组扩容，数组根据指定下标删除。

/**
* @param      src      the source array. 原数组
* @param      srcPos   starting position in the source array.  开始位置
* @param      dest     the destination array.  目标数组
* @param      destPos  starting position in the destination data. 目标数组开始位置
* @param      length   the number of array elements to be copied. copy数量
*/
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

六、 contains() 方法

判断是否包含指定元素，主要是遍历数组，对一个元素一个元素进行判断。

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}



public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

七、总结

ArrayList 容器算是比较简单的容器，理解起来不是很困难，很适合源码阅读入门。

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖