Java集合常见知识点总结(上)

JavaJuice约 18321 字大约 61 分钟

一、集合概述

Java 集合的含义

在 Java 中，集合（Collection） 是一种用于存储和操作数据的框架。它是 Java 标准库的一部分，定义了用于存储和操作对象的类和接口的集合。集合提供了很多方法，使得数据的存储、访问、插入、删除等操作变得更加简便和高效。

Java 集合分为两大类：

Collection 接口：这是 Java 集合框架的根接口，定义了集合的基本操作方法，如添加、删除、查询等。它主要包括三种类型的集合：List、Set 和 Queue。
Map 接口：它不是 Collection 的子接口，但也是 Java 集合框架的一部分，主要用于存储键值对（key-value）。

Java 集合框架的组成

Java 集合框架主要由以下几个接口和实现类组成：

1. Collection 接口

Collection 是所有集合类的根接口，定义了集合的基本操作。Collection 接口主要有以下子接口：

List：有序集合，允许元素重复。常见实现类有 ArrayList、LinkedList、Vector 等。
Set：不允许元素重复的集合。常见实现类有 HashSet、LinkedHashSet、TreeSet 等。
Queue：队列接口，适用于先进先出的顺序。常见实现类有 LinkedList、PriorityQueue 等。

2. Map 接口

Map 是用于存储键值对的集合，它不继承自 Collection 接口，常见实现类有：

HashMap：基于哈希表的实现，不保证顺序。
TreeMap：基于红黑树的实现，按键的自然顺序或自定义顺序进行排序。
LinkedHashMap：按插入顺序维护键值对的顺序。

集合与数组的区别

大小：数组的大小是固定的，而集合的大小是可变的。
类型：数组只能存储同一类型的元素，而集合可以存储不同类型的对象（通过泛型机制）。
功能：集合提供了丰富的操作方法，比如自动扩容、排序、查找、删除等，而数组操作相对简单。

常见集合实现类及其特点

1. List 接口的实现类

ArrayList：基于动态数组实现，查询效率较高，插入和删除效率较低。
LinkedList：基于双向链表实现，插入和删除操作较高效，查询效率较低。

2. Set 接口的实现类

HashSet：基于哈希表实现，不保证元素的顺序。元素是唯一的。
TreeSet：基于红黑树实现，元素是唯一的，并且按自然顺序排序。
LinkedHashSet：基于哈希表和链表实现，保证插入顺序。

3. Queue 接口的实现类

PriorityQueue：基于优先队列实现，按优先级顺序来处理元素。
LinkedList：既实现了 List 接口，也实现了 Queue 接口，既可以作为链表使用，也可以作为队列使用。

4. Map 接口的实现类

HashMap：基于哈希表实现，提供键值对映射，不保证顺序。
TreeMap：基于红黑树实现，键是有序的。
LinkedHashMap：保持插入顺序或访问顺序。

集合的特点是什么？

动态性：集合类的大小是动态可变的，可以根据需要自动增长。
泛型支持：Java 集合类通常是泛型的，可以确保类型安全，在编译时检查类型。
提供丰富的操作：集合框架提供了大量的方法来进行增、删、改、查等操作，使得处理数据变得非常方便。

常见集合的操作有哪些？

添加元素：add()、addAll() 等。
删除元素：remove()、removeAll() 等。
查找元素：contains()、containsAll() 等。
获取元素：get()、iterator() 等。
排序：sort()、Collections.sort() 等。

总结

Java 集合是一个非常强大的工具，它为开发者提供了一组高度灵活和高效的数据结构和算法。通过集合框架，开发者可以轻松地管理和操作各种数据，从而大大提高程序的开发效率。

List, Set, Queue, Map 四者的区别是什么？

List

特点：有序集合，允许重复元素。
元素顺序：存储的元素按插入顺序排列。
访问方式：可以通过索引访问元素。
常见实现：ArrayList、LinkedList、Vector。

Set

特点：无序集合，不允许重复元素。
元素顺序：不保证元素的顺序（HashSet），但 LinkedHashSet 保证插入顺序，TreeSet 按自然顺序或自定义顺序排序。
访问方式：不允许通过索引访问元素。
常见实现：HashSet、LinkedHashSet、TreeSet。

Queue

特点：通常用于存储待处理的元素，遵循特定的顺序（如先进先出 FIFO）。
元素顺序：有序，遵循队列操作规则（FIFO）。
常见实现：LinkedList、PriorityQueue、ArrayDeque。

Map

特点：存储键值对（key-value），每个键最多映射到一个值。
元素顺序：键值对的顺序由实现决定（HashMap 不保证顺序，LinkedHashMap 保证插入顺序，TreeMap 按键的自然顺序或自定义顺序排序）。
访问方式：通过键（key）访问对应的值（value）。
常见实现：HashMap、LinkedHashMap、TreeMap。

总结

List：有序、可重复的元素集合。
Set：无序、不重复的元素集合。
Queue：有序、可重复的元素集合，遵循队列的先进先出（FIFO）规则。
Map：存储键值对（key-value），键唯一，值可重复。

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

List

ArrayList：底层是 Object[] 数组。动态扩容，元素顺序存储，支持按索引访问。
Vector：底层是 Object[] 数组。与 ArrayList 类似，但 Vector 是线程安全的，扩容时比 ArrayList 更为昂贵。
LinkedList：底层是双向链表（JDK 1.7 之后不再是循环链表）。支持快速插入和删除操作，访问速度较慢。

Set

HashSet：底层是 HashMap，采用哈希表实现。元素无序且不允许重复。
LinkedHashSet：底层是 LinkedHashMap。保持元素的插入顺序，比 HashSet 多了一个双向链表。
TreeSet：底层是红黑树（自平衡排序二叉树）。元素有序且不重复，支持按顺序访问。

Queue

PriorityQueue：底层是 Object[] 数组，采用小顶堆实现。优先队列，根据优先级顺序处理元素。
DelayQueue：底层是 PriorityQueue。专用于处理定时或延时元素，只有在元素满足条件时才能被提取。
ArrayDeque：底层是可扩容的动态双向数组，提供栈和队列的功能。性能较好，适合用作栈和队列。

Map

HashMap：底层是数组和链表（JDK 1.8 之后加入了红黑树）。使用哈希表来存储键值对，解决哈希冲突通过链表（拉链法）。当链表长度大于 8 时，转化为红黑树以提高查找效率。
LinkedHashMap：底层是 LinkedHashMap。继承自 HashMap，增加了双向链表来保持元素的插入顺序。
Hashtable：底层是数组和链表。与 HashMap 类似，但 Hashtable 是线程安全的，不推荐使用。
TreeMap：底层是红黑树（自平衡排序二叉树）。元素根据键的自然顺序或提供的 Comparator 排序，支持按顺序访问。

总结

List：基于数组或链表，允许重复元素，按插入顺序存储。
Set：基于哈希表或红黑树，不允许重复元素。
Queue：基于堆、链表或双端队列，支持排队、延时和优先级处理。
Map：基于数组、链表或红黑树，存储键值对，键唯一，值可重复。

如何选用集合？

选择合适的集合类型主要取决于需求中的几个关键因素，比如访问方式、元素是否唯一、是否需要排序、是否需要线程安全等。以下是常见的选用原则：

根据键值获取元素时

选用 Map 接口下的集合：
- 如果需要根据键（key）快速查找对应的值（value），则使用 Map。
- 排序需求：
  - 如果需要键的有序排列，选择 TreeMap。
  - 如果不需要排序，可以选择 HashMap，它通常具有较好的性能。
- 线程安全需求：
  - 如果需要线程安全，使用 ConcurrentHashMap。

存放单一元素值时

选用 Collection 接口下的集合：
- 需要存放单一元素时，可以使用 Collection 接口下的实现类。
- 元素唯一性要求：
  - 如果要求元素唯一，选择 Set 接口的集合实现，比如 HashSet 或 TreeSet。
  - TreeSet 会按照元素的自然顺序或自定义比较器排序，而 HashSet 不保证顺序。
- 不需要唯一性时：
  - 如果元素可以重复，使用 List 接口的实现类，如 ArrayList 或 LinkedList。
  - ArrayList 提供了高效的随机访问，适合于查询较多的场景。
  - LinkedList 适合于频繁插入和删除操作的场景，但查询性能较差。

根据性能需求

ArrayList：适用于频繁查询，插入删除较少的场景。
LinkedList：适用于频繁插入和删除的场景，但查询效率较低。
HashSet：适用于元素唯一且不需要顺序的情况，查找和插入性能较好。
TreeSet：适用于需要排序且要求唯一性的场景，查找和插入性能较差，但支持按顺序操作。
PriorityQueue：适用于有优先级排序的场景，如任务调度。

