ArrayList

!!! note 目录

ArrayList

ArrayList集合底层采用了数组这种数据结构。

  • ArrayList集合优点： 底层是数组，因此根据下标查找元素的时间复杂度是O(1)，检索效率高。

  • ArrayList集合缺点： 随机增删元素的效率较低。不过只要数组的容量还没满，对末尾元素进行增删的效率不受影响。

  • ArrayList集合适用场景： 需要频繁检索元素，并且很少进行随机增删元素时，建议使用ArrayList集合。

一、ArrayList初始化容量

1.1 调用ArrayList无参构造方法初始化的容量

调用ArrayList集合的无参数构造方法时，初始容量为0，第一次添加元素时，容量会扩展为10。

  1. 源码
    1
    2
    3
    public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
1
2
3
4
5
6
/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

二、ArrayList扩容策略

  1. 初始容量：通过无参数构造方法创建的ArrayList，初始容量为0。第一次添加元素时，容量会扩展为10。

  2. 扩容条件：当ArrayList中添加新元素时，如果当前容量不足以容纳新的元素，ArrayList会进行扩容。

  3. 扩容大小：扩容时，新容量为旧容量的1.5倍（即旧容量加上旧容量的一半）。具体来说，扩容后的新容量计算公式为newCapacity = oldCapacity + (oldCapacity >> 1)。

  4. 确保容量：扩容后的新容量必须能够容纳当前需要存储的元素数量。如果按上述计算的新容量仍不足以容纳新元素，ArrayList会将新容量直接设置为所需要的最小容量。

三、ArrayList集合源码分析

3.1 属性分析

  1. transient Object[] elementData;

    这是用来存储 ArrayList 元素的数组。ArrayList 的容量就是这个数组的长度。
    如果一个 ArrayList 是空的，并且它的初始数据是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那么在添加第一个元素时，它的容量会扩展到 DEFAULT_CAPACITY。

  2. private int size;

    ArrayList 的大小（它实际包含的元素数量）。