数据容器

**# 0. 概述

为什么要解析数据容器?

解析数据容器源码，​最终目的不是为了记住每一行代码，而是为了将这些内容的设计智慧内化为自己的工程能力。​​ 这能让：

• ​在编码时，做出最合理的数据结构选择。
• ​在调优时，一针见血地找到性能瓶颈。
• ​在排查问题时，能直击根源，而不仅是处理表面现象。

1. 集合类

集合类概述

在Java中我们提到了集合类,这里不过多赘述,重点记忆集合类的继承关系

常用的集合类有List,Set,Map. 其中List和Set又继承了Collection接口,各接口还提供了不同的实现类. 继承关系图如下：

classDiagram
Java.lang.Object <|-- Map
Map <|-- HashMap
Map <|-- TreeMap
Java.lang.Object <|-- Collection
Collection <|-- Set
Set <|-- HashSet
Set <|-- TreeSet
Collection <|-- List
List <|-- ArrayList
List <|-- LinkedList

1.0 Collection接口

接口介绍(原文档翻译)

集合层次结构中的根接口。集合代表一组对象，这些对象称为其元素。有些集合允许重复元素，有些则不允许。有些是有序的，有些是无序的。具有定义顺序的集合通常是 SequencedCollection 接口的子类型。JDK 不提供此接口的任何直接实现：它提供了更具体子接口（如 Set 和 List）的实现。此接口通常用于在需要最大通用性的情况下传递和操作集合。

包或多重集合（可能包含重复元素的无序集合）应直接实现此接口。

所有通用目的 Collection 实现类（通常通过其子接口之一间接实现 Collection）应提供两个”标准”构造器：一个无参构造器，用于创建空集合；以及一个具有 Collection 类型单参数的构造器，用于创建与其参数具有相同元素的新集合。实际上，后一个构造器允许用户复制任何集合，生成所需实现类型的等效集合。无法强制执行此约定（因为接口不能包含构造器），但 Java 平台库中的所有通用目的 Collection 实现都遵守此约定。

某些方法被指定为可选操作。如果集合实现未实现特定操作，则应定义相应方法以抛出 UnsupportedOperationException。此类方法在集合接口的方法规范中标记为”可选操作”。

某些集合实现对其可能包含的元素有限制。例如，某些实现禁止 null 元素，而某些实现对元素类型有限制。尝试添加不合格元素会抛出未经检查的异常，通常是 NullPointerException 或 ClassCastException。尝试查询不合格元素的存在可能会抛出异常，或者可能仅返回 false；某些实现会表现前一种行为，某些会表现后一种行为。更一般地说，尝试对不合格元素执行操作，如果该操作的完成不会导致将不合格元素插入集合中，则可能会抛出异常或可能成功，具体取决于实现的选项。此类异常在此接口的规范中标记为”可选”。

每个集合自行决定其同步策略。在实现没有提供更强保证的情况下，对正在被另一个线程修改的集合调用任何方法可能会导致未定义行为；这包括直接调用、将集合传递给可能执行调用的方法以及使用现有迭代器检查集合。

集合框架接口中的许多方法都是根据 equals 方法定义的。例如，contains(Object o) 方法的规范说：“当且仅当此集合包含至少一个元素 e 使得 (o==null ? e==null : o.equals(e)) 时返回 true。” 此规范不应被解释为暗示使用非 null 参数 o 调用 Collection.contains 将导致对任何元素 e 调用 o.equals(e)。实现可以自由实现优化，从而避免 equals 调用，例如，首先比较两个元素的哈希码。（Object.hashCode() 规范保证具有不相等哈希码的两个对象不能相等。）更一般地说，各种集合框架接口的实现可以自由利用底层 Object 方法的指定行为，只要实现者认为合适。

某些对集合执行递归遍历的集合操作可能会因自引用实例（集合直接或间接包含自身）而失败并抛出异常。这包括 clone()、equals()、hashCode() 和 toString() 方法。实现可以选择性地处理自引用场景，但是大多数当前实现不这样做。

视图集合
大多数集合管理其包含元素的存储。相比之下，视图集合本身不存储元素，而是依赖后备集合来存储实际元素。视图集合本身未处理的操作被委托给后备集合。视图集合的示例包括 Collections.checkedCollection、Collections.synchronizedCollection 和 Collections.unmodifiableCollection 等方法返回的包装器集合。视图集合的其他示例包括提供相同元素的不同表示的集合，例如 List.subList、NavigableSet.subSet、Map.entrySet 或 SequencedCollection.reversed 提供的集合。对后备集合所做的任何更改在视图集合中都是可见的。相应地，对视图集合所做的任何更改（如果允许更改）都会写回到后备集合。虽然从技术上讲不是集合，但 Iterator 和 ListIterator 的实例也可以允许修改写回到后备集合，并且在某些情况下，对后备集合的修改在迭代期间对 Iterator 是可见的。

不可修改集合
此接口的某些方法被认为是”破坏性的”，并被称为”修改器”方法，因为它们修改它们所操作的集合中包含的对象组。如果此集合实现不支持该操作，可以指定它们抛出 UnsupportedOperationException。如果调用对集合没有影响，此类方法应（但不要求）抛出 UnsupportedOperationException。例如，考虑一个不支持 add 操作的集合。如果在此集合上调用 addAll 方法，并以空集合作为参数，会发生什么？添加零个元素没有影响，因此此集合简单地不执行任何操作且不抛出异常是可接受的。但是，建议此类情况无条件抛出异常，因为仅在特定情况下抛出异常可能导致编程错误。

不可修改集合是指所有修改器方法（如上定义）都被指定为抛出 UnsupportedOperationException 的集合。因此，无法通过调用其任何方法来修改此类集合。为了使集合真正不可修改，从它派生的任何视图集合也必须不可修改。例如，如果 List 是不可修改的，则 List.subList 返回的 List 也是不可修改的。

不可修改集合不一定是不可变的。如果包含的元素是可变的，则整个集合显然是可变的，即使它可能是不可修改的。例如，考虑两个包含可变元素的不可修改列表。如果元素已被修改，则调用 list1.equals(list2) 的结果可能因调用而异，即使两个列表都是不可修改的。但是，如果不可修改集合包含所有不可变元素，则可以认为它实际上是不可变的。

不可修改视图集合
不可修改视图集合是不可修改的集合，并且也是后备集合的视图。其修改器方法抛出 UnsupportedOperationException，如上所述，而读取和查询方法被委托给后备集合。效果是提供对后备集合的只读访问。这对于组件向用户提供对内部集合的读取访问权限，同时防止他们意外修改此类集合非常有用。不可修改视图集合的示例是 Collections.unmodifiableCollection、Collections.unmodifiableList 及相关方法返回的集合。

请注意，对后备集合的更改可能仍然可能，如果发生，它们通过不可修改视图是可见的。因此，不可修改视图集合不一定是不可变的。但是，如果不可修改视图的后备集合实际上是不可变的，或者如果对后备集合的唯一引用是通过不可修改视图，则该视图可以被认为是实际上不可变的。

集合的可序列化性
集合的可序列化性是可选的。因此，没有一个集合接口被声明为实现 java.io.Serializable 接口。但是，可序列化性通常被认为是有用的，因此大多数集合实现都是可序列化的。

公共类（如 ArrayList 或 HashMap）的集合实现如果实际上是可序列化的，则被声明为实现 Serializable 接口。某些集合实现不是公共类，例如不可修改集合。在这种情况下，此类集合的可序列化性在创建它们的方法的规范中或其他适当位置描述。在未指定集合可序列化性的情况下，不保证此类集合的可序列化性。特别是，许多视图集合不可序列化，即使原始集合是可序列化的。

实现 Serializable 接口的集合实现不能保证是可序列化的。原因是，通常集合包含其他类型的元素，并且无法静态确定某些元素类型的实例是否实际上是可序列化的。例如，考虑一个可序列化的 Collection<E>，其中 E 不实现 Serializable 接口。如果该集合仅包含 E 的某个可序列化子类型的元素，或者如果它是空的，则该集合可能是可序列化的。因此，集合被称为有条件可序列化的，因为整个集合的可序列化性取决于集合本身是否可序列化以及所有包含的元素是否也可序列化。

SortedSet 和 SortedMap 实例会出现另一种情况。这些集合可以使用对集合元素或映射键施加排序的 Comparator 创建。仅当提供的 Comparator 也是可序列化的时，此类集合才是可序列化的。

此接口是 Java Collections Framework 的成员。

实现要求：
默认方法实现（继承或其他）不应用任何同步协议。如果 Collection 实现具有特定的同步协议，则必须覆盖默认实现以应用该协议。

自：
1.2

请参阅：
Set, List, Map, SortedSet, SortedMap, HashSet, TreeSet, ArrayList, LinkedList, Vector, Collections, Arrays, AbstractCollection

作者：
Josh Bloch, Neal Gafter

类型形参：
<E> – 此集合中元素的类型

重点:

🔥 核心概念

1. 根接口 - 集合层次结构的顶层接口

2. 元素特性：

   • 允许/禁止重复元素

   • 有序/无序集合

   • 有序集合通常实现 SequencedCollection

⚡ 实现要点

1. JDK 不直接实现 - 只提供 Set、List 等子接口实现

2. Bag/Multiset 应直接实现 Collection 接口

3. 标准构造器要求：

   • 无参构造器（创建空集合）

   • Collection 参数构造器（复制功能）

⚠️ 重要特性

1. 可选操作 - 不支持的操作应抛出 UnsupportedOperationException

2. 元素限制 - 某些实现限制元素类型或禁止 null 元素

3. 线程安全 - 各实现自行决定同步策略

4. equals 优化 - 实现可优化 equals 调用（如先比较 hash code）

🔍 特殊集合类型

1. 视图集合：

   • 不存储元素，依赖后备集合

   • 示例：Collections.unmodifiableCollection、List.subList 等

   • 对视图的修改会写回后备集合

2. 不可修改集合：

   • 所有修改器方法抛出 UnsupportedOperationException

   • 不等于不可变 - 如果元素可变，集合仍可变

   • 派生视图也必须不可修改

3. 不可修改视图集合：

   • 提供对后备集合的只读访问

   • 后备集合的修改在视图中可见

💾 序列化特性

1. 可选序列化 - 集合接口不强制实现 Serializable

2. 条件序列化 - 依赖元素和 Comparator 的可序列化性

3. 视图集合通常不可序列化

🔧 实现要求

• 默认无同步 - 需要同步的实现必须重写默认方法

• 自引用处理 - 递归操作可能对自引用集合失败

源代码解析

源代码

package java.util;  
  
import java.util.function.IntFunction;  
import java.util.function.Predicate;  
import java.util.stream.Stream;  
import java.util.stream.StreamSupport;
 
public interface Collection<E> extends Iterable<E> {  
    // 查询操作
  
    /**  
     * 返回此集合中元素的数量。如果此集合包含的元素超过 Integer.MAX_VALUE，则返回 Integer.MAX_VALUE。
     *    
     * @return 此集合中的元素数量 
     */    
     int size();  
  
  
    /**  
     * 判空操作。如果该集合不包含任何元素，则返回 true
     *    
     * @return 如果该集合不包含任何元素，则返回 true  
     */    
     boolean isEmpty();  
  
    /**  
     * 如果此集合包含指定的元素，则返回 true。更准确地说，当且仅当此集合至少包含一个元素 e，使得 Objects.equals(o, e) 为 true 时，才返回 true。
     *    
     * @param o 要测试其是否存在于此集合中的元素
     * @return 如果此集合包含指定元素，返回true
     * @throws ClassCastException 如果指定元素的类型与此集合不兼容（可选）
     * @throws NullPointerException 如果指定的元素为null并且此集合不允许 null 元素
     */    
     boolean contains(Object o);  
  
    /**  
     * 返回此集合中元素的迭代器。对于元素返回的顺序没有保证（除非此集合是某个提供保证的类的实例）。  
     * @return 对该集合中元素的迭代器
     */    
     Iterator<E> iterator();  
  
    /**  
     * 返回一个包含此集合中所有元素的数组。如果此集合对其迭代器返回元素的顺序做出任何保证，则此方法必须按相同的顺序返回元素。返回的数组的运行时组成类型是 Object。
     *    
     * 返回的数组将是“安全的”，因为此集合不会保留对它的任何引用。（换句话说，即使该集合由数组支持，此方法也必须分配一个新数组。）因此，调用者可以自由地修改返回的数组。  
     *    
     * API 说明 
     * 这种方法充当基于数组的 API 和基于集合的 API 之间的桥梁。它返回一个运行时类型为 Object[] 的数组。使用 toArray(T[]) 可以重用现有数组，或使用 toArray(IntFunction) 来控制数组的运行时类型。
       
     * @return 一个数组，其运行时组件类型为 Object，包含此集合中的所有元素
     */    
     Object[] toArray();  
  
    /**  
     * 返回一个包含此集合中所有元素的数组；返回数组的运行时类型与指定数组相同。如果集合能够容纳在指定数组中，则返回该数组。否则，将分配一个新数组，其运行时类型为指定数组的类型，大小为此集合的大小。    
     *    
     * 如果此集合能够放入指定的数组并且还有剩余空间（即数组的元素多于此集合的元素），则集合末尾之后的数组元素将被设置为 null。（仅当调用者知道此集合不包含任何 null 元素时，这在确定集合长度时才有用。）
     *    
     * 如果该集合对其迭代器返回元素的顺序提供任何保证，则此方法必须以相同的顺序返回元素。      *    
     * API 说明
     * 此方法作为基于数组和基于集合的 API 之间的桥梁。它允许在特定情况下重用现有数组。使用 toArray() 可以创建运行时类型为 Object[] 的数组，或者使用 toArray(IntFunction) 来控制数组的运行时类型。假设 x 是一个已知仅包含字符串的集合。以下代码可用于将集合导入预先分配的 String 数组：String[] y = new String[SIZE];...y = x.toArray(y);返回值会重新赋给变量 y，因为如果集合 x 中的元素过多而无法放入现有数组 y，将会分配一个新的数组并返回。注意，toArray(new Object[0]) 在功能上与 toArray() 是相同的。
     *    
     * @param <T> 数组的组件类型以包含集合
     * @param a 将此集合的元素存储到的数组，如果数组足够大；否则，将为此目的分配一个相同运行时类型的新数组。  
     * @return 包含此集合中所有元素的数组
     * @throws ArrayStoreException 如果此集合中任何元素的运行时类型不可分配给指定数组的运行时组件类型
     * @throws NullPointerException 如果指定的数组为 null
       
       允许在某些场景下复用已有数组，减少内存分配开销
     */    
     <T> T[] toArray(T[] a);  
  
  
    /**  
     * 返回一个包含此集合中所有元素的数组，使用提供的生成器函数来分配返回的数组。
     *    
     * 如果此集合对其迭代器返回元素的顺序有任何保证，则此方法必须以相同的顺序返回这些元素。    
     *    
     * API 说明  
     * 此方法充当基于数组的 API 与基于集合的 API 之间的桥梁。它允许创建特定运行时类型的数组。使用 toArray() 可以创建运行时类型为 Object[] 的数组，或者使用 toArray(T[]) 来重用现有数组。假设 x 是一个已知仅包含字符串的集合。以下代码可用于将集合内容转储到新分配的 String 数组中：String[] y = x.toArray(String[]::new);
     *  
     * 实现要求 
     * 默认实现使用零调用生成器函数，然后将生成的数组传递给 toArray(T[])。
     *    
     * @param <T> 数组中用于包含集合的组件类型
     * @param generator 一个生成所需类型和指定长度的新数组的函数    
     * @return 包含此集合中所有元素的数组
     * @throws ArrayStoreException 如果此集合中任何元素的运行时类型不可分配给生成数组的运行时组件类型
     * @throws NullPointerException 如果生成器函数为空
     * @since 11  
       
       特点：
       自定义数组生成器：通过 IntFunction<T[]> 提供一个函数，由其决定如何创建目标数组。
       无需预分配数组：开发者只需提供“如何生成数组”的逻辑，无需手动创建数组。
       更灵活：适用于需要特定运行时类型的数组（如 String[]、Integer[] 等）。
     */    
     default <T> T[] toArray(IntFunction<T[]> generator) {  
        return toArray(generator.apply(0));  
    }  
    