线程安全需求

线程安全的集合：
- 如果需要多线程环境下的安全操作，可以选择线程安全的集合类：
  - ConcurrentHashMap：适用于并发修改的场景，性能优于 Hashtable。
  - CopyOnWriteArrayList、CopyOnWriteArraySet：适用于修改不频繁但查询较多的场景。
- 如果不需要线程安全，可以选择普通集合类（如 HashMap、ArrayList 等），性能较好。

总结

需要键值对存储：选择 Map，根据排序和线程安全要求选择具体实现。
需要存放唯一元素：选择 Set，如果需要排序选择 TreeSet，如果不需要排序选择 HashSet。
需要存放有序或重复元素：选择 List，根据操作特点选择 ArrayList 或 LinkedList。
性能要求高：优先选择 HashMap、ArrayList、HashSet 等常见实现，避免不必要的开销。

为什么要使用集合？

1. 动态大小

数组：一旦创建，大小固定，不能动态调整。
集合：集合类（如 ArrayList, HashSet）可以根据需求动态扩展大小，适应数据量的变化。

2. 支持多种数据类型

数组：数组需要在创建时就确定元素类型，且数组类型是固定的。
集合：Java 集合支持泛型，可以存储多种类型的对象，且在编译时就确保类型安全，避免了类型转换的麻烦。

3. 内建操作方法

数组：数组本身不提供高级操作，开发者需要手动实现排序、查找等操作。
集合：Java 集合框架提供了大量的内建算法和方法，如排序、查找、过滤、批量操作等，大大简化了开发工作。

4. 多样化的集合类型

数组：数组只能存储元素，且元素类型固定，无法高效地处理更复杂的数据操作。
集合：Java 提供了多种集合类型（List, Set, Queue, Map 等），每种类型都有其特定的应用场景，能够更好地解决特定问题。例如，HashSet 用于去重，TreeMap 用于按顺序存储键值对等。

5. 易于扩展与维护

数组：数组的扩展和维护较为复杂，特别是在数组大小不固定时，常常需要重新分配内存，进行数据迁移。
集合：集合类通常提供了更灵活的扩展机制，如 ArrayList 会自动扩展数组大小，LinkedList 通过链表结构动态管理内存，避免了数组扩展时的性能瓶颈。

6. 高效的并发支持

数组：数组本身没有线程安全机制，无法直接支持并发操作。
集合：Java 集合框架提供了一些线程安全的集合类（如 ConcurrentHashMap、CopyOnWriteArrayList 等），使得在多线程环境下也能高效操作数据。

7. 支持更复杂的数据结构

数组：数组通常用于存储简单的数据集合，不支持直接存储复杂的元素结构。
集合：Java 集合框架支持多种复杂的数据结构，如树、堆、队列、图等，使得开发者可以轻松实现更复杂的数据模型和算法。

总结

Java 集合框架相较于数组具有以下优势：

动态大小，适应数据量变化。
支持泛型，类型安全。
提供内建算法，简化常见操作。
提供多样的集合类型，解决不同应用场景的问题。
易于扩展与维护，避免数组扩展的复杂性。
提供线程安全支持。
支持更复杂的数据结构。

这些优势使得 Java 集合在实际开发中比数组更加灵活、高效，能够更好地满足现代软件开发中对数据存储和处理的多样化需求。

二、List

ArrayList 和 Array（数组）的区别

ArrayList 和 Array 是 Java 中最常见的两种存储数据的方式，各有其特点。以下是它们的主要区别：

1. 长度和容量

Array：一旦创建，长度是固定的，无法动态改变。如果需要更大的数组，必须创建一个新的数组并复制原数据。
ArrayList：内部基于动态数组实现，可以根据需要自动扩展或缩小容量。

2. 类型安全

Array：可以存储任何类型的数据，包括基本数据类型和对象类型，但没有泛型的支持。
ArrayList：支持泛型，可以确保存储元素的类型安全，避免类型转换错误。

3. 存储元素的类型

Array：可以存储基本数据类型（如 int、char、double 等）和对象。
ArrayList：只能存储对象，不能直接存储基本类型的数据。对于基本数据类型，需要使用其包装类（例如 Integer、Double、Character 等）。

4. 操作方式

Array：提供固定大小的容器，访问元素时只能通过下标（array[index]）来获取、修改元素，操作比较简单。
ArrayList：提供了丰富的操作方法，比如 add()、remove()、set()、get() 等，支持动态的插入、删除和访问元素。

5. 创建时指定大小

Array：创建时必须指定长度，一旦指定无法改变。
ArrayList：创建时可以不指定大小，默认容量会根据需要动态扩展。

6. 性能

Array：因为其固定长度，访问元素的时间复杂度是 O(1)，因此在频繁访问元素时，性能优于 ArrayList。
ArrayList：因为有扩容和缩容机制，可能会出现一定的性能损耗，尤其是当 ArrayList 扩容时，需要重新分配内存并将原数据复制到新数组。

示例对比

`Array` 示例

// 初始化一个 String 类型的数组
String[] stringArr = new String[]{"hello", "world", "!"};
// 修改数组元素的值
stringArr[0] = "goodbye";
System.out.println(Arrays.toString(stringArr)); // [goodbye, world, !]
// 删除数组中的元素，需要手动移动后面的元素
for (int i = 0; i < stringArr.length - 1; i++) {
    stringArr[i] = stringArr[i + 1];
}
stringArr[stringArr.length - 1] = null;
System.out.println(Arrays.toString(stringArr)); // [world, !, null]

`ArrayList` 示例

// 初始化一个 String 类型的 ArrayList
ArrayList<String> stringList = new ArrayList<>(Arrays.asList("hello", "world", "!"));
// 添加元素到 ArrayList 中
stringList.add("goodbye");
System.out.println(stringList); // [hello, world, !, goodbye]
// 修改 ArrayList 中的元素
stringList.set(0, "hi");
System.out.println(stringList); // [hi, world, !, goodbye]
// 删除 ArrayList 中的元素
stringList.remove(0);
System.out.println(stringList); // [world, !, goodbye]

总结

Array 是一种固定大小的容器，适用于大小已知且不需要动态变化的情况。
ArrayList 是一种动态数组，适合需要频繁插入、删除或扩展的场景。

ArrayList 和 Vector 的区别

ArrayList 和 Vector 都是实现了 List 接口的集合类，底层均使用 Object[] 数组来存储元素。它们的主要区别在于线程安全和扩容机制：

1. 线程安全

ArrayList：不是线程安全的。如果多个线程同时访问同一个 ArrayList，并且至少一个线程对列表进行了结构修改（如添加或删除元素），则必须自行确保同步。
Vector：是线程安全的。它通过方法同步来保证多线程访问时的线程安全，但这会导致性能上的开销。

2. 扩容方式

ArrayList：默认情况下，当元素数量超过当前数组容量时，ArrayList 会扩容为原容量的 1.5 倍（JDK 1.8 及以后版本）。
Vector：默认情况下，当元素数量超过当前数组容量时，Vector 会扩容为原容量的 2 倍。

3. 性能

ArrayList：由于没有线程安全的开销，在单线程或多线程环境中不需要同步时，ArrayList 的性能通常优于 Vector。
Vector：由于方法是同步的，所以 Vector 的性能相对较差，尤其是在多线程竞争严重的场景下。

4. 构造函数的区别

ArrayList：可以通过默认构造函数或传入初始容量来创建，不会指定增长因子。
Vector：构造时可以指定初始容量和增长因子，默认情况下初始容量为 10，增长因子为 2。

总结

ArrayList 适用于单线程或不需要同步的场景，性能更好。
Vector 适用于需要线程安全的场景，但因为同步机制的原因，性能不如 ArrayList。

Vector 和 Stack 的区别有哪些？

Vector 和 Stack 都是线程安全的集合类，它们的主要区别在于数据结构和用途：

1. 继承关系

Vector：是一个实现了 List 接口的动态数组，底层使用 Object[] 来存储元素，适用于顺序存储和随机访问。
Stack：继承自 Vector，是一个后进先出（LIFO, Last In First Out）的栈结构，专门用于栈操作，如入栈（push）、出栈（pop）等。

2. 数据结构和功能

Vector：是一个动态扩展的列表，支持随机访问，可以通过索引访问元素。常用于存储和查找。
Stack：是一个栈，只提供了 push()、pop()、peek()（查看栈顶元素）等操作，不支持随机访问。

3. 操作方式

