1. ArrayList 比照数组能做些什么？

众所周知，Java 中数组能用来批量存储同一类对象，可是数组在使用中会有所约束。数组需求在声明的时候就需求声明长度。按照长度从内存中申请一整片接连的内存。

由于内存是接连的所以数组的检索非常快，能够快速的经过数组下标找到对应下标在内存中的方位。

一起也由于内存是接连的导致数组无法进行扩容，例如声明了一个长度为 10 的数组，此刻现已放进去了 10 个元素，想要放入第 11 个元素，可是数组后的内存块或许现已被占用，就会导致无法扩容。

ArrayList 的出现就是为了处理数组无法主动扩容的问题，ArrayList 在其内部保护了一个数组，在需求进行扩容时便会申请一个容量更大的数组一起将老数组的数据复制到新数组。

2. ArrayList 办法

2.1 结构办法

2.2 具体办法（主要办法）

2.3 要点办法原理解说

add(Ee)

• 判别数组是否是空数组（新建 ArrayList 时，其中的数组默许指向空数组）

  • 是：获取当前数组需求的最小容量： minCapacity= max(默许初始容量10, 存量元素数+增量元素数)
  • 否：获取当前数组需求的最小容量：minCapacity=存量元素数+增量元素数

• 检查当前需求的数组最小容量是否小于数组长度

  • 是：刺进数据

  • 否：

    • 核算新的容量：newCapacity=oldCapacity+(oldCapacity>>1) 约为之前 1.5 倍

      • 新容量 newCapacity 是否大于当前所需最小容量 minCapacity

        • 是：将 minCapacity 赋值给新容量 newCapacity
        • 否：newCapacity 坚持不变

    • 依据获取到的新容量 newCapacity 生成新数组

    • 将老数组数据复制到新数组

    • 刺进数据

newCapacity=oldCapacity+(oldCapacity>>1) 进行了位运算，将 oldCapacity 的二进制向右移了一位。 例如

● 7 的二进制表明为 111，二进制向右移一位变为 11 对应十进制 3

● 8 的二进制表明位 1000，二进制向右移一位变为 100 对应十进制 4

可见对于奇数，二进制最终一位为 1，做右移一位操作会丢掉最终一位的 1 一起除以 2：n >> 1 = (n – 1) / 2 对于偶数，二进制最终一位为 0，做右移一位操作无影响，仅为原先数值处以 2：n >> 1 = n / 2

---

假如需求接连屡次的调用 add(E e) 增加元素，能够调用 ensureCapacity(int minCapacity) 输入期待数组的最小容量让 ArrayList 提早进行扩容，防止进行屡次扩容

add(intindex,Eelement)

• 刺进新元素先确保容量是否满足刺进新元素

  • 否：先进行扩容

• 将要刺进下标往后的元素一致往后挪一个下标

• 将新元素放到对应下标

疑问：将数组 2, 3, 4, 5 往后移动是怎样做的？

假如是正常思路或许是使用遍历顺次将 5 往后挪一位，再将 4 往后挪一位，然后一次挪动 3, 2

可是这样或许会形成 cpu 资源的糟蹋，

为此检查 ArrayList 代码发现底层调用了，System 的本地静态办法

static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

直接将原数组 2, 3, 4, 5 所在的内存块一致往后挪了一个单位，这样仅需求进行一次移动。

能够比照两种办法的功能差异

// 设置较大容量，防止数组扩容影响
ArrayList<Integer> list = new ArrayList<>(20000);
for (int i = 1; i <= 10000; i++) {
    list.add(i);
}
list.add(null);
long start = System.currentTimeMillis();
/**
* 第一种办法：
* 循环调用往后挪，耗时 3~5 ms
**/
for (int i = 9999; i >= 1 ; i--) {
    list.set(i + 1, list.get(i));
}
list.set(1, 2);
/**
* 第二种办法
* 直接复制一整块内存，耗时 0ms
**/
list.add(1, 2);
System.out.println(System.currentTimeMillis() - start);

remove(intindex)

在删去元素过程中，底层数组不会进行缩容

3. 总结

ArrayList 的扩缩容主要使用 System 的本地静态办法

static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

进行一次数据块的复制 + 新建数组完成。

实践扩容，会扩容为原容量的 1.5 倍，所以假如需求进行屡次增操作，需求提早评价数组容量防止屡次扩容。