    // 修改操作
  
    /**  
     * 所有集合类（如 List, Set, Queue）共有的基础操作之一
     * 确保此集合包含指定的元素（可选操作）。如果由于此调用而导致集合发生变化，则返回 true。（如果此集合不允许重复且已包含指定元素，则返回 false。） 
     *  
     * 支持此操作的集合可能会对可以添加到该集合中的元素施加限制。尤其是，一些集合会拒绝添加 null 元素，而其他集合则会对可添加元素的类型施加限制。集合类应在其文档中明确说明对可添加元素的任何限制。
     *  
     * 如果一个集合因任何原因拒绝添加某个特定元素（除了它已经包含该元素之外），则必须抛出异常（而不是返回 false）。这样可以保持一个不变量，即在此调用返回后，集合始终包含指定的元素。
     *    
     * @param e 需要确保在此集合中存在的元素
     * @return 如果此集合因调用而发生了变化，返回true
     * @throws UnsupportedOperationException 如果此集合不支持添加操作
     * @throws ClassCastException 如果指定元素的类阻止它被添加到此集合中  
     * @throws NullPointerException 如果指定的元素为 null 并且此集合不允许包含 null 元素  
     * @throws IllegalArgumentException 如果元素的某些属性阻止它被添加到此集合中
     * @throws IllegalStateException 如果由于插入限制当前无法添加该元素
     */    
       
    boolean add(E e);  
  
    /**  
     * 如果此集合中存在指定的元素，则从集合中删除该元素的一次出现（可选操作）。更正式地说，如果此集合包含一个或多个这样的元素，则删除一个满足 Objects.equals(o, e) 的元素。如果此集合包含指定的元素（或者等价地，如果此集合因为此次调用而发生了变化），则返回 true。
     *    
     * @param o 如果存在，从此集合中移除的元素
     * @return 如果一个元素因该调用而被移除，返回true
     * @throws ClassCastException 如果指定元素的类型与此集合不兼容（可选） 
     * @throws NullPointerException 如果指定的元素为 null 并且此集合不允许包含 null 元素
     * @throws UnsupportedOperationException 如果此集合不支持移除操作
     */    
    boolean remove(Object o);  
  
  
    // 批量操作
  
    /**  
     * 如果这个集合包含指定集合里的所有元素，就会返回 true。    
     *    
     * @param  c 要检查是否包含在此集合中的集合
     * @return 如果此集合包含指定集合中的所有元素，返回true    
     * @throws ClassCastException 如果指定集合中一个或多个元素的类型与此集合不兼容
     * @throws NullPointerException 如果指定的集合包含一个或多个空元素，并且该集合不允许空元素（#optional-restrictions 可选），或者如果指定的集合为 null。 
     * @see    contains(Object)  
     */    
     boolean containsAll(Collection<?> c);  
  
  
    /**  
     * 将指定集合中的所有元素添加到此集合中（可选操作）。如果在操作进行期间指定的集合被修改，则此操作的行为是未定义的。（这意味着如果指定的集合是此集合且该集合非空，则此调用的行为是未定义的。）如果指定的集合具有定义的遍历顺序，其元素的处理通常按该顺序进行。   
     *    
     * @param c 包含要添加到此集合中的元素的集合
     * @return 如果此集合因调用而发生变化，返回true
     * @throws UnsupportedOperationException 如果此集合不支持 addAll 操作
     * @throws ClassCastException 如果指定集合中的某个元素的类阻止其被添加到此集合中     
     * @throws NullPointerException 如果指定的集合包含空元素，而此集合不允许空元素，或者指定的集合为 null
     * @throws IllegalArgumentException 如果指定集合中的某个元素的某些属性阻止它被添加到此集合中  
     * @throws IllegalStateException 如果由于插入限制无法在此时添加所有元素    
     * @see add(Object)  
     */    
     boolean addAll(Collection<? extends E> c);  
  
    /**  
     * 移除此集合中所有也包含在指定集合中的元素（可选操作）。在此方法返回后，此集合将不包含与指定集合共有的任何元素。    
     *    
     * @param c 包含将从此集合中移除的元素的集合
     * @return 如果此集合因调用而发生更改，则为真    
     * @throws UnsupportedOperationException 如果此集合不支持 removeAll 操作  
     * @throws ClassCastException 如果此集合中一个或多个元素的类型与指定的集合不兼容
     * @throws NullPointerException 如果此集合包含一个或多个空元素，并且指定的集合不支持空元素（#optional-restrictions 可选限制），或者指定的集合为 null 
     * @see #remove(Object)  
     * @see #contains(Object)  
     */    
     boolean removeAll(Collection<?> c);  
  
    /**  
     * 移除此集合中所有满足给定条件的元素（可选操作）。在迭代过程中或由谓词引发的错误或运行时异常将传递给调用方。    
     *    
     * 实现要求
     * 默认实现使用其迭代器遍历集合的所有元素。每个匹配的元素都使用 Iterator.remove() 方法移除。如果集合的迭代器不支持移除操作，则在第一个匹配的元素上会抛出 UnsupportedOperationException 异常。    
     *    
     * @param filter 一个返回 true 的谓词，用于要被移除的元素
     * @return 如果任意元素被移除，则为真
     * @throws NullPointerException 如果指定的过滤器为 null
     * @throws UnsupportedOperationException 如果此集合不支持 removeIf 操作
     * @since 1.8  
     */    
     default boolean removeIf(@NotNull Predicate<? super E> filter) {  
        Objects.requireNonNull(filter);  
        boolean removed = false;  
        final Iterator<E> each = iterator();  
        while (each.hasNext()) {  
            if (filter.test(each.next())) {  
                each.remove();  
                removed = true;  
            }
        }
        return removed;  
    }  
    /**  
     * 保留当前集合中也存在于指定集合 c 中的所有元素，即只保留两个集合的交集部分。   
     *    
     * @param c 包含要保留在此集合中的元素的集合
     * @return {@code true} if this collection changed as a result of the call  
     * @throws UnsupportedOperationException 如果此集合不支持 retainAll 操作 
     * @throws ClassCastException 如果此集合中一个或多个元素的类型与指定的集合不兼容
     * @throws 如果此集合包含一个或多个空元素，并且指定的集合不允许空元素（#可选限制 可选）或者指定的集合为 null
     * @see #remove(Object)  
     * @see #contains(Object)  
     */    
     boolean retainAll(Collection<?> c);  
  
    /**  
     * 从此集合中移除所有元素（可选操作）。在此方法返回后，集合将为空。    
     *    
     * @throws UnsupportedOperationException 如果此集合不支持清空操作
     */    
    void clear();  
  
  
  
    // 比较和哈希
  
    /**  
     * 将指定的对象与此集合进行比较以确定是否相等。 --> 内容比较 
     *  
     * 虽然 Collection 接口没有对 Object.equals 的一般契约增加任何规定，但直接实现 Collection 接口的程序员（换句话说，创建一个是 Collection 但不是 Set 或 List 的类）如果选择重写 Object.equals，则必须小心。其实没有必要这样做，最简单的做法是依赖 Object 的实现，但实现者可能希望实现“值比较”来替代默认的“引用比较”。（List 和 Set 接口要求必须进行这种值比较。）
     *  
     * Object.equals 方法的一般契约规定，equals 方法必须是对称的（换句话说，a.equals(b) 当且仅当 b.equals(a)）。List.equals 和 Set.equals 的契约则规定，列表只与其他列表相等，集合只与其他集合相等。因此，一个自定义的集合类的 equals 方法，如果它既不实现 List 接口也不实现 Set 接口，当该集合与任何列表或集合进行比较时，必须返回 false。（根据同样的逻辑，不可能编写一个既正确实现 Set 接口又实现 List 接口的类。）
     *    
     * @param o 要与此集合进行相等比较的对象
     * @return 如果指定对象与此集合相等，则为 true    
     *   
     * @see Object#equals(Object)  
     * @see Set#equals(Object)  
     * @see List#equals(Object)  
     */   
     boolean equals(Object o);  
  
  
    /**  
     * 返回此集合的哈希码值。虽然 Collection 接口没有对 Object.hashCode 方法的一般约定添加任何要求，但程序员应注意，任何重写 Object.equals 方法的类也必须重写 Object.hashCode 方法，以满足 Object.hashCode 方法的一般约定。特别地，c1.equals(c2) 意味着 c1.hashCode() == c2.hashCode()。
     *    
     * @return 此集合的哈希码值
     *    
     * @see Object#hashCode()  
     * @see Object#equals(Object)  
     */   
     int hashCode();  
  
    /**  
     * 实现高效的 并行处理 和 分片遍历
     * 在此集合中的元素上创建一个 Spliterator。实现应记录 Spliterator 报告的特性值。如果 Spliterator 报告了 Spliterator.SIZED 并且此集合不包含任何元素，则不需要报告这些特性值。    
     *    
     * 默认实现应由可以返回更高效分割迭代器的子类覆盖。为了保持 stream() 和 parallelStream() 方法的预期惰性行为，分割迭代器应拥有 IMMUTABLE 或 CONCURRENT 特性，或采用延迟绑定。如果这些都不可行，覆盖类应描述分割迭代器在绑定和结构干扰方面的文档策略，并应覆盖 stream() 和 parallelStream() 方法，以使用分割迭代器的 Supplier 创建流，如下所示：
     *     Stream<E> s = StreamSupport.stream
       (() -> spliterator(), spliteratorCharacteristics)  
       
     * 这些要求确保由 stream() 和 parallelStream() 方法生成的流将在终端流操作开始时反映集合的内容。   
     *    
     * 实现要求 
     * 默认实现从集合的迭代器创建一个延迟绑定的拆分迭代器。该拆分迭代器继承了集合迭代器的快速失败特性。创建的拆分迭代器会报告 Spliterator.SIZED。
     *    
     * 实现说明
     * 创建的 Spliterator 还会报告 Spliterator.SUBSIZED。如果一个 spliterator 不包含任何元素，那么除了 SIZED 和 SUBSIZED之外的其他特性值报告，对客户端控制、专门化或简化计算没有帮助。然而，这确实允许对于空集合共享使用不可变且空的 spliterator 实例（参见 Spliterators.emptySpliterator()），并使客户端能够确定该 spliterator 是否不包含任何元素。   
     *    
     * @return a 对该集合中的元素进行分割迭代
     * @since 1.8  
     */    
    @Override  
    default Spliterator<E> spliterator() {  
        return Spliterators.spliterator(this, 0);  
    }  
    
    
    /**  
     * 返回一个以此集合作为源的顺序流。
     *    
     * 当 spliterator() 方法无法返回 IMMUTABLE、CONCURRENT 或延迟绑定的 spliterator 时，应重写此方法。（详情请参见 spliterator()。）    
     *    
     * 实现要求 
     * 默认实现会从集合的 Spliterator 创建一个顺序流。
     *    
     * @return a 对该集合中的元素进行顺序流处理
     * @since 1.8  
     */    
    default Stream<E> stream() {  
        return StreamSupport.stream(spliterator(), false);  
    }  
    /**  
     * 返回一个可能并行的流，以此集合作为其来源。此方法也可以返回顺序流。   
     *    
     * 当 spliterator() 方法无法返回 IMMUTABLE、CONCURRENT 或延迟绑定的 spliterator 时，应重写此方法。（详情请参见 spliterator()。） 
     *    
     * 实现要求
     * 默认实现会从集合的 Spliterator 创建一个并行流。
     *    
     * @return 在此集合中的元素上可能的并行流 
     * @since 1.8  
       
       使用场景: 利用多线程并行处理集合数据，简化并发编程的同时提高处理效率，特别适用于大数据量和计算密集型场景。
     */    
    default Stream<E> parallelStream() {  
        return StreamSupport.stream(spliterator(), true);  
    }
}

1.1 List

List接口

API介绍

一个有序集合，用户能够精确控制每个元素在列表中的插入位置。用户可以通过元素的整数索引（在列表中的位置）来访问元素，并可以搜索列表中的元素。

与集合（Set）不同，列表通常允许重复元素。更正式地说，列表通常允许存在成对的元素 e1 和 e2，且满足 e1.equals(e2)。如果列表允许空元素，它们通常也允许多个空元素。虽然可以想象有人可能希望通过在用户尝试插入重复元素时抛出运行时异常来实现一个禁止重复元素的列表，但我们预计这种用法很少见。

List 接口在 Collection 接口指定的约定之外，还对迭代器、add、remove、equals 和 hashCode 方法的契约附加了规定。为了方便起见，此处也包含了其他继承方法的声明。

List 接口提供了四种通过位置（索引）访问列表元素的方法。列表（像 Java 数组一样从零开始索引）。请注意，对于某些实现（例如 LinkedList 类），这些操作执行所需的时间可能与索引值成正比。因此，如果调用者不了解具体实现，遍历列表中的元素通常比通过索引遍历更可取。

List 接口提供了一种特殊的迭代器，称为 ListIterator，除了 Iterator 接口提供的常规操作外，它还允许元素的插入和替换，以及双向访问。还提供了一个方法用于获取从列表中指定位置开始的列表迭代器。

List 接口提供了两种方法来搜索指定对象。从性能角度看，应谨慎使用这些方法。在许多实现中，它们将执行代价高昂的线性搜索。

List 接口提供了两种方法，用于在列表中的任意点高效地插入和删除多个元素。

注意：虽然允许列表将自身作为元素包含在内，但应极其谨慎：在此类列表上，equals 和 hashCode 方法不再有明确的定义。

某些列表实现对它们可能包含的元素有限制。例如，某些实现禁止空元素，而某些实现对元素的类型有限制。尝试添加不合格的元素会抛出未经检查的异常，通常是 NullPointerException 或 ClassCastException。尝试查询不合格元素是否存在可能会抛出异常，或者可能仅返回 false；有些实现会表现前一种行为，有些则会表现后一种行为。更一般地说，对不合格元素尝试执行某个操作，如果该操作的完成不会导致将不合格元素插入列表中，则该操作可能抛出异常，也可能成功，这取决于实现的选择。在此接口的规范中，此类异常被标记为”可选的”。

源代码解析

源代码

public interface List<E> extends SequencedCollection<E> {  
    // 查询选项
  
    /**  
     * 返回此列表中的元素数量。如果此列表包含的元素数量超过Integer.MAX_VALUE，则返回Integer.MAX_VALUE。
     *     
     * @return 返回此列表中的元素数量
     */    
     int size();  
  
