详解Java之集合框架 part1—集合框架概述及其List接口下的常用容器

集合概述

Java 集合框架概述

Java 集合，也叫作容器，主要是由两大接口派生而来：

• 一个是 Collection接口，主要用于存放单一元素；
  • 对于Collection 接口，下面又有三个主要的子接口：List、Set 、 Queue。
• 另一个是 Map 接口，主要用于存放键值对。

Java 集合框架概览

如下是更详细的，带上了抽象类的

image-20260204114015885

集合框架的体系如下

• 接口（Interfaces）：定义集合的行为（如 Collection, List, Set, Queue, Map）。
• 实现类（Implementations）：提供具体的数据结构（如 ArrayList, HashSet, LinkedList, HashMap）。
• 算法（Algorithms）：如排序、查找等（通过 Collections 工具类提供）。
• 迭代器（Iterator）：用于遍历集合元素。

那么，在这里简单说一下 List, Set, Queue, Map 这四个主要集合接口的区别

• List：List继承 Collection，元素严格保持插入顺序，允许重复元素，支持 get(index)索引访问等索引操作，典型实现类有 ArrayList, LinkedList,Vector，也就是说，它的含义是有序可重复列表

• Set：Set继承 Collection，除了LinkedHashSet/TreeSet有序，其他实现无序，而且不允许重复，底部基于equals() 判断，不支持索引访问，一般用于去重和唯一校验，也就是说，它的含义是不可重复列表

  • SortedSet是继承于 Set 用于保存有序的集合的接口。

  • 注意，自定义对象在Set中无法去重，这是因为没有重写equals()和hashCode()方法。确保在将自定义对象存储到Set或Map中时，正确实现这两个方法。

• Queue：Queue继承 Collection，实现均有序，按照 FIFO（先进先出）或按优先级排序， 一般允许重复，不支持索引访问，只能操作队首队尾，存储的元素可以重复，也就是说，它的含义是可重复有序队列

  • Queue 的扩展接口为 Deque，它的含义是双端队列，也可以理解为堆栈，支持栈（LIFO）操作。

    因为 Java 堆栈Stack类已经过时，Java官方推荐使用 Deque 替代 Stack 使用。所以 Deque 支持堆栈操作方法：push()、pop()、peek()等

• Map：Map 是独立接口，代表存储键值对的映射，遵循 Key-Value 结构，每个 Key 唯一，映射最多一个 Value。Key 不可重复，Value 可重复，一般情况下无索引，除LinkedHashMap/TreeMap 均无序

而对于 Collection 接口，Collection 是最基本的集合接口，一个 Collection 代表一组 Object，即 Collection 的元素, Java不提供直接继承自 Collection 的类，只提供继承于 Collection 的子接口（如List和set）。Collection 接口存储一组不唯一，无序的对象。

集合框架常用类概述

我们需要根据他们的特点来选用集合，这里只做一个综述，详细内容针对每个实现类下面再说

所有集合从 Java 5 起支持泛型，避免类型转换错误

List

• ArrayList：底层使用动态数组，它有序，可重复，支持索引访问，初始容量在 JDK 8+ 中空参构造器初始为 0，首次添加时扩容至 10。扩容机制是1.5 倍扩容。对于查询是O(1)，因为是索引访问，增删是O(n)，因为需移动后续元素，非线程安全
• LinkedList：底层结构使用双向链表，首尾增删是O(1)，随机访问是O(n)，因为需遍历。非线程安全。对于 LinkedList，它同时实现 List 和 Deque，可作栈或队列
• Vector：（遗留类，不推荐使用）底层结构类似ArrayList，也是Object[] 数组，而且线程安全，因为 所有方法加 synchronized，所以性能差，扩容是 2 倍扩
  • 子类是Stack后进先出栈，是使用数组实现的栈，不推荐使用
• CopyOnWriteArrayList：并发场景用的ArrayList，底层结构是不可变数组 + 写时复制，读操作无锁，直接读原数组。写操作加锁，复制整个数组修改后替换引用，所以有弱一致性

Set

• HashSet：封装 HashMap，元素存于 key，value 为固定对象 PRESENT，是无序的，而且允许一个 null，增删查平均 O(1)

• LinkedHashSet：封装 LinkedHashMap，在 HashSet 基础上维护双向链表，所以他能保持插入顺序，性能略低于 HashSet，当需去重且保留插入顺序，使用这个

• TreeSet：封装了 TreeMap，基于红黑树，它支持自然排序，因为元素实现了Comparable<T>，而且唯一，因为比较结果为 0 视为重复，不允许null，因无法比较，查询和增删都是O(log n)，代表需排序的唯一集合

• CopyOnWriteArraySet：它的内部使用 CopyOnWriteArrayList，所以也是读无锁，写加锁复制，适合用于并发下的去重集合

• EnumSet：专用于枚举类型，它的底层使用位向量来进行实现，高性能、紧凑内存、但是线程不安全。

• BitSet：一种特殊类型的数组来保存位值，底层使用位向量

Queue

• LinkedList：同时实现 List 和 Queue。针对它作为 Queue 的实现类这边的特点，就是支持 FIFO 队列操作offer(), poll(), peek() 。
• PriorityQueue：底层结构使用二叉堆，其中二叉堆使用数组实现，排序基于自然顺序或 Comparator，而且队首始终是最小元素，不支持null，因为无法比较
• DelayQueue：延时队列，用于各种延时时调度、缓存过期场景，线程安全，基于优先队列PriorityQueue实现，确保最快到期的元素在队列头部
• ReferenceQueue：引用队列，我就在学GC的时候用过两次，奇怪的容器太多了。。。。。

Deque

• ArrayDeque：底层结构是循环数组，所以无容量限制，自动扩容，在性能方面，有说是优于 Stack 和 LinkedList 作栈/队列，不支持 null，JDK建议用它替代 Stack

Map

• HashMap：JDK1.8后，底层结构变成了数组 + 链表 + 红黑树，使用了哈希优化，而且遵循 Key 唯一性，依赖 hashCode() 和 equals()，线程不安全，插入顺序不可靠
• LinkedHashMap：可以理解为保顺序的 HashMap，使用双向链表，维护元素插入顺序（默认）或访问顺序
• TreeMap：自动排序的 Map，因为 Key 实现 Comparable<T>，不允许 null Key
• Hashtable：Hashtable 是个古老的 Map 实现类，貌似已经被淘汰掉了，不同于HashMap，Hashtable 是线程安全的，但是由于是全局锁，性能不是很好，而且不允许 null。一般情况下，我们使用 ConcurrentHashMap
• ConcurrentHashMap：线程安全的 HashMap，支持高并发读，因为读无锁 ，支持并发写，所以有弱一致性，因为会有比较细力度的锁，不允许 null
• WeakHashMap：Key 可被 GC 回收，因为 Key 被包装为 WeakReference，当 Key 无强引用时，GC 可回收，并在下次操作时自动清理 Entry，所以适合用于缓存，避免内存泄漏（普通 Map 的 Key 永远不会被回收）
• IdentityHashMap：基于对象地址比较，比较方式使用 == 而非 equals()
• BitMap：类似 Redis 中的位图，用一个二进制位来标记某个元素的value，也就是说，哪个索引有东西，值为1就，而且查找是O(1)的，去重非常快
• Properties：Properties 类是 Hashtable 的子类，该对象用于处理属性文件
• EnumMap：针对枚举常量的 Map，线程安全