Vector：支持随机访问、添加、删除等操作。元素的插入是按位置索引进行的。
Stack：限制了访问方式，只能通过栈顶进行添加和移除（LIFO），适用于需要后进先出数据结构的场景。

4. 用途

Vector：适合用于需要动态数组功能的场景，支持元素的随机访问。
Stack：适合用于需要栈操作的场景，如解析表达式、实现递归算法等。

5. 线程安全

Vector 和 Stack 都是线程安全的，因为它们的操作是通过同步方法来保证线程安全的（使用 synchronized）。

总结

Vector 是一个通用的动态数组实现，适用于存储和查找元素。
Stack 是 Vector 的子类，专门用于后进先出（LIFO）的栈操作，适用于需要栈结构的场景。

随着并发编程的发展，Vector 和 Stack 已经逐渐被淘汰，推荐使用现代的并发集合类（如 ConcurrentHashMap、CopyOnWriteArrayList）或者手动实现线程安全的机制来替代。

ArrayList 可以添加 null 值吗？

ArrayList 是允许存储 null 值的，因为它是基于对象数组实现的，null 被认为是有效的对象引用。因此，你可以向 ArrayList 中添加 null 值。

然而，尽管技术上是允许的，但不建议在 ArrayList 中使用 null 值。使用 null 会增加代码的复杂性，尤其是在后续操作时忘记做空值检查（比如调用 get() 或者对元素进行操作时）可能会导致 NullPointerException。

示例代码：

ArrayList<String> listOfStrings = new ArrayList<>();
listOfStrings.add(null);
listOfStrings.add("java");
System.out.println(listOfStrings);

输出：

[null, java]

总结

技术上：ArrayList 可以包含 null 值。
实践中：建议避免使用 null 值，除非有充分的理由。为避免 NullPointerException，应确保在访问 null 元素时进行空值检查。

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

插入操作

头部插入：
- 由于需要将所有元素向后移动一个位置，时间复杂度为 O(n)。
尾部插入：
- 当 ArrayList 的容量未达到极限时，往列表尾部插入元素的时间复杂度为 O(1)，因为只需在数组末尾插入一个元素。
- 当容量已满且需要扩容时，时间复杂度为 O(n)，因为需要创建一个新的更大的数组并将原数组的数据复制过去，之后再执行 O(1) 的操作添加新元素。
指定位置插入：
- 需要将目标位置之后的所有元素向后移动一个位置，然后将新元素插入该位置。由于需要移动平均 n/2 个元素，时间复杂度为 O(n)。

删除操作

头部删除：
- 需要将所有元素向前移动一个位置，时间复杂度为 O(n)。
尾部删除：
- 当删除元素位于列表的尾部时，删除操作是直接删除，不需要移动元素，因此时间复杂度为 O(1)。
指定位置删除：
- 需要将目标位置之后的所有元素向前移动一个位置以填补被删除元素的空白，时间复杂度为 O(n)。

示例解释

假设 ArrayList 的底层数组大小为 10，当前存储了 7 个元素：

// 初始 ArrayList
+---+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |   |   |   |
+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9

在索引为 1 的位置插入元素 8：

// 在索引为 1 位置插入元素 8，后面的元素向右移动
+---+---+---+---+---+---+---+---+---+---+
| 1 | 8 | 2 | 3 | 4 | 5 | 6 | 7 |   |   |
+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9

时间复杂度：O(n)，需要移动元素。

删除索引为 1 的位置的元素：

// 删除索引为 1 的元素，后面的元素向左移动
+---+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |   |   |   |
+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9

时间复杂度：O(n)，需要移动元素。

总结

头部插入和删除：O(n)
尾部插入和删除：O(1)（在不扩容的情况下）
指定位置插入和删除：O(n)

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

LinkedList 是基于双向链表实现的，因此其插入和删除操作相比于 ArrayList 在某些情况下具有不同的时间复杂度。

1. 头部插入/删除

插入：在链表的头部插入元素，只需修改头结点的指针即可，因此时间复杂度是 O(1)。
删除：删除链表的头部元素，只需修改头结点的指针即可，因此时间复杂度是 O(1)。

2. 尾部插入/删除

插入：在链表的尾部插入元素，只需修改尾结点的指针即可。如果尾指针存在，时间复杂度为 O(1)。如果没有尾指针，链表必须遍历到尾部，时间复杂度则是 O(n)。
删除：删除尾部元素只需修改尾结点的指针，时间复杂度是 O(1)。但如果需要删除最后一个元素，且链表没有尾指针，必须遍历到尾部，时间复杂度为 O(n)。

3. 指定位置插入/删除

需要先遍历链表找到指定位置，再修改节点的指针进行插入或删除。由于可以从头或尾开始遍历，所以在大部分情况下，平均遍历的元素个数是 n/4，因此时间复杂度是 O(n)。

示例说明

假设有一个 LinkedList，我们要执行不同的插入和删除操作。

头部插入/删除

LinkedList<Integer> list = new LinkedList<>();
list.addFirst(1); // 头部插入
list.addFirst(2); // 头部插入
System.out.println(list); // [2, 1]
list.removeFirst(); // 头部删除
System.out.println(list); // [1]

时间复杂度：O(1)

尾部插入/删除

LinkedList<Integer> list = new LinkedList<>();
list.addLast(1); // 尾部插入
list.addLast(2); // 尾部插入
System.out.println(list); // [1, 2]
list.removeLast(); // 尾部删除
System.out.println(list); // [1]

时间复杂度：O(1)

指定位置插入/删除

LinkedList<Integer> list = new LinkedList<>();
list.add(0, 1); // 在索引 0 位置插入
list.add(1, 2); // 在索引 1 位置插入
System.out.println(list); // [1, 2]
list.remove(0); // 删除索引 0 位置的元素
System.out.println(list); // [2]

时间复杂度：O(n)

总结

头部插入/删除：O(1)
尾部插入/删除：O(1)（如果有尾指针）
指定位置插入/删除：O(n)

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

RandomAccess 是一个标记接口，表示一个集合类支持高效的随机访问，也就是说它能够在常数时间内通过索引快速访问元素。实现了 RandomAccess 接口的类，如 ArrayList，可以在给定的索引位置直接访问元素，时间复杂度为 O(1)。

然而，LinkedList 不能实现 RandomAccess 接口的原因在于它的底层实现是链表，而链表的元素在内存中并不是连续存储的，它们通过节点的指针连接起来。因此，访问某个元素时，需要从头部或尾部开始遍历，逐个节点向目标位置移动，直到找到该元素。这个过程的时间复杂度是 O(n)，而不是 O(1)。

总结

ArrayList 实现了 RandomAccess 接口，因为它使用的是连续的内存空间（数组），可以在常数时间内通过索引访问元素。
LinkedList 由于采用的是链表结构，元素是分散存储的，无法在常数时间内通过索引访问，所以 不能实现 RandomAccess 接口。

ArrayList 和 LinkedList 的区别

ArrayList 和 LinkedList 都是 Java 中实现 List 接口的类，但它们的底层结构和使用场景不同，导致在性能和功能上有一些显著的区别。

1. 底层数据结构

ArrayList 使用的是 动态数组（Object[]）。当元素数量超过数组的容量时，ArrayList 会扩容，通常是将容量扩大为原来的一倍。由于数组是连续存储的，ArrayList 可以通过索引直接访问元素，因此支持 快速随机访问。
LinkedList 使用的是 双向链表，每个元素（节点）都包含一个数据部分和两个指针，分别指向前一个和后一个元素。由于链表是通过节点连接的，它不需要预留空间，并且支持快速的头部和尾部插入与删除操作。

2. 插入和删除操作的性能

ArrayList：
- 尾部插入：当我们使用 add() 在数组的末尾添加元素时，如果数组还有空间，时间复杂度是 O(1)。但是当数组容量满了时，需要重新分配一个更大的数组并将旧数据复制到新数组中，这时操作的时间复杂度是 O(n)。
- 中间插入或删除：如果我们要在数组的中间插入或删除元素，Java 必须将插入位置之后的元素都向后或向前移动，以保持数组的连续性。因此，时间复杂度为 O(n)，其中 n 是元素的个数。
LinkedList：
- 头尾插入和删除：LinkedList 在头部和尾部插入或删除元素时，只需修改指针（不需要移动元素），因此时间复杂度是 O(1)。
- 中间插入或删除：如果我们需要在链表的中间插入或删除元素，首先需要遍历链表找到对应的节点（这个过程的时间复杂度是 O(n)）。然后再进行指针的修改（修改指针的时间复杂度是 O(1)）。

总体来说，LinkedList 在头尾操作的性能优于 ArrayList，但如果涉及到随机访问或中间操作，ArrayList 更具优势。