    /**  
     * 如果列表中没有元素返回true
     *     
     * @return {@code true} if this list contains no elements  
     */    
     boolean isEmpty();  
  
    /**  
     * 如果此列表包含指定元素，则返回true。更正式地说，当且仅当此列表至少包含一个元素e，使得Objects.equals(o, e)为真时，返回true。
     *     
     * @param o 要测试此列表中是否存在的元素
     * @return 如果此列表包含指定元素，则为true 
     * @throws ClassCastException 如果指定元素的类型与此列表不兼容（可选） 
     * @throws NullPointerException 如果指定的元素为null，并且此列表不允许null元素
     */    
     boolean contains(Object o);  
  
    /**  
     * Returns an iterator over the elements in this list in proper sequence.     *     * @return an iterator over the elements in this list in proper sequence  
     */    
     Iterator<E> iterator();  
  
    /**  
     * 返回一个数组，该数组按正确的顺序（从第一个元素到最后一个元素）包含此列表中的所有元素。     
     *     
     * 返回的数组将是“安全的”，因为此列表不维护对它的引用。（换句话说，即使此列表由数组支持，此方法也必须分配一个新数组）。因此，调用者可以自由修改返回的数组。
     *     
     * 此方法充当基于数组和基于集合的API之间的桥梁。
     *   
     * @return 按正确顺序包含此列表中所有元素的数组
     * @see Arrays#asList(Object[])  
     */    
     Object[] toArray();  
  
    /**  
     * 返回一个数组，该数组按正确的顺序（从第一个元素到最后一个元素）包含此列表中的所有元素；返回数组的运行时类型是指定数组的类型。如果列表适合指定的数组，则返回该数组。否则，将使用指定数组的运行时类型和此列表的大小分配一个新数组。
     *   
     * 如果列表适合指定的数组，并且有多余的空间（即数组的元素比列表多），则列表末尾后面的数组中的元素将设置为null。（只有当调用者知道列表不包含任何空元素时，这才有助于确定列表的长度。）
     *     
     * 与toArray（）方法一样，此方法充当基于数组和基于集合的API之间的桥梁。此外，这种方法允许对输出数组的运行时类型进行精确控制，并且在某些情况下可用于节省分配成本。
     *     
     * 假设x是一个已知只包含字符串的列表。以下代码可用于将列表转储到新分配的String数组中：
     * String[] y = x.toArray(new String[0]);  
     * 
     * 请注意，toArray（new Object[0]）的函数与toArray（）完全相同。
     *    
     * @param a 此列表中的元素要存储到的数组（如果足够大）；否则，将为此分配一个相同运行时类型的新数组。
     * @return 包含此列表元素的数组
     * @throws ArrayStoreException 如果指定数组的运行时类型不是此列表中每个元素的运行时类型的超类型     
     * @throws NullPointerException 如果指定的数组为null
     */    
     <T> T[] toArray(T[] a);  
  
  
    // 修改操作
  
    /**  
     * 将指定元素附加到此列表的末尾（可选操作）。
     *     
     * 支持此操作的列表可能会限制可以添加到此列表中的元素。特别是，一些列表将拒绝添加空元素，而另一些列表将对可能添加的元素类型施加限制。列表类应在其文档中明确规定对可以添加哪些元素的任何限制。
     *    
     * @param e 要附加到此列表的元素
     * @return true（由Collection.add指定） 
     * @throws UnsupportedOperationException 如果此列表不支持添加操作
     * @throws ClassCastException 如果指定元素的类阻止将其添加到此列表中 
     * @throws NullPointerException 如果指定的元素为null，并且此列表不允许null元素   
     * @throws IllegalArgumentException 如果此元素的某些属性阻止将其添加到此列表中  
     */    
     boolean add(E e);  
  
    /**  
     * R如果指定元素存在，则从该列表中删除第一个出现的元素（可选操作）。如果此列表不包含元素，则保持不变。更正式地说，删除索引i最低的元素，使Objects.equals（o，get（i））（如果存在这样的元素）。如果此列表包含指定元素（或者等效地，如果此列表因调用而更改），则返回true。
     *   
     * @param o 要从此列表中删除的元素（如果存在）  
     * @return 如果此列表包含指定元素，则为true  
     * @throws ClassCastException 如果指定元素的类型与此列表不兼容（可选）  
     * @throws NullPointerException 如果指定的元素为null，并且此列表不允许null元素（可选）
     * @throws UnsupportedOperationException 如果此列表不支持删除操作
     */    
     boolean remove(Object o);  
  
  
    // 批量修改操作 
  
    /**  
     * 如果此列表包含指定集合的所有元素，则返回true
     *   
     * @param  c 要检查此列表中包含的集合
     * @return 如果此列表包含指定集合的所有元素，则为true
     * @throws ClassCastException 如果指定集合中的一个或多个元素的类型与此列表不兼容（可选） 
     * @throws NullPointerException 如果指定的集合包含一个或多个空元素，并且此列表不允许空元素（可选），或者如果指定的集为空  
     * @see #contains(Object)  
     */    
     boolean containsAll(Collection<?> c);  
  
  
    /**  
     * 按照指定集合的迭代器返回的顺序，将指定集合中的所有元素附加到此列表的末尾（可选操作）。如果在操作过程中修改了指定的集合，则此操作的行为未定义。（请注意，如果指定的集合是此列表，并且它不是空的，则会发生这种情况。）
     *   
     * @param c 包含要添加到此列表的元素的集合
     * @return 如果此列表因调用而更改，则为true 
     * @throws UnsupportedOperationException 如果此列表不支持addAll操作
     * @throws ClassCastException 如果指定集合的某个元素的类阻止将其添加到此列表中  
     * @throws NullPointerException 如果指定的集合包含一个或多个空元素，并且此列表不允许空元素，或者如果指定的集为空
     * @throws IllegalArgumentException 如果指定集合的某个元素的某些属性阻止将其添加到此列表中     
    * @see #add(Object)  
    */    
     boolean addAll(Collection<? extends E> c);  
     
     
    /**  
     * 将指定集合中的所有元素插入到此列表的指定位置（可选操作）。将当前位于该位置的元素（如果有的话）和任何后续元素向右移动（增加其索引）。新元素将按照指定集合的迭代器返回的顺序出现在此列表中。如果在操作过程中修改了指定的集合，则此操作的行为未定义。（请注意，如果指定的集合是此列表，并且它不是空的，则会发生这种情况。）    
     *     
     * @param index 从指定集合中插入第一个元素的索引 
     * @param c 包含要添加到此列表的元素的集合
     * @return 如果此列表因调用而更改，则为true  
     * @throws UnsupportedOperationException 如果此列表不支持addAll操作
     * @throws ClassCastException 如果指定集合的某个元素的类阻止将其添加到此列表中
     * @throws NullPointerException 如果指定的集合包含一个或多个空元素，并且此列表不允许空元素，或者如果指定的集为空  
     * @throws IllegalArgumentException 如果指定集合的某个元素的某些属性阻止将其添加到此列表中
     * @throws IndexOutOfBoundsException 如果索引超出范围(索引<0||索引>size()) 
     */    
     boolean addAll(int index, Collection<? extends E> c);  
      
    /**  
     * 从此列表中删除指定集合中包含的所有元素（可选操作）   
     *    
     * @param c 包含要从此列表中删除的元素的集合
     * @return 如果此列表因调用而更改，则为true
     * @throws UnsupportedOperationException 如果此列表不支持removeAll操作
     * @throws ClassCastException 如果此列表中某个元素的类与指定的集合不兼容（可选）
     * @throws NullPointerException 如果此列表包含null元素，并且指定的集合不允许null元素（可选），或者如果指定的集合为null
     * @see #remove(Object)  
     * @see #contains(Object)  
     */    
     boolean removeAll(Collection<?> c);  
  
    /**  
     * 仅保留此列表中包含在指定集合中的元素（可选操作）。换句话说，将此列表中所有不在指定集合中的元素移除。
     *    
     * @param c 包含需保留在本列表中的元素的集合
     * @return 如果此列表因调用而发生更改，则为真  
     * @throws UnsupportedOperationException 如果此列表不支持retainAll操作
     * @throws ClassCastException 如果此列表中某个元素的类与指定的集合不兼容（可选）
     * @throws NullPointerException 如果此列表包含null元素，并且指定的集合不允许null元素（可选），或者如果指定的集合为null    
     * @see #remove(Object)  
     * @see #contains(Object)  
     */    
     boolean retainAll(Collection<?> c);  
  
    /**  
     * 将此列表的每个元素替换为对该元素应用运算符的结果（可选操作）。操作员抛出的错误或运行时异常会转发给调用者。
     *    
     * @implSpec  
       实现要求: 
     * 对于此列表，默认实现等效于：  
     * final ListIterator<E> li = list.listIterator();
	   while (li.hasNext()) {
         li.set(operator.apply(li.next()));
	   } 
     *  
     * 如果列表的列表迭代器不支持set操作，则在替换第一个元素时将抛出 UnsupportedOperationException。   
     *    
     * @param operator 应用于每个元素的运算符
     * @throws UnsupportedOperationException 如果此列表不支持replaceAll操作   
     * @throws NullPointerException 如果指定的运算符为null，或者运算符结果为null值，并且此列表不允许null元素（可选）
     * @since 1.8  
     */    
     default void replaceAll(UnaryOperator<E> operator) {  
        Objects.requireNonNull(operator);  
        final ListIterator<E> li = this.listIterator();  
        while (li.hasNext()) {  
            li.set(operator.apply(li.next()));  
        }    
    }  
    /**  
     * 根据指定的Comparator所诱导的顺序对此列表进行排序（可选操作）。排序是稳定的：此方法不能对相等的元素进行重新排序。    
     *    
     * 此列表中的所有元素必须使用指定的比较器进行相互比较（即c.compare（e1，e2）不得对列表中的任何元素e1和e2抛出ClassCastException）。
     *    
     * 如果指定的比较器为空，则此列表中的所有元素都必须实现Comparable接口，并且应使用元素的自然顺序。
     * 此列表必须可修改，但不需要调整大小。 
     *    
     * @implSpec  
       实现要求:
     * 默认实现获得一个包含此列表中所有元素的数组，对数组进行排序，并迭代此列表，从数组中的相应位置重置每个元素。（这避免了试图对链表进行排序时产生的n2 log（n）性能。） 
     *    
     * @implNote  
       实现说明:
     *  这种实现是一种稳定、自适应、迭代的合并排序，当输入数组部分排序时，需要远少于    n*lg（n）次比较，而当输入数组随机排序时，它提供了传统合并排序的性能。如果输入数组接近排序，则实现需要大约n次比较。临时存储要求各不相同，从几乎排序的输入数组的小常数到随机排序的输入阵列的n/2个对象引用。
		该实现在其输入数组中同时利用了升序和降序，并且可以在同一输入数组的不同部分利用升序和降序。它非常适合合并两个或多个排序数组：只需连接数组并对结果数组进行排序。    
		该实现改编自Tim Peters的Python列表排序（TimSort）。它使用了Peter McIlroy的“乐观排序和信息理论复杂性”中的技术，该技术发表于1993年1月举行的第四届ACM-SIAM离散算法研讨会论文集中，第467-474页。
     *    
     * @param c 用于比较列表元素的比较器。空值表示应使用元素的自然顺序
     * @throws ClassCastException 如果列表包含使用指定比较器无法相互比较的元素 
     * @throws UnsupportedOperationException 如果此列表不支持排序操作    
     * @throws IllegalArgumentException （可选）如果发现比较器违反了Comparator的规则    
     * @since 1.8  
     */    
     @SuppressWarnings({"unchecked", "rawtypes"})  
    default void sort(Comparator<? super E> c) {  
        Object[] a = this.toArray();  
        Arrays.sort(a, (Comparator) c);  
        ListIterator<E> i = this.listIterator();  
        for (Object e : a) {  
            i.next();  
            i.set((E) e);  
        }
    }  
    /**  
     * 从此列表中移除所有元素（可选操作）。此调用返回后，列表将为空。    
     *    
     * @throws UnsupportedOperationException 如果此列表不支持清除操作 
     */    
    void clear();  
  
  
    // 比较与哈希
  
    /**  
     * 将指定的对象与此列表进行比较以判断是否相等。仅当指定的对象也是列表、两个列表的大小相同，并且两列表中所有对应的元素对都相等时，才返回 true。（如果 Objects.equals(e1, e2) 为真，则认为两个元素 e1 和 e2 相等。）换句话说，如果两个列表包含相同顺序的相同元素，则定义为相等。此定义确保 equals 方法在 List 接口的不同实现之间能够正常工作。
     *    
     * @param o 要与此列表进行相等比较的对象
     * @return 如果指定对象等于此列表，则为真
     */    
     boolean equals(Object o);  
     
  
    /**  
     * 返回此列表的哈希码值。列表的哈希码定义为以下计算结果：
     *     int hashCode = 1;  
     *     for (E e : list)    
     *         hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
       
     * 这确保了对于任何两个列表 list1 和 list2，如果 list1.equals(list2) 成立，则 list1.hashCode() == list2.hashCode() 也成立，这是 Object.hashCode 的通用约定所要求的。
     *    
     * @return 此列表的哈希码值
     * @see Object#equals(Object)  
     * @see #equals(Object)  
     */    
     int hashCode();  
     
  
  
    // 位置访问操作
  
  
    /**  
     * 返回此列表中指定位置的元素。    
     *    
     * @param index 要返回的元素索引
     * @return 列表中指定位置的元素 
     * @throws IndexOutOfBoundsException 如果索引超出范围 
       (index < 0 || index >= size())
     */    
     E get(int index);  
     
  
    /**  
     * 将此列表中指定位置的元素替换为指定元素（可选操作）。    
     *    
     * @param index 要替换的元素索引
     * @param element 要存储在指定位置的元素
     * @return 先前位于指定位置的元素
     * @throws UnsupportedOperationException 如果此列表不支持集合操作   
     * @throws ClassCastException 如果指定元素的类阻止它被添加到此列表中    
     * @throws NullPointerException 如果指定的元素为 null 并且此列表不允许 null 元素
     * @throws IllegalArgumentException 如果指定元素的某些属性阻止它被添加到此列表中    
     * @throws IndexOutOfBoundsException 如果索引超出范围 
       (index < 0 || index >= size())
     */    
     E set(int index, E element);  
     
  
    /**  
     * 在此列表的指定位置插入指定元素（可选操作）。将当前位置的元素（如果有）以及之后的所有元素向右移动（它们的索引加一）。   
     *    
     * @param index 要插入指定元素的索引
     * @param element 要插入的元素
     * @throws UnsupportedOperationException 如果此列表不支持添加操作    
     * @throws ClassCastException 如果指定元素的类阻止它被添加到此列表中    
     * @throws NullPointerException 如果指定的元素为 null 并且此列表不允许 null 元素    
     * @throws IllegalArgumentException 如果指定元素的某些属性阻止它被添加到此列表中    
     * @throws IndexOutOfBoundsException 如果索引超出范围
       （index < 0 || index > size()）
     */    
     void add(int index, E element);  
     
  
  
    /**  
     * 删除此列表中指定位置的元素（可选操作）。将随后的元素向左移动（其索引减一）。返回从列表中删除的元素。    
     *    
     * @param index 要移除的元素的索引
     * @return 先前位于指定位置的元素
     * @throws UnsupportedOperationException 如果此列表不支持移除操作   
     * @throws IndexOutOfBoundsException 如果索引超出范围
       （index < 0 || index > size()）
     */    
     E remove(int index);  
  
  
    // 查询操作
  