集合框架底层数据结构总结

List

• ArrayList：Object[] 数组。也就是动态数组

  

  image-20260204112337085

• LinkedList：双向链表，它也实现 List 和 Deque

  

  image-20260204115302900

  

  image-20260204115342664

  可以看到是不循环的

  

  image-20260204115401076

• Vector：同样也是 Object[] 数组

  

  image-20260204121239577

• CopyOnWriteArrayList：使用 Object[]动态数组，而且通过 transient volatile 修饰Object[]保证线程安全。

  

  image-20260204123132373

Set

• HashSet：无序，唯一，基于HashMap 实现的，底层采用 HashMap 来保存元素。

  

  image-20260204122727482

  

  image-20260204122807073

• LinkedHashSet：LinkedHashSet 是 HashSet 的子类

  

  image-20260204122846551

  并且其内部是通过 LinkedHashMap 来实现的。

  

  image-20260204122901784

• TreeSet：有序，唯一，内部使用 TreeMap，所以是使用红黑树(自平衡的排序二叉树)

  

  image-20260204122922510

  

  image-20260204123017977

• CopyOnWriteArraySet：内部使用 CopyOnWriteArrayList 包装线程安全

  

  image-20260204123046967

• EnumSet：首先说明，EnumSet是一个抽象类，但是文档中明确指出，枚举集在内部以位向量表示，这种表示极其紧凑高效，真正的位向量实现在其两个包私有的子类中，所以我们使用EnumSet的适合就用EnumSet 的静态工厂方法，EnumSet 的静态工厂方法会根据枚举大小自动选择

  

  image-20260204123348368

  其静态工厂方法

  

  image-20260204123834071

• BitSet：BitSet底部使用动态位向量

  

  image-20260204123937361

  每个 long 占 64 位 ，所以可表示 64 个布尔值，位运算什么的也是O(1)，非常快

Queue

• PriorityQueue：使用 Object[] 数组来实现小顶堆

  

  image-20260204124129473

  其中，初始化就是初始化小顶堆

  

  image-20260204124217643

  

  image-20260204124224223

• DelayQueue：内部使用 PriorityQueue

  

  image-20260204124245974

• ArrayDeque：可扩容的动态双向数组

  

  image-20260204124315952

  

  image-20260204124336548

Map

• HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的，

  

  image-20260204124902726

  JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间

  

  image-20260204124927278

  HashMap 并没有直接使用 key.hashCode() 作为最终的哈希值，而是通过一个内部的 hash() 方法进行了二次处理

  

  image-20260204124956680

• LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。

  

  image-20260204124451369

  而且，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。

  

  image-20260204124502865

• Hashtable：因为是古老的线程安全HashMap，所以结构和古老的HashMap差不多，也是数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。

  

  image-20260204124532896

  

  image-20260204124553497

• TreeMap：红黑树，自平衡的排序二叉树

  

  image-20260204124620597

  

  image-20260204124810960

• EnumMap：支持枚举常量类型的Object[]

  

  image-20260204124721938

集合算法

集合框架定义了几种算法，可用于集合和映射。这些算法被定义为集合类的静态方法。

集合定义三个静态的变量：EMPTY_SET，EMPTY_LIST，EMPTY_MAP的。这些变量都不可改变。

List

List 接口概述

List 是 Java 集合框架（java.util）中有序、可重复的集合接口，继承自 Collection 接口，是日常开发中最常用的集合类型之一。

其核心特征是：元素按插入顺序排列、允许重复元素、支持通过索引访问元素

List 继承了 Collection 的所有方法，并扩展了索引相关的核心方法

方法	作用
E get(int index)	获取指定索引的元素
E set(int index, E element)	替换指定索引的元素，返回原元素
void add(int index, E element)	在指定索引插入元素，后续元素后移
E remove(int index)	删除指定索引的元素，返回被删除元素
int indexOf(Object o)	返回元素首次出现的索引，不存在则返回 -1
int lastIndexOf(Object o)	返回元素最后出现的索引，不存在则返回 -1
List<E> subList(int fromIndex, int toIndex)	截取子列表（左闭右开），注意：子列表是原列表的视图，修改会同步
ListIterator<E> listIterator()	返回支持双向遍历的迭代器（可向前 / 向后遍历，还能添加 / 修改元素）

Java 提供了多个 List 实现类，适配不同的业务场景，核心有以下 4 种

ArrayList

ArrayList的基本特性

对于这个十个容器九个你的常用容器，我感觉我有必要大篇幅的细说一下

ArrayList实现了List接口，是顺序容器，所以 List 的特性有的他也有，所以它有序且允许重复，支持索引访问和操作

但是它线程不安全，它的所有方法都不是线程安全的，所以多线程情况下需要你自己进行同步 Collections.synchronizedList(new ArrayList<>()) 来包装它，或者使用并发容器

源码注释明确指出：Note that this implementation is not synchronized. 如果多个线程同时访问一个 ArrayList 实例，并且至少有一个线程在结构上修改了它（添加或删除元素），那么必须在外部进行同步。

说一下有关基本方法的时间复杂度，size()， isEmpty()，get()，set()方法均能在常数时间内完成，也就是O(1)，add()方法的时间开销跟插入位置有关，因为它是尾部插入高效，在列表末尾添加元素 (add(E e)) 的摊还时间复杂度 (Amortized Time Complexity) 为 O(1)。虽然偶尔会触发 O(n) 的扩容操作，但平摊到每一次 add 操作上，成本是常数级别的。所以说，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间

所以，它查询高效，增删相对低效

而且允许放入 null 元素，底层通过数组（Object[]）实现。不过，不建议向ArrayList 中添加 null 值， null 值无意义，会让代码难以维护比如忘记做判空处理就会导致NPE

image-20260204175014111