3. 随机访问性能

ArrayList 支持 快速随机访问，通过索引直接访问元素的时间复杂度是 O(1)，因为底层是数组，可以直接通过内存地址计算位置。
LinkedList 不支持快速随机访问，因为要访问链表中的某个元素，必须从头或尾开始逐个遍历，直到找到目标节点。因此，访问元素的时间复杂度是 O(n)。

4. 内存使用

ArrayList 的底层是数组，内存空间是连续的。由于需要在数组末尾预留一定的空余容量来避免频繁扩容，可能会造成内存的浪费。
LinkedList 的每个节点除了存储数据，还需要额外的两个指针（prev 和 next）。因此，链表的内存开销比 ArrayList 大，因为每个元素除了存储实际的数据外，还需要额外的空间存储指针。

5. 线程安全

ArrayList 和 LinkedList 都是 非线程安全 的。如果需要在多线程环境下使用它们，可以使用 Collections.synchronizedList() 方法来包装，或者使用 CopyOnWriteArrayList 等线程安全的类。

6. 使用场景

ArrayList 更适合 需要频繁随机访问 和 少量插入/删除操作 的场景。例如，若你需要频繁通过索引获取元素，ArrayList 的性能会明显优于 LinkedList。
LinkedList 更适合 频繁在头尾进行插入和删除操作 的场景。例如，若你要经常在列表的头部或尾部添加/删除元素，LinkedList 会提供更好的性能。

总结对比

特性	ArrayList	LinkedList
底层数据结构	动态数组（`Object[]`）	双向链表（每个节点包含前后指针）
插入和删除性能	头尾操作快（O(1)），中间操作慢（O(n)）	头尾操作快（O(1)），中间操作也需遍历（O(n)）
随机访问性能	快速随机访问（O(1)）	随机访问性能差（O(n)）
内存使用	内存连续，有可能浪费空间（预留空余容量）	每个节点需要存储两个额外的指针（`prev` 和 `next`）
线程安全	非线程安全（需要手动同步）	非线程安全（需要手动同步）
使用场景	适合频繁访问、少量插入和删除的场景	适合频繁插入/删除头尾的场景

总结

如果你的应用中需要 频繁地随机访问 或者你知道你会对集合进行大量的索引操作，选择 ArrayList 是更合适的。
如果你的应用中主要是 频繁插入和删除元素，尤其是在头部和尾部，并且你不需要频繁地通过索引访问元素，选择 LinkedList 可能会更好。

总体而言，ArrayList 通常会比 LinkedList 更受欢迎，因为它的随机访问速度更快，而且通常能满足大多数的应用需求。

`ArrayList` 扩容机制

ArrayList 在存储元素时，底层采用的是一个 动态数组。当数组容量达到最大限制时，ArrayList 会自动进行扩容，以保证能够继续存储新元素。

扩容机制是 ArrayList 的关键特性之一，它保证了我们能够动态增加元素而无需预先指定容量。然而，扩容是一个相对较为耗时的操作，了解其机制可以帮助我们在实际开发中进行优化。

1. 初始容量

当我们创建一个 ArrayList 时，如果没有指定初始容量，它的默认容量是 10。这意味着，ArrayList 会首先创建一个大小为 10 的数组用于存储元素。

ArrayList<Integer> list = new ArrayList<>();
// 默认容量是10

如果我们在创建 ArrayList 时指定了初始容量，它就会根据我们指定的值来初始化数组的大小。

ArrayList<Integer> list = new ArrayList<>(50);
// 初始容量是50

2. 扩容规则

当 ArrayList 中存储的元素数量超过当前数组的容量时，它会进行扩容。扩容的规则是 每次将容量扩展为原来的 1.5 倍，这个规则源自 ArrayList 的源码实现。

例如：

如果原数组的容量为 10，扩容后新数组的容量将变为 10 * 1.5 = 15。
如果原数组的容量为 15，扩容后新数组的容量将变为 15 * 1.5 = 22（向上取整）。

ArrayList<Integer> list = new ArrayList<>(10);
list.add(1); // 数量为1
list.add(2); // 数量为2
// 当添加到第11个元素时，ArrayList 会进行扩容

3. 扩容的具体步骤

1.5倍扩容：当现有容量不足以容纳新元素时，ArrayList 会创建一个新的、更大的数组（容量是原数组的 1.5 倍），并将原数组的元素复制到新数组中。
时间复杂度：扩容时，需要将所有现有元素从旧数组复制到新数组，这个过程的时间复杂度为 O(n)，其中 n 是当前数组的大小。

扩容的过程实际上会导致较大的开销，因此在使用 ArrayList 时，如果预期需要存储大量元素，事先设定一个合适的容量是一个很好的优化手段。

4. 是否总是扩容1.5倍？

从 JDK 1.8 开始，ArrayList 的扩容策略从固定的 1.5 倍变成了 oldCapacity + (oldCapacity >> 1)，即将原容量增加 50%。这种方式使得扩容计算更加高效，避免了浮点运算。

例如：

假设初始容量为 10，扩容后容量将变为 10 + (10 >> 1) = 10 + 5 = 15。
如果容量为 15，扩容后容量将变为 15 + (15 >> 1) = 15 + 7 = 22。

这种扩容方式比固定的 1.5 倍扩容略微更加高效。

5. 扩容的性能问题

由于扩容时需要重新分配内存并复制数组，扩容是一个 O(n) 操作，这意味着每次扩容都会导致性能下降。因此，频繁的扩容会对 ArrayList 的性能造成不利影响，特别是在存储大量数据时。

如何优化：

预先设置容量：如果我们已经知道 ArrayList 需要存储的元素大概数量，可以在初始化时设置一个足够的容量，避免频繁扩容。
```
ArrayList<Integer> list = new ArrayList<>(1000); // 预设容量1000
```

6. 扩容时如何影响性能？

扩容的开销主要来自两个方面：

内存重新分配：扩容时，ArrayList 会分配一个新的、更大的数组。这个操作可能会导致内存的碎片化，特别是当 ArrayList 存储大量元素时。
数组元素复制：每次扩容都需要将原数组的元素复制到新的数组中，这个过程的时间复杂度是 O(n)，会消耗较多的时间。

为了避免频繁扩容，我们可以根据实际需求来调整 ArrayList 的初始容量。

7. 扩容后的容量

需要注意的是，扩容后的容量并不会因为元素的删除而减少。ArrayList 只会在元素数量达到当前容量时才进行扩容。即使数组中有大量空闲空间，容量也不会自动减小。

如果需要手动调整容量，可以使用 trimToSize() 方法来精确设置 ArrayList 的容量，使其等于当前元素的数量。

ArrayList<Integer> list = new ArrayList<>(100);
list.add(1);
list.trimToSize();  // 调整容量为实际大小

小结

ArrayList 的扩容机制主要是通过每次将容量扩展 1.5 倍（或增加 50%）来保证它可以容纳更多元素。
扩容是一个 O(n) 的操作，可能会对性能产生影响，特别是当元素数量非常大时。
可以通过在初始化时设置合适的容量，或者使用 trimToSize() 来优化内存使用和性能。

通过理解 ArrayList 的扩容机制，我们可以在实际使用中更好地控制内存的使用和操作的性能。

`fail-fast` 和 `fail-safe` 的区别

fail-fast 和 fail-safe 是在多线程环境下，尤其是在处理集合类时，常用的两种设计思想。这两种机制的目标是提高代码的鲁棒性和并发操作的安全性。

1. Fail-Fast（快速失败）

fail-fast 机制是一种尽早发现并终止程序异常的策略。当集合在被迭代时，如果检测到集合在迭代过程中被修改了（例如，在多线程环境下，某个线程对集合进行了修改），就会立即抛出异常。这种机制帮助程序尽早捕捉潜在的并发问题，避免在运行时产生难以预料的错误。

关键特点：

检测并发修改： 通过维护 modCount（修改次数），在集合迭代过程中比对修改次数是否一致来判断是否发生并发修改。
快速失败： 如果检测到并发修改，fail-fast 会立即抛出 ConcurrentModificationException，停止迭代。

示例：

List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100; i++) {
    list.add(i);
}

Thread t1 = new Thread(() -> {
    for (Integer i : list) {
        i++;  // 不修改list，只是对元素进行操作
    }
});

Thread t2 = new Thread(() -> {
    list.remove(1);  // 删除元素
});

t1.start();
t2.start();

在上述例子中，Thread t1 在进行迭代时，Thread t2 删除了一个元素，导致 modCount 不一致，t1 会抛出 ConcurrentModificationException。

底层实现：