    /**  
     * 返回此列表中指定元素首次出现的索引，如果列表不包含该元素，则返回 -1。更正式地说，返回满足 Objects.equals(o, get(i)) 的最低索引 i，如果不存在这样的索引，则返回 -1。  
     *    
     * @param o 要搜索的元素
     * @return 此列表中指定元素首次出现的索引，如果列表不包含该元素，则返回 -1 
     * @throws ClassCastException 如果指定元素的类型与此列表不兼容（可选）
     * @throws NullPointerException 如果指定的元素为 null 并且此列表不允许为 null 的元素（可选）
     */    
     int indexOf(Object o);  
     
  
    /**  
     * 返回指定元素在此列表中最后一次出现的索引，如果此列表不包含该元素，则返回 -1。更正式地说，返回满足 Objects.equals(o, get(i)) 的最大索引 i，如果不存在这样的索引，则返回 -1。    
     *    
     * @param o 要搜索的元素
     * @return 此列表中指定元素最后一次出现的索引，如果列表不包含该元素，则返回 -1  
     * @throws ClassCastException 如果指定元素的类型与此列表不兼容（可选）
     * @throws NullPointerException 如果指定的元素为 null 并且此列表不允许为 null 的元素（可选）
     */    
     int lastIndexOf(Object o);  
  
  
  
    // 列表迭代器
  
    /**  
     * 返回此列表中元素的列表迭代器（按正确的顺序）。    
     *    
     * @return 此列表中元素的列表迭代器（按正确的顺序）。 
     */    
     ListIterator<E> listIterator();  
  
    /**  
     * 获取一个从指定位置开始遍历列表的迭代器，需要在某个特定位置开始遍历列表时非常有用
     * 返回此列表中元素的列表迭代器（按正确顺序），从列表中指定的位置开始。指定的索引表示首次调用 next 时将返回的第一个元素。首次调用 previous 将返回索引减一的元素。    
     *    
     * @param index 迭代器首次调用 next() 方法时将返回的第一个元素的索引。如果 index 为 0，则从列表的第一个元素开始；如果 index 为 size()，则迭代器处于列表末尾，第一次调用 next() 将抛出异常
     * @return 在此列表中的元素上的列表迭代器（按正确的顺序），从列表中指定的位置开始
     * @throws IndexOutOfBoundsException 如果索引超出范围
       （index < 0 || index > size()）
     */    
     ListIterator<E> listIterator(int index);  
  
  
    // 视图
  
    /**  
     * 返回此列表中从指定的 fromIndex（包含）到 toIndex（不包含）之间部分的视图。（如果 fromIndex 和 toIndex 相等，返回的列表为空。）返回的列表由此列表支持，因此返回列表中的非结构性更改会反映在此列表中，反之亦然。返回的列表支持此列表支持的所有可选列表操作。
     *  
     * 这种方法消除了对显式范围操作（通常存在于数组中）的需求。任何期望接收列表的操作都可以通过传递子列表视图而不是整个列表来用作范围操作。例如，下面的用法可以从列表中移除一段元素：
     *      list.subList(from, to).clear();
       
     * 类似的惯用法可以用于 indexOf 和 lastIndexOf，并且 Collections 类中的所有算法都可以应用于子列表。
     *  
     * 如果以除通过返回的列表以外的任何方式对支持列表（即此列表）进行结构性修改，则此方法返回的列表的语义将变为未定义。（结构性修改是指改变此列表的大小或以其他方式干扰它，以至于正在进行的迭代可能产生不正确的结果。）    
     *    
     * @param fromIndex 起始索引（包含）
     * @param toIndex 结束索引（不包含）
     * @return 此列表中指定范围的视图
     * @throws IndexOutOfBoundsException 对于非法的端点索引值 
       (fromIndex < 0 || toIndex > size || fromIndex > toIndex)
     */    
       List<E> subList(int fromIndex, int toIndex);  
  
  
    /**  
     * 在此列表中的元素上创建一个 Spliterator（分割器）。
     *    
     * Spliterator 报告 Spliterator.SIZED 和 Spliterator.ORDERED。实现应记录额外特征值的报告情况。
     *    
     * 实现要求 
     * 默认实现创建了一个如下所示的延迟绑定拆分器：
       
     * 如果列表是 RandomAccess 的一个实例，则默认实现会创建一个通过调用 get 方法遍历元素的分割迭代器。如果这种调用导致或可能导致 IndexOutOfBoundsException，则分割迭代器将快速失败并抛出 ConcurrentModificationException。如果列表也是 AbstractList 的实例，则分割迭代器将使用列表的 modCount 字段提供额外的快速失败行为。
     *否则，默认实现会从列表的迭代器创建一个分割器。该分割器继承了列表迭代器的快速失败机制。
     *  
     * 实现说明
     * 创建的 Spliterator 还会报告 Spliterator.SUBSIZED。
     *    
     * @return 此列表中的元素上创建一个 Spliterator（分割器）
     * @since 1.8  
     */    
    @Override  
    default Spliterator<E> spliterator() {  
        if (this instanceof RandomAccess) {  
            return new AbstractList.RandomAccessSpliterator<>(this);  
        } else {  
            return Spliterators.spliterator(this, Spliterator.ORDERED);  
        }    
    }  
    // ========== 序列集合 ==========  
  
    /**  
     * 将指定元素插入到列表的开头位置（即索引为 0 的位置）。
     * 调用 this.add(0, e)，即在索引 0 处添加元素，这会将原有元素向后移动一位。
     */    
     default void addFirst(E e) {  
        this.add(0, e);  
    }  
    /**  
     * 将指定元素插入到列表的末尾位置。
     * 调用 this.add(e)，即调用无参索引的 add 方法，在列表末尾添加元素。
     */    
     default void addLast(E e) {  
        this.add(e);  
    }  
    /**  
     * 获取此集合的第一个元素。
     *    
     * 实现要求
     * 如果此列表不为空，则该接口中的实现返回调用 get(0) 的结果。否则，它会抛出 NoSuchElementException。
     *    
     * @throws NoSuchElementException 如果集合为空
     * @since 21  
     */    
     default E getFirst() {  
        if (this.isEmpty()) {  
            throw new NoSuchElementException();  
        } else {  
            return this.get(0);  
        }    
    }  
    /**  
     * 获取集合中的最后一个元素
     *    
     * 实现要求
     * 如果此列表不为空，则此接口中的实现会返回调用 get(size() - 1) 的结果。否则，它会抛出 NoSuchElementException。
     *    
     * @throws NoSuchElementException 如果集合为空
     * @since 21  
     */    
     default E getLast() {  
        if (this.isEmpty()) {  
            throw new NoSuchElementException();  
        } else {  
            return this.get(this.size() - 1);  
        }    
    }  
    /**  
     * 移除并返回此集合的第一个元素（可选操作）。
     *    
     * 实现要求
     * 如果此列表不为空，则该接口中的实现返回调用 remove(0) 的结果。否则，它会抛出 NoSuchElementException。 
     *    
     * @throws NoSuchElementException 如果集合为空
     * @throws UnsupportedOperationException 如果此集合实现不支持此操作
     * @since 21  
     */    
     default E removeFirst() {  
        if (this.isEmpty()) {  
            throw new NoSuchElementException();  
        } else {  
            return this.remove(0);  
        }
    }  
    /**  
     * 移除并返回此集合的最后一个元素（可选操作）。
     *    
     * 实现要求
     * 如果此列表不为空，则此接口中的实现会返回调用 remove(size() - 1) 的结果。否则，它会抛出 NoSuchElementException。
     *    
     * @throws NoSuchElementException 如果集合为空
     * @throws UnsupportedOperationException 如果此集合实现不支持此操作
     * @since 21  
     */    
     default E removeLast() {  
        if (this.isEmpty()) {  
            throw new NoSuchElementException();  
        } else {  
            return this.remove(this.size() - 1);  
        }    
    }  
    /**  
     * 返回此集合的反向排序视图。返回视图中元素的遍历顺序是此集合中元素遍历顺序的逆序。反向排序会影响所有对顺序敏感的操作，包括对返回视图的视图集合的操作。如果集合实现允许对该视图进行修改，则修改会“写入”到底层集合。对底层集合的更改可能在此反向视图中可见，也可能不可见，这取决于具体实现。
     *    
     * 实现要求
     * 此接口中的实现返回一个逆序的 List 视图。视图的 reversed() 方法返回对该 List 的引用。视图上的其他操作通过调用此 List 的公共方法来实现。视图上的调用与对该 List 调用之间的确切关系未指定。然而，顺序敏感的操作通常表现得好像它们委托给具有相反方向的相应方法。例如，在视图上调用 getFirst 可能会导致对该 List 调用 getLast。
     *    
     * @return 将此集合以列表形式逆序查看
     * @since 21  
     */    
     default List<E> reversed() {  
        return ReverseOrderListView.of(this, true); 
        // 我们必须假设它是可修改的
    }  
  
    // ========== static methods ==========  
  
    /**  
     * 返回一个不包含任何元素的不可修改列表。有关详细信息，请参阅不可修改列表。
     *    
     * @param <E> 列表的元素类型
     * @return 返回一个空的、不可修改的列表
     *    
     * @since 9  
     */    
     @SuppressWarnings("unchecked")  
    static <E> List<E> of() {  
        return (List<E>) ImmutableCollections.EMPTY_LIST;  
    }  
    // 上述方法的若干重载，都是不可变集合，针对不同大小的列表使用不同的内部实现
    // 1个元素
     static <E> List<E> of(E e1) {  
        return new ImmutableCollections.List12<>(e1);  
    }  
    // 2个元素  
     static <E> List<E> of(E e1, E e2) {  
        return new ImmutableCollections.List12<>(e1, e2);  
    }  
    // 3个元素   
     static <E> List<E> of(E e1, E e2, E e3) {  
        return ImmutableCollections.listFromTrustedArray(e1, e2, e3);  
    }  
    // 4个元素    
     static <E> List<E> of(E e1, E e2, E e3, E e4) {  
        return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4);  
    }  
    // 5个元素    
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5) {  
        return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5);  
    }  
    // 6个元素    
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6) {  
        return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5,  
                                                         e6);  
    }  
    // 7个元素   
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {  
        return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5,  
                                                         e6, e7);  
    }  
    // 8个元素     
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {  
        return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5,  
                                                         e6, e7, e8);  
    }  
    // 9个元素     
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {  
        return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5,  
                                                         e6, e7, e8, e9);  
    }  
    // 10个元素   
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {  
        return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5,  
                                                         e6, e7, e8, e9, e10);  
    }  
    /**  
     * 返回一个不可修改的列表，包含任意数量的元素。有关详细信息，请参阅不可修改的列表。 
     *    
     * API说明
     * 此方法也接受一个数组作为参数。生成的列表的元素类型将是数组的组件类型，列表的大小将等于数组的长度。要创建一个单元素为数组的列表，请执行以下操作：    
     *    
     * 
     *     String[] array = ... ;  
     *     List<String[]> list = List.<String[]>of(array);  
     *
     *  
     * 这将导致调用 List.of(E) 方法。  
     *    
     * @param <E> 列表的元素类型
     * @param elements 要包含在列表中的元素
     * @return a 包含指定元素的列表
     * @throws NullPointerException 如果一个元素为空或数组为空
     *    
     * @since 9  
     */    
    @SafeVarargs  
    @SuppressWarnings("varargs")  
    static <E> List<E> of(E... elements) {  
        switch (elements.length) { // implicit null check of elements  
            case 0:  
                @SuppressWarnings("unchecked")  
                var list = (List<E>) ImmutableCollections.EMPTY_LIST;  
                return list;  
            case 1:  
                return new ImmutableCollections.List12<>(elements[0]);  
            case 2:  
                return new ImmutableCollections.List12<>(elements[0], elements[1]);  
            default:  
                return ImmutableCollections.listFromArray(elements);  
        }
    }  
    /**  
     * 返回一个不可修改的列表，该列表包含给定集合中的元素，并按其迭代顺序排列。给定的集合不能为空，且不能包含任何空元素。如果随后修改给定的集合，返回的列表将不会反映这些修改。
     *    
     * 实现说明
     * 如果给定的集合是一个不可修改的列表，调用 copyOf 通常不会创建副本。  
     *    
     * @param <E> 列表的元素类型
     * @param coll 从中抽取元素的集合必须非空
     * @return 一个包含给定集合元素的列表
     * @throws NullPointerException 空集合或其中存在空元素
     * @since 10  
     */    static <E> List<E> copyOf(Collection<? extends E> coll) {  
        return ImmutableCollections.listCopy(coll);  
    }
}

ArrayList

类说明

ArrayList 是 List 接口的一个可调整大小的数组实现。它实现了所有可选的列表操作，并允许所有元素（包括 null）。除了实现 List 接口外，该类还提供了用于操作内部用于存储列表的数组大小的方法。（这个类大致相当于 Vector，但它是非同步的。）

性能特点

• 常数时间 操作：size, isEmpty, get, set, getFirst, getLast, removeLast, iterator, listIterator, 和 reversed。
• 分摊常数时间 操作：add 和 addLast（添加 n 个元素需要 O(n) 时间）。
• 线性时间 操作：所有其他操作（大致来说）。
• 与 LinkedList 实现相比，ArrayList 的常数因子较低。 容量
• 每个 ArrayList 实例都有一个 容量。容量是用于存储列表中元素的数组的大小。它总是至少与列表大小一样大。
• 当元素被添加到 ArrayList 时，其容量会自动增长。增长策略的细节没有明确规定，但保证添加元素具有常数分摊时间成本。
• 应用程序可以使用 ensureCapacity 操作在添加大量元素之前手动增加 ArrayList 实例的容量。这可以减少增量式重新分配的次数。

同步与线程安全

• 注意：此实现不是同步的。

• 如果多个线程并发访问一个 ArrayList 实例，并且至少有一个线程在结构上修改了列表，那么它必须在外部进行同步。（结构修改是指任何添加或删除一个或多个元素的操作，或者显式调整后备数组的大小；仅设置元素的值不是结构修改。）

• 实现外部同步的常用方法：

  1. 同步某个封装该列表的对象。

  2. 使用 Collections.synchronizedList 方法在创建时对列表进行”包装”。

     • List list = Collections.synchronizedList(new ArrayList(...));

迭代器的快速失败机制

• 该类的 iterator 和 listIterator 方法返回的迭代器是快速失败的：
• 如果在创建迭代器之后的任何时候，列表被结构上修改（除了通过迭代器自身的 remove 或 add 方法之外），迭代器将抛出 ConcurrentModificationException。
• 因此，面对并发修改，迭代器会快速而干净地失败，而不是在未来某个不确定的时间冒着任意、不确定行为的风险。

重要说明：

• 迭代器的快速失败行为无法得到绝对保证，因为通常来说，在存在非同步并发修改的情况下不可能做出任何硬性保证。

• 快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。

• 因此，编写依赖于此异常来保证程序正确性的代码是错误的：迭代器的快速失败行为应仅用于检测 bug。

框架成员
此类是 Java Collections Framework 的成员。

源代码解析

类声明

package java.util;  
  
import java.util.function.Consumer;  
import java.util.function.Predicate;  
import java.util.function.UnaryOperator;  
import jdk.internal.access.SharedSecrets;  
import jdk.internal.util.ArraysSupport;
 
