本文已收录到 AndroidFamily，技术和职场问题，请重视公众号 [彭旭锐] 发问。

前语

大家好，我是小彭。

在前面的文章里，咱们学习了许多数据结构与算法思想。在实践的事务开发中，往往不需求咱们手写数据结构，而是直接运用规范库的数据结构 / 容器类。

在后续的文章里，咱们将以 Java 语言为例，剖析从 ArrayList 到 LinkedHashMap 等一系列规范库容器类，最终再有一篇总结回忆，请重视。

思维导图：

Java 数据结构：ArrayList 可以完全替代数组吗？

1. 说一下 ArrayList 和 LinkedList 的区别？

  • 1、数据结构： 在数据结构上，ArrayList 和 LinkedList 都是 “线性表”，都继承于 Java 的 List 接口。别的 LinkedList 还完成了 Java 的 Deque 接口，是根据链表的栈或行列，与之对应的是 ArrayDeque 根据数组的栈或行列；

  • 2、线程安全： ArrayList 和 LinkedList 都不考虑线程同步，不确保线程安全；

  • 3、底层完成： 在底层完成上，ArrayList 是根据动态数组的，而 LinkedList 是根据双向链表的。事实上，它们许多特性的区别都是由于底层完成不同引起的。比如说：

    • 在遍历速度上： 数组是一块接连内存空间，根据局部性原理能够更好地射中 CPU 缓存行，而链表是离散的内存空间对缓存行不友好；

    • 在拜访速度上： 数组是一块接连内存空间，支持 O(1) 时刻复杂度随机拜访，而链表需求 O(n) 时刻复杂度查找元素；

    • 在添加和删去操作上： 假如是在数组的结尾操作只需求 O(1) 时刻复杂度，但在数组中心操作需求转移元素，所以需求 O(n)时刻复杂度，而链表的删去操作自身仅仅修正引证指向，只需求 O(1) 时刻复杂度（假如考虑查询被删去节点的时刻，复杂度剖析上仍然是 O(n)，在工程剖析上仍是比数组快）；

    • 额外内存消耗上： ArrayList 在数组的尾部添加了搁置方位，而 LinkedList 在节点上添加了前驱和后继指针。

2. ArrayList 源码剖析

这一节，咱们来剖析 ArrayList 中主要流程的源码。

2.1 ArrayList 的特点

ArrayList 的特点很好了解，底层是一个 Object 数组，我要举手发问：

  • ‍♀️疑问 1： 为什么 elementData 字段不声明 private 关键字？
  • ‍♀️疑问 2： 为什么 elementData 字段声明 transient 关键字？
  • ‍♀️疑问 3： 为什么elementData 字段不声明为泛型类型 E？
  • ‍♀️疑问 4： 为什么 ArrayList 的最大容量是 Integer.MAX_VALUE，Long.MAX_VALUE 不行吗？
  • ‍♀️疑问 5： 为什么 ArrayList 的最大容量是 MAX_VALUE - 8，一定会减 8 吗？

这些问题咱们在剖析源码的进程中答复。疑问这么多，ArrayList 瞬间不香了。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // new ArrayList() 默许初始容量
    private static final int DEFAULT_CAPACITY = 10;
    // new ArrayList(0) 的大局空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // new ArrayList() 的大局空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 修正次数记载
    protected transient int modCount = 0;
    // 数组的最大长度
    // 疑问 4：为什么 ArrayList 的最大容量是 Integer.MAX_VALUE，Long.MAX_VALUE 不行吗？
    // 疑问 5：为什么 ArrayList 的最大容量是 MAX_VALUE - 8，一定会减 8 吗？
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
    // 疑问 1：为什么不声明 private（后文答复）
    // 疑问 2：为什么声明 transient（后文答复）
    // 疑问 3：为什么不声明为泛型类型 E
    // 底层数组
    transient Object[] elementData;
    // 数组的有用长度（不是 elementData.length）
    private int size;
    // size() 回来的是数组的有用长度（合理，底层数组咱们不关心）
    public int size() {
        return size;
    }
}

2.2 ArrayList 的结构办法

ArrayList 有三个结构函数：

  • 1、带初始容量的结构办法： 假如初始容量大于 0，则创立指定长度的数组。假如初始容量是 0，则指向第 1 个大局空数组 ；EMPTY_ELEMENTDATA；
  • 2、无参结构办法： 指向第 2 个大局空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA；
  • 3、带调集的结构办法： 将调集转为数组，假如数组为空，则指向第 1 个大局空数组 EMPTY_ELEMENTDATA；

