ArrayList 深入浅出

加载中

ArrayList

特性：按加上排列顺序、可反复、非线程安全；
最底层完成：二维数组
扩充基本原理：复位结合时，默认设置容积为 0，第一次加上原素时扩充为 10，容积不足时扩充为原先容积的 1.5 倍。

这儿扩充指的是无参结构复位时的情景。针对特定结合长短的构造方法复位时，原始容积为特定长短，容积不足时再扩充为原先的 1.5 倍。

下边关键详细介绍无参结构复位时的情景。

复位-构造方法

主要参数界定：

transient Object[] elementData; // 具体储存数据信息的二维数组缓冲区域

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 原始二维数组

默认设置复位比较简单，启用无参构造器，复位一个空二维数组。真真正正扩充的逻辑性在每一次加上原素实行。

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

加上原素-扩充

加上方式：

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

size：ArrayList 的长短，可以用 List#size() 获得

加上方式一共干了2件事：

分辨二维数组容积是不是充足，不足则给二维数组扩充；
向二维数组中加上特定的原素；

加上原素无需多讲，向二维数组中的下一个部位插进就可以。下边主要详细介绍容积分辨的逻辑性：

1. 分辨容积尺寸

最先分辨当今结合容积尺寸是不是充足，假如不足就启用扩充方式 grow(int minCapacity)。

// 保证结合能够 加上下一个原素 minCapacity：当今必须 的最少容积
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  ;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

2. 扩充方式

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

旧容积为当今数组长度；
新容积为旧容积的 1.5 倍；（这里根据位运算测算，偏移1位等同于除于 2，再加原先值即扩张1.5倍）
假如新容积低于所需最少容积，则将新容积取值为所需最少容积；（这儿关键实行情景为结合复位时，旧容积为0，新容积扩张1.5倍后也为0，这时候新容积将被取值为默认设置容积 10）
假如新容积超出较大二维数组尺寸（int 最高值 - 8），这时候会报内存溢出或扩充为 int 的较大选值。
最终将原先二维数组数据信息拷贝到扩充到新容积尺寸的二维数组中。

加上原素-具体步骤

最先复位一个 ArrayList，向里边循环系统加上 11 个原素。下边对于于第一次加上和第一1次加上各自查询数组初始化和二维数组扩充的逻辑性。

public static void main(String[] args) {
    List<string> list = new ArrayList<>();

    for (int i = 0; i < 11; i  ) {
        list.add("items");
    }
}