// 类型形参: <E> – 列表中的数据类型
public class ArrayList<E> extends AbstractList<E>  
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
    // ...
}

关键字段解析

// 用于序列化机制，确保在反序列化时类的版本兼容性。
@java.io.Serial  
private static final long serialVersionUID = 8683452581122892189L;  
  
/**  
 * 定义了 ArrayList 的默认初始容量。当创建无参构造函数的实例时，内部数组将初始化为该大小. 
 */
private static final int DEFAULT_CAPACITY = 10;  
  
/**  
 * 用于表示空的 ArrayList 实例，避免每次创建都分配新数组，提升性能
 */
 private static final Object[] EMPTY_ELEMENTDATA = {};  
  
/**  
 * 与 EMPTY_ELEMENTDATA 类似，但用于默认容量的空实例。当第一个元素被添加时，会扩容至 DEFAULT_CAPACITY. 
 */
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  
  
/**  
 * 作用：存储 ArrayList 中实际元素的数组缓冲区。transient 表示该字段不会被序列化，因为其内容可通过其他方式重建。注释中提到“非私有以简化嵌套类访问”，即为了简化内部类访问而设为非私有
 */
 transient Object[] elementData; // 非私有以简化嵌套类访问
  
/**  
 * 记录当前 ArrayList 中实际包含的元素个数，即逻辑大小。它不等于数组长度（capacity），而是有效元素的数量
 */  
private int size;

相关方法解析

构造方法

/**  
 * 构建一个具有指定初始容量的空列表。
 * 
 * @param  initialCapacity  初始容量
 * @throws IllegalArgumentException 如果指定的初始容量为负数
 */
public ArrayList(int initialCapacity) {  
    if (initialCapacity > 0) {  
        this.elementData = new Object[initialCapacity];  
    } else if (initialCapacity == 0) {  
        this.elementData = EMPTY_ELEMENTDATA;  
    } else {  
        throw new IllegalArgumentException
        ("Illegal Capacity: "+initialCapacity);  
    }
}  
  
/**  
 * 以10为初始容量的空参构造
 */
public ArrayList() {  
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
}  
  
/**  
 * 构建一个列表，其中包含指定集合的元素，顺序按集合迭代器返回的顺序排列。
 *
 * @param c 要放入此列表的集合元素 
 * @throws NullPointerException 如果指定集合为空
 */
public ArrayList(Collection<? extends E> c) {  
    Object[] a = c.toArray();  
    if ((size = a.length) != 0) {  
        if (c.getClass() == ArrayList.class) {  
            elementData = a;  
        } else {  
            elementData = Arrays.copyOf(a, size, Object[].class);  
        }    } else {  
        // replace with empty array.  
        elementData = EMPTY_ELEMENTDATA;  
    }
}

常规方法

容量和内存管理

// 扩容机制
/**
 * 确保ArrayList的容量至少为指定的最小容量。
 * 如果当前容量小于最小容量，则会扩容。
 *
 * @param minCapacity 所需的最小容量
 */
public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}
 
/**
 * 扩容的核心方法
 * @param minCapacity 所需的最小容量
 */
private void grow(int minCapacity) {
    // 获取当前数组的长度
    int oldCapacity = elementData.length;
    // 新容量 = 旧容量 + 旧容量/2 (即扩容1.5倍)
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量小于最小需求容量，则直接使用最小需求容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量超过了最大数组大小限制，则使用最大可能的容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制原数组到新数组，完成扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}
 
/**
 * 处理超大容量的情况
 * @param minCapacity 所需的最小容量
 * @return 适合的容量
 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 溢出
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
 
/**
 * 调整ArrayList的容量为实际元素数量，减少内存占用
 */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0) ?
            EMPTY_ELEMENTDATA :
            Arrays.copyOf(elementData, size);
    }
}

增删改查

// 添加元素到末尾
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保容量足够
    elementData[size++] = e;           // 赋值并自增size
    return true;
}
 
// 在指定位置插入元素
public void add(int index, E element) {
    rangeCheckForAdd(index);           // 检查索引是否越界
    ensureCapacityInternal(size + 1);  // 确保容量足够
    // 将index及之后的元素向后移动一位
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;      // 在index位置插入新元素
    size++;                            // 自增size
}
 
// 获取指定位置的元素
public E get(int index) {
    rangeCheck(index);                 // 检查索引是否越界
    return elementData(index);         // 返回对应位置的元素
}
 
// 设置指定位置的元素
public E set(int index, E element) {
    rangeCheck(index);                 // 检查索引是否越界
    E oldValue = elementData(index);   // 获取旧值
    elementData[index] = element;      // 设置新值
    return oldValue;                   // 返回旧值
}
 
// 删除指定位置的元素
public E remove(int index) {
    rangeCheck(index);                 // 检查索引是否越界
    modCount++;
    E oldValue = elementData(index);   // 获取旧值
    int numMoved = size - index - 1;   // 计算需要移动的元素数量
    if (numMoved > 0)
        // 将index+1及之后的元素向前移动一位
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null;        // 清空最后一个位置的引用，帮助GC
    return oldValue;                   // 返回旧值
}
 
// 删除指定元素
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; // 帮助GC
}

遍历

// 迭代器遍历
public Iterator<E> iterator() {
    return new Itr();
}
 
// 内部迭代器类
private class Itr implements Iterator<E> {
    int cursor;       // 下一个要返回的元素的索引
    int lastRet = -1; // 最后一个返回的元素的索引；如果没有则为-1
    int expectedModCount = modCount; // 期望的修改次数
 
    Itr() {}
 
    public boolean hasNext() {
        return cursor != size;
    }
 
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification(); // 检查并发修改
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
 
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification(); // 检查并发修改
 
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
 
    // 检查并发修改
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
 
// ListIterator遍历
public ListIterator<E> listIterator() {
    return new ListItr(0);
}
 
// 从指定位置开始的ListIterator
public ListIterator<E> listIterator(int index) {
    rangeCheckForAdd(index);
    return new ListItr(index);
}
 
// 内部ListIterator类，支持双向遍历和修改
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }
 
    public boolean hasPrevious() {
        return cursor != 0;
    }
 
    public int nextIndex() {
        return cursor;
    }
 
    public int previousIndex() {
        return cursor - 1;
    }
 
    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;
        return (E) elementData[lastRet = i];
    }
 
    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
 
        try {
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
 
    public void add(E e) {
        checkForComodification();
 
        try {
            int i = cursor;
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

其它

// 获取元素数量
public int size() {
    return size;
}
 
// 判空
public boolean isEmpty() {
    return size == 0;
}
 
// 检查是否包含指定元素
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
 
// 获取指定元素首次出现的索引
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;
}
 
// 获取指定元素最后一次出现的索引
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;
}
 
// 克隆方法
public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // 这不可能发生，因为我们实现了Cloneable
        throw new InternalError(e);
    }
}
 
// 序列化方法
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    // 写出非transient字段
    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();
    }
}
 
// 反序列化方法
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    // 读取非transient字段
    s.defaultReadObject();
 
    // 读取元素数量
    int size = s.readInt();
    if (size > 0) {
        // 计算容量
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, capacity);
        // 创建新数组
        Object[] elements = new Object[capacity];
 
        // 读取所有元素
        for (int i=0; i<size; i++) {
            elements[i] = s.readObject();
        }
 
        elementData = elements;
    } else if (size == 0) {
        elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new java.io.InvalidObjectException("Invalid size: " + size);
    }
}

LinkedList

类说明

双向链表实现了 List 和 Deque 接口。实现了所有可选的列表操作，并允许所有元素（包括 null）。
所有操作的表现都符合双向链表的预期。对列表进行索引的操作会从列表的开始或结束遍历，以靠近指定索引的位置为准。
请注意，该实现不是同步的。如果多个线程同时访问一个链表，并且至少其中一个线程会对链表进行结构性修改，则必须在外部进行同步。（结构性修改是指添加或删除一个或多个元素的操作；仅仅设置元素的值不属于结构性修改。）通常这是通过对自然封装列表的某个对象进行同步来实现的。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法对列表进行“包装”。最好在创建时进行，以防止列表的意外不同步访问： List list = Collections.synchronizedList(new LinkedList(…)); 这个类的 iterator 和 listIterator 方法返回的迭代器是快速失败的：如果在迭代器创建之后的任何时间，除了通过迭代器自身的 remove 或 add 方法之外以任何方式对列表进行结构性修改，迭代器都会抛出 ConcurrentModificationException 异常。因此，在面对并发修改时，迭代器会快速且干净地失败，而不是在未来某个未确定的时间冒险产生任意的、不可预测的行为。
请注意，迭代器的快速失败行为不能得到保证，一般来说，在存在未同步并发修改的情况下无法做出任何严格保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException 异常。因此，编写依赖于此异常来保证程序正确性的代码是错误的：迭代器的快速失败行为应仅用于检测错误。

这个类是 Java 集合框架的一员。

源代码解析

类声明

package java.util;  
  
import java.io.IOException;  
import java.io.ObjectInput;  
import java.io.ObjectOutput;  
import java.util.function.Consumer;  
import java.util.function.IntFunction;  
import java.util.function.Predicate;  
import java.util.function.UnaryOperator;  
import java.util.stream.Stream;
public class LinkedList<E>  
    extends AbstractSequentialList<E>  
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable  
{
	// ...
}

说明

1. 数据结构：基于双向链表实现
2. 继承与实现：

• 继承AbstractSequentialList：提供顺序访问的骨架实现
• 实现List：支持列表操作
• 实现Deque：支持双端队列操作，可作栈或队列使用
• 实现Cloneable：支持克隆
• 实现Serializable：支持序列化

关键字段

transient int size = 0;  
  
// 头节点
transient Node<E> first;  
  
// 尾节点
transient Node<E> last;

相关方法

构造方法

// 空参构造
public LinkedList() {
}
// 含参构造
/**  
 * 构建一个列表，其中包含指定集合的元素，顺序与集合迭代器返回的顺序一致。
 * 
 * @param  c 其元素将被放入此列表的集合
 * @throws NullPointerException 如果指定的集合为 null  
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

内部节点类

// 双向链表的节点类
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;
    }
}

常规方法

增删改查

// 添加元素到链表末尾
public boolean add(E e) {
    linkLast(e);
    return true;
}
 
// 在指定位置插入元素
public void add(int index, E element) {
    checkPositionIndex(index); // 检查索引是否合法
 
    if (index == size) // 如果索引等于大小，直接添加到末尾
        linkLast(element);
    else // 否则插入到指定位置
        linkBefore(element, node(index));
}
 
// 添加元素到链表开头
public void addFirst(E e) {
    linkFirst(e);
}
 
// 添加元素到链表末尾
public void addLast(E e) {
    linkLast(e);
}
 
// 获取指定位置的元素
public E get(int index) {
    checkElementIndex(index); // 检查索引是否合法
    return node(index).item;
}
 
// 获取链表第一个元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
 
// 获取链表最后一个元素
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
 
// 设置指定位置的元素
public E set(int index, E element) {
    checkElementIndex(index); // 检查索引是否合法
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element; // 替换元素
    return oldVal; // 返回旧值
}
 
// 删除指定位置的元素
public E remove(int index) {
    checkElementIndex(index); // 检查索引是否合法
    return unlink(node(index));
}
 
// 删除链表第一个元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
 
// 删除链表最后一个元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
 
// 删除指定元素
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

链表操作核心方法

// 在链表开头添加节点
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null) // 如果链表为空，新节点也是最后一个节点
        last = newNode;
    else // 否则将原第一个节点的prev指向新节点
        f.prev = newNode;
    size++;
    modCount++;
}
 
// 在链表末尾添加节点
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 // 否则将原最后一个节点的next指向新节点
        l.next = newNode;
    size++;
    modCount++;
}
 
// 在指定节点前插入新节点
void linkBefore(E e, Node<E> succ) {
    // 获取指定节点的前驱节点
    final Node<E> pred = succ.prev;
    // 创建新节点，前驱为pred，后继为succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将succ的前驱指向新节点
    succ.prev = newNode;
    if (pred == null) // 如果pred为null，说明succ是第一个节点，新节点成为第一个节点
        first = newNode;
    else // 否则将pred的后继指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}
 
// 删除指定节点
E unlink(Node<E> x) {
    // 获取节点的元素、前驱和后继
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
 
    if (prev == null) { // 如果前驱为null，说明x是第一个节点
        first = next;
    } else { // 否则将前驱的后继指向x的后继
        prev.next = next;
        x.prev = null; // 帮助GC
    }
 
    if (next == null) { // 如果后继为null，说明x是最后一个节点
        last = prev;
    } else { // 否则将后继的前驱指向x的前驱
        next.prev = prev;
        x.next = null; // 帮助GC
    }
 
    x.item = null; // 帮助GC
    size--;
    modCount++;
    return element;
}
 
// 删除第一个节点
private E unlinkFirst(Node<E> f) {
    // 获取节点的元素和后继
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // 帮助GC
    first = next;
    if (next == null) // 如果后继为null，说明链表为空了
        last = null;
    else // 否则将后继的前驱设为null
        next.prev = null;
    size--;
    modCount++;
    return element;
}
 
// 删除最后一个节点
private E unlinkLast(Node<E> l) {
    // 获取节点的元素和前驱
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // 帮助GC
    last = prev;
    if (prev == null) // 如果前驱为null，说明链表为空了
        first = null;
    else // 否则将前驱的后继设为null
        prev.next = null;
    size--;
    modCount++;
    return element;
}
 
// 根据索引获取节点，优化了遍历方向
Node<E> node(int index) {
    // 如果索引小于size/2，从链表头开始遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        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;
    }
}

遍历

// 迭代器遍历
public Iterator<E> iterator() {
    return new Itr();
}
 
// 内部迭代器类
private class Itr implements Iterator<E> {
    private Node<E> lastReturned; // 最后返回的节点
    private Node<E> next;         // 下一个要返回的节点
    private int nextIndex;        // 下一个要返回的节点的索引
    private int expectedModCount = modCount; // 期望的修改次数
 
    Itr() {
        next = first; // 初始化为第一个节点
        nextIndex = 0;
    }
 
    public boolean hasNext() {
        return nextIndex < size;
    }
 
    public E next() {
        checkForComodification(); // 检查并发修改
        if (!hasNext())
            throw new NoSuchElementException();
 
        lastReturned = next;
        next = next.next; // 移动到下一个节点
        nextIndex++;
        return lastReturned.item;
    }
 
    public void remove() {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification(); // 检查并发修改
 
        try {
            LinkedList.this.remove(lastReturned);
            if (next == lastReturned)
                next = lastReturned.next;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount = modCount;
        } catch (NoSuchElementException ex) {
            throw new ConcurrentModificationException();
        }
    }
 
    // 检查并发修改
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
 
// ListIterator遍历
public ListIterator<E> listIterator() {
    return new ListItr(0);
}
 
// 从指定位置开始的ListIterator
public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}
 
// 内部ListIterator类，支持双向遍历和修改
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        // 将迭代器移动到指定位置
        for (nextIndex = 0; nextIndex < index; nextIndex++)
            next = next.next;
    }
 
    public boolean hasPrevious() {
        return nextIndex > 0;
    }
 
    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();
 
        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }
 
    public int nextIndex() {
        return nextIndex;
    }
 
    public int previousIndex() {
        return nextIndex - 1;
    }
 
    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }
 
    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount = modCount;
    }
}

其它

// 获取链表大小
public int size() {
    return size;
}
 
// 判空
public boolean isEmpty() {
    return size == 0;
}
 
// 检查元素是否存在
public boolean contains(Object o) {
    return indexOf(o) != -1;
}
 
// 获取元素首次出现的索引
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}
 
// 获取元素最后一次出现的索引
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}
 
// 清空链表
public void clear() {
    // 遍历链表，清空所有节点的引用
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}
 
// 克隆方法
public Object clone() {
    LinkedList<E> clone = superClone();
 
    // 清空克隆链表
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;
 
    // 复制原链表的所有元素
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);
 
    return clone;
}
 
// 序列化方法
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    // 写出非transient字段
    s.defaultWriteObject();
 
    // 写出元素数量
    s.writeInt(size);
 
    // 写出所有元素
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}
 
// 反序列化方法
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    // 读取非transient字段
    s.defaultReadObject();
 
    // 读取元素数量
    int size = s.readInt();
 
    // 读取所有元素并添加到链表
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}

1.2 Set

TreeSet

类说明

一个基于 TreeMap 的可导航集合（NavigableSet）实现。元素按照其自然顺序排序，或者按照在创建集合时提供的 Comparator 排序，这取决于使用的构造函数。 该实现为基本操作（添加、移除和包含）提供保证的对数时间成本（log(n)）。 请注意，为实现 Set 接口而维护的集合排序（无论是否提供显式 Comparator）必须与 equals 一致。（有关与 equals 一致的准确定义，请参见 Comparable 或 Comparator。）这是因为 Set 接口是以 equals 操作为定义的，但 TreeSet 实例使用其 compareTo（或 compare）方法进行所有元素比较，因此从集合的角度来看，通过此方法被认为相等的两个元素是相等的。即使集合的排序与 equals 不一致，其行为也是良确定的；只是它无法遵守 Set 接口的一般约定。

请注意，这个实现不是同步的。如果多个线程同时访问一个树集合，并且至少有一个线程对集合进行了修改，则必须在外部进行同步。通常，这可以通过对某个自然包含该集合的对象进行同步来实现。如果不存在这样的对象，则应使用 Collections.synchronizedSortedSet 方法对集合进行“包装”。最好在创建时就进行包装，以防止意外的非同步访问集合：

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(…));

由该类的 iterator 方法返回的迭代器是快速失败的：如果在迭代器创建之后集合以任何方式被修改（除了通过迭代器自身的 remove 方法），迭代器将抛出 ConcurrentModificationException 异常。因此，在并发修改的情况下，迭代器会迅速且干净地失败，而不会在未来任何不确定的时间导致任意且不可预测的行为。 请注意，迭代器的快速失败（fail-fast）行为不能被保证，因为一般来说，在存在未同步的并发修改时，不可能做出任何严格保证。快速失败的迭代器会尽最大努力抛出 ConcurrentModificationException 异常。因此，编写依赖于此异常来确保程序正确性的代码是错误的：迭代器的快速失败行为应仅用于检测错误。

此类的 addFirst 和 addLast 方法会抛出 UnsupportedOperationException 异常。元素的遍历顺序由比较方法决定，因此不支持显式定位。

此类是 Java 集合框架（Java Collections Framework）的一部分。

源代码解析

类声明

package java.util;
public class TreeSet<E> extends AbstractSet<E>  
    implements NavigableSet<E>, Cloneable, java.io.Serializable  
{
	// ...
}

说明

1. 核心特征

• 有序集合：基于红黑树实现的有序Set，元素自动排序
• 唯一性：继承Set接口，不允许重复元素
• 排序机制：
  • 自然排序：元素实现Comparable接口
  • 自定义排序：构造时传入 Comparator 比较器

2. 继承与实现

• AbstractSet<E>：提供Set的基本实现
• NavigableSet<E>：支持导航方法（如first(), last(), lower(), higher()等)
• Cloneable：支持克隆操作
• Serializable：支持序列化

3. 关键约束

• 不允许空元素
• 元素必须可比较
• 插入、删除、查找的时间复杂度为对数级

关键字段

// 底层的NavigableMap，用于实际存储数据
private transient NavigableMap<E,Object> m;  
  
// 固定的占位符对象，作为Map中所有key对应的value值。因为Set只关心元素是否存在，不关心值，所以用一个公共的占位符即可，声明为static final，所有TreeSet实例共享同一个对象，节省内存
private static final Object PRESENT = new Object();

相关方法

构造方法

// 构建一个由指定的可导航映射支持的集合。
public TreeSet() {
    this(new TreeMap<>());
}
 
/**
 * 构建一个新的空树集合，根据其元素的自然顺序进行排序。所有插入集合的元素必须实现 Comparable 接口。此外，所有这些元素必须可以相互比较：对于集合中的任意元素 e1 和 e2，e1.compareTo(e2) 不得抛出 ClassCastException。如果用户试图向集合中添加违反此约束的元素（例如，用户试图向元素为整数的集合中添加字符串元素），则 add 调用将抛出 ClassCastException。
 * @param comparator 将用于对该集合进行排序的比较器。如果为 null，则使用元素的自然顺序。
*/
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
 