能够看到，除了指定大于 0 的初始容量外，ArrayList 在结构时不会创立数组，而是指向大局空数组，这是懒初始化的策略。

结构器的源码不难，但小朋友总有太多的问号，举手发问 ‍♀️：

  • ‍♀️疑问 6：既然都是容量为 0 ，为什么 ArrayList 要区分出 2 个空数组？

这个问题直接答复吧：ArrayList 以为无参结构函数应该运用默许行为，在初次添加数据时会创立长度为 10（DEFAULT_CAPACITY） 的默许初始数组；而显现设置初始容量为 0 是开发者的显式目的，所以不运用默许初始数组，在初次添加数据时只会创立长度为 1 （size + 1）的数组（能够结合后文源码了解下）。

  • ‍♀️疑问 7： 在带调集的结构办法中，为什么会存在调集转化后的数组类型不是 Object[].class 的状况？
// 带初始容量的结构办法
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 创立 initialCapacity 长度的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 指向第 1 个大局空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 不合法的初始容量
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    }
}
// 无参结构办法
public ArrayList() {
    // 指向第 1 个大局空数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 带调集的结构办法
public ArrayList(Collection<? extends E> c) {
    // 将调集转为数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 疑问 7：这一个条件句子好奇怪，toArray() 的回来值类型便是 Object[] 啊？
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

2.3 ArrayList 的添加与扩容办法

ArrayList 能够在数组结尾或数组中心添加元素：

  • 假如是在数组结尾添加，均摊时刻只需求 O(1) 时刻复杂度；
  • 假如在数组中心添加，由于需求转移数据，所以需求 O(n) 时刻复杂度。

添加前会先检查数据容量，缺乏会先扩容：

  • 在运用无参结构器初始化时，初次添加元素时会直接扩容到 10 的容量；
  • 在其他状况，会直接扩容到旧容量的 1.5 倍，而不是扩容到最小容量要求。

不管是扩容到 10 仍是扩容到 1.5 倍，都是为了防止频频扩容，防止每次 add 添加数据都要扩容一次。

现在，咱们能够回到一些小朋友的疑问：

  • ‍♀️疑问 4：为什么 ArrayList 的最大容量是 Integer.MAX_VALUE，Long.MAX_VALUE 不行吗？

本质上看，应该说是数组长度的束缚，而不是 ArrayList 长度的束缚。在 《目标的内存分为哪几个部分？》 这篇文章里，咱们讨论过目标的内存布局。数组目标的长度是记载在目标头中的 “数组长度” 字段中，这个字段是 4 字节，正好便是 Integer 也是 4 个字节，所以束缚为 Integer.MAX_VALUE，而不能运用 Long.MAX_VALUE。

不对啊，Java Integer 是有符号整数，所以 Integer.MAX_VALUE 只有 31 位有用位，还少了 1 位呢。没错，是少了一位。假如要榨干这 1 位容量，当然能够用 long 类型而且束缚到 32 位能够表明的最大正整数上，而且在源码中到处加上数组越界判断，想想就不稳定的。相比之下，束缚数组长度为 int 类型且最大长度为 Integer.MAX_VALUE，假如有超越 Integer.MAX_VALUE 存储容量的需求，那就创立两个数组呀：）你觉得哪种更好。

Java 目标内存布局

Java 数据结构：ArrayList 可以完全替代数组吗？

  • ‍♀️疑问 5：为什么 ArrayList 的最大容量是 MAX_VALUE - 8，一定会减 8 吗？

仍然与目标的内存布局有关。在 Java 虚拟机废物收回算法中，需求计算目标的内存巨细，计算结果是存储在 jint 类型变量（Java int 类型在 JNI 中的映射）中的。假如数组的长度是 MAX_VALUE，那么加上目标头之后就整型溢出了，所以 ArrayList 会预先减掉目标头或许占用的 8 个字节。目标头的具体巨细取决于虚拟机完成，减 8 是相对保存的。

其实，ArrayList 的最大容量也纷歧定会减 8，假如最小容量要求是超越 MAX_ARRAY_SIZE 的，那么仍是会扩容到 MAX_VALUE 。这有点摆烂的意思，会不会溢出运行时再说。

数组长度溢出

OutOfMemoryError: Requested array size exceeds VM limit
  • ‍♀️疑问 8：不该该是 elementData.length – minCapacity > 0 吗？ 这是考虑到整型溢出的状况，minCapacity 溢出就变成负数了。
// 在数组结尾添加元素
public boolean add(E e) {
    // 先确保底层数组容量满足包容 size + 1，缺乏会扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 在 size + 1 的方位赋值
    elementData[size++] = e;
    return true;
}
// 在数组中心刺进元素
public void add(int index, E element) {
    // 规模检查
    rangeCheckForAdd(index);
    // 先确保容量满足包容 size + 1，缺乏会扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 先转移数据腾出空位
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // 在 index 的方位赋值
    elementData[index] = element;
    // 长度加一
    size++;
}
// 在数组结尾添加调集
public boolean addAll(Collection<? extends E> c) {
    // 调集转数组
    Object[] a = c.toArray();
    // 先确保底层数组容量满足包容 size + numNew，缺乏会扩容
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 转移原数据
    System.arraycopy(a, 0, elementData, size, numNew);
    // 长度加 numNew
    size += numNew;
    return numNew != 0;
}
// 在数组中心刺进调集
public boolean addAll(int index, Collection<? extends E> c) {
    // 略，原理相似
}
// 测验扩容
// （提示：源码调用了 calculateCapacity() 函数，这儿做内联简化）
private void ensureCapacityInternal(int minCapacity) {
    // 运用无参结构器初始化时，指定扩容为 10 
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity =  Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 疑问 8：不该该是 elementData.length - minCapacity > 0 吗？
    // 假如底层数组长度不行 minCapacity 最小容量要求，则需求扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // 旧容量
    int oldCapacity = elementData.length;
    // 新容量 = 旧容量 * 1.5 倍（有或许整型溢出）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 假如新容量小于最小容量要求，则运用最小容量（addAll 大调集的状况）
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    // （提示：上一个 if 的 newCapacity 有或许是溢出的）
    // 假如新容量超出最大数组长度束缚，说明无法扩容 1.5 倍，回归到 minCapacity 上
    // （提示：源码调用了 hugeCapacity() 函数，这儿做内联简化）
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        // 最小容量要求产生整型溢出，无法满足要求，只能直接抛出 OOM
        if (minCapacity < 0) throw new OutOfMemoryError();
        // 假如最小容量要求超出最大数组长度束缚，则扩容到 MAX_VALUE（说明纷歧定会减 8）
        // 否则，扩容到最大数组长度束缚（MAX_VALUE - 8）
        newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }
    // 扩容到 newCapacity 长度
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    // 现已内联简化到 grow 办法中
}

除了扩容之外，ArrayList 还支持缩容，将底层数组的容量缩小到实践元素的数量：

// 缩容
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
    }
}

