目录Collection 接口概览Collection 家族详解
1. List
1.1 ArrayList 1.2 Vector 1.3 LinkedList 1.4 CopyOnWriteArrayList
2. Set
2.1 HashSet 2.2 LinkedHashSet
2.3、TreeSet
3、Queue
Collection 接口概览在Java集合框架中，Collection 是最基础的根接口。需要注意的是，虽然 Map 同属集合框架范畴，但它与Collection并非继承关系，而是两个独立的顶级接口。
Collection 接口定义在 java.util 包中，是一个泛型接口，继承自 Iterable 接口。
package java.util;// 继承了 Iterable，意味着所有 Collection 实现类都可以使用 for-each 循环public interface Collection
}从架构层面来看，Collection 接口主要扩展为三大核心子接口：List：有序、可重复的集合Set：无序、不可重复的集合Queue：队列，通常遵循FIFO（先进先出）规则Collection 定义了所有单列集合共有的操作。根据功能可分为四大类：添加、删除、查询（判断）及其他操作：添加操作方法签名描述注意事项boolean add(E e)向集合中添加一个元素 e若集合发生变化（例如 Set 成功插入元素），则返回 true；若集合未发生变化（例如 Set 中已存在该元素），则返回 false boolean addAll(Collection c)将指定集合 c 中的所有元素添加到当前集合相当于将另一个集合合并到当前集合中删除操作方法签名描述注意事项boolean remove(Object e)删除集合中指定的单个元素 o如果存在并删除成功返回 true；不存在返回false boolean removeAll(Collection c)删除当前集合中包含在集合 c 里的所有元素执行差集运算（当前集合减去集合c）
void clear()清空集合中所有元素集合中的元素清空，但集合对象本身还存在default boolean removeIf(Predicate filter) (JDK 8 新增)删除满足给定条件的所有元素配合 Lambda 表达式使用，非常强大查询与判断方法签名描述注意事项int size()返回集合中元素的个数最大值是Integer.MAX_VALUE(2^{31} - 1) boolean isEmpty()判断集合是否为空（size == 0）
建议用此方法判断，而不是size() == 0，因为语义更清晰boolean contains(Object o)判断集合是否包含指定元素o底层依赖equals()方法boolean containsAll(Collection c)判断当前集合是否包含集合c中的所有元素判断当前集合是否包含子集 c数组转换与遍历方法签名描述注意事项Object[] toArray()将集合转换为Object类型数组类型丢失，通常不推荐使用T[] toArray(T[] a)将集合转换为指定类型的数组推荐使用。当数组a容量不足时，JDK 会自动创建新的数组Iterator iterator()返回在此集合上进行迭代的迭代器用于遍历和删除元素自 JDK 8 起，Collection 接口新增了多个 default 方法，显著提升了集合操作的函数式编程能力和使用便捷性：default boolean removeIf(Predicate filter)：用于删除满足条件的元素default Stream
default Spliterator
一句话总结：Collection 定义了单列集合 “能干什么”，而 List、Set、Queue 定义了 "怎么干"（具体的行为约束）。
Collection 家族详解
1. List
List 是一个有序的集合（序列），可以精确控制每个元素的插入位置。用户可以通过索引来访问元素。
核心特点：
有序：元素按插入顺序排列，每个元素都有索引。
可重复：
可以存储任意多个相同的元素。
1.1 ArrayList ArrayList 是 List 接口的一个可变长数组实现。它可以动态地增长和缩减其容量，以容纳任意数量的的元素。
核心特点：
基于数组实现：
其底层是一个 Object[] 数组，这决定了它的大部分性能特性。
有序：
元素按照插入顺序排列，每个元素都有一个精确的索引（从 0 开始）。
可重复：
可以存储任意数量的重复元素，包含 null。
非线程安全：
多个线程同时修改一个 ArrayList 实例时，需要外部同步。否则可能会导致数据不一致。
底层原理：动态数组的奥秘ArrayList 的精髓在于其 "动态" 二字，那它是如何实现一个可以动态扩容的数组呢？
核心存储：elementData 与 size要理解ArrayList，首先要区分两个看似相似但意义完全不同的概念：容量和大小。
public class ArrayList
// transient 关键字表示该字段不会被序列化transient Object[] elementData;// ArrayList 中包含的元素数量private int size;// ..........
}elementData（容量）
：这是ArrayList的仓库。它是一个Object[]数组，其长度（elementData.length）代表了 ArrayList 当前最多能够装多少个元素。
size（大小）
：这是 ArrayList 的库存清单。它是一个 int 值，记录了仓库中实际存放了多少个元素。它永远小于或等于 elementData.length.
诞生之初ArrayList 提供了三种构造函数，它们决定了 elementData 的初始状态。
ArrayList()这是最常用的无参构造函数。
public ArrayList(){this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}这里关键点在于理解为什么会初始化一个空数组，而不是一个有默认容量10 的数组。这是一种延迟初始化（懒加载）
的优化策略。在旧版本（JDK1.6及之前）中，它会直接创建一个容量为10的数组。这就意味着，即使你创建了一个ArrayList，但马上就丢弃了，或者只往里面放了一两个元素，系统也会预先分配10个对象引用的内存空间，这可能就造成了内存浪费。故而从JDK1.7开始，ArrayList的实现进行了优化，采用了懒加载策略。当你 new ArrayList() 时，它只是将 elementData 指向一个共享的空数组，此时几乎没有占用额外的内存空间（除对象本身的少量开销）。真正的容量10 是在第一次添加元素时进行分配的，ArrayList 会检查当前的 elementData 是不是那个默认的空数组，如果是，它就会为这个数组分配初始容量的内存空间，然后将新元素放入其中。
//JDK 1.6 public ArrayList() {this(10); // 直接调用带容量的构造函数，传入 10}public ArrayList(int initialCapacity) {super();if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);this.elementData = new Object[initialCapacity]; // 立即创建一个长度为 10 的数组}ArrayList(int initialCapacity)这个构造函数接受一个整数参数，用于初始化 ArrayList 的底层数组大小。
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {// 如果初始容量大于0，创建对应大小的Object数组this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {// 如果初始容量为0，使用预定义的空数组常量this.elementData = EMPTY_ELEMENTDATA;} else {// 如果初始容量为负数，抛出非法参数异常throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);}}当你知道大概要存储多少元素时，可以预先指定容量，避免频繁扩容带来的性能开销。
注意：
初始容量过小会导致频繁扩容，影响性能初始容量过大会浪费内存空间ArrayList(Collection c)这个构造函数接收一个实现Collection接口的集合作为参数，用于创建一个新的ArrayList实列。
public ArrayList(Collection c) {// 使用Collection的toArray()方法将传入的集合转换为数组Object[] a = c.toArray();// 将数组长度赋值给 size,同时判断数组长度是否为0// 如果数组长度不等于 0,则向下继续执行// 否则，就使用预定义的空数组EMPTY_ELEMENTDATA if ((size = a.length) != 0) {//判断集合本身是否是ArrayList//如果是，就直接使用其内部数组（elementData）
//否则，使用Arrays.copyOf()创建一个新的数组副本//其目的是为了保证新创建的ArrayList的内部数组完全独立，不受原集合影响if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);}} else {elementData = EMPTY_ELEMENTDATA;}}该构造函数主要用于将其他类型的集合转换为ArrayList、创建一个已存在集合的ArrayList副本和快速初始化一个包含特定元素的ArrayList。在使用时需要注意类型安全的问题，虽然使用了通配符，但在编译时会进行类型检查，如果传入的集合包含不兼容的类型，在编译时会报错。
扩容机制扩容是 ArrayList 最核心、也最耗时的操作。接下来通过add(E e)方法追踪下 ArrayList 的扩容过程。
步骤 1：添加元素 add（E e）
public boolean add(E e) {ensureCapacityInternal(size + 1); // 关键：检查容量是否足够elementData[size++] = e; // 将元素放入数组，并增加 size return true;}在放入元素前，它会先调用ensureCapacityInternal( size +1 )，其目的是在放入第 size + 1 个元素前，检查下容量够不够。
步骤 2：容量检查 ensureCapacityInternal(size + 1)private void ensureCapacityInternal(int minCapacity) {// 如果elementData 是否是默认的空数组if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// 如果是，则将最小容量设置为默认容量(10)和请求容量中的较大值// 确保了第一次添加元素时，数组至少有10个元素的空间minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}这就是延迟初始化（懒加载）
的体现：第一次调用add(E e)方法时，minCapacity会被直接提升到10，为后续的元素预留空间步骤 3：触发扩容判断 ensureExplicitCapacity(int minCapacity) private void ensureExplicitCapacity(int minCapacity) {// 修改计数器，用于迭代器的快速失败机制// 快速失败机制（fail-fast）:是一种错误检测机制。当在迭代过程中，// 如果检测到集合结构被修改（非迭代器自身的方法导致的修改）
// 迭代器会立即抛出ConcurrentModificationException异常，// 而不是继续执 行可能导致不确定行为。
modCount++;// 检查是否需要扩容 (所需最小容量大于当前数组的长度) if (minCapacity - elementData.length > 0)// 执行扩容操作 grow(int minCapacity) grow(minCapacity);}步骤 4：扩容的核心 grow(int minCapacity)private void grow(int minCapacity) {// overflow-conscious code// 旧容量int oldCapacity = elementData.length;// 新容量 = 旧容量 + 旧容量/2 (即 1.5 倍) int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果 1.5 倍后还不够，就用所需的最小容量if (newCapacity - minCapacity < 0) newCapacity = minCapacity;// 处理极端情况，防止新容量超过 Integer.MAX_VALUE if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:// 关键：复制数组elementData = Arrays.copyOf(elementData, newCapacity);}性能的权衡：为何扩容因子是1.5倍：
避免频繁扩容：
如果扩容因子过小（如 1.1 倍），那么扩容会非常频繁，容易导致大量的数组复制开销。
避免内存浪费：如果扩容因子过大（如 2.0 倍，Vector的选择），可能会导致一次扩容后预留大量未用空间，造成内存浪费。对于超大列表，这种内存浪费是惊人的。
数学上的合理性：1.5 倍（oldCapacity + (oldCapacity >> 1)）可以通过位运算快速完成，比乘法效率略高。它在空间和时间成本之间取得了很好的平衡。
Arrays.copyOf()：它是java.util.Arrays 工具类中的一个核心方法，主要功能是复制一个指定的数组，并可以指定新数组的长度，从而实现截取和扩容。这个方法是ArrayList 动态数组实现扩容的关键。
Arrays.copyOf()的内部工作流：
创建新的数组：
在堆内存中开辟一块新的、连续的内存空间，大小为newCapacity。
数据复制：
使用System.arraycopy() 这个本地方法，将 elementData 中的所有元素（从索引0 至 size -1 ） 按字节拷贝到新的数组中。这是一个O(n)的操作。
引用切换：
将 elementData 的引用指向新的数组，旧数组会在下一次GC时被回收。
使用建议扩容操作涉及数组复制，相对耗时。如果能预估元素数量，建议在初始化时指定容量，避免多次扩容。
1.5 倍的扩容策略也存在可能导致内存浪费，如不需要添加元素时，可以使用 trimToSize() 释放多余空间。
ArrayList不是线程安全的，在多线程环境下使用可能会导致出现数据不一致的情况。
1.2 Vector它是最早的集合类之一，是线程安全列表的鼻祖。然而在如今的现代java开发中，它的身影却是越来越少见了，甚至被贴上了 “过时” 的标签。Vector 与 ArrayList 非常相似，它也是一个基于动态数组实现的 List 。它同样是有序的、允许重复元素和 null 值的。
Vector 最独一无二的特点是：它是线程安全的。
这就意味着，它的所有公共方法都被 synchronized 关键字修饰。当一个线程访问 Vector 的任何一个方法时，它会先获取 Vector 实例的对象锁，其他试图访问的线程必须等待，直至锁被释放。
public synchronized void addElement(E obj) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = obj;}public synchronized boolean removeElement(Object obj) {modCount++;int i = indexOf(obj);if (i >= 0) {removeElementAt(i);return true;}return false;}public synchronized void removeAllElements() {modCount++;// Let gc do its work for (int i = 0; i < elementCount; i++) elementData[i] = null;elementCount = 0;}public synchronized E get(int index) {if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index);return elementData(index);}public synchronized E set(int index, E element) {if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}public synchronized E remove(int index) {modCount++;if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index);E oldValue = elementData(index);int numMoved = elementCount - index - 1;if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--elementCount] = null; // Let gc do its work return oldValue;}//...........
性能分析：
Vector的性能瓶颈在于其粗粒度的锁。即使只是进行一个简单的 get()读操作，也需要获取整个对象的锁，这会阻塞所有其他线程的读和写操作。在并发度稍高的场景下，这种串行化的执行方式会成为严重的性能瓶颈。
底层原理：加锁的动态数组Vector 的底层实现与 ArrayList 高度相似，都是基于一个可动态扩容的数组。
核心成员变量public class Vector
protected int capacityIncrement; // 容量增长系数private static final long serialVersionUID = -2767605614048989439L;// 定义一个数组理论上的最大容量上限// 注意：这个 8 不是一个魔法数字，它是基于对主流 JVM 实现对象内存布局的经验值。
// 它足够大，可以覆盖大多数虚拟机中数组对象的额外开销。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//...........
}与 ArrayList 相比，Vector 多了一个 capacityIncrement 字段。这个字段用于自定义扩容时的增长量。如果设置为 0 （默认值），则容量翻倍。
扩容机制Vector的扩容机制与ArrayList类似，都是在容量不足时创建一个新数组并复制旧数据。但关键区别在于扩容的倍数。
private void grow(int minCapacity) {// overflow-conscious code int oldCapacity = elementData.length; // 获取当前数组容量// 计算新容量 newCapacity：// 如果设置了capacityIncrement（扩容增量），则新容量 = 旧容量 + capacityIncrement// 如果没有设置capacityIncrement（默认为0），则新容量 = 旧容量的2倍int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);// 检查新容量是否满足最小需求，如果不满足则使用minCapacity if (newCapacity - minCapacity < 0) newCapacity = minCapacity;// 检查新容量是否超过最大数组限制（MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8）
if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);// 使用Arrays.copyOf创建新数组并复制原有元素elementData = Arrays.copyOf(elementData, newCapacity);}这是 Vector 特有的扩容机制，与 ArrayList 不同（ArrayList 默认 1.5 倍）。
capacityIncrement 可以在构造 Vector 时指定，用于控制每次扩容的增长量。
方法 hugeCapacity(minCapacity) 处理容量超过Integer.MAX_VALUE - 8的情况。
为什么 Vector 会被弃用？
Vector 被标记为 “过时”，并非是因为有Bug，而是有了更好的代替方案。综上所述，因为 Vector 所有的公共方法都被synchronized 关键字修饰，所以其带来的性能开销在并发的场景下是难以接受的。
更好的替代品：
Collections.synchronizedList (new ArrayList<>()):它是一个包装器，它和Vector一样，也是通过synchronized为每个方法加锁保证线程安全。它的出现，使开发者可以用更灵活的ArrayList来获得线程安全能力，而不必锁在Vector这个具体的实现上。
java.util.concurrent.CopyOnWriteArrayList：这是JDK 1.5 引入的并发集合。它采用 “写时复制”策略，实现了读无操作锁，极大提升了读多写少场景下的并发性能。是对Vector的降维打击。
1.3 LinkedList LinkedList 是基于节点的集合，其中的每个元素都包含了对前一个元素和后一个元素的引用。这种结构就像是一列火车，每个车厢都连接着前一节和后一节车厢。
核心特点：
基于双向链表实现：
与 ArrayList 相比，这是最根本的区别。
有序：
元素按插入顺序排列。
可重复：
可以存储任意相同元素和 null 值。
非线程安全：
与 ArrayList 一样，不是线程安全的。
双重身份：
它不仅实现了 List 接口，还实现了 Deque 接口（双端队列），这意味着它可以被当作栈或队列来使用。
底层原理：双向链表的节点艺术LinkedList 的优雅与强大，完全隐藏在其精巧的节点结构和指针操作之中。
基石：Node
private static class Node双向链表节点由三部分组成：存储的数据（item）、指向前驱节点的指针（prev）以及指向后继节点的指针（next）。
宏观结构：first、last和size LinkedList 类本身并不直接存储元素，而是通过三个核心成员变量来管理整个链表的状态。
public class LinkedList
}这种结构让头部和尾部的操作变得非常高效，因为可以直接通过指针访问。
性能分析：快与慢的另一面操作类型时间复杂度原因分析访问（get(int index)）
O(n)数组可以通过索引直接计算地址，但链表必须从 first 或 last 开始，一个一个地向前或向后遍历，直至查找到目标索引。
头部/尾部添加（addFirst/addLast）
O(1)只需要修改first或last的引用，并让新节点指向旧的头部/尾部即可，不涉及数据移动。
中间插入（add(int index, E e)）
O(n)虽然插入本身是 O(1)（只需修改前后节点的指针），但找到插入位置需要 O(n) 的时间去遍历。
头部/尾部删除（removeFirst/removeLast）
O(1)同头部/尾部添加，只需修改first或last的引用。
中间删除（remove(int index)）
O(n)与中间插入同理，主要时间消耗在找到待删除节点上。
查找 (contains(Object o)) O(n)必须从头到尾遍历整个链表。
访问（ get(int index) ）
public E get(int index) {// 检查传入索引是否有效checkElementIndex(index);// 如果索引有效，调用 node(int index) 方法找到对应索引得节点，并返回找到的节点的 item 字段return node(index).item;}private void checkElementIndex(int index) {// 检查传入索引是否有效（即在指定范围内），无效则抛出IndexOutOfBoundsException的异常if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private boolean isElementIndex(int index) {// 判断索引是否在0到size-1范围内return index >= 0 && index < size;}Node链表的get操作时间复杂度为O(n) .因为可能需要遍历链表。且索引必须在 0 到 size-1 范围内，否则会抛出异常。如若在多线程环境下使用，需要外部同步，因为该方法不是线程安全的。
头部/尾部添加 (addFirst/addLast)public void addFirst(E e){linkFirst(e); // 将实际元素 e 链接到列表开头}public void linkFirst(E e){// 保存当前头节点的引用final NodeaddFirst / addLast 方法本身是一个简单的包装器，实际操作操作是由 linkFirst / linkLast 完成。linkFirst / linkLast 方法通常会在链表数据结构中实现，它会在链表头部/尾部插入一个新的节点，并将新节点的 next / prev 引用指向原 头节点/尾节点，然后更新链表的 头节点/尾节点 为新节点。
在指定位置插入元素（ add(int index,E e) ）
public void add(int index, E element){// 检查索引是否越界checkPositionIndex(index);// 如果插入位置是末尾if(index == size) linkLast(element); //调用linkLast 方法添加至尾部else linkBefore(element,node(index)); // 否则，在指定节点前插入}private void checkPositionIndex(int index){// 检查传入索引是否有效（即在指定范围内），无效则抛出IndexOutOfBoundsException异常if(!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private boolean isPositionIndex(int index){// 判断索引是否在0到size范围内return index >= 0 && index <= size;}void linkBefore(E e, Nodeadd( int index, E e) 的实现是一个典型的 “查找 + 插入” 的模式：检查索引的合法性判断位置，选择最高效的路径（末尾直接插入，其他位置先查找）
查找节点时采用双向遍历优化，减少一半的遍历时间插入节点本身是高效的 O(1) 操作，只涉及指针修改头部/尾部删除（removeFirst/removeLast）
public E removeFirst(){// 获取链表头节点，并用 final 修饰，确保引用不会被改变final Node在执行 removeFirst 或 removeLast 方法删除首尾元素时，会先获取目标节点并进行非空校验。若节点为空，则抛出 NoSuchElementException 异常；若节点存在，则调用对应的 unlinkFirst 或 unlinkLast 方法完成删除操作。
删除指定位置元素（ remove(int index) ）
public E remove(int index){检查索引是否有效checkElementIndex(index);// 调用 unlink 方法删除指定位置元素，并返回删除元素的值return unlink(node(index));}private void checkElementIndex(int index){// 检查传入索引是否有效（即在指定范围内），无效则抛出IndexOutOfBoundsException的异常if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private boolean isElementIndex(int index) {// 判断索引是否在0到size-1范围内return index >= 0 && index < size;}E unlink(Node
modCount++;// 返回被移除节点的元素值return element;}删除指定位置元素remove(int index)的时间复杂度为O(n)，原因在于需要先通过node(index)方法定位目标节点，这个定位过程需要线性时间。虽然实际删除操作仅需常数时间O(1)，但整体时间复杂度仍由较耗时的定位步骤决定。
查找 ( contains(Object o) )public boolean contains(Object o){// 调用 indexOf 查找目标元素 o 的索引，并判断目标元素索引不等于 -1// 目标元素索引等于 -1，等式不成立，返回 false; 不等于则返回 true return indexOf(o) != -1;}public int indexOf(Object o){// 初始化索引记数器int index = 0;// 分别处理查找 null 值和非 null 值的情况，避免出现NullPointerException// 处理查找null值的情况if (o == null) {for (Nodecontains 方法将“查找元素是否存在”的问题，巧妙地转换成了“查找元素的索引是否为-1”的问题。如若查找目标元素 o 在链表中存在相同元素，只会返回第一个匹配项的索引。
LinkedList的内存与空间局部性
内存开销：
每个元素都需要一个 Node 对象来包装。除了存储元素 E 本身，每个 Node 还额外需要两个引用（ prev 和 next ）的空间。在 64 位JVM （开启压缩指针）中，一个 Node 对象头占 12字节，两个引用占 8字节，总共20字节的开销，这其中还不包含元素 E 本身的大小。而 ArrayList 只是一个数组中的引用。
空间局部性差：
ArrayList 的元素在内存中是连续存放的，当 CPU 访问一个元素时，可以预加载其相邻的元素到缓存中，这就极大地提高了遍历性能。而 LinkedList 的节点在内存中是散落的，CPU无法有效的预取，缓存命中率低，遍历性能远不如 ArrayList。
迭代器：
ListIterator如果说普通的 Iterator 只能让你在集合中”
单向、只读（主要）
“地前进，那么 ListIterator 就像是给了你一辆可以倒车、随时变速、还能边开边修路的全地形车。它是 Java 集合专门为 List 接口设计的强大迭代器。
普通的 Iterator 由有三个明显的局限：单向遍历：只能从前往后走，不能回头无法获取索引：在迭代过程中，存在无法知道当前已经迭代到了几个元素修改能力弱：只能通过 remove() 方法删除元素，不能添加或替换元素ListIterator 正是为了克服这些局限而诞生，它允许你：双向遍历：向前或向后遍历获取索引：精确知道当前光标的位置强大的修改能力：可以在遍历过程中添加、删除、修改元素概念：光标想象列表元素之间有间隙，光标就落在这个间隙里：元素(0) 元素(1) 元素(2) 元素(3)
A B C D
| | | | |
^(0) ^(1) ^(2) ^(3) ^(4)初始状态，光标在位置0（即第一个元素之前）。
next() 会跳过光标后的元素，并将光标向后移动。
previous() 会跳过光标前的元素，并将光标向前移动。
核心方法ListIterator 接口继承 Iterator，并扩展以下核心方法：遍历与移动方法作用光标变化返回值next()返回下一个元素，并向后移动光标index -> index+1下一个元素previous()返回上一个元素，并向前移动光标index -> index-1上一个元素hasNext()检查后面是否还有元素不变true / false hasPrevious()检查前面是否还有元素不变true / false索引查询方法作用返回值nextIndex()返回下一次调用next()时返回的元素的索引int previousIndex()返回下一次调用previous()时返回的元素的索引int修改操作方法作用前置条件set(E e)替换最后一次通过 next() 或 previous() 返回的元素必须先调用 next() 或 previous()，且在这之后没调用过 add() 或 remove() add(E e)插入一个元素到光标当前位置无前置条件remova()删除最后一次通过 next() 或 previous() 返回的元素必须先调用 next() 或 previous()，且在这之后没调用过 add() 或 remove(）
import java.util.LinkedList;import java.util.ListIterator;public class ListIteratorDemo {public static void main(String[] args){LinkedList
注意：
虽然 ListIterator 允许在迭代过程中修改列表（通过它自己的add/remove/set），但如果你在迭代过程中使用了列表对象自身的方法（如list.add()）去修改结构，迭代器会立即抛出ConcurrentModificationException。
1.4 CopyOnWriteArrayList CopyOnWriteArrayList 是 java.util.concurrent 包下的成员，它是线程安全的 ArrayList。它的名字 CopyOnWrite （写时复制）已经揭示了它的核心秘密：当你需要修改列表时，不要直接在原数组上改，而是先把原数组复制一份，在副本上修改，修改完成后，再让引用指向新数组。
核心思想：读写分离（读线程与写线程互不干扰）
CopyOnWriteArrayList 解决并发问题的思路与 Vector 或 synchronizedList 截然不同：Vector 等悲观锁方案：为了保证数据一致性，无论是读还是写，都要抢同一把锁。这就导致了读操作被写操作阻塞，性能低下。
CopyOnWriteArrayList 乐观锁方案：读操作采用无锁设计，因为它不会修改数据（允许读取到稍旧的数据）。写操作则通过加锁机制确保原子性，防止多线程并发复制。加锁后，所有写操作都在新副本上进行。
底层原理解析CopyOnWriteArrayList是一个设计精巧的并发容器。它用写操作的昂贵代价（复制数组）
换取了读操作的极致性能（无锁）。
核心成员变量public class CopyOnWriteArrayList
}注意这里使用了volatile，这是 CopyOnWriteArrayList 保证线程安全的基石之一，它确保了当写操作把 array 指针指向新数组时，读线程能立刻感知到。
读操作：get(int index) —— 完美无锁public E get(int index) {// 先调用 getArray() 获取 array 引用，不加任何锁// 然后调用另一个重载的get方法，传入数组和索引，返回数组中的元素return get(getArray(),index);}private E get(Object[] a, int index) {return (E) a[index];}读操作性能极佳，即使存在并发写操作，读线程也能无阻塞地并行读取，且不会抛出ConcurrentModificationException。不过需要注意其弱一致性问题：当写线程修改数据但尚未更新数组引用时，读线程可能读取到旧数据。虽然这不适用于对实时性要求极高的系统，但对于大多数业务场景（如配置列表、白名单等）来说完全可接受。
写操作：add(E e) —— 写时复制public boolean add(E e) {// 获取锁对象final ReentrantLock lock = this.lock;// 加锁，确保线程安全lock.lock();try {// 获取当前数组Object[] elements = getArray();// 获取当前数组长度int len = elements.length;// 创建一个新数组，长度为原数组+1，并拷贝旧数组Object[] newElements = Arrays.copyOf(elements, len + 1);// 在新数组末尾添加新元素newElements[len] = e;// 将新数组设置为底层数组setArray(newElements);return true;} finally {// 释放锁lock.unlock();}}写操作存在着明显的性能瓶颈和延迟问题：
内存消耗：
每次写入都需要完整复制底层数组。当处理大型数组（例如存储10万个对象）且频繁修改时，会产生巨大的内存压力，容易触发Young GC甚至Full GC。
性能损耗：
尽管仅涉及加锁和复制操作，但对于大规模数据（N值较大），Arrays.copyof的时间复杂度达到O(n)，导致写入效率较低。
弱一致性：
写入过程中其他线程可能仍在读取旧数组，存在短暂的数据不一致。CopyOnWriteList返回的迭代器基于"数组快照"机制，无法反映后续的修改。
import java.util.Iterator;import java.util.List;import java.util.concurrent.CopyOnWriteArrayList;public class CopyOnWriteArrayListDemo {public static void main(String[] args) {List
2. Set
Set 是一个无序且唯一的集合。它不允许包含重复的元素，就像学校班级的一个花名册，每个学生都是独一无二的。
核心特点：
元素唯一：
不允许出现重复元素（最多只能包含一个 null 元素）。
无序：
无法确保元素的存储与遍历顺序 。
2.1 HashSet HashSet 虽然它的名字带个 "Set"，但它实际上是披着 "Set" 外衣的 HashMap。它是一个伪装者，它所有的核心特性——唯一性、快速查找、无序性——全部来自 HashMap。
底层原理解析理解 HashSet 的核心，就在于理解它是如何利用 HashMap 来实现唯一性的。
揭秘 HashSet 的本质public class HashSet
public HashSet() {map = new HashMap<>();}// 创建一个包含指定集合元素的 HashSet，根据集合大小计算合适的初始容量，确保不会频繁扩容public HashSet(Collection c) {map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));addAll(c);}// 创建 HashSet,允许自定义初始容量和加载因子public HashSet(int initialCapacity, float loadFactor) {map = new HashMap<>(initialCapacity, loadFactor);}// 创建 HashSet, 允许自定义初始容量public HashSet(int initialCapacity) {map = new HashMap<>(initialCapacity);}}HashSet 本质上是通过 HashMap 实现的特殊结构。它将所有元素作为 HashMap 的键存储，利用 HashMap 键不可重复的特性来实现去重功能。为了维持 HashMap 的键值对结构，HashSet 使用一个名为 PRESENT 的常量作为占位符填充值字段。
核心操作源码解析public boolean add(E e) {// 直接用 map 的 put 方法存储元素 e// e 是 key, PRESENT 是固定的 value return map.put(e, PRESENT)==null;}public boolean remove(Object o) {// 直接调用 map 的 remove 方法删除元素 o return map.remove(o)==PRESENT;}public boolean contains(Object o) {// 直接调用 map 的 containsKey 方法查找元素 o return map.containsKey(o);}HashSet 的所有核心操作（包括 add、remove 和 contains）实际上都是通过直接调用底层 HashMap 的对应方法来实现的，这体现了典型的委托模式设计。具体实现细节如下：在 HashSet 内部维护了一个 HashMap 实例作为存储容器当调用 add(E e) 方法时，实际上是执行 map.put(e, PRESENT) 操作：PRESENT 是一个固定的 Object 对象作为占位值这样设计可以复用 HashMap 的键唯一性特性remove(Object o) 方法对应 map.remove(o) 调用返回的是是否成功移除，而非被移除的值contains(Object o) 方法直接委托给 map.containsKey(o)
这种委托模式的优势在于：
代码复用：直接利用 HashMap 已经实现的哈希表功能维护简单：HashSet 只需要关注集合接口的实现性能保证：所有操作的时间复杂度与 HashMap 一致这种设计模式在 Java 集合框架中很常见，类似的还有：TreeSet 委托给 TreeMap LinkedHashSet 委托给 LinkedHashMap HashSet 的去重机制：基于 HashMap 的委托实现HashSet 的核心特性在于其能够自动过滤重复元素，而这一机制并非由其自身复杂的逻辑实现，而是全权委托给了底层的 HashMap。正如 JDK 官方源码注释所明确指出的：* This class implements the Set interface, backed by a hash table
* (actually a HashMap instance). It makes no guarantees as to the
* iteration order of the set; in particular, it does not guarantee that the
* order will remain constant over time. This class permits the null
* element.
中文释义：此类实现了Set接口，以哈希表支持（实际上是HashMap实例）。它不保证集合的迭代顺序；特别是，它不保证顺序会随时间保持不变。此类允许null元素。
这种“委托模式”在HashSet的add方法中体现得淋漓尽致。
// Adds the specified element to this set if it is not already present.
public boolean add(E e) {return map.put(e, PRESENT)==null;}HashSet 将待存储的元素 e 作为 Key 传入 HashMap，并使用静态常量对象 PRESENT 作为占位 Value。
去重的具体判定完全依赖于 map.put() 的返回值：当方法返回null时，表示HashMap中原本不存在该 Key，判定为不重复，插入成功。
当方法返回非null值（即旧的PRESENT）时，表示HashMap中已存在相同的 Key，判定为重复，插入失败。
深入分析 map.put() 方法后，我们发现 HashSet 的去重功能实际上是通过 putVal() 方法实现的。
public V put(K key, V value) {// 调用hash(key)方法计算键的哈希值// 将哈希值、键、值以及其他参数传递给putVal方法return putVal(hash(key), key, value, false, true);}static final int hash(Object key) {int h;// 如果 key 是 null，返回 0；否则将 h 右移 16 位并与自身异或（高位运算，减少冲突）
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}// hash: key的哈希值// key: 要存储的键// value: 要存储的值// onlyIfAbsent: 如果为true，则仅在键不存在时才插入// evict: 是否在插入后执行可能的移除操作（用于LinkedHashMap）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node
if (e != null) { // existing mapping for key V oldValue = e.value;// 根据 onlyIfAbsent 决定是否覆盖（HashSet 永远是覆盖）
if (!onlyIfAbsent || oldValue == null) e.value = value;afterNodeAccess(e);// 返回旧值，这对 HashSet 意味着 add 失败return oldValue;}}// 如果程序能走到这里，说明 e 为 null，是新增节点++modCount; //增加修改计数// 检查是否需要扩容if (++size > threshold) resize();afterNodeInsertion(evict);return null; // 返回 null，这对 HashSet 意味着 add 成功}根据源码分析，HashSet 判断重复元素的机制可分为两个关键步骤：
1. 哈希值比对（hashCode）:
首先计算新元素的 hashCode()若该哈希值与集合中现有元素均不相同，则判定为不重复元素，直接存入若出现哈希值相同的情况（哈希冲突），则进入下一步判断
2. 内容比对（equals）:
当哈希值相同时，调用 equals() 方法进行内容比较若 equals() 返回 true，则判定为重复对象，拒绝存入若 equals() 返回 false，则视为不同对象，将其添加到该哈希值对应的链表（或红黑树）结构中hashCode 与 equals 的“黄金契约”
在 Java 集合框架中，hashCode 与 equals 并非两个单独的方法，它们之间存在着一种隐含的、必须严格遵守的 “契约”。这种契约不仅是设计原则，更是保证对象能被正确存储（特别是存入 HashSet 或作为 HashMap 的 Key）的法律底线。
简单来说，这个契约可以概括为三个核心规则：
1、
相等的对象必须拥有相等的 Hash 码。这是契约的基石。如果两个对象通过 equals 判定为逻辑上的 “同一者”，那么它们调用 hashCode 返回的整数值必须完全一致。
反例：如果两个对象 equals 为 true，但 hash 值不同，它们在 HashMap 中会被分发给不同的“房间"（数组下标）。这不仅违反了唯一性逻辑，更会导致去重机制彻底失效——集合会将它们认为是两个完全不同的陌生人。
2、
Hash 码相同的对象，不一定相等。这是 Hash 碰撞的必然结果。由于 Hash 算法是将任意长度的输入映射到固定长度的输出，冲突是不可避免的。
解读：仅仅因为两个对象落在了同一个“房间”（Hash 值相同），并不能说明它们是同一个对象。此时，必须由equals方法出马进行最后的“人脸识别”，以决定是覆盖（相同）还是挂载（不同）到链表上。
3、
重写 equals 时，必须重写 hashCode。这是 Java 开发的铁律。如果你为了自定义对象的比较逻辑而重写了equals，却保留了继承自 Object 的默认hashCode（基于内存地址计算），你就亲手撕毁了这个契约。
重写 equals，不重写 hashCode 造成后果：你将得到一个看似正常、实则内部混乱的集合。对象可能会被错误地覆盖，或者重复数据无法被剔除。
在 Java.util.HashSet 的源码注释明确指出，该类的底层实现基于哈希表（实际是一个 HashMap 实例）。其去重机制完全依赖于 HashMap 对 Key 的唯一性约束。在 add(E e) 方法实现中（源码：return map.put(e, PRESENT) == null），通过判断 map.put 的返回值来确定元素是否已添加。这就要求存储对象必须严格遵循 Object 类的契约：当两个对象相等时，调用它们的 hashCode 方法必须返回相同的整数值，这样才能确保先计算哈希值再比较对象的去重流程正常运作。
总结：
hashCode负责宏观定位（将对象快速分流到对应的存储区域），而equals负责微观甄别（在区域内精确比对对象内容）。只有当“定位”与“甄别”的标准保持一致时，Java 的哈希集合才能高效、准确地运行。
HashSet 的扩容机制HashSet 的扩容机制是其保证查询效率和存储容量的核心手段。本质上，它是底层 HashMap 扩容机制的直接映射。当元素数量增加到一定程度，数组的长度会翻倍，并且所有元素的位置会重新计算。
扩容的“扳机”（核心参数）
public class HashMap
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16// 最大容量（最大容量为2的30次方）
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824// 默认负载因子（默认的负载因子为0.75，加载因子 = 哈希表中元素数量 / 容量）
static final float DEFAULT_LOAD_FACTOR = 0.75f;// .........
}
注意：
1、容量必须是2的幂次方，这是 HashMap 设计的重要特点，其目的：使用位运算代替模运算，提供性能使哈希分布更均匀
2、这些常量的选择都是经过性能测试和优化的结果：
初始容量 16：足够小以节省初始内存，又足够大以减少早期扩容最大容量 1073741824：这个限制主要是因为数组在 Java 中最大长度限制，避免内存溢出。考虑到实际使用场景，这个容量已经足够大了负载因子 0.75：0.75 是一个权衡值，在时间和空间成本之间寻求平衡，太大会导致空间浪费，太小又会导致哈希冲突增多，影响性能
3、在实际使用中：
如果知道大概要存储多少元素，可以指定初始容量以减少扩容次数如果内存充足且追求查询性能，可以适当降低加载因子如果内存紧张，可以适当提高加载因子触发判断：HashMap 的 putVal() 方法在 HashMap.putVal 中，当元素插入成功后，会检查是否需要扩容。
// java.util.HashMap final V putVal(int hash, K key, V value, boolean onlyIfAbsent，boolean evict){// ......（省略前面的计算索引和处理链表逻辑）
++modCount;// 插入成功后，size 自增// 【核心扩容判断】// size：当前元素数量// threshold：扩容阈值（容量*负载因子）
if(++size > threshold) resize(); // 触发扩容afterNodeInsertion(evict);return null;}当 HashSet 中的实际元素个数（size）
大于扩容阈值（默认：16 * 0.75 = 12）
时，就会触发扩容。
注意：
判断标准基于元素数量而非数组占用情况。即使数组某个位置存在长链表，只要元素总数未超过扩容阈值（12），通常不会触发扩容。
除非链表长度达到 8 且数组长度未达到 64（size < 64& 链表长度>= 8）时，这通常是因为数组容量太小，导致大量元素挤在同一个桶位（Hash 碰撞严重），而不是因为这些元素本身的 Hash 代码冲突。
这种情况下，会先进行扩容（尝试打散：长链表打散成短链表），把 Hash 取模的范围变大，将原本挤在一起的元素会被重新分配到不同的索引下。如果扩容后，数组大了，链表还是很长，再转红黑树进行处理。这属于另一种特殊情况优化（预防性扩容优化/延迟树化）。
这实际上是一个两段式的防御策略：低水位防御（数组 < 64）
：用扩容解决冲突高水位防御（数组 >= 64）
：用红黑树解决冲突扩容的核心：HashMap 的 resize() 方法这是扩容的灵魂所在。
// java.util.HashMap final Node
// HashMap需要扩容的临界值，通常为容量*加载因子int oldThr = threshold;// 声明新的容量（newCap）和新的阈值（newThr）
int newCap, newThr = 0;// 如果旧数组不为空if (oldCap > 0) {// 如果旧容量已经达到最大值，不再扩容if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab; // 返回旧表格}// 【核心逻辑】：新容量 = 旧容量左移1位 (即乘以2)// (newCap = oldCap << 1) 例如 16 -> 32// 如果计算的新容量没达到最大值且旧容量大于默认初始容量，计算新阈值else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 新阈值也乘以2 newThr = oldThr << 1;}// 当oldThr > 0时，说明HashMap已经被初始化过// 这种情况下，新的容量(newCap)直接设置为旧的阈值(oldThr)// 注释"initial capacity was placed in threshold"表明初始容量被存储在了阈值中else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr;// 初始化时，如果用户没有指定初始容量（即 threshold 为 0）的情况下else {// 设置默认容量和扩容阈值newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 如果新阈值是 0 (比如使用默认构造函数时)，重新计算if (newThr == 0) {// 新的容量：(newCap)乘以加载因子(loadFactor) float ft = (float)newCap * loadFactor;// 使用浮点数ft进行中间计算，避免精度丢失，将计算结果转换为整数赋值给threshold newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr; // 更新全局阈值Node
1、检查旧容量：
获取当前数组的长度oldCap如果当前数组长度已经达到最大限制（2^30），则将阈值设为Integer.MAX_VALUE，不再扩容，直接返回
2、确定新容量：
如果旧容量大于 0 且未达上限，新容量 = 旧容量 << 1（即乘以 2）
例如：16 变为 32，32 变为 64
3、确定新阈值：
新的扩容阈值 = 新容量 × 负载因子（默认 0.75）
例如：新容量 16 × 0.75 = 12。这意味着当存入第 13 个元素时，会再次触发扩容第二阶段：申请新数组 (内存阶段)
1、创建新桶数组：
在内存中创建一个新的Node数组，大小为第一步计算出的newCap
2、暂存：
此时，新数组是空的，旧数组依然存在，里面存着所有数据第三阶段：数据迁移 (核心迁移阶段)这是扩容最耗时的一步，需要遍历旧数组中的每个元素，并将其放入新数组。
1、遍历旧数组：
依次取出每个位置上的数据（可能是 null，可能是单个节点，可能是链表，也可能是红黑树）
2、分类处理：
单个元素：
直接计算新索引，放入新数组
红黑树：
将树拆分为低位树和高位树，如果节点数太少（<=6），会退化回链表
链表：
利用(e.hash & oldCap)判断，如果(e.hash & oldCap) == 0，元素在扩容后，索引不变（仍在j位置）；如果(e.hash & oldCap) != 0,元素在扩容后，移动到j + oldCap位置。这样就将一个长链表拆分成了两个短链表，并保持了原有顺序（尾插法）
第四阶段：引用切换与清理 (收尾阶段)
1、切换引用：
将HashMap内部维护的table属性指向新的数组
2、置空旧数组：
原数组的引用被丢弃，等待 JVM 垃圾回收器（GC）进行回收
简易流程图：
开始
↓
检查元素个数 > 阈值 ?
↓ (是)
计算新容量 (x2) 和新阈值
↓
创建一个更大的新数组 (2倍大小)
↓
遍历旧数组的每个桶位
↓
判断数据类型?
├─ 单个节点 → 直接移到新位置
├─ 红黑树 → 拆树/移树
└─ 链表 → (hash & oldCap) 判断
├─ == 0 → 留在原位
└─ != 0 → 移到 (原位 + 旧容量)
↓
将 table 指向新数组
↓
扩容结束在 JDK 1.7 版本中，扩容时需要重新计算每个元素的索引位置（index = hash & (newCap - 1)），并且采用头插法会导致链表顺序反转。而在 JDK 1.8 版本中，它不需要重新计算 Hash，也不需要通过& (newCap - 1)重新计算索引，只需要判断一个位（ if ((e.hash & oldCap) == 0) ），就能决定元素是留在原地，还是移动到原位置 + 原容量的地方。这极大地提升了扩容效率。
为了防止 Hash 冲突严重导致链表变成“长龙”（查询退化成 O(n)），JDK 1.8 引入了红黑树优化方案：触发条件：链表长度>8且数组容量>64时自动转为红黑树退化机制：元素数量≤6时自动恢复为链表结构，节省存储空间注意：如果数组容量没到 64，只是链表长了（Hash 冲突极多），HashSet 会选择优先扩容数组，而不是转树。因为扩容能打散链表。
2.2 LinkedHashSet LinkedHashSet 是 Java 集合中 Set 接口的一个重要实现类，位于 java.util 包中。它是 HashSet 的子类，在具有哈希表查找效率的同时，结合了链表的结构来维护插入顺序。
public class LinkedHashSet
}一句话概括：LinkedHashSet 是一种有序集合（这是它与 HashSet 的主要区别）。虽然需要维护额外链表来保证顺序导致性能略低于 HashSet，但它在增删操作上依然保持高效。与所有 Set 实现一样，LinkedHashSet 不允许存储重复元素。
继承关系：LinkedHashSet 继承 HashSet数据结构：其底层实现是一个 LinkedHashMap（委托给 LinkedHashMap）
哈希表：负责根据元素的 hashCode 存储数据，保证元素的唯一性和快速查询（O(1)时间复杂度）
双向链表：负责维护元素的插入顺序（或访问顺序），保证遍历时的有序性
底层原理解析：
在 Java 集合框架江湖中，LinkedHashSet 是一个非常奇特的存在。它是 Java 源码设计中 “组合优于继承” 和 “代码复用” 的一个精彩案例。
源码初印象：极简主义如果你去翻阅 JDK 源码，你会发现一个惊人的事实：LinkedHashSet 类的源码极其简短，所有的核心逻辑竟然都在它的父类 HashSet 里。
public class LinkedHashSet整个类只有四个构造函数，所有的构造函数都调用了super(.... , true)，没有任何 add、remove 或 iterator 方法的实现。这意味着它完全复用了父类HashSet的逻辑。
源码核心：HashSet 中的 “后门”
为了支持 LinkedHashSet，HashSet 在源码中预留了一个特殊的构造方法。这个方法通常是 protected 或者 default（包级私有）的，专门供子类或同包下的类使用。
// java.util.HashSet
// 底层存储 Map private transient HashMap
/*** 构造一个新的空的链接哈希集合实例。
* （这个构造函数只给 LinkedHashSet 访问，dummy 没有实际意义）
*/ HashSet(int initialCapacity, float loadFactor, boolean dummy) {// 注意这里：new 的不是 HashMap，而是 LinkedHashMap！
map = new LinkedHashMap<>(initialCapacity, loadFactor);}LinkedHashSet 继承自 HashSet。在构造过程中，它会调用 HashSet 的特殊构造函数HashSet(int initialCapacity, float loadFactor, boolean dummy)。这个构造函数初始化了父类 HashSet 的 map 成员变量，但并非创建普通的 HashMap，而是实例化了一个 LinkedHashMap。因此，LinkedHashSet 本质上仍是 HashSet，只是其内部 map 变量实际指向的是 LinkedHashMap 实例。
LinkedHashSet 如何保证其有序性既然 LinkedHashSet 底层是 LinkedHashMap，那么它的有序性就完全由 LinkedHashMap 决定。
在 HashMap 中，每个节点都是 Node
public class HashMap
}}public class LinkedHashMap这意味着，LinkedHashMap 中的每个节点都同时处在 “两个链表” 中：哈希桶链表（单向）：用于解决 hash 冲突，保证快速查找（复用了 HashMap 中的 next 指针）
双向链表（双向）：用于维护顺序（新增了前驱指针 before 和 后继指针 after）
哈希表数组 双向链表 (维护顺序)
+----------+ +--------<--------+--------->----------+
| Index 0 | -----> | Entry A | Entry B |
+----------+ | (before:null) | (before:A) |
| (after:B) | (after:null) |
+----------+ +----------------+-------------------+
| Index 1 | -----> | Entry C
+----------+ | (before:null) <-- 注意：如果C是最后插入的
| (after:null) 链表指针会重新连接核心成员变量：定义 “有序” 的规则LinkedHashMap 提供了两种有序模式：插入顺序：元素按照添加的先后顺序排列，先插入的元素在前访问顺序（LRU 机制）：最近被访问（get/put）的元素会被移至末尾，实现最近最少使用算法这两种模式通过一个 boolean 类型的标志位进行切换控制。
// java.util.linkedHashMap// 双向链表的头节点// transient关键字表示这个字段不会被序列化transient LinkedHashMap.Entry
// 当为 false 时，按照插入顺序迭代 （默认为 false）
final boolean accessOrder;节点上链既然数据结构变了，那么在插入新节点时，LinkedHashMap 必然要维护这个双向链表。
当 HashMap 调用 put 添加元素时，发现计算出的哈希位置当前没有数据，需要创建一个新节点。此时会调用 LinkedHashMap 重写的 newNode 方法。
// java.util.LinkedHashMap NodeHashMap 在执行 map.put 操作时，首先计算键的哈希值来确定数组下标。LinkedHashMap 则通过重写 newNode 方法，在节点创建过程中生成特殊的 Entry 对象，并调用 linkNodeLast 方法将该 Entry 通过 before 和 after 指针链接到双向链表末尾。无论哈希值如何分布，双向链表始终按照插入顺序进行扩展。
访问顺序与 LRU 实现LinkedHashMap 内部维护了一个双向链表，这个链表的顺序由accessOrder
参数控制：
accessOrder = false (默认)：按照插入顺序排序（FIFO）
accessOrder = true：按照访问顺序排序（LRU）。
这就是 LRU 的开关// java.util.LinkedHashMap public V get(Object key) {// 声明一个 Node 类型的变量 e,用于存储找到的节点Node当 accessOrder 设置为 true 时，每次执行 get(key) 操作（即访问数据），LinkedHashMap 会在内部自动调用 afterNodeAccess 方法，将被访问的节点移至双向链表尾部。
这就好比排队。
插入顺序：
来了一个人，站到队尾，以后不管他怎么说话，位置不动
访问顺序：
来了一个人，站到队尾。一旦这个人和你说了句话（访问了get），他立马插队跑到队尾去队首的永远是最久没有被访问的元素。这就是 LRU（Least Recently Used）缓存淘汰策略的基础！
工作流程图如下：
数据结构示意：
[ 最近最少使用 ] <-----> [ ...中间数据... ] <-----> [ 最近刚使用 ]
(Head) (Tail)
↑ ↑
|--- 当缓存满时，删除 Head（最久未用） |--- 新访问或插入的数据移到这链表头部：存放的是最久未被访问的数据链表尾部：存放的是最近刚被访问的数据淘汰策略：当缓存数量达到预设上限时，删除链表头部的节点
注意：
线程安全：
LinkedHashMap 并非线程安全类，在多线程环境下使用时需进行外部同步控制
性能考虑：
每次访问节点都可能触发链表的调整操作，这在频繁访问时会有一定的性能开销。如果不需要按访问顺序排序，建议将accessOrder设为false，以避免不必要的开销内存占用：LinkedHashMap 在 HashMap 的基础上额外维护了一个双向链表结构，因此会消耗更多的内存空间。迭代器：有序HashMap 的迭代器通过按数组索引顺序（0 到 15）遍历来访问元素，因此其遍历顺序是不确定的。相比之下，LinkedHashMap 通过重写迭代器逻辑，实现了有序遍历。
// java.util.LinkedHashMap abstract class LinkedHashIterator {LinkedHashMap.Entry
next = e.after;return e;}}迭代器无需关注数组的存储位置，只需沿着 after 指针依次访问即可。由于 after 指针已按顺序维护，遍历结果自然保持有序。
LinkedHashMap 通过"双链路"机制，巧妙实现了 O(1) 查询性能与可预测遍历顺序的完美结合。
2.3、TreeSet
TreeSet 是 Java 集合框架中 Set 接口的一个实现类，它位于 java.util 包中。与 HashSet 基于哈希表实现不同，TreeSet 是基于红黑树（Red-Black Tree）数据结构实现的。
核心特点：
有序性：
TreeSet 中的元素会按照自然顺序或者自定义比较器进行排序
唯一性：
作为 Set 的实现，它不包含重复元素
非线程安全：
与大多数集合一样，TreeSet 不是线程安全的。如果需要在多线程环境下使用，必须进行外部同步
注意：
LinkedHashSet 和 TreeSet 虽然都是有序集合，但它们的排序机制存在本质区别。LinkedHashSet 严格维护元素的插入顺序，遍历时会按照 A→B→C 的顺序输出，与元素插入时间完全一致。而 TreeSet 则依据元素的自然排序规则（如字母顺序或数值大小）自动排序（使用自然排序，元素不能类型不能比较 null，否则会抛出 NullPointerException），无论插入顺序如何，遍历结果始终是 A→B→C 这样的有序序列。
代码示例如下：
import java.util.Arrays;import java.util.LinkedHashSet;import java.util.Set;import java.util.TreeSet;// 插入顺序 vs 排序顺序public class OrderDemo {public static void main(String[] args) {String[] letters = {"C", "A", "B", "A"};// LinkedHashSet: 维持插入顺序SetTreeSet 的继承体系
类图结构：
public class TreeSet
}AbstractSet：提供了 Set 接口的骨干实现，减少了实现此接口所需的工作量NavigableSet：扩展了 SortedSet，提供导航方法（如 lower、floor、ceiling、higher 等），允许对集合进行最接近匹配的搜索Cloneable：支持对象克隆Serializable：支持序列化底层原理解析TreeSet 是 Java 集合框架中著名的 “伪装者”。打开 JDK 源码，你会发现 TreeSet.java 只有 300 多行代码，且没有任何核心算法。它的一切行为，都直接委托给了一个内部私有的 NavigableMap 对象，而这个对象运行时通常是 TreeMap 的实例。
核心成员变量public class TreeSet
}m：这是 TreeSet 的核心。NavigableMap 是一个接口，TreeSet 默认使用其实现类 TreeMap。TreeSet 的元素实际是作为这个 NavigableMap 的 Key 存储PRESENT：这是一个静态的 Object 对象，作为所有的 TreeMap 条目的 value。因为 TreeSet 只关心元素本身（即 Key），所以所有的 value 都指向同一个 PRESENT 对象底层数据结构（TreeMap.Entry
// java.util.TreeMap static final class Entry
} Parent 指针：这是一个双向链表结构的体现。不仅知道子节点，还能回溯父节点。这使得 TreeSet 能够轻松实现 lower()（前驱）、higher()（后继）等导航操作。
Color 属性：红黑树通过颜色约束（根黑、叶黑、红不相连、黑高相同）来保证平衡，从而将查询的复杂度控制在 O(log n)。
构造方法TreeSet 提供了多个构造方法，它们主要区别在于如何初始化内部的 m（TreeMap）以及是否提供自定义比较器。
// java.util.TreeSet// 无参构造器，使用自然排序public TreeSet() {this(new TreeMap所有公共构造方法最终都会通过 this(new TreeMap<>(...)) 或 this(m) 来初始化内部的 NavigableMap 对象 m。若未指定 Comparator，TreeMap 将默认采用元素的自然排序（此时元素需实现 Comparable 接口，如果元素类未实现该接口，会抛出ClassCastException）。
核心流程：add 操作的源码级复现要理解add方法，首先需要掌握这些规则——源码中的fixAfterInsertion（插入修复）机制正是为了在规则被破坏后重新修复它们。
红黑树的五大铁律：
节点非黑即红根节点是黑色所有叶子节点（NIL 空节点）是黑色红色节点的两个子节点必须是黑色（即不能有连续的两个红色节点）
从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点add() 方法：排序规则// java.util.TreeSet public boolean add(E e) {// 直接调用底层 TreeMap 的 put 方法// 如果之前不存在该 key，则 put 返回 null，add 返回 true (添加成功)// 如果之前已存在该 key (根据排序规则)，则 put 返回旧 value，add 返回 false (添加失败，元素已存在) return m.put(e,PRESENT) == null;}这是最常用的操作。表面上看是往集合中添加东西，底层实际上是在操作红黑树。
// java.util.TreeMap public V put(K key, V value) {Entry插入新节点（默认红色）后，可能违反了“红色节点不能相连”的规则。JDK 源码通过变色和旋转来修复。
// java.util.TreeMap private void fixAfterInsertion(Entry
rotateLeft(x);}// 叔节点是黑色，且当前节点是左孩子setColor(parentOf(x), BLACK); // 父节点变黑setColor(parentOf(parentOf(x)), RED); // 祖父节点变红rotateRight(parentOf(parentOf(x))); // 右旋（以祖父节点为中心）
}} else {// 父节点是祖父的右孩子，逻辑同上，只是左右互换（镜像情况）
Entry
root.color = BLACK;}当插入新节点导致“双红冲突”（父节点与子节点同为红色）时，遵循以下处理逻辑：
1、叔节点为红——染色上溯
操作：将父节点与叔节点染为黑色，祖父节点染为红色逻辑：相当于将红色冲突“上传”给祖父，将祖父视为新节点继续向上循环判断2、叔节点为黑 + 当前为右子——左旋重定向操作：以父节点为中心进行左旋，将当前节点指向原父节点逻辑：将“内侧”冲突转换为“外侧”，以便统一处理。
3、
叔节点为黑 + 当前为左子——变色换位操作：将父节点染黑，祖父节点染红，以祖父节点为中心进行右旋逻辑：通过变色和旋转，将父节点提升为新的局部根节点，从而彻底解决冲突，终止循环注意：若父节点是祖父的右孩子，上述逻辑中的“左/右”和“内/外”需镜像互换。
具体实现步骤：
1、初始化检查（检查树是否为空，若为空）：
调用 compare 进行类型检查创建新的根节点更新 size 和 modCount返回 null （因为是新插入）
2、查找插入位置：
准备变量：比较结果 cmp、父节点 parent 、比较器 cpr
使用比较器情况：
如果有自定义比较器：
保存当前节点为父节点比较key和当前节点key根据比较结果向左或向右移动（小，往左走；大，往右走）
如果相等，更新值并返回旧值
如果没有自定义比较器：
检查key是否为null将key强制转换为Comparable使用自然排序进行比较同样根据比较结果移动或更新值
3、插入新节点：
创建新的Entry节点根据最后的比较结果决定插入到父节点的左子树还是右子树
4、维护红黑树性质：
调用fixAfterInsertion调整树的结构，保持红黑树的平衡更新size和modCount返回null（表示新插入）
流程图如下：
遍历机制：迭代器的实现TreeSet 的 iterator() 方法返回了一个按顺序排列的迭代器。它是如何做到 “从小到大” 遍历的？
// java.util.TreeSet public Iterator进入 TreeMap 的内部类 KeyIterator 或 NavigableSubMap 的迭代器实现：// java.util.TreeMap final class KeyIterator extends PrivateEntryIterator核心在于 nextEntry()方法。它利用了红黑树的性质：中序遍历。
final Entry
// 如果没有右子树，下一个节点是第一个“祖先”节点，该节点的左子树包含当前节点。
if ((next = successor(e)) == null) next = null;lastReturned = e;return e;}// 寻找后继节点的算法static
Entry
高级特性：NavigableSet 的实现TreeSet 实现了 NavigableSet，这意味着它不仅能排序，还能在有序集合中进行 “搜索” 。
floor(E e) 与 ceiling(E e)这些方法也是基于TreeMap的二叉查找特性实现的。
// java.util.TreeSet public E floor(E e) {return m.floorKey(e);}public K floorKey(K key) {Entry子视图 subMap 的惊人效率public NavigableSet
注意：
返回的TreeSet并不是复制数据！它持有了一个指向原TreeMap的视图对象（通常是TreeMap.AscendingSubMap）。这个视图对象仅仅记录了fromElement和toElement的边界。
当你对这个子集进行遍历时，迭代器会在每次next()时检查是否越界。如果你向子集中添加元素，add方法内部会拦截并检查新元素是否在范围内，如果不在范围直接抛出IllegalArgumentException。
这意味着：
subSet操作是 O(1) 的，极其轻量无论原集合多大，获取子集几乎没有内存开销
3、Queue
在 Java 集合框架的庞大体系中，Queue（队列）是一个非常特殊的且重要的接口。如果说 List 是为了存储和索引，Set 是为了去重，那么 Queue 的存在就是为了处理数据。
Queue 通常用于模拟 “先进先出（FIFO）” 的数据结构，但在 Java 语境下，它的含义远不止如此。它涵盖了一系列以有序处理为核心的集合。
Queue 继承自 Collection 接口，主要用于在处理之前保存元素。除了标准的集合操作外，Queue 提供了三组特定的操作方式，这是其最显著的特征：
插入：
向队列尾部添加元素
移除：
移除并返回队列头部元素
检查：
返回队列头部元素但不移除为了应对不同的业务场景（特别是容量受限的场景），Queue 为每种操作都定义了两种方法：操作抛出异常返回特殊值说明插入add(E e) offer(E e)队列满时，add 抛出IllegalStateException异常，offer 返回 false移除remove() poll()队列空时，remove 抛出 NoSuchElementException，poll 返回 null检查element() peek()队列空时，element 抛出 NoSuchElementException，peek 返回 null 3.1 Deque 双端队列（Java 官方推荐的 栈 的替代者）
Deque 是 “ Double Ended Queue” 的缩写，读音通常为 “Deck”。它继承自 Queue 接口，定义了一个支持在两端进行元素插入和移除的线性集合。
这意味着：
它可以作为 FIFO 队列 使用（一端进，另一端出）
它可以作为 LIFO 栈 使用（同一端进，同一端出）
它可以作为 双端队列 使用（两端都可以进出）
Deque 的核心在于 “双端”，打破了传统 Queue 只能队尾进、对头出的限制。
3.2 ArrayDeque （Java 中实现栈和队列的首选类）
在 Java 集合框架的工具箱中，ArrayDeque 是一把锋利、高效且专精的单刃刀。它不是最老资格的（Vector 和 Stack 比它老），也不是功能最全的（LinkedList 实现了 List 接口），但它是在线性数据操作（栈、队列、双端队列）场景下的性能王者。
ArrayDeque （全称 "Array Double Ended Queue（数组双端队列）"）是 Deque 接口的一种可变数组实现。
核心特性：
双端：可以在头部或尾部高效地插入或删除元素非线程安全：没有 synchronized 修饰，适用于单线程环境禁止 null：不允许插入 null 元素（为了区分空队列和 null 值）
为什么 ArrayDeque 这么快？
ArrayDeque 之所以被称为 Java 集合框架中的 “性能王者”，并非由单一因素决定，而是数据结构、算法设计、内存管理和硬件优化四个方面共同作用的结果。
数据结构层面：循环数组 vs 链表节点这是 ArrayDeque 和 LinkedList (常见的双端队列替代品) 最根本的区别
指针开销的消除：
LinkedList：每存储一个元素，都需要创建一个 Node 对象，内部包含 prev（前驱指针）、next（后继指针）、item（节点数据）三个引用。在 64 位 JVM 中，仅对线头和引用就要占用几十个字节，内存开销是数据本身的好几倍ArrayDeque：底层是纯粹的对象数组 Object[]。数据直接存储，没有额外的包装对象。这意味着同样的内存空间，可以存储更多的数据，减少 GC（垃圾回收）扫描和回收的压力物理内存连续性（CPU 缓存友好）：LinkedList：节点在堆内存中是离散分布的。CPU 读完节点 A，去读节点 B 时，很可能发生缓存未命中，必须重新从较慢的主存中读取数据ArrayDeque：数组在内存中是连续分配的。CPU 在读取 element[0] 时，会智能地将 element[1] 至 element[n] 一并加载到 L1/L2 缓存行中。当遍历或连续操作时，CPU 命中缓存的概率极高，几乎不需要等待主存算法设计层面：位运算 vs 取模这是 ArrayDeque 比普通数组队列快的原因
位运算替代取模：
普通队列：实现循环逻辑通常使用取模运算 index = (index + 1) % length。取模运算在 CPU层面涉及除法指令，这是一条昂贵的指令，周期很长。
ArrayDeque：强制要求数组长度为 2 的幂次方。它使用位运算 index = (index + 1) & (length - 1)。& 运算是 CPU 最基础的原位操作，只需要一个时钟周期，速度比取模快几十倍O(1) 的双端操作：不同于 ArrayList 在头部插入需要移动 System.arraycopy 所有元素，ArrayDeque 的 addFirst 和 addLast 仅仅是修改 head 或 tail 指针的值。没有拷贝数据，时间复杂度稳定为 O(1)并发策略层面：无锁设计 vs 同步锁这是 ArrayDeque 比古老的 Stack 或 Vector 快的原因去除 synchronized：Stack / Vector：为了保证线程安全，所有公共方法都添加了 synchronized 。这意味着即使是单线程操作，也需要获取锁。加锁、释放锁、挂起线程（在竞争时）都会带来巨大的性能消耗ArrayDeque：完全非线程安全。它假设你在单线程环境下使用，或由外部自己控制并发。因此，它甩掉了所有同步锁的包袱，飞快运行内存操作层面：预分配 vs 动态分配
扩容策略优化：
ArrayDeque 默认初始容量为 16，每次扩容为原来的 2 倍。这种指数级扩容策略分摊了扩容的时间复杂度，使得 add 操作的平均时间复杂度依然为 O(1)虽然扩容时也需要 Arrays.copyOf，但由于它是基于数组的，批量内存复制（利用 CPU 的 SIMD 指令集）效率非常高，远高于链表逐个节点的分配和链接底层原理解析ArrayDeque 是 Java 集合框架中务实的代表。它没有花哨的功能，专注于把 “双端操作” 做到极致。
核心源码结构：精简的基石public class ArrayDeque
transient int tail;// 最小初始容量private static final int MIN_INITIAL_CAPACITY = 8;}elements.length：数组长度始终保持为 2 的幂次方（8，16，32........）。这是 ArrayDeque 高效的基石。
Head 与 Tail：这是两个游标head：指向双端队列头部元素的索引tail：指向双端队列尾部下一个可以插入元素的索引位置如果队列为空，head 的值等于 tail核心操作源码解析
1、添加元素
// java.util.ArrayDeque// 对头入队public void addFirst(E e){// 安全检查: ArrayDeque 不允许 null if (e == null) throw new NullPointerException();// 元素入队，head 指针向前移动一位elements[head = (head - 1) & (elements.length - 1)] = e;// 在插入元素后，检查 head 是否追上了 tail// 在 ArrayDeque 中，数组中始终至少留一个空位// 当 head == tail 时，说明数组已经满了，没有空位了if (head == tail) doubleCapacity();}// 队尾入队public void addLast(E e){// 安全检查: ArrayDeque 不允许 null if (e == null) throw new NullPointerException();// 元素入队，放在 tail 指向的位置elements[tail] = e;// tail 指针后移并判断是否需要扩容// (tail + 1) & (elements.length - 1) 等同于 (tail + 1) % length// 如果移动后的 tail 撞上了 head，说明数组已经满了if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity();}
2、删除元素
// java.util.ArrayDeque// 删除队列头部元素public E removeFirst() {// 调用 pollFirst() 方法尝试获取并移除队列头部的元素，并将结果赋值给变量 x E x = pollFirst();// 如果 pollFirst() 返回 null（意味着队列为空），则抛出一个 NoSuchElementException 异常if(x == null) throw new NoSuchElementException();// （队列不为空）返回获取到的元素 x return x;}public E pollFirst() {// 将当前队列头部的索引 head 赋值给局部变量 h int h = head;// @SuppressWarnings("unchecked") 用于抑制编译器的“未检查类型转换”警告// elements 数组是 Object[] 类型，将其中的元素强制转换为泛型 E 类型时，编译器会发出警告// 这里开发人员确认这种转换是安全的，因此忽略警告@SuppressWarnings("unchecked")// 取出数组中索引为 h 的元素，并强制转换为泛型 E 类型，赋值给 result E result = (E) elements[h];// 判断取出的元素是否为 null if (result == null) return null;// 将原头部位置的数组元素显式设为 null// 手动置为 null，防止内存泄漏// 在 Java 中，只要一个对象被引用，垃圾回收器（GC）就不会回收它// 虽然我们即将把 head 指针移走，但数组中该位置仍然引用着旧的对象// 如不手动置为 null，这个对象可能一直占用内存直到数组被覆盖或回收elements[h] = null;// 计算新的头部索引head = (h + 1) & (elements.length - 1);// 返回之前取出的元素return result;}// 删除队列尾部元素public E removeLast() {// 调用 pollLast() 方法尝试获取并移除队列尾部的元素，并将结果赋值给变量 x E x = pollLast();// 如果 pollLast() 返回 null（意味着队列为空），则抛出一个 NoSuchElementException 异常if(x == null) throw new NoSuchElementException();// （队列不为空）返回获取到的元素 x return x;}public E pollLast() {// 计算队尾元素索引// tail 指向下一个可用元素的位置（即当前队尾元素的下一位）
// 实际的最后一个元素索引是 tail - 1 int t = (tail - 1) & (elements.length - 1);@SuppressWarnings("unchecked")// 取出数组中索引为 t 的元素，并强制转换为泛型 E 类型，赋值给 result E result = (E) elements[t];// 判断取出的元素是否为 null if (result == null) return null;// 显式置空，帮助 GC elements[t] = null;// 将队尾指针 tail 移动到刚才取出元素的位置tail = t;// 返回取出的元素return result;}扩容机制：doubleCapacity当 head == tail 时，数组已满，需要进行 2 倍扩容。这个方法非常巧妙，它不仅扩大了容量，还重排了数据。
// java.util.ArrayDeque private void doubleCapacity() {// 断言 head 等于 tail// 在循环数组中，当队列满时，head 和 tail 会指向同一个位置// （即下一个要插入的位置会被覆盖，或者表示没有空间）
// 这个断言确保该方法只在队列满时被调用assert head == tail;// 保存当前队首的索引位置到变量 p int p = head;// 获取旧数组的长度 n int n = elements.length;// 计算从 head (即 p) 到数组末尾的元素个数int r = n - p;// 计算新容量，n 左移 1 位相当于 n * 2 int newCapacity = n << 1;// 检查新容量是否溢出// 如果 n 已经非常大（接近 Integer.MAX_VALUE），n * 2 会变成负数（整数溢出）
// 此时队列已经无法继续扩容，抛出异常if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big");// 创建一个容量为 newCapacity 的新数组 a Object[] a = new Object[newCapacity];// 复制 head 到数组末尾的部分 到 新数组的开头System.arraycopy(elements, p, a, 0, r);// 复制 数组开头 到 tail 的部分 到 新数组的后面System.arraycopy(elements, 0, a, r, p);// 将队列内部的数组引用指向新数组 a elements = a;// 重置队首 head 为新数组的 0 索引head = 0;// 重置队尾 tail 为旧数组的长度 n tail = n;}ArrayDeque 的数据在循环数组中可能跨越了数组末尾（一部分在头，一部分在尾）。扩容时，它通过两次 System.arraycopy 将这两部分数据“拼”在一起，在新数组中变成了连续数据。
这种重排保证了后续操作的内存连续性，进一步提高缓存命中率。
图解扩容过程：
假设 ArrayDeque 的底层数组 elements 的初始容量为 8（索引 0 ~7）。
1.扩容前的状态（队列已满）
此时，队列中已经存入了 8 个元素，数组已满，无法再插入新元素head 指向索引 4（队首元素是 A）
tail 指向索引 4（下一个要插入的位置）
注意：因为数组是循环使用的，元素被分成了两部分：右半部分：从 head（4）到数组末尾（7），存放了元素 A、B、C、D左半部分：从 数组开头（0）到 head（4）之前，存放了元素 E、F、G、H
数组视图：
索引: 0 1 2 3 4 5 6 7
数据: [E] [F] [G] [H] [A] [B] [C] [D]2、执行 doubleCapacity() 的过程// java.util.ArrayDeque( doubleCapacity() ) int p = head; // p = 4 int n = elements.length; // n = 8 int r = n - p; // r = 8 - 4 = 4 (head右边有4个元素) int newCapacity = n << 1; // newCapacity = 16 Object[] a = new Object[newCapacity]; // 创建新数组，长度 16// 步骤 1: 复制右半部分 [A, B, C, D] 到新数组开头System.arraycopy(elements, p, a, 0, r);// 步骤 2: 复制左半部分 [E, F, G, H] 到新数组后面System.arraycopy(elements, 0, a, r, p);elements = a; // 引用指向新数组head = 0; // 重置 head tail = n; // 重置 tail = 8步骤1：复制右半部分将旧数组中从 head（索引 4）开始的 r（4个）元素复制到新数组的索引 0 处
旧数组：
索引: 0 1 2 3 4 5 6 7
数据: [E] [F] [G] [H] [A] [B] [C] [D]
|--- 这4个 ---|
新数组（复制右半部分后）：
索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
数据: [A] [B] [C] [D] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
|--- 这4个 ---|步骤2：复制左半部分将旧数组中从索引 0 开始的 p（4个）元素复制到新数组的索引 r (4) 处
旧数组：
索引: 0 1 2 3 4 5 6 7
数据: [E] [F] [G] [H] [A] [B] [C] [D]
|--- 这4个 ---|
新数组（复制左半部分后）：
索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
数据: [A] [B] [C] [D] [E] [F] [G] [H] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
|--- 这4个 ---|
3、扩容后的状态
复制完成后，更新指针：
head 设为 0 tail 设为旧数组长度 8
最终新数组视图：
索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
数据: [A] [B] [C] [D] [E] [F] [G] [H] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
^ ^
head=0 tail=8
通过这个过程，可以看到：
逻辑连续，物理分离的数据（A,B,C,D 和 E,F,G,H）被重新拼接成物理连续的数据（A,B,C,D,E,F,G,H）
head 回到了数组的起点，这简化了后续的索引计算tail 指向了最后一个元素的下一个位置（8），正好是旧数组的长度，为新元素的插入留出了空间3.3 PriorityQueue（打破先来后到的“特权队列”）
在 Java 集合框架中，如果说 LinkedList 和 ArrayDeque 遵循的是严格的 “先来后到”（FIFO，先进先出）原则，那么 PriorityQueue 就是一个彻底的 “打破规则者”。
它不关心你是什么时候排队的，它只关心你的优先级。
PriorityQueue（优先级队列）是 Java 中基于优先级堆（Priority Heap）实现的无界优先级队列。
核心特性：
无界：理论上可以无限扩容（直到内存溢出），初始容量默认为 11无序：当你遍历 PriorityQueue 时，元素不一定是有序的有序的出队：每次调用 pop() 或 remove() 时，它保证取出的都是当前队列中优先级最高（最小或最大）的元素不支持 null：不允许插入 null 值
注意：
PriorityQueue 具有"内部无序但出队有序"的特性，这一特点容易让人产生混淆。要准确理解这一机制，关键在于区分"内存中的实际存储结构"和"逻辑上的优先级关系"。
简而言之：PriorityQueue 就像一个杂乱无章的房间，但配备了精准的导航雷达。
它是堆，不是有序数组很多人的直觉认为，优先级队列应该排列似 [1,2,3,4,5] 这样整齐的数组。但 PriorityQueue 底层维护的是二叉堆。
堆的核心规则只有一条：
小顶堆：父节点的值不大于其子节点的规则仅限于父子之间，不涉及兄弟节点这导致了只需确保父节点不小于子节点即可，而对左右子节点的大小关系，或是同一层级最后一个节点与下一层级首个节点的相对大小并无具体要求。
图解存储过程：
假设我们依次插入数字：5,3,1,4,2。
如果是有序数组，它们在内存中是这样的：[ 1,2,3,4,5 ]（非常整齐）
但在 PriorityQueue（二叉堆）中，它们的逻辑结构（树状）是这样的：1 <-- 堆顶 (最小)
/ \
3 2
/ \
5 4对应到底层数组 Object[] queue 的存储顺序是：索引：[0] [1] [2] [3] [4]数值：[ 1, 3, 2, 5, 4]这个数组的顺序是错乱的！3排在2前面，5又排在4前面，完全没有按照顺序排列。如果你直接遍历数组（比如用for(int i : pq)），得到的结果会是1、3、2、5、4，这就是典型的"内部无序"现象。
出队操作：有序虽然数组里的元素乱七八槽，但堆顶（索引为 0 的位置）永远是所有元素中最小的那个。
调用poll
方法时的执行逻辑如下：
移除堆顶元素：直接取出数组首元素queue[0]（当前最小值）
填补空缺：将数组末尾元素移动到堆顶位置下沉调整：若当前父节点（堆顶）值大于子节点，则进行下沉操作父节点与较小的子节点交换位置若交换后仍不满足堆性质，则继续下沉直至堆底形成新堆：经过调整后，原第二小的元素会升至堆顶位置
图解过程：
第一次 poll 前：1
/ \
3 2
/ \
5 4输出：1调整后（poll 后）：2 <-- 新的王者 (第二小)
/ \
4 3
/
5数组变成了：[2, 4, 3, 5, .....] （依然是乱序的，但堆顶变了）
第二次 poll()，你会得到 2。
第三次 poll()，你会得到 3。
结论：尽管数组内部元素始终是无序排列的，但每次调用 poll() 方法都能准确获取当前最小值。通过连续调用该方法，最终就能得到一个有序的输出序列。
import java.util.PriorityQueue;public class priorityQueueDemo {public static void main(String[] args) {PriorityQueue为什么这样设计？
你可能会疑惑："既然有序数组也能实现快速遍历和出队，为什么不直接采用这种存储方式呢？"这就涉及到了时间复杂度的权衡：操作PriorityQueue有序数组差距插入（add）
O(log n) O(n)堆完胜删除堆顶（poll）
O(log n) O(n)堆完胜获取最小值O(1) O(1)平手
原因：
有序数组：每次插入一个新元素，都要把后面比它大的元素全部往后挪一格（System.arraycopy），非常慢PriorityQueue（堆）：插入操作只需将新元素置于末尾，然后像冒泡排序那样逐层上浮（最多 log n 次），无需移动其他元素底层原理解析PriorityQueue 是 Java 集合框架中的特殊实现。与 ArrayList 的线性存储方式和 HashMap 的哈希结构不同，它采用二叉堆算法实现，能够在 O(log n) 时间复杂度内高效获取极值（最大值或最小值）。
核心源码结构：简而精// java.util public class PriorityQueue
transient int modCount = 0;}尽管名为 Queue（队列），但其底层实现采用了 Object[] queue 数组结构。通过巧妙运用数组索引关系，该结构完美模拟了完全二叉树的特性。
具体实现细节如下：
数组索引从0开始，通过数学关系构建树形结构：对于任意节点 i（0 ≤ i < size）：其左子节点索引为 2 * i + 1其右子节点索引为 2 * i + 2其父节点索引为 (i - 1) >>> 1（无符号右移，等同于除以 2）
这种数组实现方式具有以下优势：内存连续，访问效率高不需要额外的指针存储空间完全二叉树的性质保证了O(log n)的时间复杂度入队：offer(e) 与 “上浮”算法PriorityQueue 的 add 方法实际上是调用了 offer 方法。其核心入队逻辑分为两步：首先将新元素添加到队列末尾，然后通过"上浮"操作将其调整到合适的位置。
// java.util.PriorityQueue public boolean add(E e) {return offer(e);}public boolean offer(E e) {// 非空检查// PriorityQueue 不允许插入 null 元素，如果插入 null 抛出异常if(e == null) throw new NullPointerException();// 修改计数器更新modCount++;// 获取当前队列的大小 i int i = size;// 如果当前元素数量 i 已经大于或等于底层数组 queue 的长度，说明数组已满if (i >= queue.length)// 调用 grow(i + 1) 方法进行扩容，以确保能容纳新元素grow(i + 1);// 更新队列大小 i size = i + 1;// 如果插入前队列是空的（i == 0），直接将元素放在数组的第一个位置 queue[0]if (i == 0) queue[0] = e;// 如果队列不为空，调用 siftUp(i, e) 方法，执行上浮调整else siftUp(i, e);return true;}核心算法：siftUp这是维护小顶堆性质的核心操作。具体实现时，先将新元素 e 插入数组末尾（位置 i），然后将其与父节点进行比较。若发现新元素小于父节点（符合小顶堆特性），则交换两者位置。该过程循环执行，直至新元素到达堆顶或不再小于其父节点时终止。
// java.util.PriorityQueue private void siftUp(int k,E x) {if (comparator != null) siftUpUsingComparator(k, x);else siftUpComparable(k, x);}private void siftUpUsingComparator(int k,E x) {// 循环条件：while (k > 0)// 只要当前节点索引 k 不是根节点（根节点索引为 0），就继续尝试上浮while (k > 0) {// 计算当前节点的父节点索引int parent = (k - 1) >>> 1;// 取出父节点存储的元素Object e = queue[parent];// 使用比较器比较当前待插入元素 x 和父节点元素 e// 如果 x 大于或等于 e，则 break 跳出循环。此时位置 k 就是 x 的最终归宿if (comparator.compare(x, (E) e) >= 0) break;// 如果 x 小于 e，说明违反了堆序性质（子节点比父节点小），需要交换位置。
queue[k] = e;// 更新当前索引 k 为父节点的索引，准备继续向上层比较k = parent;}// 循环结束后（要么找到了合适的位置，要么到了根节点），将目标元素 key 放入最终确定的位置 k queue[k] = x;}private void siftUpComparable(int k,E x) {// 将传入的元素 x 强制转换为 Comparable 类型// PriorityQueue 需要比较元素的大小来确定优先级Comparable key = (Comparable) x;// 开始循环。只要当前节点索引 k 大于 0（即当前节点不是根节点），就继续尝试上浮while (k > 0) {// 计算当前节点的父节点索引int parent = (k - 1) >>> 1;// 取出父节点存储的元素Object e = queue[parent];// 比较当前插入元素 key 和父节点元素 e 的大小// 如果 key >= e// 说明堆的性质已经满足（父节点小于等于子节点），无需继续交换，直接 break 跳出循环if (key.compareTo((E) e) >= 0) break;// 如果 key < e，说明子节点比父节点小，违反了最小堆性质// 则将父节点 e 向下移动到当前子节点 k 的位置queue[k] = e;// 更新当前索引 k 为父节点的索引，准备继续向上层比较k = parent;}// 循环结束后（要么找到了合适的位置，要么到了根节点），将目标元素 key 放入最终确定的位置 k queue[k] = key;}入队操作流程：将新元素添加至数组末尾，随后进行上浮调整。循环比较该元素与其父节点，若优先级更高则交换位置，直至到达堆顶或满足堆条件为止。
出队：poll() 与 下沉算法poll()操作需要移除堆顶的最小值元素。移除后，我们将数组末尾的元素移至堆顶位置，然后通过"下沉"操作使其重新找到合适的位置，以维持堆结构的完整性。
// java.util.PriorityQueue public E poll() {// 检查队列是否为空if (size == 0) return null; // 如果为空，返回 null（区别于 remove() 方法抛出异常）
// 记录操作前的元素个数，并将 size 减 1// s 变成了原数组最后一个元素的下标int s = --size;// 更新修改计数器modCount++;// 获取堆顶元素（即最小值），作为最终要返回的结果E result = (E) queue[0];// 获取队列末尾的元素E x = (E) queue[s];// 将原末尾位置置为 null，帮助 GC 回收，避免内存泄漏queue[s] = null;// 如果队列中不止一个元素，则需要执行下沉操作// 将刚才取出的末尾元素 x 放到堆顶位置（下标 0），并开始下沉if (s != 0) siftDown(0, x);// 返回之前获取的最小值return result;}核心算法：siftDown将堆末尾的大元素移至堆顶后，由于它必然大于子节点，需要通过下沉操作进行调整。具体下沉规则是：父节点需要与左右孩子中较小者进行交换。
// java.util.PriorityQueue private void siftDown(int k, E x) {if (comparator != null) siftDownUsingComparator(k, x);else siftDownComparable(k, x);}private void siftDownUsingComparator(int k, E x) {// 计算非叶子节点边界int half = size >>> 1; // 无符号右移（等同于 size / 2）
while (k < half) {// 计算当前节点 k 的左孩子的索引int child = (k << 1) + 1;// 获取左孩子元素Object c = queue[child];// 计算右孩子的索引int right = child + 1;// 如果右孩子存在，且右孩子比左孩子小if (right < size &&comparator.compare((E) c, (E) queue[right]) > 0) c = queue[child = right]; // 更新 child 指向右孩子// 如果当前元素 x 已经小于等于较小的孩子，说明下沉结束if (comparator.compare(x, (E) c) <= 0) break;// 否则，交换位置（孩子上浮成为父节点）
queue[k] = c;k = child;}// 将末尾元素放到最终的位置queue[k] = x;}private void siftDownComparable(int k, E x) {// 将待下沉的元素 x 强制转换为 Comparable 接口类型// 因为需要调用 compareTo 方法来比较元素大小Comparable key = (Comparable)x;// 计算非叶子节点边界int half = size >>> 1; // 无符号右移（等同于 size / 2）
while (k < half) {// 计算当前节点 k 的左孩子的索引int child = (k << 1) + 1;// 获取左孩子元素Object c = queue[child];// 计算右孩子的索引int right = child + 1;// 比较左右孩子// right // c.compareTo(queue[right])>0：如果左孩子比右孩子大（compareTo 返回正数）说明右孩子更小if (right < size &&((Comparable) c).compareTo((E) queue[right]) > 0)// 满足条件，将 c 指向右孩子，并将 child 更新为右孩子的索引c = queue[child = right];// 如果 key 小于等于 c（compareTo 返回 0 或负数），说明堆的顺序已经正确（父节点小于子节点） if (key.compareTo((E) c) <= 0)// 跳出循环，下沉结束break;// 如果 key 大于 c，说明堆性质被破坏。将较小的子节点 c 移动到当前父节点 k 的位置queue[k] = c;// 更新 k 为子节点的位置，准备进行下一轮比较k = child;}// 循环结束后，将原始元素 key 放到最终确定的位置 k 上queue[k] = key;}出队操作：移除堆顶的最小值元素后，将数组末尾元素移至堆顶。随后将该元素与其左右子节点中较小者进行比较，若当前元素较大则交换位置（下沉操作）。重复此过程直至堆恢复平衡状态。 扩容机制：grow PriorityQueue 的扩容策略很有意思，不是简单的 2 倍扩容，而是根据当前容量阶段性的增长。 // 如果之前的计算（例如 minCapacity = oldCapacity + (oldCapacity >> 1)）导致数值超过了 int 的最大值// 由于整数溢出，结果会变成负数if (minCapacity < 0) throw new OutOfMemoryError();// 如果 minCapacity 大于 MAX_ARRAY_SIZE，则直接返回 Integer.MAX_VALUE（即 2147483647）尝试分配理论上的最大数组长度// 如果 minCapacity 小于或等于 MAX_ARRAY_SIZE，则返回 MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8（即 2147483639）） return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}PriorityQueue 是非线程安全的类，其 grow 方法未实现同步机制。在多线程并发添加元素触发扩容时，可能导致数据不一致或数组越界问题。建议在多线程场景下使用线程安全的 PriorityBlockingQueue 替代。 到此这篇关于Java集合框架的 Collection 分支的文章就介绍到这了,更多相关Java集合框架Collection 内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！ 您可能感兴趣的文章:Java单列集合Collection常用方法示例详解java Collection集合接口的介绍和使用详解关于Java集合框架Collection接口详解Java Map集合与Collection类的使用详解java集合collection接口与子接口及实现类Java 详解Collection集合之ArrayList和HashSet java9新特性Collection集合类的增强与优化方法示例Java集合的Collection接口和List接口详解java集合Collection实现类解析ArrayList LinkedList及Vector// java.util.PriorityQueue private void grow(int minCapacity) {// 获取当前底层数组 queue 的长度int oldCapacity = queue.length;// 如果旧容量小于 64，则扩容 2 倍 + 2// 如果旧容量大于 64，则扩容 1.5 倍 (即 oldCapacity + (oldCapacity >> 1)) int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :(oldCapacity >> 1));// 防止溢出，如果计算出的容量过大if (newCapacity - MAX_ARRAY_SIZE > 0)// 调用 hugeCapacity 方法尝试分配newCapacity = hugeCapacity(minCapacity);// 调用 Arrays.copyOf 方法，将原数组中的数据复制到一个长度为 newCapacity 的新数组中，并将 queue 引用指向这个新数组queue = Arrays.copyOf(queue, newCapacity);}private static int hugeCapacity(int minCapacity) {// 溢出检查：通过检查 minCapacity 是否小于 0，来判断是否发生了整数溢出// 在 Java 中，int 是有符号的 32 位整数，最大值为 Integer.MAX_VALUE（约 21 亿）