ArrayList 中的迭代器在调用 next() 方法时，会执行 checkForComodification() 方法来检查是否发生并发修改。

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

2. Fail-Safe（安全失败）

fail-safe 机制则与 fail-fast 完全不同，它的设计目标是允许并发修改而不抛出异常。即使在集合被修改的过程中，fail-safe 集合也不会抛出 ConcurrentModificationException，而是会通过某种方式保证迭代器可以继续工作。

关键特点：

不会抛出异常： 即使在迭代时发生并发修改，fail-safe 集合依然会继续迭代，通常通过复制底层数据（快照）来确保不会影响迭代。
适用于并发环境： fail-safe 机制通常用于并发容器，保证多线程操作时的线程安全，避免数据竞争和不一致性。

典型实现：

CopyOnWriteArrayList 是一个典型的 fail-safe 集合。它通过“写时复制”（copy-on-write）的方式，保证在修改集合时不影响正在进行的迭代操作。

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

在 CopyOnWriteArrayList 中，每次修改操作（如 add() 或 remove()）都会创建一个新的数组副本。这样，即使在修改期间，迭代器仍然能够遍历旧的数组副本，而不受到新修改的影响。

3. 对比

特性	Fail-Fast	Fail-Safe
并发修改	会抛出 `ConcurrentModificationException`	允许并发修改，操作不会影响迭代
容器类型	一般应用于非线程安全的集合，如 `ArrayList`、`HashMap`	用于线程安全的集合，如 `CopyOnWriteArrayList`
性能开销	较低，因为只进行修改计数检查，不需要复制数据	较高，需要复制底层数组来进行修改
适用场景	适合需要检测并发问题并及时终止的场景	适合对并发修改容忍并确保线程安全的场景

4. 总结

Fail-Fast 机制的主要优点是能够尽早检测到并发修改并停止程序，避免不一致的结果。在多数情况下，它帮助开发者及时发现潜在的并发问题，增强程序的可靠性。
Fail-Safe 机制则在并发环境中更具容错性，通过复制数据来避免因并发修改而导致的问题。虽然它不会抛出异常，但其代价较高，可能会影响性能，特别是在频繁修改的场景下。

选择使用哪种机制，通常取决于应用的场景。如果你需要高效的并发处理并且能容忍一定的性能开销，fail-safe 可能是更合适的选择。如果你需要快速检测错误并终止程序，避免隐性问题，fail-fast 是更好的选择。

三、Set

`Comparable` 和 `Comparator` 的区别

Comparable 和 Comparator 都是 Java 中用来实现对象排序的接口，但它们的使用场景和实现方式有所不同。具体区别如下：

1. `Comparable` 接口

接口位置：java.lang.Comparable
主要方法：compareTo(T o)
定义排序规则：Comparable 接口允许一个类自身定义排序规则，通常用于对象的自然排序。
使用场景：当我们希望对象的排序规则是固定的，且只能按照一种规则排序时，使用 Comparable 接口。
实现方式：在类中实现 compareTo 方法，通过 this 和 o 比较大小来决定排序顺序。

示例：

public class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Person o) {
        return Integer.compare(this.age, o.getAge());  // 按年龄排序
    }
}

使用示例：

TreeSet<Person> set = new TreeSet<>();
set.add(new Person("张三", 30));
set.add(new Person("李四", 20));
set.add(new Person("王五", 25));

for (Person p : set) {
    System.out.println(p.getName() + ": " + p.getAge());
}

输出：

李四: 20
王五: 25
张三: 30

2. `Comparator` 接口

接口位置：java.util.Comparator
主要方法：compare(T o1, T o2)
定义排序规则：Comparator 允许我们在外部定义排序规则，适用于需要多种排序方式的场景。
使用场景：当我们需要对同一个类的对象进行多种不同的排序时，使用 Comparator 接口。
实现方式：我们可以通过创建一个 Comparator 对象，在外部指定排序规则，而不需要修改原始类的代码。

示例：

public class PersonComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return p1.getName().compareTo(p2.getName());  // 按姓名排序
    }
}

使用示例：

List<Person> list = new ArrayList<>();
list.add(new Person("张三", 30));
list.add(new Person("李四", 20));
list.add(new Person("王五", 25));

Collections.sort(list, new PersonComparator());

for (Person p : list) {
    System.out.println(p.getName() + ": " + p.getAge());
}

输出：

李四: 20
王五: 25
张三: 30

3. `Comparable` 和 `Comparator` 的区别

特性	`Comparable`	`Comparator`
定义位置	`java.lang.Comparable`	`java.util.Comparator`
排序规则	类内部定义（自然排序）	外部定义（可以多种排序规则）
实现方式	实现 `compareTo(T o)` 方法	实现 `compare(T o1, T o2)` 方法
适用场景	适用于单一排序规则的场景	适用于需要多种排序方式的场景
修改原始类	需要在类中修改，重写 `compareTo` 方法	不需要修改原始类，只需外部实现 `Comparator`
排序优先级	优先排序（类实现 `Comparable` 后，所有排序默认使用）	可根据需求选择不同的 `Comparator` 排序方式

4. 组合使用 `Comparable` 和 `Comparator`

有时我们需要根据不同的条件排序同一类对象，可以通过 Comparable 和 Comparator 配合使用：

Comparable 用于定义默认排序（自然排序）。
Comparator 用于指定其他排序规则。

示例：

public class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Person o) {
        return Integer.compare(this.age, o.getAge());  // 默认按年龄排序
    }
}

public class PersonComparatorByName implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return p1.getName().compareTo(p2.getName());  // 按姓名排序
    }
}

使用示例：

List<Person> list = new ArrayList<>();
list.add(new Person("张三", 30));
list.add(new Person("李四", 20));
list.add(new Person("王五", 25));

// 默认按年龄排序
Collections.sort(list);
for (Person p : list) {
    System.out.println(p.getName() + ": " + p.getAge());
}

// 使用自定义的比较器按姓名排序
Collections.sort(list, new PersonComparatorByName());
for (Person p : list) {
    System.out.println(p.getName() + ": " + p.getAge());
}

输出：

默认排序（按年龄）：
李四: 20
王五: 25
张三: 30

按姓名排序：
李四: 20
王五: 25
张三: 30

5. 总结

Comparable 适用于需要单一排序规则的情况，它使得对象本身具备排序能力。
Comparator 适用于多重排序规则，允许外部定义排序规则，并且不需要修改类的代码。

通常，如果排序规则是固定的并且在多个地方使用，使用 Comparable；如果需要灵活的多种排序方式，使用 Comparator。

无序性和不可重复性的含义

1. 无序性

定义：无序性指的是集合中元素的存储顺序不固定，不遵循插入顺序。对于像 HashSet 这样的集合，元素并不是按它们被添加的顺序存储的，而是由元素的 哈希值 决定存储的位置。也就是说，集合的底层数据结构（如哈希表）可能根据哈希值对元素进行重新排列，因此集合中的元素顺序不可预测。
无序性不等于随机性：虽然元素存储的顺序是无序的，但并不意味着它们的顺序是完全随机的。无序性只是表示集合的元素顺序是由哈希值决定的，而不是像数组那样根据索引顺序排列。
- 例子：HashSet 和 HashMap 都是无序的集合。即使我们按顺序向集合中添加元素，取出来的顺序可能与我们插入时的顺序不同。
```
Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Orange");

// 输出顺序可能和添加顺序不同
for (String s : set) {
    System.out.println(s);
}
```

2. 不可重复性

定义：不可重复性意味着集合中不能存储重复的元素。当我们尝试向集合中添加一个已经存在的元素时，添加操作会失败，集合保持元素的唯一性。这是通过 equals() 方法判断元素是否相等来实现的，因此同一个元素必须满足两个条件：
1. equals()：用于判断元素是否相同。
2. hashCode()：用于计算元素的哈希值。两个相等的元素必须具有相同的哈希值。
如果类中的 equals() 方法和 hashCode() 方法没有正确重写，可能导致集合无法正确识别重复元素，从而违反不可重复性原则。
- 例子：HashSet 和 HashMap 都不允许重复的元素。试图添加重复的元素时，集合会忽略重复的元素。
```
Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Apple");  // 该元素被忽略，集合只存储一个 "Apple"

System.out.println(set.size());  // 输出 1
```
注意：如果自定义对象作为集合的元素，在使用 HashSet 或 HashMap 等基于哈希表的数据结构时，必须同时重写 equals() 和 hashCode() 方法，否则集合无法正确判断元素是否重复。

总结

无序性：集合的元素存储顺序由哈希值决定，不一定是插入顺序。
不可重复性：集合中的元素不能重复，重复元素通过 equals() 方法判断，必须重写 equals() 和 hashCode()。