这里我说一个误区啊，所以说，生产环境中，不是非 Optional 不可，很多人包括我只是更喜欢在编写业务的时候使用 Optional，来处理可能为 null 的值，因为Optional 不是为了 消灭 null，而是为了规范化、可视化地处理 null，从 ArrayList 取出元素后直接操作是高频场景，Optional 包裹后，能强制你显式处理 null 情况，从语法层面规避 NPE，而且约定大约配置啊，Optional 作为语义化标记能直接告诉大伙这个值可能为 null，需要特殊处理。

更多情况，业务中如果不用 Optional，常需要写大量 if (xxx == null) 或者默认值判断的重复代码，Optional 提供了 orElse()、orElseGet()、orElseThrow() 等方法，这谁不喜欢

虽然说多了，但是我感觉有必要说一下这个事情

而且，每个ArrayList都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。这就是下面会详细说的，扩容机制

ArrayList 在 JDK1.8 前后的实现，有一些区别：

• JDK1.7：像饿汉式，直接创建一个初始容量为10的数组
• JDK1.8：像懒汉式，一开始创建一个长度为0的数组，当添加add第一个元素时再创建一个初始容量为10的数组

ArrayList的结构分析

首先，ArrayList 继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。

image-20260204180312716

这些都是什么意思

• List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
• RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。在 ArrayList 中，我们就可以通过元素的序号快速获取元素对象，这就是快速随机访问。
• Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
• Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便适合进行网络传输

ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。

// 存储元素的底层数组
transient Object[] elementData;

// 列表中实际包含的元素个数
private int size;

// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;

// 用于空实例的共享空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 用于默认大小空实例的共享空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

• 注意，存储元素的底层数组 elementData，它是 transient 的，这意味着在序列化时，JVM 不会自动序列化这个字段。ArrayList 自己实现了 writeObject 和 readObject 方法来控制序列化过程，只序列化实际的元素（size 个），而不是整个 elementData 数组，从而节省空间。
• size:表示列表中实际元素的数量，也是下一个元素将要被插入的位置（索引）。size 永远小于或等于 elementData.length（即容量）。

其中，构造函数如下

• 无参构造

  public ArrayList() {
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }

  初始化一个空的 elementData，指向特殊的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。此时容量为0，直到第一次 add 操作才会扩容到 DEFAULT_CAPACITY (10)。

• 指定初始容量

  

  image-20260204180528859

• 指定集合的元素的列表构造，用的非常非常少，本来都有容器了非要那ArrayList包装一下

  

  image-20260204181018959

常用操作分析

添加元素

这是 ArrayList 最核心的操作之一。以 add 方法为例子

image-20260204181710597

// 核心就这些步骤

public boolean add(E e) {
    modCount++;   // 1. 修改计数器+1，用于fail-fast机制
    add(e, elementData, size);   // 2. 调用私有辅助方法
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)    // 3. 检查是否需要扩容
        elementData = grow();    // 4. 执行扩容
    elementData[s] = e;    // 5. 将元素放入数组,就是赋值
    size = s + 1;     // 6. 更新size
}

• 对于modCount，这是一个继承自 AbstractList 的字段，记录了列表结构被修改的次数。任何结构性修改（增、删、clear）都会增加它。迭代器在创建时会记录当时的 modCount，在每次操作前检查是否一致，不一致则抛出 ConcurrentModificationException。

对于添加元素，JDK21有addFirst(E) / addLast(E)，巨好用，让 ArrayList 在 API 上或者在语义上更像一个双端队列（Deque），尽管性能上 addFirst 依然是 O(n)。getFirst() / getLast()也有

删除元素

以 remove(int index) 为例子说明了，来看这个方法

public E remove(int index) {
    Objects.checkIndex(index, size); // 1. 检查索引有效性
    final Object[] es = elementData;
    @SuppressWarnings("unchecked") E oldValue = (E) es[index]; // 2. 获取旧值
    
    fastRemove(es, index); // 3. 快速删除
    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize = size - 1;
    if (newSize > i) 
        // 4. 将被删除元素后面的元素整体向前移动一位
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null; // 5. 清除最后一个元素的引用，帮助GC
}

• 很明显，删除操作的时间复杂度是 O(n)，因为需要移动被删除元素之后的所有元素
• 而且它会将原 size-1 位置的元素显式设为 null，可以防止内存泄漏

SubList 视图

subList(fromIndex, toIndex) 方法返回的是原列表的一个视图 (View)，而不是一个全新的独立列表，像是浅拷贝，但是又有一定区别，因为，它是返回一个 SubList 内部类实例。

image-20260204202949558

image-20260204202924977

• 对 SubList 的修改会直接反映到原 ArrayList 上，反之亦然，这是双向绑定

• 它结构脆弱，不禁玩，如果在创建 SubList 之后，对原列表进行了结构性修改，那么再对 SubList 进行任何操作都会抛出 ConcurrentModificationException。

  • 原因其实很明显，就是SubList 内部持有对原列表 (root) 的引用，并且有自己的 modCount。它的 modCount 只会在通过 SubList 自身进行修改时才更新。如果原列表被外部修改，root.modCount 改变，但 SubList 的 modCount 没变，两者不一致就会抛异常。

    

    image-20260204203158988

  • 所以说，它不怎么被使用，因为很鸡肋，就这么想，如果你持有一个巨大列表的很小一部分的 SubList，并且丢弃了对原列表的引用，但由于 SubList 内部仍然持有对原列表底层数组 (elementData) 的强引用，会导致整个巨大的数组无法被GC。

常用操作分析

操作	时间复杂度	源码关键点	备注
get(int index)	O(1)	return elementData(index);	直接数组访问，极快。
set(int index, E e)	O(1)	elementData[index] = element;	直接数组赋值。
add(E e)	Amortized O(1)	调用 grow() (偶尔 O(n))	尾部追加，摊还成本低。
add(int index, E e)	O(n)	System.arraycopy(...)	需要移动 index 之后的所有元素。
remove(int index)	O(n)	fastRemove -> System.arraycopy(...)	需要移动 index 之后的所有元素，并清理末尾引用。
remove(Object o)	O(n)	先 indexOf (O(n))，再 fastRemove (O(n))	最坏情况需要遍历两次。
contains(Object o)	O(n)	本质是 indexOf(o) >= 0	需要线性遍历查找。
indexOf(Object o)	O(n)	indexOfRange 线性遍历	从头开始找第一个匹配项。
lastIndexOf(Object o)	O(n)	lastIndexOfRange 从后往前遍历	从尾开始找最后一个匹配项。

扩容机制分析

image-20260204181114008

image-20260204181119525

以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。

然后，在涉及到添加元素的时候，当容量不够了，也就是 size == elementData.length 时，就会触发扩容。