/**  
 *构建一个新的树集合，其中包含指定集合中的元素，并根据其元素的自然顺序进行排序。插入到集合中的所有元素都必须实现 Comparable 接口。此外，所有此类元素必须可以相互比较：对于集合中的任何元素 e1 和 e2，e1.compareTo(e2) 都不能抛出 ClassCastException。
 *
 * @param c 其元素将组成新集合的集合
 * @throws ClassCastException 如果 c 中的元素不可比较，或者彼此之间不可比较
 * @throws NullPointerException 如果指定的集合为 null
 */
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
 
/**  
 * 构造一个新的树集合，包含相同的元素，并使用与指定排序集合相同的排序方式。
 * 
 * @param s 其元素将组成新集合的有序集合
 * @throws NullPointerException 如果指定的有序集合为空
 */
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}
 
// 构建一个由指定的可导航映射支持的集合。
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

常规方法

// 添加元素
public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}
 
// 添加集合中的所有元素
public boolean addAll(Collection<? extends E> c) {
    // 如果集合大小为0，直接返回false
    if (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) {
        SortedSet<? extends E> set = (SortedSet<? extends E>) c;
        TreeMap<E,Object> map = (TreeMap<E, Object>) m;
        Comparator<?> cc = set.comparator();
        Comparator<? super E> mc = map.comparator();
        // 如果比较器相同，直接批量添加
        if (cc==mc || (cc != null && cc.equals(mc))) {
            map.addAllForTreeSet(set, PRESENT);
            return true;
        }
    }
    // 否则调用父类的addAll方法
    return super.addAll(c);
}
 
// 删除元素
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}
 
// 清空集合
public void clear() {
    m.clear();
}
 
// 检查元素是否存在
public boolean contains(Object o) {
    return m.containsKey(o);
}
 
// 获取集合大小
public int size() {
    return m.size();
}
 
// 判空
public boolean isEmpty() {
    return m.isEmpty();
}
 
// 返回迭代器
public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}
 
// 返回逆序迭代器
public Iterator<E> descendingIterator() {
    return m.descendingKeySet().iterator();
}
 
// 返回逆序集合
public NavigableSet<E> descendingSet() {
    return new TreeSet<>(m.descendingMap());
}
 
// 返回子集合
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive, toElement, toInclusive));
}
 
// 返回子集，包含fromElement，不包含toElement
public SortedSet<E> subSet(E fromElement, E toElement) {
    return subSet(fromElement, true, toElement, false);
}
 
// 返回头部子集
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new TreeSet<>(m.headMap(toElement, inclusive));
}
 
// 返回头部子集，不包含toElement
public SortedSet<E> headSet(E toElement) {
    return headSet(toElement, false);
}
 
// 返回尾部子集
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
    return new TreeSet<>(m.tailMap(fromElement, inclusive));
}
 
// 返回尾部子集，包含fromElement
public SortedSet<E> tailSet(E fromElement) {
    return tailSet(fromElement, true);
}
 
// 获取比较器
public Comparator<? super E> comparator() {
    return m.comparator();
}
 
// 获取第一个元素
public E first() {
    return m.firstKey();
}
 
// 获取最后一个元素
public E last() {
    return m.lastKey();
}
 
// 获取小于指定元素的最大元素
public E lower(E e) {
    return m.lowerKey(e);
}
 
// 获取小于等于指定元素的最大元素
public E floor(E e) {
    return m.floorKey(e);
}
 
// 获取大于等于指定元素的最小元素
public E ceiling(E e) {
    return m.ceilingKey(e);
}
 
// 获取大于指定元素的最小元素
public E higher(E e) {
    return m.higherKey(e);
}
 
// 弹出第一个元素
public E pollFirst() {
    Map.Entry<E,?> e = m.pollFirstEntry();
    return (e == null) ? null : e.getKey();
}
 
// 弹出最后一个元素
public E pollLast() {
    Map.Entry<E,?> e = m.pollLastEntry();
    return (e == null) ? null : e.getKey();
}
 
// 克隆方法
public Object clone() {
    TreeSet<E> clone;
    try {
        clone = (TreeSet<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
    clone.m = new TreeMap<>(m);
    return clone;
}
 
// 序列化方法
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    s.defaultWriteObject();
    s.writeObject(m);
}
 
// 反序列化方法
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    m = (NavigableMap<E,Object>) s.readObject();
}

HashSet

类说明

这个类实现了 Set 接口，由哈希表（实际上是 HashMap 实例）支持。它不保证集合的迭代顺序；特别是，它不保证顺序随时间保持不变。这个类允许 null 元素。

这个类为基本操作（add、remove、contains 和 size）提供常量时间的性能，前提是哈希函数能正确地将元素分散到各个桶中。迭代这个集合所需的时间与 HashSet 实例的大小（元素数量）加上支持的 HashMap 实例的“容量”（桶的数量）之和成正比。因此，如果迭代性能很重要，不要将初始容量设置得过高（或负载因子过低）是非常重要的。

请注意，此实现不是同步的。如果多个线程同时访问哈希集合，并且至少有一个线程修改了该集合，则必须在外部进行同步。这通常通过对某个自然封装集合的对象进行同步来实现。如果不存在这样的对象，应使用 Collections.synchronizedSet 方法对集合进行“包装”。最好在创建时进行包装，以防止对集合的意外非同步访问： Set s = Collections.synchronizedSet(new HashSet(...));

本类的 iterator 方法返回的迭代器是快速失败（fail-fast）的：如果在创建迭代器之后以任何方式修改了集合，但通过迭代器自身的 remove 方法除外，迭代器会抛出 ConcurrentModificationException 异常。因此，在并发修改的情况下，迭代器会快速而干净地失败，而不会在未来某个未知时间出现任意的、不确定的行为。

请注意，迭代器的快速失败行为并不能得到保证，因为通常情况下，在存在未同步的并发修改时，不可能做出任何硬性保证。快速失败迭代器会在尽最大努力的基础上抛出 ConcurrentModificationException 异常。因此，依赖此异常来保证程序正确性是错误的：迭代器的快速失败行为应仅用于检测程序错误。

本类是 Java 集合框架的一员。

源代码解析

类声明

package java.util;  
  
import java.io.InvalidObjectException;  
import jdk.internal.access.SharedSecrets;
public class HashSet<E>  
    extends AbstractSet<E>  
    implements Set<E>, Cloneable, java.io.Serializable  
{
	// ...
}

说明

1. 核心特性

• 不允许有重复元素
• 允许空元素
• 无序集合
• 性能优秀，基本操作(add、remove、contains)的时间复杂度为常数级
• 非线程安全，多线程环境下需要同步

2. 继承与实现

• AbstractSet<E>：提供Set接口的基本实现
• Set<E>：定义Set集合的核心行为
• Cloneable：支持对象克隆功能
• java.io.Serializable：支持对象的序列化和反序列化

3. 特点

关键字段

// 序列化版本号，用于在反序列化过程中验证序列化的对象和当前类是否兼容。当类的结构发生重大变化时，这个ID会改变，防止使用旧版本序列化数据时出现异常。@java.io.Serial 注解标记这是一个与序列化相关的字段（Java 14引入）
@java.io.Serial  
static final long serialVersionUID = -5024744406713321676L;  
  
  
// 这是HashSet的核心数据结构，所有HashSet的操作最终都会委托给这个HashMap实例，transient 关键字表明这个字段不会被自动序列化，HashSet通过自定义序列化方法来控制序列化过程。使用HashMap的键来存储HashSet的元素，而值则是共享的虚拟对象(PRESENT)
transient HashMap<E,Object> map;  
  
  
// 这是一个静态常量对象，作为HashMap中每个键对应的值，因为HashSet只关心元素的存在与否，不关心值，所以所有键都使用同一个对象作为值。这样节省了内存空间，避免为每个元素创建单独的值对象
static final Object PRESENT = new Object();

相关方法

构造方法

/*
* 构造一个新的空集合；所支持的 HashMap 实例具有默认初始容量（16）和加载因子（0.75）。
*/
public HashSet() {
    map = new HashMap<>();
}
 
/**  
 * 构建一个包含指定集合中元素的新集合。HashMap 使用默认的加载因子（0.75）创建，并具有足够容纳指定集合中元素的初始容量。
 * @param c 其元素将被放入此集合的集合
 * @throws NullPointerException 如果指定的集合为 null
 */
public HashSet(Collection<? extends E> c) {
    map = HashMap.newHashMap(Math.max(c.size(), 12));
    addAll(c);
}
 
/**  
 * 构造一个新的空集合；其背后的 HashMap 实例具有指定的初始容量和指定的加载因子。
   
 * @apiNote  
 * 要创建一个具有初始容量并能容纳预期元素数量的 HashSet，请使用 newHashSet。 
 * 
 * @param      initialCapacity   哈希表的初始容量
 * @param      loadFactor        哈希表的负载因子
 * @throws     IllegalArgumentException 如果初始容量小于零，或者负载因子非正 
 */
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
 
/**  
 * 构造一个新的空集合；其所支持的 HashMap 实例具有指定的初始容量和默认负载因子（0.75）。
 *
 * @apiNote  
 * 要创建一个具有初始容量的 HashSet，以容纳预期数量的元素，可以使用 newHashSet。
 *
 * @param      initialCapacity   哈希表的初始容量
 * @throws     IllegalArgumentException 如果初始容量小于零
 */
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
 