这些特性常见于基于哈希表的集合类，如 HashSet、HashMap 等。

比较 `HashSet`、`LinkedHashSet` 和 `TreeSet` 三者的异同

1. 共同点

都实现了 Set 接口，因此都能保证集合中的元素是唯一的，不能有重复元素。
都不是线程安全的：这些集合类都不支持多线程下的并发修改，若需要线程安全，可以使用 Collections.synchronizedSet() 或 CopyOnWriteArraySet 等线程安全集合。
都不保持插入顺序（但有细微差别），即元素的顺序不固定，除非底层结构支持。

2. 区别点

特性	`HashSet`	`LinkedHashSet`	`TreeSet`
底层数据结构	哈希表（基于 `HashMap` 实现）	哈希表 + 双向链表（结合了 `HashMap` 和 `LinkedList`）	红黑树（自平衡二叉查找树）
元素排序	无序（不保证插入顺序）	保证元素按照插入顺序迭代	元素有序（自然排序或定制排序）
插入顺序	不保证顺序	保证插入顺序（FIFO）	根据排序规则（升序或定制排序）进行顺序
访问效率	O(1) 查找、插入、删除	O(1) 查找、插入、删除，迭代时 O(n)	O(log n) 查找、插入、删除
用途	用于不需要排序且不关心插入顺序的场景	用于需要保持元素插入顺序的场景	用于需要排序或自定义排序的场景

3. 详细分析

HashSet：
- 底层实现：基于 哈希表（实际上是 HashMap），通过元素的哈希值来决定其存储位置。
- 特点：不保证元素的顺序，因此元素在遍历时的顺序是无序的。
- 适用场景：当我们不关心元素的顺序，只需要保证元素的唯一性时，HashSet 是最常用的选择。
```
Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Orange");
// 无法保证顺序
for (String fruit : set) {
    System.out.println(fruit);
}
```
LinkedHashSet：
- 底层实现：结合了哈希表和双向链表。哈希表用于存储元素，而链表则保证了元素的插入顺序。
- 特点：保持元素的 插入顺序，即按照元素添加的顺序进行迭代。
- 适用场景：当我们需要保证元素的唯一性，并且关心元素的插入顺序时，可以使用 LinkedHashSet。
```
Set<String> set = new LinkedHashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Orange");
// 保证插入顺序
for (String fruit : set) {
    System.out.println(fruit);
}
```
TreeSet：
- 底层实现：基于 红黑树，这是一种自平衡的二叉查找树。红黑树保证了元素的 有序性，并提供高效的查找、插入和删除操作。
- 特点：元素是排序的，可以使用自然顺序（如果元素实现了 Comparable 接口），或者通过传入自定义的 Comparator 进行排序。
- 适用场景：当我们需要对元素进行排序时，尤其是要在有序集合中去重时，TreeSet 是理想选择。
```
Set<Integer> set = new TreeSet<>();
set.add(10);
set.add(5);
set.add(15);
// 元素会按升序排序
for (Integer num : set) {
    System.out.println(num);
}
```

4. 性能比较

HashSet：
- 插入、删除和查找操作的时间复杂度大约为 O(1)，因为哈希表基于哈希值进行查找和定位，效率较高。
- 不保证元素的顺序。
LinkedHashSet：
- 插入、删除和查找操作的时间复杂度为 O(1)，与 HashSet 类似，但由于维护了双向链表用于记录插入顺序，迭代时的性能稍逊（O(n)）。
- 保证插入顺序。
TreeSet：
- 插入、删除和查找操作的时间复杂度为 O(log n)，因为底层使用的是红黑树，这是一种平衡二叉树。
- 元素是有序的，按照自然顺序或自定义排序顺序排列。

5. 总结

HashSet：用于无序且不需要排序的集合，性能最优，适用于基本的去重操作。
LinkedHashSet：用于需要保持插入顺序的集合，在顺序性要求较高时使用。
TreeSet：用于需要排序的集合，适用于需要元素排序（升序或自定义顺序）的场景。

每种 Set 实现类根据底层数据结构的不同，适用于不同的使用场景，选择合适的集合可以提高代码的性能和可维护性。

四、Queue

`Queue` 与 `Deque` 的区别

1. 定义

Queue：单端队列，遵循 先进先出（FIFO） 规则，只能从队列的一端插入元素（队尾），从另一端删除元素（队首）。
Deque：双端队列，可以从队列的两端（队首和队尾）插入和删除元素，支持更灵活的操作，提供更多的功能。

2. 操作方法对比

2.1 `Queue` 接口方法

插入元素到队尾：
- add(E e)：插入元素，如果队列已满则抛出异常 IllegalStateException。
- offer(E e)：插入元素，如果队列已满，则返回 false。
删除队首元素：
- remove()：删除并返回队首元素，如果队列为空则抛出异常 NoSuchElementException。
- poll()：删除并返回队首元素，如果队列为空则返回 null。
查看队首元素：
- element()：查看队首元素，但不删除，如果队列为空则抛出异常 NoSuchElementException。
- peek()：查看队首元素，但不删除，如果队列为空则返回 null。

2.2 `Deque` 接口方法

Deque 扩展了 Queue，增加了对队首和队尾两端操作的支持。

插入元素到队首和队尾：
- addFirst(E e)：将元素插入到队首，如果队列已满则抛出异常。
- addLast(E e)：将元素插入到队尾，如果队列已满则抛出异常。
- offerFirst(E e)：将元素插入到队首，如果队列已满则返回 false。
- offerLast(E e)：将元素插入到队尾，如果队列已满则返回 false。
删除队首和队尾元素：
- removeFirst()：删除队首元素，如果队列为空则抛出异常。
- removeLast()：删除队尾元素，如果队列为空则抛出异常。
- pollFirst()：删除并返回队首元素，如果队列为空则返回 null。
- pollLast()：删除并返回队尾元素，如果队列为空则返回 null。
查看队首和队尾元素：
- getFirst()：查看队首元素但不删除，如果队列为空则抛出异常。
- getLast()：查看队尾元素但不删除，如果队列为空则抛出异常。
- peekFirst()：查看队首元素但不删除，如果队列为空则返回 null。
- peekLast()：查看队尾元素但不删除，如果队列为空则返回 null。

3. 双端队列的其他功能

Deque 提供的额外方法：
- push(E e)：将元素压入栈的顶端，等同于在队首插入元素。
- pop()：移除并返回栈顶元素，等同于删除队首元素。

这些方法使得 Deque 可以作为栈（LIFO）或队列（FIFO）来使用，给开发者提供了更灵活的数据结构选择。

4. 使用场景

Queue：
- 用于需要先进先出（FIFO）操作的场景，例如任务队列、请求处理等。
- 适合只需要单端插入和删除的场景。
Deque：
- 用于需要从队列两端插入和删除元素的场景，例如双端队列、栈、滑动窗口等。
- 适合需要更复杂操作的场景，如同时操作队首和队尾的数据结构。

5. 总结

Queue 主要适用于队列（FIFO）的需求，且只能从一端插入和删除元素。
Deque 作为 双端队列，不仅支持队列的操作，还支持双端的插入和删除，甚至可以模拟栈（LIFO）操作，具有更灵活的功能。

`ArrayDeque` 与 `LinkedList` 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，能够用于双端队列操作（即在队首和队尾都可以进行插入和删除）。它们的主要区别体现在底层数据结构、性能表现以及功能等方面：

1. 底层实现

ArrayDeque：
- 使用可变长的数组来实现队列。通过双指针（头指针和尾指针）来管理队列的首尾，并在需要时进行动态扩容。
- 基于数组的实现使得其在访问元素时具有较高的缓存局部性，读取性能较好。
LinkedList：
- 使用链表来实现，每个元素包含指向前一个和后一个元素的指针，因此插入和删除元素时不需要移动其他元素。
- 访问元素时需要遍历链表，相比数组访问来说，性能较低（O(n)），但插入和删除操作可以在常数时间内完成（O(1)）。

2. 是否支持存储 `NULL` 元素

ArrayDeque：
- 不支持存储 NULL 元素。插入 NULL 元素时会抛出 NullPointerException。
LinkedList：
- 支持存储 NULL 元素，可以将 NULL 插入到队列中。

3. 扩容与内存分配

ArrayDeque：
- 由于使用数组实现，当数组满时需要进行扩容（通常是将数组大小翻倍），扩容操作可能会带来性能开销。
- 然而，均摊后的插入操作时间复杂度为 O(1)，即大多数插入操作的性能是常数时间。
LinkedList：
- 不需要像数组那样进行扩容，因为它是基于链表的，每次插入操作都只需要分配一个新的节点并修改指针即可。
- 然而，链表的插入操作需要分配新的内存，并且每次插入都涉及到指针的更新，均摊的性能相比 ArrayDeque 更差。