image-20260204181811326

核心方法是grow(int minCapacity)，而入口方法是 private Object[] grow()，它计算出最小需要的容量为 size + 1，并调用重载方法。

image-20260204203759222

我们可以推断其行为，它的扩容有两种操作其大小的情况，其中，扩容的情况如下

• 常规扩容

  数组已经存在（oldCapacity > 0）或者不是由无参构造器创建的空数组。调用 ArraysSupport.newLength 工具方法推断扩容大小

  1. 首选增长量： oldCapacity >> 1，即 oldCapacity / 2然后相加。所以常规情况下，新容量 = 1.5 * 旧容量
  2. *最小增长量： minCapacity - oldCapacity。这确保了即使请求的增长量很大（比如 addAll 一个很大的集合），新容量也至少能满足需求。
  3. 最终容量**： newCapacity = oldCapacity + max(preferredGrowth, minimumGrowth)。

  对于其中ArraysSupport.newLength 内部逻辑，它会选择 max(最小增长量, 首选增长量) 作为实际的增长量。该方法还会处理整数溢出。

  

  image-20260204205202707

• 首次添加元素

  数组是通过无参构造器 new ArrayList<>() 创建的，此时 elementData 指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，上面也说了这个是空列表，且 oldCapacity 为0。

  直接创建一个大小为 DEFAULT_CAPACITY (10) 的新数组。这是一个优化，避免了在第一次 add 时只扩容到1，导致后续频繁扩容。

因为，扩容使用的是 Arrays.copyOf，它是一个拷贝和重引用，频繁扩容会很大的影响性能。

“当我们在 ArrayList 中调用 add 方法添加元素时，它首先会检查当前的元素数量 size 是否等于底层数组的长度。如果相等，说明数组已满，就需要进行扩容。

扩容的具体逻辑在 grow 方法中。对于大多数情况（非首次添加），它会采用一种‘1.5倍’的扩容策略。更准确地说，它会计算一个‘首选增长量’（当前容量的一半）和一个‘最小增长量’（满足本次操作所需的最小空间），然后取两者中的较大值来确定新容量。这个计算是由 JDK 内部的 ArraysSupport.newLength 工具类完成的，它还负责处理整数溢出等边界情况。

有一个特殊情况是，如果我们使用的是无参构造器创建的 ArrayList，那么在第一次添加元素时，它会直接扩容到默认的初始容量10，而不是1。

最终，扩容通过 Arrays.copyOf 方法完成，它会分配一个新的、更大的数组，并将旧数组中的所有元素拷贝过去，然后更新 ArrayList 的内部引用。这个过程的时间复杂度是 O(n)，但由于是‘摊还’的，所以 add 操作的平均时间复杂度仍然是 O(1)。”

迭代器

ArrayList 的迭代器是 Fail-Fast 的。这是 ArrayList 并发安全的核心

image-20260204202428874

首先，modCount是继承自 AbstractList的，就是记录结构修改次数。

private class Itr implements Iterator<E> {
    int cursor;         // 下一个要返回的元素的索引
    int lastRet = -1;   // 上次返回的元素的索引
    int expectedModCount = modCount; // 期望的修改计数

    public E next() {
        checkForComodification(); // 每次操作前都检查
        // ... 返回元素
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

• 在迭代过程中（next(), remove() 等），每次操作前都会调用 checkForComodification()。这个方法就是根据 modCount 的情况做并发检查

  

  image-20260204202509318

迭代器在创建时会保存一份 modCount 的快照叫做expectedModCount。在迭代过程中，如果发现 modCount 发生了变化（意味着有其他线程或代码在外部修改了列表），就会立即抛出 ConcurrentModificationException，告诉你出现了并发修改，ArrayList 处理不好，直接爆了

这是一种快速失败的策略，旨在尽早暴露并发修改的 bug，而不是让程序在不确定的状态下继续运行，避免产生难以预料的结果。

image-20260204181509864

为什么 ArrayList 在进行了这样的检查之后，他还是线程不安全的呢？因为，它是 Fail-Fast 是一种 bug检测机制，而非并发控制和并发实现的手段。它无法在多线程环境下提供绝对的安全性，因为检查和抛异常不是原子的。

换句话说，如果你单线程在迭代过程中直接修改了原列表，也会触发此异常。

所以，在这里产生了一个经典的面试题

List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
for (String s : list) {
    if ("B".equals(s)) {
        list.remove(s); // 这里会抛出 ConcurrentModificationException!因为 List 的增强for循环本质上就是迭代器，所以应该使用迭代器自身的 remove() 方法。
    }
}

LinkedList

基础特性

LinkedList 是一个基于双向链表实现的集合类，经常被拿来和 ArrayList 做比较。

双向链表

关于 LinkedList 和ArrayList的详细对比，我们下面作为一个面试题说

但是，我是能不用LinkedList就不用，不仅需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，而且LinkedList的性能差点意思，而且就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 LinkedList 。

img

另外，不要下意识地认为 LinkedList 作为链表就最适合高频增删，低频读的场景，但是LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的平均时间复杂度都是 O(n) 。这和ArrayList 差了不太多，顶多ArrayList只是尾加看似O(1)

但是，虽然LinkedList 实现了 List 接口，但它与 ArrayList 在性能上有天壤之别。关键在于它的底层结构是双向链表，所以不支持高效的随机访问，你看连 RandomAccess 接口都没有实现

image-20260204210141442

说一下 LinkedList 对于 List 的一些基本特性，首先， LinkedList 是线程不安全的，需要Collections.synchronizedList(new LinkedList<String>())，但是并发场景下更推荐使用 java.util.concurrent.ConcurrentLinkedDeque线程安全的双端队列，它是无锁实现，并发性能远高于同步包装的 LinkedList。

而且 LinkedList 是有序的，它维护了元素的插入顺序，而且也支持重复元素，因为双向链表能做到，而且它支持所有的 List 操作，并允许所有的值，包括null。

对于 LinkedList，无需像 ArrayList 那样维护容量 和 扩容逻辑，链表节点按需创建销毁，理论上无容量上限，受 JVM 内存限制。

“LinkedList 是基于双向链表实现的 List。它的核心优势在于头尾的插入和删除操作都是 O(1) 的常数时间，这得益于它维护了 first 和 last 两个指针。同时，因为它实现了 Deque 接口，所以也非常适合作为栈或队列来使用。

然而，它的致命弱点是不支持高效的随机访问。像 get(int index) 或 set(int index, E e) 这样的操作，都需要从头或尾开始线性遍历，时间复杂度是 O(n)。即使源码中做了‘从近端开始’的优化，也无法改变其线性时间的本质。

因此，在选择 List 实现时，如果应用场景是频繁在列表两端进行增删操作，或者需要当作栈/队列，LinkedList 是很好的选择。但如果需要频繁通过索引访问元素，那么 ArrayList 会是更优的选择。

此外，LinkedList 的迭代器也是 Fail-Fast 的，并且它有自己定制的序列化方法，只序列化有效元素，提高了效率。”

结构分析

这是理解 LinkedList 一切行为的基础。它的底层实现是双向列表

• Node 内部类: 链表的基本单元。

  private static class Node<E> {
      E item;          // 存储的数据
      Node<E> next;    // 指向下一个节点的引用
      Node<E> prev;    // 指向前一个节点的引用
      
      Node(Node<E> prev, E element, Node<E> next) {
          this.item = element;
          this.next = next;
          this.prev = prev;
      }
  }

  每个节点都持有前后两个邻居的引用，这使得在链表中向前或向后遍历都成为可能，也为高效的插入和删除操作奠定了基础。但是是经典的空间换时间

• 头尾指针: LinkedList 通过两个成员变量来管理整个链表。

  transient int size = 0;
  transient Node<E> first; // 指向链表的第一个节点
  transient Node<E> last;  // 指向链表的最后一个节点

  • size: 记录当前元素数量，使得 size() 方法可以在 O(1) 时间内返回。
  • transient: 这些字段不会被默认序列化机制处理，但是不是为了线程安全考虑的，因为 LinkedList 有自己定制的 writeObject/readObject 方法，以保证序列化的效率和正确性。

而且LinkedList 不仅是一个 List，还是一个功能完备的双端队列 (Deque)，可以当作栈 (Stack) 或队列 (Queue) 使用，而且有对应的两套操作的方法

官方推荐用 LinkedList 代替过时的 Stack 类

• 栈操作:
  • push(E e): 等价于 addFirst(e)
  • pop(): 等价于 removeFirst()
• 队列操作:
  • offer(E e): 等价于 add(e) (尾部插入)
  • poll(): 等价于 removeFirst() (头部移除)
• 双端队列
  • deque.offerFirst("b");：头部添加元素
  • deque.offerLast("c"); ：尾部添加元素
  • deque.pollFirst(); ： 移除头部元素
  • deque.pollLast(); ：移除尾部元素

对于其构造方法

image-20260205005325460

为什么 LinkedList 不能实现 RandomAccess 接口0？

• 首先，RandomAccess 是一个标记接口，用来表明实现该接口的类支持随机访问，由于 LinkedList 底层数据结构是链表，内存地址不连续，只能通过指针来定位，底层结构决定了它不能支持随机快速访问，所以不能实现 RandomAccess 接口

常见操作分析

插入元素

对于插入元素，它的性能是 头/尾 O(1)，中间 O(n)

以 尾部插入 (add(E e))为例子

image-20260205010513353

• 对于其中 linkLast 尾插方法

  void linkLast(E e) {
      final Node<E> l = last;
      final Node<E> newNode = new Node<>(l, e, null);
      last = newNode;
      if (l == null) // 如果链表为空
          first = newNode;
      else
          l.next = newNode; // 将原尾节点的 next 指向新节点
      size++;
      modCount++;
  }

  由于 last 指针的存在，尾部插入是 O(1) 操作。

对于任意位置插入add(int index, E e)：这种插入方式需要先移动到指定位置，再修改指定节点的指针完成插入/删除

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index)); // 1. 先通过 node(index) 找到目标节点
}