别的，由于扩容涉及到数据转移操作，所以假如能事前知道数据的容量，最好在创立 ArrayList 时就显式指定数据量巨细。

2.4 ArrayList 的迭代器

Java 的 foreach 是语法糖，本质上也是选用 iterator 的方式。ArrayList 供给了 2 个迭代器：

  • iterator():Iterator()： 单向迭代器
  • ListIterator listIterator()： 双向迭代器

在迭代器遍历数组的进程中，有或许呈现多个线程并发修正数组的状况，形成数据纷歧致甚至数组越界，所以 Java 许多容器类的迭代器中都有 fail-fast 机制。

假如在迭代的进程中发现 expectedModCount 变化，说明数据被修正，此刻就会提早抛出 ConcurrentModificationException 反常（当然也纷歧定是被其他线程修正）。

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    // 创立迭代器是会记载外部类的 modCount
    int expectedModCount = modCount;
    ...
    Itr() {}
    public boolean hasNext() {
        return cursor != size;
    }
    @SuppressWarnings("unchecked")
    public E next() {
        // 检查
        checkForComodification();
        ...
    }
    public void remove() {
        ...
        // 更新
        expectedModCount = modCount;
    }
}
  • ‍♀️疑问 1：为什么 elementData 字段不声明 private 关键字？

在注释中的解释是：“non-private to simplify nested class access”。但咱们知道在 Java 中，内部类是能够拜访外部类的 private 变量的，所以这就说不通的。我的了解是：由于内部类在编译后会生成独立的 Class 文件，假如外部类的 elementData 字段是 private 类型，那么编译器就需求在 ArrayList 中刺进 getter / setter，并经过办法调用，而 non-private 字段就能够直接拜访字段。

2.5 ArrayList 的序列化进程

  • ‍♀️疑问 2：为什么 elementData 字段声明 transient 关键字？