/**  
 * 构建一个新的、空的链式哈希集合。（这个包私有构造函数仅由 LinkedHashSet 使用。）作为支持的 HashMap 实例是一个具有指定初始容量和指定负载因子的 LinkedHashMap。
 * @param      initialCapacity   哈希表的初始容量  
 * @param      loadFactor        哈希表的负载因子
 * @param      dummy             忽略（将此构造函数与其他 int、float 构造函数区分开。）
 * @throws     IllegalArgumentException 如果初始容量小于零，或者负载因子非正
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

常规方法

// 添加元素
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
 
// 删除元素
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
 
// 清空集合
public void clear() {
    map.clear();
}
 
// 检查元素是否存在
public boolean contains(Object o) {
    return map.containsKey(o);
}
 
// 获取集合大小
public int size() {
    return map.size();
}
 
// 判空
public boolean isEmpty() {
    return map.isEmpty();
}
 
// 返回迭代器
public Iterator<E> iterator() {
    return map.keySet().iterator();
}
 
// 克隆方法
public Object clone() {
    try {
        HashSet<E> newSet = (HashSet<E>) super.clone();
        newSet.map = (HashMap<E, Object>) map.clone();
        return newSet;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}
 
// 序列化方法
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    // 写出非transient字段
    s.defaultWriteObject();
 
    // 写出HashMap的容量和加载因子
    s.writeInt(map.capacity());
    s.writeFloat(map.loadFactor());
 
    // 写出元素数量
    s.writeInt(map.size());
 
    // 写出所有元素
    for (E e : map.keySet())
        s.writeObject(e);
}
 
// 反序列化方法
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    // 读取非transient字段
    s.defaultReadObject();
 
    // 读取HashMap的容量和加载因子
    int capacity = s.readInt();
    float loadFactor = s.readFloat();
 
    // 读取元素数量
    int size = s.readInt();
 
    // 检查参数合法性
    if (capacity < 0) {
        throw new InvalidObjectException("Illegal capacity: " + capacity);
    }
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new InvalidObjectException("Illegal load factor: " + loadFactor);
    }
    if (size < 0) {
        throw new InvalidObjectException("Illegal size: " + size);
    }
 
    // 根据size调整capacity
    capacity = (size > 0) ? Math.max((int) (size / loadFactor) + 1, capacity) : 1;
 
    // 创建新的HashMap
    map = HashMap.newHashMap(capacity, loadFactor);
 
    // 读取所有元素
    for (int i=0; i<size; i++) {
        @SuppressWarnings("unchecked")
        E e = (E) s.readObject();
        map.put(e, PRESENT);
    }
}

1.3 Map

TreeMap

类说明

基于红黑树的可导航映射实现。该映射根据键的自然顺序进行排序，或者根据映射创建时提供的 Comparator 进行比较排序，具体取决于使用的构造函数。

此实现为 containsKey、get、put 和 remove 操作提供了有保证的 log(n) 时间成本。算法改编自 Cormen、Leiserson 和 Rivest 的《算法导论》中的算法。

请注意，树映射所维护的排序（与任何有序映射一样），无论是否提供了显式比较器，都必须与 equals 方法保持一致，以便此有序映射能正确实现 Map 接口。（有关”与 equals 一致”的精确定义，请参阅 Comparable 或 Comparator。）这是因为 Map 接口是根据 equals 操作定义的，但有序映射在执行所有键比较时都使用其 compareTo（或 compare）方法，因此，从有序映射的角度来看，被此方法视为相等的两个键就是相等的。即使排序与 equals 不一致，有序映射的行为也是定义良好的；只是它违反了 Map 接口的通用约定。

请注意，此实现不是同步的。如果多个线程并发访问一个映射，并且至少有一个线程在结构上修改了该映射，则必须在外部进行同步。（结构修改是指添加或删除一个或多个映射的任何操作；仅更改与现有键关联的值不是结构修改。）这通常通过同步某个自然封装了该映射的对象来实现。如果不存在这样的对象，则应使用 Collections.synchronizedSortedMap 方法”包装”该映射。最好在创建时完成此操作，以防止意外非同步地访问该映射： SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

此类的所有”集合视图方法”返回的集合，其 iterator 方法返回的迭代器都是快速失败 的：在创建迭代器之后，如果任何时候对映射进行了结构修改，除非通过迭代器自身的 remove 方法，否则迭代器将抛出 ConcurrentModificationException。因此，面对并发修改，迭代器会快速而干净地失败，而不是在将来某个不确定的时间冒着出现任意、不确定行为的风险。

请注意，无法保证迭代器的快速失败行为，因为一般来说，在存在非同步并发修改的情况下，不可能做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序以确保其正确性是错误的做法：迭代器的快速失败行为应仅用于检测错误。

方法 ceilingEntry、firstEntry、floorEntry、higherEntry、lastEntry、lowerEntry、pollFirstEntry 和 pollLastEntry 返回的 Map.Entry 实例表示的是调用时刻映射的快照。它们不支持通过可选的 setValue 方法对底层映射进行修改。

此类的 putFirst 和 putLast 方法抛出 UnsupportedOperationException。映射的遭遇顺序由比较方法决定；因此，不支持显式定位。

此类是 Java 集合框架的成员。

源代码解析

声明

package java.util;
 
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;
 
public class TreeMap<K,V> extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, Serializable {
    // ...
}

关键字段

// 序列化版本号
@java.io.Serial
private static final long serialVersionUID = 919286545866124006L;
 
// 比较器，用于对键进行排序
private final Comparator<? super K> comparator;
 
// 根节点
private transient Entry<K,V> root;
 
// 元素数量
private transient int size = 0;
 
// 修改次数，用于快速失败机制
private transient int modCount = 0;
 
// 红黑树的节点类
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;          // 键
    V value;        // 值
    Entry<K,V> left; // 左子节点
    Entry<K,V> right; // 右子节点
    Entry<K,V> parent; // 父节点
    boolean color = BLACK; // 节点颜色，默认黑色
 
    // 构造方法
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
 
    // 获取键
    public K getKey() {
        return key;
    }
 
    // 获取值
    public V getValue() {
        return value;
    }
 
    // 设置值
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
 
    // 比较相等性
    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
    }
 
    // 计算哈希码
    public int hashCode() {
        int keyHash = (key==null ? 0 : key.hashCode());
        int valueHash = (value==null ? 0 : value.hashCode());
        return keyHash ^ valueHash;
    }
 
    // 字符串表示
    public String toString() {
        return key + "=" + value;
    }
}
 
// 红黑树的颜色常量
private static final boolean RED   = false;
private static final boolean BLACK = true;

相关方法

构造方法

// 默认构造方法，使用自然顺序排序
public TreeMap() {
    comparator = null;
}
 
// 使用指定比较器构造TreeMap
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}
 
// 从SortedMap构造TreeMap，使用相同的比较器
public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}
 
// 从Collection构造TreeMap，使用自然顺序排序
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

核心操作

// 添加或更新键值对
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        // 如果根节点为空，创建新根节点
        compare(key, key); // 检查key是否为null
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // 确定比较器
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        // 使用指定比较器查找插入位置
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                // 键已存在，更新值
                return t.setValue(value);
        } while (t != null);
    } else {
        // 使用自然顺序排序
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                // 键已存在，更新值
                return t.setValue(value);
        } while (t != null);
    }
    // 创建新节点
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    // 修复红黑树性质
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}
 
// 获取指定键的值
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}
 
// 查找指定键的节点
final Entry<K,V> getEntry(Object key) {
    // 如果使用比较器，使用比较器查找
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    // 使用自然顺序查找
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}
 
// 使用比较器查找指定键的节点
final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
    K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}
 
// 删除指定键的节点
public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;
 
    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}
 
// 删除指定节点
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;
 
    // 情况1：节点有两个子节点
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    }
 
    // 情况2：节点只有一个子节点或没有子节点
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
 
    if (replacement != null) {
        // 情况2a：节点有一个子节点
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;
 
        p.left = p.right = p.parent = null;
 
        // 修复红黑树性质
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) {
        // 情况2b：节点是根节点且没有子节点
        root = null;
    } else {
        // 情况2c：节点没有子节点
        if (p.color == BLACK)
            fixAfterDeletion(p);
 
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}
 
// 获取第一个（最小）键
public K firstKey() {
    return key(getFirstEntry());
}
 
// 获取最后一个（最大）键
public K lastKey() {
    return key(getLastEntry());
}
 
// 获取第一个（最小）节点
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}
 
// 获取最后一个（最大）节点
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}
 
// 获取小于指定键的最大键
public K lowerKey(K key) {
    return key(lowerEntry(key));
}
 
// 获取小于等于指定键的最大键
public K floorKey(K key) {
    return key(floorEntry(key));
}
 
// 获取大于等于指定键的最小键
public K ceilingKey(K key) {
    return key(ceilingEntry(key));
}
 
// 获取大于指定键的最小键
public K higherKey(K key) {
    return key(higherEntry(key));
}
 
// 获取小于指定键的最大节点
public Map.Entry<K,V> lowerEntry(K key) {
    return exportEntry(getLowerEntry(key));
}
 
// 获取小于等于指定键的最大节点
public Map.Entry<K,V> floorEntry(K key) {
    return exportEntry(getFloorEntry(key));
}
 
// 获取大于等于指定键的最小节点
public Map.Entry<K,V> ceilingEntry(K key) {
    return exportEntry(getCeilingEntry(key));
}
 
// 获取大于指定键的最小节点
public Map.Entry<K,V> higherEntry(K key) {
    return exportEntry(getHigherEntry(key));
}
 
// 获取并移除第一个（最小）节点
public Map.Entry<K,V> pollFirstEntry() {
    Entry<K,V> p = getFirstEntry();
    Map.Entry<K,V> result = exportEntry(p);
    if (p != null)
        deleteEntry(p);
    return result;
}
 
// 获取并移除最后一个（最大）节点
public Map.Entry<K,V> pollLastEntry() {
    Entry<K,V> p = getLastEntry();
    Map.Entry<K,V> result = exportEntry(p);
    if (p != null)
        deleteEntry(p);
    return result;
}

红黑树调整方法

// 插入后修复红黑树性质
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;
 
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // 情况1：父节点是祖父节点的左子节点
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                // 情况1a：叔叔节点是红色
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    // 情况1b：叔叔节点是黑色，当前节点是父节点的右子节点
                    x = parentOf(x);
                    rotateLeft(x);
                }
                // 情况1c：叔叔节点是黑色，当前节点是父节点的左子节点
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            // 情况2：父节点是祖父节点的右子节点
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                // 情况2a：叔叔节点是红色
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    // 情况2b：叔叔节点是黑色，当前节点是父节点的左子节点
                    x = parentOf(x);
                    rotateRight(x);
                }
                // 情况2c：叔叔节点是黑色，当前节点是父节点的右子节点
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}
 
// 删除后修复红黑树性质
private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            // 情况1：当前节点是父节点的左子节点
            Entry<K,V> sib = rightOf(parentOf(x));
 
            if (colorOf(sib) == RED) {
                // 情况1a：兄弟节点是红色
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
 
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                // 情况1b：兄弟节点的两个子节点都是黑色
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    // 情况1c：兄弟节点的右子节点是黑色
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                // 情况1d：兄弟节点的右子节点是红色
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else {
            // 情况2：当前节点是父节点的右子节点
            Entry<K,V> sib = leftOf(parentOf(x));
 
            if (colorOf(sib) == RED) {
                // 情况2a：兄弟节点是红色
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }
 
            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                // 情况2b：兄弟节点的两个子节点都是黑色
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    // 情况2c：兄弟节点的左子节点是黑色
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                // 情况2d：兄弟节点的左子节点是红色
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }
 
    setColor(x, BLACK);
}
 
// 左旋操作
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}
 
// 右旋操作
private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null)
            l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else
            p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

辅助方法

// 获取节点的父节点
private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
    return (p == null ? null : p.parent);
}
 
// 获取节点的左子节点
private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
    return (p == null) ? null : p.left;
}
 
// 获取节点的右子节点
private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
    return (p == null) ? null : p.right;
}
 
// 获取节点的颜色
private static <K,V> boolean colorOf(Entry<K,V> p) {
    return (p == null ? BLACK : p.color);
}
 
// 设置节点的颜色
private static <K,V> void setColor(Entry<K,V> p, boolean c) {
    if (p != null)
        p.color = c;
}
 
// 获取节点的后继节点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        // 情况1：节点有右子树，后继节点是右子树中的最小节点
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 情况2：节点没有右子树，后继节点是第一个祖先节点，该节点是其父节点的左子节点
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}
 
// 获取节点的前驱节点
static <K,V> TreeMap.Entry<K,V> predecessor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.left != null) {
        // 情况1：节点有左子树，前驱节点是左子树中的最大节点
        Entry<K,V> p = t.left;
        while (p.right != null)
            p = p.right;
        return p;
    } else {
        // 情况2：节点没有左子树，前驱节点是第一个祖先节点，该节点是其父节点的右子节点
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.left) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

HashMap

类说明

基于哈希表的 Map 接口实现。此实现提供了所有可选的映射操作，并允许使用 null 值和 null 键。（HashMap 类与 Hashtable 大致等效，区别在于它是非同步的并且允许 null。）此类不保证映射的顺序；特别是，它不保证顺序会随时间保持不变。

此实现为基本操作（get 和 put）提供了恒定时间性能，前提是哈希函数将元素正确地分散到各个桶中。对集合视图进行迭代所需的时间与 HashMap 实例的“容量”（桶的数量）加上其大小（键-值映射的数量）成正比。因此，如果迭代性能很重要，那么不要将初始容量设置得过高（或者将负载因子设置得过低）是非常关键的。

HashMap 实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中桶的数量，初始容量就是哈希表创建时的容量。负载因子是哈希表在其容量自动增加之前允许达到的满度度量。当哈希表中的条目数超过负载因子与当前容量的乘积时，哈希表会进行重新哈希（即重建内部数据结构），使得哈希表的桶数大约变为原来的两倍。

通常，默认负载因子（0.75） 在时间和空间成本之间提供了一个良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以最小化重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则永远不会发生重新哈希操作。

如果要在 HashMap 实例中存储许多映射，使用足够大的容量创建它，将比让它根据需要执行自动重新哈希以增长表来得更高效。请注意，使用许多具有相同 hashCode() 的键必然会降低任何哈希表的性能。为了减轻影响，当键是可比较的时，此类可以使用键之间的比较顺序来帮助打破平局。

请注意，此实现不是同步的。如果多个线程并发访问一个哈希映射，并且至少有一个线程在结构上修改了该映射，则必须在外部进行同步。（结构修改是指添加或删除一个或多个映射的任何操作；仅更改实例已包含的键所关联的值不是结构修改。）这通常通过同步某个自然封装了该映射的对象来实现。如果不存在这样的对象，则应使用 Collections.synchronizedMap 方法“包装”该映射。最好在创建时完成此操作，以防止意外非同步地访问该映射： Map m = Collections.synchronizedMap(new HashMap(...));

此类的所有“集合视图方法”返回的迭代器都是快速失败的：在创建迭代器之后，如果任何时候对映射进行了结构修改，除非通过迭代器自身的 remove 方法，否则迭代器将抛出 ConcurrentModificationException。因此，面对并发修改，迭代器会快速而干净地失败，而不是在将来某个不确定的时间冒着出现任意、不确定行为的风险。

请注意，无法保证迭代器的快速失败行为，因为一般来说，在存在非同步并发修改的情况下，不可能做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序以确保其正确性是错误的：迭代器的快速失败行为应仅用于检测错误。

此类是 Java 集合框架的成员。

源代码解析

声明

package java.util;
 
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;
 
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    // ...
}

关键字段

// 序列化版本号
@java.io.Serial
private static final long serialVersionUID = 362498820763181265L;
 
// 默认初始容量（16），必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
 
// 最大容量，必须是2的幂且不超过2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
 
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
// 树化阈值：当链表长度超过此值时，将链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
 
// 反树化阈值：当红黑树节点数少于此值时，将红黑树转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
 
// 树化的最小容量：只有当哈希表容量超过此值时，才会进行树化
static final int MIN_TREEIFY_CAPACITY = 64;
 
// 哈希表数组，存储链表或红黑树的头节点
transient Node<K,V>[] table;
 
// 存储所有键值对的集合
transient Set<Map.Entry<K,V>> entrySet;
 
// 元素数量
transient int size;
 
// 修改次数，用于快速失败机制
transient int modCount;
 
// 扩容阈值：当size超过此值时，进行扩容
int threshold;
 
// 加载因子
final float loadFactor;
 
// 节点类，用于链表
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;      // 哈希值
    final K key;         // 键
    V value;             // 值
    Node<K,V> next;      // 下一个节点
 
    // 构造方法
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
 
    // 获取键
    public final K getKey()        { return key; }
    // 获取值
    public final V getValue()      { return value; }
    // 字符串表示
    public final String toString() { return key + "=" + value; }
    // 计算哈希码
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    // 设置值
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    // 比较相等性
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}
 
// 红黑树节点类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // 父节点
    TreeNode<K,V> left;    // 左子节点
    TreeNode<K,V> right;   // 右子节点
    TreeNode<K,V> prev;    // 前一个节点（用于双向链表）
    boolean red;           // 节点颜色
 
    // 构造方法
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
 
    // 返回根节点
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
    // ... 红黑树相关方法
}

相关方法

构造方法

// 默认构造方法，使用默认初始容量和加载因子
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
 
// 使用指定初始容量和默认加载因子构造HashMap
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
 
// 使用指定初始容量和加载因子构造HashMap
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
 
// 从Map构造HashMap
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
 
// 计算大于等于initialCapacity的最小2的幂
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

核心操作

// 添加或更新键值对
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
 
// 计算键的哈希值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
 
// 核心put方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果哈希表为空，初始化哈希表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算索引位置，如果该位置为空，直接插入新节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 该位置不为空，处理哈希冲突
        Node<K,V> e; K k;
        // 情况1：键已存在，直接更新值
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 情况2：该位置是红黑树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 情况3：该位置是链表节点
        else {
            for (int binCount = 0; ; ++binCount) {
                // 遍历到链表末尾，插入新节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果链表长度超过树化阈值，将链表转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到已存在的键，更新值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果键已存在，更新值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 如果元素数量超过阈值，扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
 
// 获取指定键的值
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
 
// 核心get方法
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 如果哈希表不为空且该位置有节点
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 情况1：第一个节点就是要找的键
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 情况2：有后续节点
        if ((e = first.next) != null) {
            // 情况2a：红黑树查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 情况2b：链表查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
 
// 删除指定键的节点
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
 
// 核心remove方法
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 情况1：第一个节点就是要删除的键
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 情况2：有后续节点
        else if ((e = p.next) != null) {
            // 情况2a：红黑树查找
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 情况2b：链表查找
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 删除节点
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

扩容机制

// 扩容方法
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 情况1：哈希表已初始化
    if (oldCap > 0) {
        // 如果已达到最大容量，不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新容量为旧容量的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 新阈值为旧阈值的2倍
    }
    // 情况2：哈希表未初始化，但已设置阈值
    else if (oldThr > 0) 
        newCap = oldThr;
    // 情况3：哈希表未初始化，使用默认值
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 创建新的哈希表
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 如果旧哈希表不为空，将旧哈希表中的元素转移到新哈希表
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 情况1：该位置只有一个节点
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 情况2：该位置是红黑树节点
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 情况3：该位置是链表节点
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表，将链表分为两部分
                    do {
                        next = e.next;
                        // 低位链表：索引不变
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 高位链表：索引 = 原索引 + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将低位链表放入新哈希表
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 将高位链表放入新哈希表
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
 
// 将链表转换为红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 如果哈希表为空或容量小于最小树化容量，先扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 否则将链表转换为红黑树
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

辅助方法

// 检查容量是否足够
public void ensureCapacity(int minCapacity) {
    if (minCapacity > 0)
        ensureCapacityInternal(minCapacity);
}
 
// 内部检查容量方法
private void ensureCapacityInternal(int minCapacity) {
    if (table == null) {
        minCapacity = Math.max(DEFAULT_INITIAL_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
 
// 显式检查容量方法
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果所需容量超过阈值，扩容
    if (minCapacity - table.length > 0)
        resize();
}
 
// 获取哈希表容量
final int capacity() {
    return (table != null) ? table.length :
        (threshold > 0) ? threshold : DEFAULT_INITIAL_CAPACITY;
}
 
// 克隆方法
public Object clone() {
    HashMap<K,V> result;
    try {
        result = (HashMap<K,V>)super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
    result.reinitialize();
    result.putMapEntries(this, false);
    return result;
}
 
// 序列化方法
private void writeObject(ObjectOutputStream s) throws IOException {
    int buckets = capacity();
    // 写出非transient字段
    s.defaultWriteObject();
    // 写出容量和加载因子
    s.writeInt(buckets);
    s.writeInt(size);
    // 写出所有键值对
    internalWriteEntries(s);
}
 
// 反序列化方法
private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    // 读取非transient字段
    s.defaultReadObject();
    reinitialize();
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new InvalidObjectException("Illegal load factor: " + loadFactor);
    // 读取容量和大小
    s.readInt(); // 忽略容量
    int size = s.readInt();
    if (size > 0) {
        int numberBuckets = s.readInt();
        if (numberBuckets < 0)
            throw new InvalidObjectException("Illegal number of buckets: " + numberBuckets);
        // 创建新的哈希表
        int capacity = tableSizeFor(numberBuckets);
        float ft = (float)capacity * loadFactor;
        threshold = (capacity < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY ?
                     (int)ft : Integer.MAX_VALUE);
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] tab = (Node<K,V>[])new Node[capacity];
        table = tab;
        // 读取所有键值对
        for (int i = 0; i < size; i++) {
            @SuppressWarnings("unchecked")
            K key = (K)s.readObject();
            @SuppressWarnings("unchecked")
            V value = (V)s.readObject();
            putVal(hash(key), key, value, false, false);
        }
    }
}

---

2. 工具类

2.1 Iterator(迭代器)

接口说明

Iterator是Java集合框架中的核心迭代器接口，用于遍历集合中的元素。它提供了一种统一的方式来访问集合中的元素，而无需暴露集合的底层实现细节。

Iterator接口定义了以下核心方法：

• hasNext()：检查是否还有下一个元素
• next()：返回下一个元素
• remove()：删除当前元素

源代码解析

声明

package java.util;
 
import java.util.function.Consumer;
 
public interface Iterator<E> {
    // ...
}

核心方法

/**
 * 检查集合中是否还有下一个元素
 * @return 如果还有下一个元素，返回true；否则返回false
 */