// 在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

• node(index) 本身是 O(n) 操作，找到节点后的链接操作是 O(1)。所以总的时间复杂度是 O(n)。

因为 LinkedList 我更倾向于把它看成一个队列，所以，我叫成了插入，LinkedList 除了实现了 List 接口相关方法，还实现了 Deque 接口的很多方法，所以我们有很多种方式插入元素。

获取元素

对于随机访问，也就是 get set 方法，它的性能较差，因为需要遍历到 O(n)，这是 LinkedList 最显著的弱点

image-20260205010404299

image-20260205010413548

那么，类似的LinkedList获取元素相关的方法一共有 3 个：

1. getFirst()：获取链表的第一个元素。

   

   image-20260205005455355

2. getLast()：获取链表的最后一个元素。

   

   image-20260205005503967

3. get(int index)：获取链表指定位置的元素。

   

   image-20260205005544659

它们的核心都于node(int index) 这个方法息息相关，get(int index) 或 remove(int index) 等方法内部都调用了该方法来获取对应的节点。

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    // 如果index小于size的二分之一  从前开始查找（向后查找）  反之向前查找
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 遍历，循环向后查找，直至 i == index
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

从这个方法的源码可以看出，该方法通过比较索引值与链表 size 的一半大小来确定从链表头还是尾开始遍历。如果索引值小于 size 的一半，就从链表头开始遍历，反之从链表尾开始遍历。这样可以在较短的时间内找到目标节点，充分利用了双向链表的特性来提高效率

删除元素

LinkedList删除元素相关的方法一共有 5 个：

1. removeFirst()：删除并返回链表的第一个元素。
2. removeLast()：删除并返回链表的最后一个元素。
3. remove(E e)：删除链表中首次出现的指定元素，如果不存在该元素则返回 false。
4. remove(int index)：删除指定索引处的元素，并返回该元素的值。
5. void clear()：移除此链表中的所有元素

以按索引删除 (remove(int index))为例子

image-20260205010818460

可以看到它调用了一个检查下标是否合法的方法，然后就是断开链表的方法unlink，对于这个方法，我们进行如下分析

E unlink(Node<E> x) {
    //  断开x的连接，并将x的前后节点连起来
    // 获取当前节点及其上一个下一个节点
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) { // x是头节点
        // 直接让链表头指向当前节点的下一个节点
        first = next;
    } else {
        // 将前一个节点的 next 指针指向当前节点的下一个节点
        prev.next = next;
        x.prev = null; // help GC
    }

    // 如果下一个节点为空，则说明当前节点是尾节点
    if (next == null) { // x是尾节点
        // 直接让链表尾指向当前节点的前一个节点
        last = prev;
    } else {
        // 将下一个节点的 prev 指针指向当前节点的前一个节点
        next.prev = prev;
        x.next = null; // help GC
    }

    x.item = null; // help GC
    size--;
    modCount++;
    return element;
}

那么，这就是很标准的双向链表的删除方法，通过断开连接跳过这个节点，然后GC掉，如下图

image-20260205011046069

迭代器

和 ArrayList 一样，LinkedList 的迭代器也是 Fail-Fast 的。而且 LinkedList 主要提供了两种迭代器实现：