ArrayList 重写了 JDK 序列化的逻辑，只把 elementData 数组中有用元素的部分序列化，而不会序列化整个数组。

// 序列化和反序列化只考虑有用元素
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();
    // 写入数组长度
    s.writeInt(size);
    // 写入有用元素
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

2.6 ArrayList 的 clone() 进程

ArrayList 中的 elementData 数组是引证类型，因而在 clone() 中需求完成深拷贝，否则原目标与克隆目标会相互影响：

public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        // 拷贝数组目标
        v.elementData = Arrays.copyOf(elementData, size);
        // 修正计数归零
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

2.7 为什么阿里巴巴要求慎重运用 subList API？

在 《阿里巴巴 Java 开发手册》中，有关于 ArrayList#subList API 的规定。为什么阿里巴巴要做这样的束缚呢？

  • 【强制】ArrayList 的 subList 结果不可强转成 ArrayList，否则会抛出 ClassCastException 反常；
  • 【强制】在 subList 场景中，高度留意对原调集元素的添加或删去，均会导致子列表的遍历、添加、删去产生 ConcurrentModificationException 反常。

这是由于 subList API 仅仅供给经过起始索引 fromIndex 和停止索引 toIndex 包装了一个原 ArrayList 的 “视图窗口” ，并不是真的截取并创立了一个新的 ArrayList，所以强制类型转换就会抛出 ClassCastException 反常。

此刻，在 ArrayList 或 SubList 上做修正，要留意相互之间的影响：

  • 在 ArrayList 或 SubList 上修正元素，都会同步更新到对方（由于底层都是 ArrayList 自身）；
  • 在 SubList 上添加或删去元素，会影响到 ArrayList；
  • 在 ArrayList 上添加或删去元素，会导致 SubList 抛出 ConcurrentModificationException 反常。

ArrayList.java

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}
private class SubList extends AbstractList<E> implements RandomAccess {
    // 原 ArrayList
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;
    SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        // modCount 记载
        this.modCount = ArrayList.this.modCount;
    }
    public E set(int index, E e) {
        rangeCheck(index);
        // 在 ArrayList 上添加或删去元素，会导致 SubList 抛出 ConcurrentModificationException 反常
        checkForComodification();
        // 在 SubList 上添加或删去元素，会影响到 ArrayList；
        E oldValue = ArrayList.this.elementData(offset + index);
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }
}

2.8 ArrayList 怎么完成线程安全？

有 4 种方式：

  • 办法 1 – 运用 Vector 容器： Vector 是线程安全版别的数组容器，它会在所有办法上添加 synchronized 关键字；
  • 办法 2 – 运用 Collections.synchronizedList 包装类： 原理也是在所有办法上添加 synchronized 关键字；
  • 办法 3 – 运用 CopyOnWriteArrayList 容器： 根据加锁的 “读写分离” 和 “写时仿制” 完成的动态数组，适合于读多写少，数据量不大的场景。
  • 办法 4 – 运用 ArrayBlockingQueue 容器： 根据加锁的堵塞行列，适合于带堵塞操作的生产者消费者模型。

提示： 关于 CopyOnWriteArrayList 的更多内容，去看看专栏文章 《CopyOnWriteArrayList 是怎么确保线程安全的？》

3. Arrays#ArrayList：世界上的另一个我

事实上，在 Java 环境中有两个 ArrayList，这或许是一个隐藏的彩蛋（坑）：

  • ArrayList： 一般以为的 ArrayList，是一个顶级类；
  • Arrays#ArrayList： Arrays 的静态内部类，和上面这个 ArrayList 没有任何关系。

其实，Arrays#ArrayList 的定位便是在数组和和 List 直接切换而已。Arrays 供给了数组转 List 的 API，而 Arrays#ArrayList 也供给了 List 转数组的 API（这些 API 第一个 ArrayList 中也都有…）

回过头看剩下的 2 个问题：

  • ‍♀️疑问 3：为什么 elementData 字段不声明为泛型类型 E？

泛型擦除后等于 Object[] elementData，没有区别。

  • ‍♀️疑问 7：在带调集的结构办法中，为什么会存在调集转化后的数组类型不是 Object[].class 的状况？

这是由于有些 List 调集的底层数组不是 Object[] 类型，有或许是 String[] 类型。而在 ArrayList#toArray() 办法中，回来值的类型是 Object[] 类型，有类型过错危险。