boolean hasNext();
 
/**
 * 返回集合中的下一个元素
 * @return 集合中的下一个元素
 * @throws NoSuchElementException 如果没有更多元素
 */
E next();
 
/**
 * 删除当前元素（可选操作）
 * 此方法只能在调用next()之后调用，并且只能调用一次
 * @throws UnsupportedOperationException 如果此迭代器不支持remove操作
 * @throws IllegalStateException 如果next()方法尚未调用，或者remove()方法已经被调用
 */
default void remove() {
    throw new UnsupportedOperationException("remove");
}
 
/**
 * 对剩余元素执行指定操作，直到所有元素都被处理完毕
 * @param action 要对每个元素执行的操作
 * @throws NullPointerException 如果指定的操作是null
 * @since 1.8
 */
default void forEachRemaining(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    while (hasNext())
        action.accept(next());
}

实现原理

Iterator的实现通常与具体集合类紧密相关，每个集合类都有自己的Iterator实现。以下是几个常见集合的Iterator实现原理：

ArrayList.Itr

// ArrayList的内部迭代器类
private class Itr implements Iterator<E> {
    int cursor;       // 下一个要返回的元素的索引
    int lastRet = -1; // 最后一个返回的元素的索引；如果没有则为-1
    int expectedModCount = modCount; // 期望的修改次数
 
    Itr() {}
 
    public boolean hasNext() {
        return cursor != size;
    }
 
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification(); // 检查并发修改
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
 
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification(); // 检查并发修改
 
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
 
    // 检查并发修改
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

LinkedList.Itr

// LinkedList的内部迭代器类
private class Itr implements Iterator<E> {
    private Node<E> lastReturned; // 最后返回的节点
    private Node<E> next;         // 下一个要返回的节点
    private int nextIndex;        // 下一个要返回的节点的索引
    private int expectedModCount = modCount; // 期望的修改次数
 
    Itr() {
        next = first; // 初始化为第一个节点
        nextIndex = 0;
    }
 
    public boolean hasNext() {
        return nextIndex < size;
    }
 
    public E next() {
        checkForComodification(); // 检查并发修改
        if (!hasNext())
            throw new NoSuchElementException();
 
        lastReturned = next;
        next = next.next; // 移动到下一个节点
        nextIndex++;
        return lastReturned.item;
    }
 
    public void remove() {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification(); // 检查并发修改
 
        try {
            LinkedList.this.remove(lastReturned);
            if (next == lastReturned)
                next = lastReturned.next;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount = modCount;
        } catch (NoSuchElementException ex) {
            throw new ConcurrentModificationException();
        }
    }
 
    // 检查并发修改
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

HashMap.NodeIterator

// HashMap的内部节点迭代器类
final class NodeIterator extends HashIterator implements Iterator<Node<K,V>> {
    public final Node<K,V> next() {
        return nextNode();
    }
}
 
// HashMap的内部哈希迭代器基类
abstract class HashIterator {
    Node<K,V> next;        // 下一个节点
    Node<K,V> current;     // 当前节点
    int expectedModCount;  // 期望的修改次数
    int index;             // 当前桶的索引
 
    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // 找到第一个非空桶
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }
 
    public final boolean hasNext() {
        return next != null;
    }
 
    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            // 找到下一个非空桶
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }
 
    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}

使用示例

// 使用Iterator遍历ArrayList
ArrayList<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
list.add("C++");
 
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
    // 可以使用remove()方法删除元素
    if (element.equals("Python")) {
        iterator.remove();
    }
}
 
// 使用增强for循环遍历（底层也是使用Iterator）
for (String element : list) {
    System.out.println(element);
}
 
// 使用forEachRemaining方法遍历
iterator = list.iterator();
iterator.forEachRemaining(System.out::println);

快速失败机制

Iterator的快速失败机制是指在迭代过程中，如果集合被结构性修改（添加、删除元素），迭代器会立即抛出ConcurrentModificationException异常。这是通过modCount和expectedModCount字段实现的：

1. 集合中维护一个modCount字段，记录集合的修改次数
2. 迭代器创建时，会将modCount赋值给expectedModCount
3. 每次调用next()或remove()方法时，都会检查modCount是否等于expectedModCount
4. 如果不相等，说明集合已被修改，抛出ConcurrentModificationException异常

注意事项

• Iterator是单向的，只能从前往后遍历
• 调用remove()方法前必须先调用next()方法
• 每次调用next()方法后，只能调用一次remove()方法
• 增强for循环（for-each）底层使用Iterator，但不支持remove()操作
• ListIterator是Iterator的子接口，支持双向遍历和修改元素

ListIterator

ListIterator是Iterator的子接口，专门用于List集合，提供了更多功能：

public interface ListIterator<E> extends Iterator<E> {
    // 检查是否有前一个元素
    boolean hasPrevious();
 
    // 返回前一个元素
    E previous();
 
    // 返回下一个元素的索引
    int nextIndex();
 
    // 返回前一个元素的索引
    int previousIndex();
 
    // 删除当前元素
    void remove();
 
    // 设置当前元素
    void set(E e);
 
    // 在当前位置插入元素
    void add(E e);
}

ListIterator的使用示例：

// 使用ListIterator双向遍历ArrayList
ArrayList<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
list.add("C++");
 
ListIterator<String> listIterator = list.listIterator();
 
// 正向遍历
while (listIterator.hasNext()) {
    System.out.println("Index: " + listIterator.nextIndex() + ", Element: " + listIterator.next());
}
 
// 反向遍历
while (listIterator.hasPrevious()) {
    System.out.println("Index: " + listIterator.previousIndex() + ", Element: " + listIterator.previous());
}
 
// 在指定位置插入元素
listIterator = list.listIterator(1);
listIterator.add("JavaScript");
 
// 修改元素
listIterator.next();
listIterator.set("TypeScript");

---

3. 总结

3.1 数据容器共同拥有的内容

3.1.1 接口继承关系

概述

所有数据容器都继承自 Collection<E> 接口，该接口定义了基本的集合操作（如添加、删除、查询等）。具体实现类根据功能进一步继承子接口：

• List：有序集合，允许重复元素（如 ArrayList, LinkedList）。
• Set：无序集合，不允许重复元素（如 HashSet, TreeSet）。
• Map：键值对集合（如 HashMap, TreeMap）。

3.1.2 核心方法

所有数据容器都支持以下核心方法

• add(E e)：添加元素，部分实现（如 List）支持指定位置插入。
• remove(Object o)：删除元素，支持批量删除（removeAll(Collection<?>)）。
• contains(Object o)：检查元素是否存在。
• clear()：清空集合。
• iterator()：返回迭代器，支持遍历。
• toArray()：将集合转为数组，支持自定义数组类型。

3.1.3 迭代器模式

概述

所有数据容器通过 Iterator 接口提供遍历能力，部分实现（如 List）还支持 ListIterator，提供双向遍历和修改功能。

3.2 数据容器的设计智慧

3.2.1 接口分层与默认方法

Java集合框架通过接口分层

如 Collection → List → ArrayList实现扩展性。 默认方法（如 Stream、Spliterator）支持并行处理和高效分页，体现了面向接口编程的设计思想。

3.2.2 失败快速机制（Fail-Fast）

概述

Iterator 的 next() 方法在检测到集合结构修改时抛出 ConcurrentModificationException，避免数据不一致。 例如，ArrayList 的 modCount 字段记录修改次数，与迭代器的 expectedModCount 对比。

3.2.3 动态扩容与懒加载

概述

• ArrayList：初始容量为10，按需扩容（原容量的1.5倍）。
• HashMap：惰性初始化，首次 put 时才创建数组，避免不必要的内存占用。

3.2.4 线程安全与并发控制

实现方式

通过包装类（如 Collections.synchronizedList()）或内部锁实现线程安全。CopyOnWriteArrayList 采用读写分离策略，适用于读多写少场景。

3.2.5 序列化优化

具体实现

• HashMap：支持自定义序列化逻辑，避免存储空指针。
• ArrayList：序列化时仅存储实际元素，减少内存占用。

3.3 数据容器的最佳使用策略

3.3.1 选择合适的数据结构

选择策略

• 频繁随机访问：ArrayList（基于数组，O(1)随机访问）。
• 频繁插入删除：LinkedList（基于链表，O(1)插入删除）。
• 键值对存储：HashMap（无序，快速查找）；TreeMap（有序，支持范围查询）。
• 不允许重复元素：HashSet 或 LinkedHashSet。

3.3.2 避免常见陷阱

注意

1. 并发修改：使用 Iterator 的 remove() 方法，或通过 CopyOnWriteArray。
2. 哈希冲突：选择合适的哈希函数（如 String 的 hashCode()）。
3. 内存泄漏：避免使用 SoftReference 或 WeakHashMap 错误配置。

3.3.3 性能调优

具体操作

• 批量操作：使用 add(E e) 而非循环添加，减少触发扩容次数。
• 避免装箱操作：直接使用 List<Integer> 而非 List<Integer> 包装类，减少装箱开销。