1. 正向迭代器（ListIterator）：通过 listIterator() 方法获取；

   

   image-20260205012054887

2. 反向迭代器（DescendingIterator）：通过 descendingIterator() 方法获取。

   

   image-20260205011926078

正向迭代器

对于正向迭代器，ListItr 是 LinkedList 的内部私有类，实现了 ListIterator<E> 接口

private class ListItr implements ListIterator<E>

• 源码很多，总之，它支持：
  • 正向遍历（next()）
  • 反向遍历（previous()）
  • 在遍历过程中插入（add()）、删除（remove()）和修改（set()）元素

而且他也有 modCount的映射，所以，上面提到的 LinkedList 在迭代的时候不用迭代器中的方法进行修改的时候，也会爆ConcurrentModificationException()异常，反向正向都是，因为它线程不安全

image-20260205012205686

由于 LinkedList 是双向链表，node(int index) 方法还是和上面说的一样，靠近哪边就从哪边走，这使得 ListItr 在随机访问时仍保持较高效率。

反向迭代器

对于反向迭代器

DescendingIterator 是另一个内部类，它委托给 ListItr 的 previous() 方法来实现反向遍历：

private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() { return itr.hasPrevious(); }
    public E next() { return itr.previous(); }
    public void remove() { itr.remove(); }
}

• 它本质上是一个适配器（Adapter），将 ListItr 的反向操作在这个反向迭代器中重新实现一下需要反向的操作，暴露为标准的 Iterator 接口。
• 因此，它也具备 fail-fast 特性，和上面说的各种内容，不再细说

Spliterator 支持

LinkedList 还实现了 spliterator() 方法，返回一个 LLSpliterator，用于支持并行流

public Spliterator<E> spliterator() {
    return new LLSpliterator<>(this, -1, 0);
}

• LLSpliterator 是一个 late-binding（延迟绑定） 且 fail-fast 的分割迭代器。

• 它支持有限的并行处理，通过 trySplit() 将链表分段处理。

• 同样检查 modCount，确保在并行遍历时若发生结构修改会抛出异常。

序列化

LinkedList 没有使用默认的序列化机制。

对于序列化writeObject

private void writeObject(java.io.ObjectOutputStream s) {
    s.defaultWriteObject(); // 写入非transient字段
    s.writeInt(size);       // 只写入size
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item); // 按顺序写入每个元素
}

• 它自己实现序列化反序列化代码是有一定理由的，你看这个序列化的就是避免了序列化大量的 Node 对象及其 next/prev 引用，只序列化有效数据，效率更高，生成的字节流也更小

反序列化方法readObject

private void readObject(java.io.ObjectInputStream s) {
    s.defaultReadObject();
    int size = s.readInt();
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject()); // 通过linkLast重建链表
}

Vector

对于 ArrayList 的古老的线程安全实现，与 ArrayList 类似，方法加了 synchronized 锁。所以我将不会再多说太多

image-20260204202144713

Vector 的本质是线程安全的动态扩容数组，与 ArrayList 一样，所有元素存储在 Object 数组中

image-20260204202153254

有构造方法四种：

1. 无参构造，初始容量和 ArrayList 一样是10

   

   image-20260204130623153

2. 指定初始容量构造

   

   image-20260204130646696

3. 指定初始容量 + 扩容增量构造

   

   image-20260204130617218

4. 基于集合构造

   

   image-20260204130651700

Vector 的扩容机制

• 和 ArrayList 差不多，调用 add()/addAll() 时，若 elementCount + 新增元素数 > elementData.length，触发扩容方法。

  

  image-20260204130858546

  

  image-20260204130933942

  

  image-20260204130820836

  但是注意是扩容默认 2 倍，ArrayList 是 1.5 倍

最后，它基本被 CopyOnWriteArrayList 替代或者直接使用 ArrayList，仅兼容旧代码时使用。

image-20260204202355306

CopyOnWriteArrayList

基本特性

CopyOnWriteArrayList 是 Java 并发包 (java.util.concurrent) 中一个非常重要的线程安全集合。它在特定的读多写少场景下表现优异。

CopyOnWriteArrayList 完全实现了 java.util.List 接口，因此它具备所有标准 List 的行为和方法，有序啊，可重复啊，可序列化可克隆啊什么的，但是它允许 null 值

image-20260204133759960

• 在 indexOfRange 和 lastIndexOfRange 等方法中，都对 o == null 的情况做了特殊处理，确保 null 值可以被正确地查找和比较。

而且

• 它实现了 RandomAccess 标记接口，表明通过整数索引访问元素是非常高效的（O(1)）。这得益于其底层的数组结构。下标流还是太超模了

  

  image-20260204133915767

关于 CopyOnWriteArrayList 的基本特性，它不仅支持 List 的基本特性，而且自身还有一些特殊的，关于并发方面的独特特性

• 线程安全

  • 这是 CopyOnWriteArrayList 最核心的特性。所有可变操作（mutative operations），如 add, set, remove, clear 等，都是线程安全的。

  • 它不使用传统的锁（如 synchronized 块或 ReentrantLock）来保护整个数据结构而是采用了一种称为 “写时复制” (Copy-On-Write, COW) 的策略。

    • 写时复制指的就是，资源被复制的时候不分配新内存先，而是在等到某一方尝试修改时才真正复制。

    • 写时复制针对读操作无锁，也没必要啊就是我说，写操作加锁并复制，会获取一个独占锁

      

      image-20260204131441478

      1. 复制当前内部数组的完整副本。
      2. 在副本上执行修改操作。
      3. 将内部的引用（volatile Object[] array）原子地指向这个新的副本。
      4. 释放锁。

  • 而且内部的 array 字段被声明为 volatile，这保证了写操作的可见性。一旦写操作完成，所有后续的读操作都能立即看到最新的数组。

    

    image-20260204131522935

• 弱一致性

  • CopyOnWriteArrayList 返回的迭代器（Iterator, ListIterator）是快照 (Snapshot) 式的，因为迭代器在创建时会持有一个对当时内部数组的引用。在迭代器的整个生命周期内，它遍历的都是这个创建时刻的快照。所以说，虽然它迭代过程中永远不会抛出 ConcurrentModificationException，但是CopyOnWriteArrayList 返回的迭代器无法感知在它创建之后发生的任何修改
  • 所以说，它适用于对内存一致性要求不是强实时的场景，你需要容忍它读到稍旧的数据

• 不支持通过迭代器修改:

  • 源码中的 COWIterator 类的 remove(), set(), add() 方法都直接抛出 UnsupportedOperationException。这是由其快照特性决定的。

    

    image-20260204131734489

高级特性和行为分析

内部结构