4. 性能比较

ArrayDeque：
- 由于其底层是数组结构，数组的访问速度比链表快（O(1)）。因此，ArrayDeque 在大多数情况下提供更高的性能，特别是在插入和删除操作频繁时。
- 插入和删除操作的时间复杂度通常为 O(1)，但当数组需要扩容时，可能会有额外的性能开销。
LinkedList：
- LinkedList 的插入和删除操作在两端都是 O(1)，但随机访问元素时需要 O(n) 的时间，性能较差。
- 总体来说，LinkedList 在需要频繁访问元素时表现较差，因为它需要遍历链表，而 ArrayDeque 的元素访问速度更快。

5. 功能上的差异

ArrayDeque：
- 由于 ArrayDeque 使用动态数组实现，它非常适合用作栈（LIFO）或队列（FIFO）操作。
- 可以作为栈或队列使用，支持高效的插入和删除操作。
LinkedList：
- LinkedList 也支持双端队列操作，可以在两端进行插入和删除，除此之外还可以作为单向链表和双向链表使用，提供更多的操作接口。
- LinkedList 不仅适合用作队列或栈，还适用于需要频繁进行插入和删除操作的数据结构场景，尤其是当元素数目不断变化时。

6. JDK 引入时间

ArrayDeque：
- 在 JDK 1.6 中引入，主要解决了传统 Stack 和 LinkedList 性能较差的问题，提供了更高效的队列实现。
LinkedList：
- 在 JDK 1.2 中就已经存在，是 List 和 Deque 接口的实现类之一。

7. 何时使用

ArrayDeque：
- 适用于对性能要求较高的场景，尤其是频繁插入、删除元素的队列操作，或作为栈使用。
- 如果需要高效的插入和删除操作，并且不需要存储 NULL 元素，选择 ArrayDeque 更合适。
LinkedList：
- 适用于需要频繁插入和删除元素的场景，但不太关心元素访问的效率。
- 如果需要支持双向链表、单向链表，或者需要存储 NULL 元素，LinkedList 会更合适。

8. 总结

特性	`ArrayDeque`	`LinkedList`
底层数据结构	可变长度数组	双向链表
是否支持 `NULL` 元素	不支持	支持
插入与删除性能	均摊 O(1)，但可能有扩容开销	O(1)，但每次插入需要分配新的节点
随机访问性能	O(1)，较快	O(n)，较慢
引入时间	JDK 1.6	JDK 1.2
使用场景	高效的队列和栈操作，尤其在大量元素时	需要频繁插入删除或支持链表操作的场景

因此，选择 ArrayDeque 或 LinkedList 取决于你的使用场景，若你需要高效的队列操作且不关心 NULL 元素，ArrayDeque 是更好的选择；如果需要支持更复杂的链表操作或允许存储 NULL，则可以使用 LinkedList。

`PriorityQueue` 详细解析

PriorityQueue 是 Java 提供的一种基于优先级队列的实现，其底层数据结构是二叉堆。与普通队列不同的是，PriorityQueue 在出队时遵循优先级顺序，而非先进先出（FIFO）的顺序。

主要特点

底层实现：
- PriorityQueue 使用 二叉堆（通常是小顶堆）来实现。
- 二叉堆是一种完全二叉树，可以高效地进行插入和删除操作。它通过上浮和下沉操作来维护堆的性质，从而在 O(log n) 的时间复杂度内完成插入和删除堆顶元素操作。
- 数据是通过可变长的数组存储的。
元素顺序：
- PriorityQueue 中的元素是根据 优先级 来排序的，不是按照元素插入的顺序出队。
- 默认情况下，PriorityQueue 是小顶堆，即 优先级高的元素优先出队。可以通过传入 Comparator 来自定义排序规则，从而实现最大堆或其他排序方式。
线程安全：
- PriorityQueue 是 非线程安全的，在并发场景下使用时，需要外部同步来保证线程安全。
元素的比较：
- PriorityQueue 中的元素必须是 可比较的，即元素要实现 Comparable 接口，或者在创建 PriorityQueue 时提供一个自定义的 Comparator。
- 不能存储 NULL 元素，因为 null 元素没有有效的比较方法。
常见应用场景：
- PriorityQueue 常用于解决一些与优先级相关的问题，例如：
  - 堆排序：通过构建堆来排序数据。
  - 求第 K 大元素：通过维护一个最小堆，找出数据流中的第 K 大元素。
  - 带权图的遍历：如 Dijkstra 算法、A* 算法中使用优先队列来优化图的遍历过程。
常见操作：
- offer(E e)：插入元素，按照优先级排队。
- poll()：删除并返回堆顶元素，即优先级最高的元素。
- peek()：返回堆顶元素但不删除。
- remove(Object o)：删除指定元素。
- size()：返回队列中元素的个数。

示例代码

默认小顶堆示例：

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个PriorityQueue，默认是小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.offer(5);
        pq.offer(1);
        pq.offer(10);
        pq.offer(3);

        System.out.println("PriorityQueue 元素出队顺序：");
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());  // 按优先级顺序出队
        }
    }
}

输出：

PriorityQueue 元素出队顺序：
1
3
5
10

使用自定义 Comparator 来实现大顶堆：

import java.util.PriorityQueue;
import java.util.Comparator;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个PriorityQueue，使用自定义Comparator实现大顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

        pq.offer(5);
        pq.offer(1);
        pq.offer(10);
        pq.offer(3);

        System.out.println("PriorityQueue 元素出队顺序（大顶堆）：");
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());  // 按优先级顺序出队
        }
    }
}

输出：

PriorityQueue 元素出队顺序（大顶堆）：
10
5
3
1

求第 K 大元素的应用：

import java.util.PriorityQueue;

public class KthLargestElement {
    public static int findKthLargest(int[] nums, int k) {
        // 创建一个小顶堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 将前 K 个元素插入堆中
        for (int i = 0; i < k; i++) {
            minHeap.offer(nums[i]);
        }

        // 遍历数组中的剩余元素，维护堆的大小为 K
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(nums[i]);
            }
        }

        // 堆顶元素就是第 K 大元素
        return minHeap.peek();
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println("第 " + k + " 大的元素是：" + findKthLargest(nums, k));
    }
}

输出：

第 2 大的元素是：5

总结

特性	`PriorityQueue`
底层数据结构	二叉堆（小顶堆或大顶堆，取决于 `Comparator`）
是否线程安全	否
是否支持 `NULL` 元素	不支持
元素比较要求	必须实现 `Comparable` 接口或提供 `Comparator`
插入、删除操作的时间复杂度	O(log n)
典型应用场景	堆排序、求第 K 大元素、带权图遍历（如 Dijkstra 算法）
默认排序	小顶堆（可以通过 `Comparator` 定制为大顶堆或其他排序）

PriorityQueue 是一个非常强大的工具，可以处理许多与优先级有关的问题，特别是在需要动态调整优先级或求解最小值/最大值时。

`BlockingQueue` 详细解析

BlockingQueue 是 Java 提供的一个接口，继承自 Queue，用于处理线程间的协作和同步。它是一种支持阻塞操作的队列，常用于 生产者-消费者模式 中，保证线程安全地进行数据交换。

主要特点

阻塞操作：
- BlockingQueue 提供的操作会在特定条件下阻塞调用线程，直到满足条件才继续执行。
- 主要的阻塞操作是：
  - 插入元素：当队列已满时，生产者线程会被阻塞，直到队列有足够的空间。
  - 移除元素：当队列为空时，消费者线程会被阻塞，直到有元素可以消费。
线程安全：
- BlockingQueue 提供线程安全的操作，不需要额外的同步机制（如 synchronized 或 ReentrantLock）来保证线程安全。
支持公平性：
- 一些实现（如 ArrayBlockingQueue）提供公平策略，保证线程按照先后顺序访问队列，避免线程饥饿。
应用场景：
- BlockingQueue 主要用于 生产者-消费者模型，它能够自动管理线程同步、避免忙等待，提高效率。
- 常见的应用场景包括任务调度、线程池、消息队列等。

主要方法

BlockingQueue 继承自 Queue 接口，并增加了一些特定的阻塞方法，主要分为以下几类：

插入元素

put(E e)：将元素插入队列。如果队列已满，调用线程会被阻塞，直到队列有空余空间。
offer(E e, long timeout, TimeUnit unit)：在指定的等待时间内尝试将元素插入队列。如果队列已满，调用线程会等待，直到队列有空间或者超时。

