ArrayList

1. 特性：按加上排列顺序、可反复、非线程安全；
2. 最底层完成：二维数组
3. 扩充基本原理：复位结合时，默认设置容积为 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. 分辨二维数组容积是不是充足，不足则给二维数组扩充；
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. 旧容积为当今数组长度；
2. 新容积为旧容积的 1.5 倍；（这里根据位运算测算，偏移1位等同于除于 2，再加原先值即扩张1.5倍）
3. 假如新容积低于所需最少容积，则将新容积取值为所需最少容积；（这儿关键实行情景为结合复位时，旧容积为0，新容积扩张1.5倍后也为0，这时候新容积将被取值为默认设置容积 10）
4. 假如新容积超出较大 二维数组尺寸（int 最高值 - 8），这时候会报内存溢出 或扩充为 int 的较大 选值。
5. 最终将原先二维数组数据信息拷贝到扩充到新容积尺寸的二维数组中。

加上原素-具体步骤

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

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

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

数组初始化

ArrayList 复位后，最底层会复位一个空的对象数组 (elementData)，长短 (size) 为 0。当第一次加上原素时，会将其复位为一个长短为 10 的二维数组。下边看第一次加上原素的步骤：

1.进到加上方式 add(E e)

2.分辨容积尺寸

3.计算所需最少容积

当今二维数组为空二维数组，因此if 标准创立，DEFAULT_CAPACITY = 10，minCapacity = 1；

当今方式回到 10；

4.分辨二维数组是不是扩充

elementData 当今为空二维数组，length = 0；minCapacity 为上一步回到的 10；因此这里会启用扩充方式 grow()

5.二维数组扩充（初始化数组）

这儿会依据上边特定的默认设置容积 10 来给二维数组扩充。

• oldCapacity = 0；
• newCapacity = 0；
• newCapacity = 10；
• elementData 扩充为容积为10 的新二维数组

6.加上原素

• elementData[0] = items
• size = 1；

二维数组扩充

依据以前程序流程的运作，结合储存数据信息的二维数组在第一次加上原素时扩大容积为 10，因此在第 11 次加上原素时便会启用扩充的逻辑性。

1、add() 方式

minCapacity = size 1 = 11；

2、分辨容积尺寸

3、计算所需最少容积

​ 非第一次 立即回到

4、分辨是不是扩充

所需最少容积超过数组长度，启用扩充方式。

5、扩充

• oldCapatity = 10;
• newCapatity = 15;
• 复制二维数组內容到一个 容积为 15 的二维数组中，进行扩充

6、加上原素

• elementData[10] = e;
• size = 11;
  

不容易的物品仅有满怀一颗嚣张的心，假装能把它看透吧。