那么，针对CopyOnWriteArrayList 的内部结构，它

image-20260204131907126

• volatile 关键字是 COW 模式能正确工作的基石。它确保了当一个线程修改了 array 的引用后，其他线程能立刻看到这个新值。

写操作分析

对于其中的写操作，以 add 为例子

public boolean add(E e) {
    synchronized (lock) {            // 1. 获取独占锁
        Object[] es = getArray();    // 2. 获取当前数组
        int len = es.length;
        // 3. 复制数组，并在末尾添加新元素
        es = Arrays.copyOf(es, len + 1); 
        es[len] = e;
        // 4. 原子地替换内部引用
        setArray(es);
        return true;
    }
}

• 它的步骤清除，加锁 -> 读取 -> 复制+修改 -> 替换引用 -> 解锁。

• 但是还是挺要命的有个位置，因为它每次写操作都需要 Arrays.copyOf，这是一个 O(n) 的操作。如果列表很大或者写操作非常频繁，性能开销会非常大。

读操作分析

对于其中的读操作，以 get 为例子

public E get(int index) {
    return elementAt(getArray(), index); // 直接访问 volatile 数组
}

static <E> E elementAt(Object[] a, int index) {
    return (E) a[index];
}

• 整个过程没有任何同步代码块或锁。
• 而且直接通过索引访问数组元素，速度极快。O(1)
• 值得注意的是，array 是 volatile 的，读操作总是拿到的一个对于 CopyOnWriteArrayList 的内部数组的一致的一个引用（人话就是可能是旧的（弱一致性），也可能是新的，但绝不会是部分更新的）

删除操作分析

对于其中的删除操作，它是如何实现线程安全的，以索引删除 remove(int index)为例子吧

在并发集合类中，remove 方法的线程安全实现依赖于底层同步机制。

public E remove(int index) {
    synchronized (lock) {
        Object[] es = getArray();      // 1. 获取当前数组
        int len = es.length;
        E oldValue = elementAt(es, index); // 2. 获取要删除的旧值

        int numMoved = len - index - 1;  // 3. 计算需要移动的元素数量
        Object[] newElements;
        if (numMoved == 0) { 
            // 如果删除的是最后一个元素，只需复制前面部分
            newElements = Arrays.copyOf(es, len - 1);
        } else {
            // 否则，需要复制前半部分和后半部分
            newElements = new Object[len - 1];
            System.arraycopy(es, 0, newElements, 0, index); // 复制前半部分
            // 复制后半部分，跳过被删除的元素
            System.arraycopy(es, index + 1, newElements, index, numMoved);
        }
        setArray(newElements); // 4. 原子替换引用
        return oldValue;
    }
}

• 可以发现，删除也是遵循 COW 的，加锁 -> 复制 -> 修改副本 -> 替换引用

但是它支持按对象删除，这时候就有人问了，上面说的CopyOnWriteArrayList 都是快照保存的，所以找的基准是快照，那么如何保证最终的一致性

再查一遍不就行了………….这对并发来说才算啥

public boolean remove(Object o) {
    Object[] snapshot = getArray(); // 1. 获取一个快照,不加锁
    // 2. 在快照上查找元素的索引
    int index = indexOfRange(o, snapshot, 0, snapshot.length);
    // 3. 如果找到了，并且成功执行了带索引的删除，则返回true
    return index >= 0 && remove(o, snapshot, index);
}

// 私有辅助方法
private boolean remove(Object o, Object[] snapshot, int index) {
    synchronized (lock) {
        Object[] current = getArray();
        int len = current.length;
        // 检查在获取快照和加锁之间这功夫，数组是否已被其他线程修改
        if (snapshot != current) findIndex: {
            // ... (省略了复杂的重新查找逻辑，目的是在current数组中重新定位o)
            // 如果在current中找不到o，直接返回false
        }
        // 找到确切位置后，执行和 remove(int index) 类似的复制和替换操作
        Object[] newElements = new Object[len - 1];
        System.arraycopy(current, 0, newElements, 0, index);
        System.arraycopy(current, index + 1, newElements, index, len - index - 1);
        setArray(newElements);
        return true;
    }
}

• 这个设计很精妙。它首先在不加锁的情况下获取一个快照并查找索引，这是一种乐观的尝试。只有当找到索引后，才去加锁。加锁后，它会再次检查数组是否还是原来的快照（snapshot != current）。如果不是，说明有其他线程已经修改了列表，那么就需要在最新的 current 数组中重新查找 o 的位置，以避免删除错误的元素或基于过时信息操作。这体现了并发编程中的常见优化模式。

私货

而且 CopyOnWriteArrayList 还有一些值得注意的方法

• addIfAbsent(E e)：仅在元素不存在时才添加。它先检查快照中是否存在，如果不存在，再在加锁后再次检查（防止在检查和加锁之间有其他线程插入了相同元素），最后执行添加。这是一种典型的双重检查模式

  

  image-20260204132624637

• subList(int, int): 返回一个 COWSubList 视图。这个子列表也是基于快照的，并且有自己的 expectedArray 字段来检测并发修改（checkForComodification）。如果原列表在子列表创建后被修改，对子列表的任何操作都会抛出 ConcurrentModificationException。

  

  image-20260204132552768

• reversed() (JDK 21+)：返回一个反向视图，贼几把好用就是了

迭代器

emmmm，其实大部分并发容器的迭代器思路是差不多的

在高并发场景下，迭代器常采用弱一致性策略来平衡性能与数据可见性。该机制允许迭代过程中容忍一定程度的数据不一致，以避免全局锁带来的性能瓶颈。

迭代器的源码如下，只贴出部分了

static final class COWIterator<E> implements ListIterator<E> {
    private final Object[] snapshot; // 迭代器持有的快照
    private int cursor;

    COWIterator(Object[] es, int initialCursor) {
        cursor = initialCursor;
        snapshot = es; // 在构造时捕获当前数组
    }

    public E next() {
        if (! hasNext()) throw new NoSuchElementException();
        return (E) snapshot[cursor++]; // 从快照中读取
    }

    public void remove() {
        throw new UnsupportedOperationException(); // 不支持修改
    }
}

• 快照本质特性： snapshot 字段在迭代器创建时就被初始化为 getArray() 的返回值。之后无论原 CopyOnWriteArrayList 如何变化，snapshot 都不会改变。
• fail-safe：因为操作的是独立副本，所以天然避免了 ConcurrentModificationException。

扩容机制

和其他 List 一样，当元素插入时，若当前容量不足，系统将触发自动扩容机制。

image-20260204132927929