删除元素

take()：从队列中取出并删除元素。如果队列为空，调用线程会被阻塞，直到队列中有元素可供移除。
poll(long timeout, TimeUnit unit)：在指定的等待时间内尝试从队列中移除并返回元素。如果队列为空，调用线程会等待，直到有元素或者超时。

查询元素

peek()：查看队列头部的元素但不删除。如果队列为空，则返回 null。
remainingCapacity()：返回队列中剩余可插入元素的空间大小。

常见实现类

ArrayBlockingQueue：
- 基于数组实现的有界阻塞队列。
- 它有固定大小，并且是 FIFO（先进先出）顺序。
LinkedBlockingQueue：
- 基于链表实现的有界或无界阻塞队列。
- 默认大小为 Integer.MAX_VALUE，但是可以自定义大小。
PriorityBlockingQueue：
- 是一个无界的阻塞队列，元素按优先级顺序排列。
- 它实现了 BlockingQueue 接口，支持阻塞操作，但内部元素顺序是根据元素的优先级来排序的。
DelayQueue：
- 用于延时任务的阻塞队列，只有当元素的延迟时间到了，才能从队列中取出。
SynchronousQueue：
- 是一个特殊的队列，不保存元素，每个 put() 操作都必须等待另一个线程进行 take() 操作，反之亦然。

生产者-消费者模型示例

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class BlockingQueueExample {

    static class Producer implements Runnable {
        private final BlockingQueue<Integer> queue;

        public Producer(BlockingQueue<Integer> queue) {
            this.queue = queue;
        }

        @Override
        public void run() {
            try {
                for (int i = 1; i <= 5; i++) {
                    System.out.println("生产者生产了: " + i);
                    queue.put(i); // 阻塞操作
                    Thread.sleep(1000);
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }

    static class Consumer implements Runnable {
        private final BlockingQueue<Integer> queue;

        public Consumer(BlockingQueue<Integer> queue) {
            this.queue = queue;
        }

        @Override
        public void run() {
            try {
                for (int i = 1; i <= 5; i++) {
                    int item = queue.take(); // 阻塞操作
                    System.out.println("消费者消费了: " + item);
                    Thread.sleep(1500);
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }

    public static void main(String[] args) {
        BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(3); // 队列容量为3

        Thread producer = new Thread(new Producer(queue));
        Thread consumer = new Thread(new Consumer(queue));

        producer.start();
        consumer.start();
    }
}

输出：

生产者生产了: 1
消费者消费了: 1
生产者生产了: 2
生产者生产了: 3
消费者消费了: 2
生产者生产了: 4
生产者生产了: 5
消费者消费了: 3
消费者消费了: 4
消费者消费了: 5

总结

特性	`BlockingQueue`
继承接口	`Queue`
阻塞操作	当队列为空时，`take()` 阻塞；当队列满时，`put()` 阻塞
线程安全性	是线程安全的，不需要外部同步
支持的队列类型	有界队列、无界队列、优先级队列等
应用场景	生产者-消费者模式、任务队列、线程池等
主要实现类	`ArrayBlockingQueue`、`LinkedBlockingQueue`、`PriorityBlockingQueue`、`SynchronousQueue` 等

BlockingQueue 提供了高效的线程间协作机制，尤其适用于生产者-消费者模型等并发场景，能够减少多线程编程中对同步的需求。

`BlockingQueue` 的实现类

Java 中常用的阻塞队列实现类有以下几种：

ArrayBlockingQueue
- 实现方式：基于数组实现的有界阻塞队列。
- 特点：必须指定容量大小，且队列满时插入会阻塞，队列为空时取出会阻塞。
- 锁机制：支持公平锁和非公平锁，默认使用非公平锁。
- 应用场景：适合队列长度固定的场景，如线程池的任务队列。
LinkedBlockingQueue
- 实现方式：基于单向链表实现的可选有界阻塞队列。
- 特点：可以在创建时指定容量，若不指定则默认为 Integer.MAX_VALUE（几乎为无界队列）。
- 锁机制：仅支持非公平锁。
- 应用场景：适合不确定队列大小、可能需要动态调整队列容量的场景。
PriorityBlockingQueue
- 实现方式：无界优先级阻塞队列，支持优先级排序。
- 特点：不按插入顺序出队，而是根据优先级出队。元素必须实现 Comparable 接口，或者在构造时传入 Comparator 对象。
- 应用场景：适合需要按优先级处理任务的场景，如任务调度系统。
SynchronousQueue
- 实现方式：同步队列，不存储元素。
- 特点：每个插入操作都必须等待对应的删除操作，反之亦然。它不保存任何元素，插入和删除操作是直接交换数据的。
- 应用场景：通常用于线程间直接传递数据，适合高效的线程协作场景，如线程池的任务提交与执行。
DelayQueue
- 实现方式：基于优先级队列实现的延迟队列。
- 特点：队列中的元素在达到指定的延迟时间之前，无法出队。每个元素都有一个延迟时间，只有延迟到期的元素才能出队。
- 应用场景：适合需要延时任务执行的场景，如定时任务调度、过期任务清理等。

阻塞队列常见实现类总结

队列类型	特点	锁机制	应用场景
`ArrayBlockingQueue`	基于数组实现的有界阻塞队列	支持公平锁与非公平锁	适用于固定大小的任务队列
`LinkedBlockingQueue`	基于单向链表实现的可选有界阻塞队列	非公平锁	适用于动态调整容量的队列
`PriorityBlockingQueue`	无界优先级阻塞队列，支持优先级排序	不支持公平锁	适用于优先级任务调度
`SynchronousQueue`	不存储元素的同步队列	不适用	适用于线程之间直接数据交换
`DelayQueue`	延迟队列，元素需等待到期后才能出队	不适用	适用于定时任务或过期任务清理

这些实现类各自有不同的特性和应用场景，选择合适的实现类可以帮助开发者更好地进行线程间数据共享和协作。在多线程编程中，阻塞队列是非常重要的工具，能够有效地简化同步问题，提升程序效率。

`ArrayBlockingQueue` 和 `LinkedBlockingQueue` 的区别

ArrayBlockingQueue 和 LinkedBlockingQueue 都是 Java 并发包中的阻塞队列实现，它们的主要区别体现在底层实现、容量限制、锁机制和内存占用等方面。具体来说：

底层实现
- ArrayBlockingQueue：基于数组实现。其底层数据结构是一个固定大小的数组，因此一旦创建，队列的容量是固定的。
- LinkedBlockingQueue：基于链表实现。其底层数据结构是一个双向链表，支持动态增长。
是否有界
- ArrayBlockingQueue：是一个有界队列，必须在创建时指定容量大小，一旦指定容量，队列的大小就不可再变。
- LinkedBlockingQueue：既可以是有界队列，也可以是无界队列。如果在创建时没有指定容量，默认是 Integer.MAX_VALUE，即一个几乎无界的队列；如果指定了容量，它就是有界队列。
锁机制
- ArrayBlockingQueue：采用的是单个锁，即生产和消费都使用同一个锁。这可能会导致生产者和消费者线程之间的锁争用。
- LinkedBlockingQueue：采用的是分离锁机制，即生产者使用 putLock 锁，消费者使用 takeLock 锁。通过将生产和消费操作的锁分离，避免了生产者和消费者线程之间的锁争用，提高了性能。
内存占用
- ArrayBlockingQueue：需要预先分配一个固定大小的数组内存。如果创建时指定的容量很大，即使实际使用的元素较少，也会占用较多的内存空间。内存的分配是静态的，一旦指定容量就无法调整。
- LinkedBlockingQueue：使用链表节点动态分配内存。每次插入一个元素时，会为该元素创建一个新的节点。内存占用随着元素的增加而逐渐增长，通常比 ArrayBlockingQueue 更节省内存，特别是在元素较少时。

总结对比

特性	`ArrayBlockingQueue`	`LinkedBlockingQueue`
底层实现	数组实现	链表实现
队列容量	必须指定大小，有界队列	可以指定大小，也可以是无界队列
锁机制	生产者和消费者共享同一个锁	使用分离的锁（`putLock` 和 `takeLock`）
内存占用	固定容量，提前分配内存	动态分配内存，按需增加内存
适用场景	当需要一个固定大小的队列时	当队列大小不确定或需要动态增长时

选择建议

如果你知道队列的大小，并且需要高效地管理内存，那么 ArrayBlockingQueue 更合适。
如果你需要更灵活的队列大小，或者希望优化生产者和消费者之间的性能，LinkedBlockingQueue 是更好的选择。