一概述
ArrayList 是 Java 集合体系中最常使用, 也是最简单的集合类, 是以数组实现的线性表
数组在内存中是以一段连续的内存来进行存放的, 同样, ArrayList 也是如此, 初始化时可以指定初始容量, 也可以以默认容量 (10) 创建底层数组, 由于 ArrayList 属于可变长列表, 采用可变数组实现, 数组本身是不变的, 一旦定义就无法变长, 可变数组使用创建新数组拷贝旧数据的方式间接实现可变长, 习惯称为扩容
ArrayList 底层数组的扩容算法依据的是一个扩容算法来计算新的数组长度, 扩容的条件是当前底层数组不足以容纳新的元素
二继承结构
ArrayList 的类结构如下所示:
三底层实现
3.1 底层结构
如前所述, ArrayList 底层采用的是数组结构
1 private transient Object[] elementData;
elementData 就是定义在 ArrayList 底层的数组, 而数组就是一连串连续的内存, 其逻辑结构如下:
上图表示初始容量为 10 的 ArrayList 的底层数组, 默认的初始容量为 10, 而列表长度用 size 来定义:
1 private int size;
这个表示的是列表中元素的数量, 与数组的长度不同, size 默认为 0, 表示列表为空
3.2 添加元素
初始化的 ArrayList 的底层数组是没有元素的, 即数组的各位均为 null 使用 add 方法我们可以为列表添加元素, ArrayList 中的添加单个元素有两种方式, 一种是直接添加, 另一种是定位添加还有添加一组元素的两种方法, 一种是定组直接添加, 一种是定位定组添加
3.2.1 直接添加
所谓直接添加就是将新元素添加到列表末尾, 其实现逻辑如下:
- public boolean add(E e) {
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
上面的逻辑很简单, 首先进行列表容量检测(容后详述), 然后直接将新元素放置到底层数组中即可
图中显示添加新元素到列表中, 添加之后 size 的值会增加, 这个 size 即指向数组最新空位的下标, 有代表数组中元素的个数
3.2.2 定位添加
所谓定位添加, 就是我们将新元素, 添加到列表指定下标处
- public void add(int index, E element) {
- rangeCheckForAdd(index);
- ensureCapacityInternal(size + 1); // Increments modCount!!
- System.arraycopy(elementData, index, elementData, index + 1,
- size - index);
- elementData[index] = element;
- size++;
- }
首先进行 index 参数校验, 校验通过后进行列表容量检测(容后详述), 然后将指定下标处开始到结尾的所以元素整体后移以为, 下标处空出来后填充新添加的元素这个添加操作涉及到一部分元素的整体移动, 较为耗时, 具体视实际移动的元素数量而定
实例: 原始列表中由 e1-e5 共 5 个元素, 现在执行 add(2,e6), 表示在下标 2 处添加元素 e6, 执行步骤如下:
注意: add(int,E)方法底层数组元素的后移操作采用的是 System.arraycopy()方法实现的, 不仅此处, 后面还会多次使用这个方法来实现数组元素的拷贝
3.2.3 定组直接添加
定组直接添加方法为: addAll(Collection<? extends E>), 直接将给定的集合中的元素依次添加到当前列表的后面
- public boolean addAll(Collection<? extends E> c) {
- Object[] a = c.toArray();
- int numNew = a.length;
- ensureCapacityInternal(size + numNew); // Increments modCount
- System.arraycopy(a, 0, elementData, size, numNew);
- size += numNew;
- return numNew != 0;
- }
首先进行集合转化, 将其转化为数组, 获取其长度(元素个数), 进行列表容量检测(容后详述), 将转化好的数组元素复制到当前列表的底层数组后面, 计算 size
明显类似于直接添加, 只是添加的数量不同而已, 做个简单的图示:
只是这里讲给定的集合简化为数组形式, 其实在源码中我们也能发现, 在第 2 行对集合进行了数组转化, 便于操作元素的添加还是使用数组拷贝的形式实现
3.2.4 定位定组添加
定位定组添加类似于定位添加, 同样只是添加的元素个数不同
- public boolean addAll(int index, Collection<? extends E> c) {
- rangeCheckForAdd(index);
- Object[] a = c.toArray();
- int numNew = a.length;
- ensureCapacityInternal(size + numNew); // Increments modCount
- int numMoved = size - index;
- if (numMoved > 0)
- System.arraycopy(elementData, index, elementData, index + numNew,
- numMoved);
- System.arraycopy(a, 0, elementData, index, numNew);
- size += numNew;
- return numNew != 0;
- }
首先进行 index 参数校验, 然后将集合转化为数组, 获取其中元素个数 numNew, 再进行列表容量检测, 获取需要后移的元素的个数, 使用数组复制的方式将这些元素后移, 再将转化的数组元素复制迁移到空出的空位处计算 size
参照下方实例, 原始列表有两个元素: e1e2, 现在给定集合包含 3 个元素, e3e4e5, 现在执行 add(1,Collection<? extends E>)
也就是将给定集合的元素嵌入到当前列表中
3.3 获取元素
获取指定下标处的元素, 复杂度 O(1), 只要获取数组执行下标处的元素就可以
- public E get(int index) {
- rangeCheck(index);
- return elementData(index);
- }
首先进行 index 参数校验, 然后获取返回数组执行下标的元素
3.4 修改元素
修改元素需要提供修改下标和新值, 直接用新值替换旧值即可
- public E set(int index, E element) {
- rangeCheck(index);
- E oldValue = elementData(index);
- elementData[index] = element;
- return oldValue;
- }
首先进行 index 参数校验, 然后保存指定下标的旧值, 替换为新值, 将旧值返回
3.5 删除元素
删除元素的操作挺多的, 针对不同的情况:
3.5.1 定位删除
定位删除, 即删除指定下标的元素, 需要提供删除的元素的下标
- public E remove(int index) {
- rangeCheck(index);
- modCount++;
- E oldValue = elementData(index);
- int numMoved = size - index - 1;
- if (numMoved > 0)
- System.arraycopy(elementData, index+1, elementData, index,
- numMoved);
- elementData[--size] = null; // Let gc do its work
- return oldValue;
- }
首先进行 index 参数校验, modCount 自增 1, 保存指定下标处的旧值, 然后将指定下标的下一个元素到结尾的元素整体前移一位, 后面元素覆盖前面元素, 指定下标处的旧值被删除, 然后将原来的末尾元素置空, size 自减 1, 最后将旧值返回
同样数组元素的移动采用数组复制的方式实现
实例: 原始列表拥有 5 个元素, e1-e5, 现移除下标 2 处的元素: remove(2)
3.5.2 定元素删除
指定要删除的元素的值, 在列表中查询该值, 删除查询到的第一个即该方法只会删除符合条件的首个元素(即使列表中存在多个符合条件的元素)
- public boolean remove(Object o) {
- if (o == null) {
- for (int index = 0; index < size; index++)
- if (elementData[index] == null) {
- fastRemove(index);
- return true;
- }
- } else {
- for (int index = 0; index < size; index++)
- if (o.equals(elementData[index])) {
- fastRemove(index);
- return true;
- }
- }
- return false;
- }
- private void fastRemove(int index) {
- modCount++;
- int numMoved = size - index - 1;
- if (numMoved > 0)
- System.arraycopy(elementData, index+1, elementData, index,
- numMoved);
- elementData[--size] = null; // Let gc do its work
- }
指定元素进行删除的情况, 较为复杂, 需要针对元素的情况进行分析, 如果指定元素为 null, 则删除第一个 null 元素, 若指定元素非 null, 则查询首个符合条件的元素进行删除
欲删除元素, 必须先找到要删除元素的下标, 这个过程由循环实现(第 3 行和第 9 行), 找到下标之后, 调用内部方法 fastRemove(int), 进行指定下标元素的删除, 即定位删除, 然后返回 true, 表示删除成功
还有一种情况那就是指定的元素在列表中查询不到, 这是直接返回 false 即可
这种删除底层使用的仍然是定位删除不在画图举例了
3.5.3 定组删除
所谓定组删除, 就是删除当前列表中所以与给定集合中元素相同的元素, 该操作需要制定一个欲要删除的元素的集合(Collection)
- public boolean removeAll(Collection<?> c) {
- return batchRemove(c, false);
- }
- private boolean batchRemove(Collection<?> c, boolean complement) {
- final Object[] elementData = this.elementData;
- int r = 0, w = 0;
- boolean modified = false;
- try {
- for (; r < size; r++)
- if (c.contains(elementData[r]) == complement)
- elementData[w++] = elementData[r];
- } finally {
- // Preserve behavioral compatibility with AbstractCollection,
- // even if c.contains() throws.
- if (r != size) {
- System.arraycopy(elementData, r,
- elementData, w,
- size - r);
- w += size - r;
- }
- if (w != size) {
- for (int i = w; i < size; i++)
- elementData[i] = null;
- modCount += size - w;
- size = w;
- modified = true;
- }
- }
- return modified;
- }
定组删除的 complement 传值为 false, 用于第 11 行比较, 表示如果给定集合中不包含当前列表的当前下标的元素的情况下, 执行内部语句块, 将这个元素保留下来(亦即若包含该元素则不保留该元素, 最后查遗补漏时, 会将其消失 finally 块逻辑)
实例: 当前列表是包含 5 个元素 e1-e5, 给定集合元素包括 e2,e3,e5 三个元素, 则定位删除的图示为:
从第二步开始循环, 每次循环结束, r 就会自增 1, 而 w 表示的是下一个保留元素的下标或者保留元素的个数循环在第七步 r 自增到 5, 不满足循环条件时结束, 最后 r=5,w=2, 亦即共删除 3 个元素, modCount 需要自增 (r-w=5-2=3) 次
最后 finally 中执行第二个 if 块, 将多余的元素位置置 null, 再计算 modCount 和 size
3.5.4 定组保留删除
定组保留删除逻辑与定组删除正好相反, 需要将给定集合中包含的当前列表的元素保留下来, 将不包含的删除
- public boolean retainAll(Collection<?> c) {
- return batchRemove(c, true);
- }
实例, 同上, 图示如下:
执行过程同上
3.5.5 范围删除
ArrayList 中还有一个范围删除方法: removeRange(int,int), 根据给定的两个下标, 删除下标范围之内的所有元素该方法是 protected 修饰的, 那么很明显, 这个方法并不是面向 ArrayList 使用者的, 而是面向 JDK 实现者的, 这里只做简单介绍
- protected void removeRange(int fromIndex, int toIndex) {
- modCount++;
- int numMoved = size - toIndex;
- System.arraycopy(elementData, toIndex, elementData, fromIndex,
- numMoved);
- // Let gc do its work
- int newSize = size - (toIndex-fromIndex);
- while (size != newSize)
- elementData[--size] = null;
- }
很简单, 将 toIndex 到结尾的元素复制到 fromIndex, 空出的位置全部置空即可
3.6 查找元素
查找元素包括 3 个方法:
contains(Object)检查当前列表是否包含某个元素
indexOf(Object)检查给定元素在当前列表中首次出现的下标
lastIndexOf(Object)检查给定元素在当前列表中最后出现的下标
3.6.1 包含方法
- public boolean contains(Object o) {
- return indexOf(o) >= 0;
- }
好家伙, 自己啥也不干, 就靠后面了...
3.6.2 前序查找
前序查找就是从头开始查找元素, 返回首次出现的下标
- 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;
- }
源码显示, 需要分两种情况考虑, 如果给定元素为 null, 则查找首个 null 元素的下标并返回, 如果给定元素非 null, 则查找首次出现的下标并返回, 如果列表中不包含该元素, 则返回 - 1
3.6.3 后序查找
后序查找就是前序查找的反向查找方式:
- public int lastIndexOf(Object o) {
- if (o == null) {
- for (int i = size-1; i >= 0; i--)
- if (elementData[i]==null)
- return i;
- } else {
- for (int i = size-1; i >= 0; i--)
- if (o.equals(elementData[i]))
- return i;
- }
- return -1;
- }
参考前后查找的源码不难发现, 模式一致, 只是查找的方向不同而已
3.7 列表扩容
列表的扩容是底层自动进行的, 对列表的使用者是完全透明的, 因此其方法都是私有的扩容的条件与算法并不复杂:
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
- private void ensureCapacityInternal(int minCapacity) {
- modCount++;
- // overflow-conscious code
- if (minCapacity - elementData.length > 0)
- grow(minCapacity);
- }
- 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);
- }
- private static int hugeCapacity(int minCapacity) {
- if (minCapacity < 0) // overflow
- throw new OutOfMemoryError();
- return (minCapacity > MAX_ARRAY_SIZE) ?
- Integer.MAX_VALUE :
- MAX_ARRAY_SIZE;
- }
扩容条件: 拿给定的容量 (长度值)minCapacity 与当前列表的底层数组的容量 elementData.length 进行比较, 如果前者大, 则说明容量不足, 需要扩容, 调用 grow(minCapacity) 进行扩容
扩容算法: 扩容时存在三种情况, 第一种就是普通的自动扩容, 按照 oldCapacity + (oldCapacity >> 1)算法进行扩容, 上式计算得出的即为新的数组容量, 一般针对的是单个元素添加的情况, 即直接添加和定位添加的情况, 这种情况下, 每次只添加一个元素, 不会出现第 14 行成功的可能, 但是如果是定组直接添加和定位定组添加的时候, 由于添加的集合元素数量未知, 一旦给定的 minCapacity 比计算得出的新容量要大, 说明计算得出的容量不足以容纳所有的元素, 这是直接使用 minCapacity 作为新容量进行扩容即优先使用算法计算的容量进行扩容, 一旦计算容量还不足以容纳新元素, 则使用给定的容量进行扩容
还有一种特殊情况, 当本次扩容时, 计算得到的容量, 或者给定的容量大于 MAX_ARRAY_SIZE(=Integer.MAX_VALUE - 8)的情况下, 需要调用 hugeCapacity(minCapacity)方法进行人为限制容量超限, 将容量限制在整形的最大值之内
最后进行数组扩容, 创建新数组, 拷贝数据
3.8 迭代器
列表的迭代必不可少, 而且这里还会用到一个出现很久的变量 modCount, 此前我们对它一无所知
modCount 记录的是列表结构发生变化的次数, 所谓结构变化包括: 新增元素, 删除元素, 清空元素, 扩容等
ArrayList 的迭代器有两种, ListIterator 和 Iterator 二者虽然都是迭代器, 但是还是有些不同的
(待续)
来源: https://www.cnblogs.com/V1haoge/p/8494618.html