• 可以发现，每次添加元素前，add方法会检查是否超出数组边界
• 一旦容量不足，调用Arrays.copyOf创建新数组，大小是加一，注意它是浅复制，仅复制了引用地址，如果你在使用CopyOnWriteArrayList中存储复杂的类型，注意它们的更改情况，而且注意，复制操作阻塞写入，影响并发性能
• CopyOnWriteArrayList中没有 grow 方法来进行扩容

所以说，我一直认为，严格来说，俺寻思之力，CopyOnWriteArrayList 没有传统意义上的扩容机制（如 ArrayList 的 ensureCapacity）。它的扩容是写操作的自然结果。

• 动态增长是必然的，CopyOnWriteArrayList 的底层数组大小完全等于其元素的数量 (size() == array.length)。所以上面看到的每次调用 add 或 addAll 等增加元素的方法时，都会精确地创建一个比当前数组大 N的新数组。
• 我认为 add 操作就是扩容，就这行Arrays.copyOf(es, len + 1)

CopyOnWriteArrayList 的“扩容”不是一个独立的、有策略的步骤，而是其 COW 写操作不可分割的一部分。不这样存不下你不炸了？？

一些面试题

ArrayList 和 Array（数组）的区别

首先，ArrayList 是实现了List接口的一个容器类，可以动态地调整大小，它内部使用数组来存储元素；数组 Array 是 Java 语言内置的一个原生数据结构，用于存储相同类型的多个元素。它在内存中分配一块连续的空间来存储元素，通过索引访问每个元素。

由于 ArrayList 可以动态调整大小，因此非常适合在运行时添加、删除或修改元素的情况下使用，它还提供了一组方便的 API 来处理集合数据。而当我们提到Array 的时候，通常认为它是具有固定长度的，适用于已知元素数量且不会改变的情况，创建它通常需要指定大小，而且认为它只提供索引访问的能力，不具备动态添加、删除元素的能力，需依赖 java.util.Arrays 工具类

ArrayList 可以存储任何类型的对象，但是只能存储对象，包括基本数据类型的包装类和其他引用类；数组 Array 既可以存储基本类型数据，也可以存储对象。

ArrayList 允许你使用泛型来确保类型安全，Array 则不可以。而且对于类型安全，ArrayList是编译期间使用泛型检查，Array 是运行时类型检查。

而且对于基本类型的存储 Array 比 ArrayList<Integer> 快很多

ArrayList 可以添加 null 值吗?

ArrayList 中可以存储任何类型的对象，包括 null 值。不过，不建议向ArrayList 中添加 null 值， null 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。

通常情况下，面对可能出现存储 null 的容器，我们都使用 Optional 来优雅的处理可能存在的 null，来避免在服务运行时候出现 NPE 的情况

ArrayList 插入和删除元素的时间复杂度？

对于插入：

• 头部插入：由于需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O(n)。
• 尾部插入：当 ArrayList 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)，因为它只需要在数组末尾添加一个元素即可；当容量已达到极限并且需要扩容时，则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中，然后再执行 O(1) 的操作添加元素。
• 指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O(n)。

对于删除：

• 头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O(n)。
• 尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O(1)。
• 指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

LinkedList 插入和删除元素的时间复杂度？

头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。

尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。

指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，不过由于有头尾指针，可以从较近的指针出发，因此需要遍历平均 n/4 个元素，时间复杂度为 O(n)。

ArrayList 与 LinkedList 区别?

• 底层数据结构： ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构
• 插入和删除是否受元素位置的影响：
  • ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)），时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位/向前移一位的操作。
  • LinkedList 采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o),remove(int index)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入和删除。
• 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList（实现了 RandomAccess 接口） 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
• 内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间，因为要存放直接后继和直接前驱以及数据
• 所以说最后，它们的区别诞生了它们在不同的应用场景下使用他们，ArrayList 适合使用读多写少的常见， LinkedList 适合于头尾插入删除多的场景，因为LinkedList 其他情况增删元素的平均时间复杂度都是 O(n)

说一说 ArrayList 的扩容机制吧，还有LinkedList为什么不需要扩容

首先，ArrayList 扩容是因为 ArrayList 底层是基于 Object[] 数组实现的动态数组。

由于 Java 数组一旦创建，其长度就固定不变，而 ArrayList 要支持“动态增长”，就必须在容量不足时创建更大的新数组，并将旧数据复制过去，这就是扩容的本质。

当执行 add(E e) 这种添加元素的操作时，如果当前元素数量（size）加 1 超过了底层数组 elementData 的长度（即 capacity），就会触发扩容。

若使用无参构造器时，那么ArrayList的初始容量也不是10，根据elementData 初始是一个空数组（{}），首次添加元素时才扩容到 10。

后续扩容策略是新容量 = 旧容量 + (旧容量 >> 1)，即 1.5 倍扩容，这是最佳扩容大小，而 ArrayList 会计算一个最小扩容大小也就是扩容的目标大小 - 当前空间 = 最小扩容空间，如果最小扩容大小大于了最佳扩容大小，ArrayList 会选择最小扩容大小

LinkedList 不需要扩容的根本原因是 LinkedList 底层是双向链表，不是连续内存结构，此时，内存是按需动态分配的。因此，LinkedList 没有“容量”概念，也不存在“扩容”操作

所以，ArrayList 的扩容是为了在‘连续内存’限制下模拟动态增长，而 LinkedList 天然具备动态性，因为它基于链式存储。

集合中的 fail-fast 和 fail-safe 是什么？

fail-fast（快速失败）和 fail-safe（安全失败）是Java集合框架在处理并发修改问题时，两种截然不同的设计哲学和容错策略。

快速失败的思想即针对可能发生的异常进行提前表明故障并停止运行，通过尽早的发现和停止错误，降低故障系统级联的风险。

在java.util包下的大部分集合（如 ArrayList, HashMap）是不支持线程安全的，为了能够提前发现并发操作导致线程安全风险，提出通过维护一个modCount记录修改的次数，迭代期间通过比对预期修改次数expectedModCount和modCount是否一致来判断是否存在并发操作，从而实现快速失败，由此保证在避免在异常时执行非必要的复杂代码。

而fail-safe也就是安全失败的含义，它旨在即使面对意外情况也能恢复并继续运行，这使得它特别适用于不确定或者不稳定的环境：

该思想常运用于并发容器，最经典的实现就是CopyOnWriteArrayList的实现，通过写时复制（Copy-On-Write）的思想保证在进行修改操作时复制出一份快照，基于这份快照完成添加或者删除操作后，将CopyOnWriteArrayList底层的数组引用指向这个新的数组空间，由此避免迭代时被并发修改所干扰所导致并发操作安全问题，当然这种做法也存在缺点，即进行遍历操作时无法获得实时结果