例如：在这段代码中，ArrayList 接纳一个由 String 数组转化的 List，最终在 ArrayList#toArray() 回来的 Object 数组中添加一个 Object 目标，就呈现反常了：

示例代码

// 假定没有特别处理
List<String> list = new ArrayList<>(Arrays.asList("list"));
// class java.util.ArrayList
System.out.println(list.getClass());
Object[] listArray = list.toArray();
// 假如过没有特别处理，实践类型是 [Ljava.lang
System.out.println(listArray.getClass());
// 假如过没有特别处理，将抛出 ArrayStoreException 反常
listArray[0] = new Object();

源码摘要：

Arrays.java

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}
private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable {
    // 泛型擦除后：Object[] a;
    private final E[] a;
    // 泛型擦除后：Object[] array;
    // Java 数组是协变的，能够接纳 String[] 类型的数组
    ArrayList(E[] array) {
        // 赋值
        a = Objects.requireNonNull(array);
    }
    // 实践回来的数组或许是 Object[] 类型，也或许是 String[] 类型
    @Override
    public Object[] toArray() {
        return a.clone();
    }
}

ArrayList.java

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    transient Object[] elementData;
    // 带调集的结构办法
    public ArrayList(Collection<? extends E> c) {
        // 将调集转为数组
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // 疑问 7：这一个条件句子好奇怪，toArray() 的回来值类型便是 Object[] 啊？
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
}

4. ArrayList 这么好用，能够彻底代替数组吗？

大多数场景能够，但不能彻底代替。

ArrayList 是根据 Object 数组封装的动态数组，咱们不需求关心底层数组的数据转移和扩容等逻辑，因而在大多数事务开发场景中，除非是为了最求极致的性能，否则直接运用 ArrayList 代替数组是更好的挑选。

那么，ArrayList 有哪些地方上比数组差呢？

  • 举例 1 – ArrayList 等容器类不支持 int 等基本数据类型，所以必定存在装箱拆箱操作；

  • 举例 2 – ArrayList 默许的扩容逻辑是会扩大到原容量的 1.5 倍，在大数据量的场景中，这样的扩容逻辑是否多余，需求打上问题；

  • 举例 3 – ArrayList 的灵活性不行。ArrayList 不允许底层数据有空泛，所有的有用数据都会 “压缩” 究竟层数组的首部。因而，当需求根据数组二次开发容器时，ArrayList 并不是一个好挑选。

    • 例如，运用 ArrayList 开发栈的结构或许适宜，能够在数组的尾部操作数据。但运用 ArrayList 开发行列就不适宜，由于在数组的首部入队或出队需求转移数据；

    • 而数组没有这些束缚，咱们能够将数组规划为 “环形数组”，就能够防止入队和出队时转移数据。例如 Java 的 ArrayBlockingQueue 和 ArrayDeque 便是根据数组的行列。

5. 总结

  • 1、ArrayList 是根据数组封装的动态数组，封装了操作数组时的转移和扩容等逻辑；

  • 2、在结构 ArrayList 时，除了指定大于 0 的初始容量外，ArrayList 在结构时不会创立数组，而是指向大局空数组，这是懒初始化的策略；

  • 3、在添加数据时会先检查数据容量，缺乏会先扩容。初次添加默许会扩容到 10 容量，后续会扩容到旧容量的 1.5 倍，这是为了防止重复扩容；

  • 4、由于扩容涉及到数据转移操作，所以假如能事前知道数据的容量，最好在创立 ArrayList 时就显式指定数据量巨细；

  • 5、ArrayList 重写了序列化进程，只处理数组中有用的元素；

  • 6、ArrayList 的 subList API 仅仅供给视图窗口，并不是创立新列表；

  • 7、ArrayList 在大多数场景中能够代替数组，但在高性能和二次封装的场景中，ArrayList 无法代替数组。

鄙人一篇文章里，咱们来讨论 ArrayList 的孪生兄弟 —— LinkedList。请重视。

版权声明

本文为稀土技术社区首发签约文章，14天内制止转载，14天后未获授权制止转载，侵权必究！

参考资料

  • 为什么阿里巴巴要求慎重运用 ArrayList 中的 subList 办法 —— HollisChuang 著
  • ArrayList 源码解析，老哥，来一同复习一哈？ —— iisheng 著
  • Arrays.asList(x).toArray().getClass() should be Object[].class —— OpenJDK
  • Why I can’t create an array with large size? —— stack overflow

Java 数据结构：ArrayList 可以完全替代数组吗？