一、集合概述

1、Java集合概览

Java 集合，也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 、 Queue。

Java 集合框架如下图所示：

注：图中只列举了主要的继承派生关系，并没有列举所有关系。例如省略了AbstractList, NavigableSet等抽象类以及其他的一些辅助类，如想深入了解，可自行查看源码。

2、说说 List, Set, Queue, Map 四者的区别？

List(对付顺序的好帮手): 存储的元素是有序的、可重复的。
Set(注重独一无二的性质): 存储的元素不可重复的。
Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，"x" 代表 key，"y" 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

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

3.1、 `Collection` 接口下面的集合

3.1.1、List

ArrayList：Object[] 数组。详细可以查看：ArrayList 源码分析。
Vector：Object[] 数组。
LinkedList：双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)。详细可以查看：LinkedList 源码分析。

3.1.2、Set

HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素。
LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。
TreeSet(有序【自动排序】唯一): 红黑树(自平衡的排序二叉树)。

容器类型	是否有序（保持插入顺序）	是否自动排序
`ArrayList`	✅ 是	❌ 否
`LinkedList`	✅ 是	❌ 否
`HashSet`	❌ 否	❌ 否
`LinkedHashSet`	✅ 是	❌ 否
`TreeSet`	❌（按排序顺序）	✅ 是

3.1.3、Queue

PriorityQueue: Object[] 数组来实现小顶堆。详细可以查看：PriorityQueue 源码分析。
DelayQueue:PriorityQueue。详细可以查看：DelayQueue 源码分析。
ArrayDeque: 可扩容动态双向数组。

3.2、 `Map` 接口下面的集合

3.2.1、Map

HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。详细可以查看：HashMap 源码分析。
LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：LinkedHashMap 源码分析
Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。
TreeMap：红黑树（自平衡的排序二叉树）。

4、如何选用集合?

主要根据集合的特点来选择合适的集合。比如：

只需要存放元素值时，就选择实现Collection 接口的集合
- 需要保证元素唯一时选择实现 Set 接口的集合，比如 TreeSet 或 HashSet；
- 不需要保证元素唯一就选择实现 List 接口的集合，比如 ArrayList 或 LinkedList；
然后再根据实现这些接口的集合的特点来选用。
需要根据键值获取到元素值时就选用 Map 接口下的集合
- 需要排序时选择 TreeMap；
- 不需要排序时就选择 HashMap；
- 需要保证线程安全就选用 ConcurrentHashMap；

5、为什么要使用集合？

当我们需要存储一组类型相同的数据时，数组是最常用且最基本的容器之一。但是，使用数组存储对象存在一些不足之处，因为在实际开发中，存储的数据类型多种多样且数量不确定。这时，Java 集合就派上用场了。与数组相比，Java 集合提供了更灵活、更有效的方法来存储多个数据对象。

Java 集合框架中的各种集合类和接口可以存储不同类型和数量的对象，同时还具有多样化的操作方式。相较于数组，Java 集合的优势在于它们的大小可变、支持泛型、具有内建算法等。

总的来说，Java 集合提高了数据的存储和处理灵活性，可以更好地适应现代软件开发中多样化的数据需求，并支持高质量的代码编写。

二、List

1、ArrayList 和 Array（数组）的区别？

ArrayList 内部基于动态数组实现，比 Array（静态数组）使用起来更加灵活：

ArrayList 会根据实际存储的元素动态地扩容或缩容，而 Array 被创建之后就不能改变它的长度了。
ArrayList 允许你使用泛型来确保类型安全，Array 则不可以。
ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。Array 可以直接存储基本类型数据，也可以存储对象。
ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 add()、remove()等。Array 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。
ArrayList 创建时不需要指定大小，而Array创建时必须指定大小。

下面是二者使用的简单对比：

Array：

java

 // 初始化一个 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 ：

java

// 初始化一个 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]

2、ArrayList 和 Vector 的区别?（了解即可）

ArrayList 是 List 的主要实现类，底层使用 Object[]存储，适用于频繁的查找工作，线程不安全。
Vector 是 List 的古老实现类，底层使用Object[] 存储，线程安全。

3、Vector 和 Stack 的区别?（了解即可）

Vector 和 Stack 两者都是线程安全的，都是使用 synchronized 关键字进行同步处理。
Stack 继承自 Vector，是一个后进先出的栈，而 Vector 是一个列表。

随着 Java 并发编程的发展，Vector 和 Stack 已经被淘汰，推荐使用并发集合类（例如 ConcurrentHashMap、CopyOnWriteArrayList 等）或者手动实现线程安全的方法来提供安全的多线程操作支持。

4、ArrayList 可以添加 null 值吗？

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

示例代码：

java

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

输出：

java

[null, java]

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

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

这里简单列举一个例子：

java

// ArrayList的底层数组大小为10，此时存储了7个元素
+---+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |   |   |   |
+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9
// 在索引为1的位置插入一个元素8，该元素后面的所有元素都要向右移动一位
+---+---+---+---+---+---+---+---+---+---+
| 1 | 8 | 2 | 3 | 4 | 5 | 6 | 7 |   |   |
+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9
// 删除索引为1的位置的元素，该元素后面的所有元素都要向左移动一位
+---+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |   |   |   |
+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9

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

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

这里简单列举一个例子：假如我们要删除节点 9 的话，需要先遍历链表找到该节点。然后，再执行相应节点指针指向的更改，具体的源码可以参考：LinkedList 源码分析。

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

RandomAccess 是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于 LinkedList 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 RandomAccess 接口。

8、ArrayList 与 LinkedList 区别?

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

在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 LinkedList 。

另外，不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。在上面也说了，LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的平均时间复杂度都是 O(n) 。

补充内容: 双向链表和双向循环链表

双向链表： 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。
双向循环链表： 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。

补充内容:RandomAccess 接口

java

public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以，在我看来 RandomAccess 接口不过是一个标识罢了。标识什么？标识实现这个接口的类具有随机访问功能。

在 binarySearch() 方法（ java.util.Collections 类提供的静态方法），它要判断传入的 list 是否 RandomAccess 的实例，如果是，调用indexedBinarySearch()方法，如果不是，那么调用iteratorBinarySearch()方法

java

    public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

ArrayList 实现了 RandomAccess 接口，而 LinkedList 没有实现。为什么呢？我觉得还是和底层数据结构有关！ArrayList 底层是数组，而 LinkedList 底层是链表。数组天然支持随机访问，时间复杂度为 O(1)，所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O(n)，所以不支持快速随机访问。ArrayList 实现了 RandomAccess 接口，就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识，并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的！

9、ArrayList 的扩容机制

详见这篇文章: ArrayList 扩容机制分析。

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

关于fail-fast，引用medium中一篇文章关于fail-fast和fail-safe的说法：

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

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

对应的我们给出下面这样一段在示例，我们首先插入100个操作元素，一个线程迭代元素，一个线程删除元素，最终输出结果如愿抛出ConcurrentModificationException：

java

// 如果使用线程安全的 CopyOnWriteArrayList ，可以避免 ConcurrentModificationException
List<Integer> list = new ArrayList<>();
CountDownLatch countDownLatch = new CountDownLatch(2);

// 添加元素
for (int i = 0; i < 100; i++) {
    list.add(i);
}

Thread t1 = new Thread(() -> {
    // 迭代元素 (注意：Integer 是不可变的，这里的 i++ 不会修改 list 中的值)
    for (Integer i : list) {
        try {
            Thread.sleep(1); // 增加延迟，方便 t2 干扰
            i++; // 这行代码实际上没有修改list中的元素
        } catch (Exception e) {
            throw new RuntimeException(e);
        }

    }
    countDownLatch.countDown();
});

Thread t2 = new Thread(() -> {
    System.out.println("删除元素1");
    list.remove(Integer.valueOf(1)); // 使用 Integer.valueOf(1) 删除指定值的对象
    countDownLatch.countDown();
});

t1.start();
t2.start();
countDownLatch.await();

在初始化时插入了100个元素，此时对应的修改modCount次数为100，随后线程 2 在线程 1 迭代期间进行元素删除操作，此时对应的modCount就变为101。线程 1 在随后foreach第 2 轮循环发现modCount 为101，与预期的expectedModCount(值为100因为初始化插入了元素100个)不等，判定为并发操作异常，于是便快速失败，抛出ConcurrentModificationException。

✅ modCount 的本质和用途:

特性	描述
定义位置	`modCount` 是 `ArrayList`、`HashMap`、`HashSet` 等非线程安全集合类中的字段
作用	用来记录“结构性修改”的次数（如：`add`、`remove`）
主要用途	支持 fail-fast 机制，即：在迭代期间如果发现 `modCount` 被修改，就抛出 `ConcurrentModificationException`，快速失败
检查位置	`Iterator` 中的 `next()` 和 `remove()` 方法中检查 `expectedModCount != modCount`

❌ CopyOnWriteArrayList 没有 modCount:

特性	描述
是否线程安全	✅ 是。通过“写时复制”（copy on write）机制实现线程安全
是否有 `modCount` 字段	❌ 没有。它不继承 `AbstractList`，而是直接继承 `Object`
迭代行为	所有迭代器基于当前数组的快照，不受后续修改影响
是否 fail-fast	❌ 不是 fail-fast，因为快照不会感知并发修改，也就没有报错的基础

对此也给出for循环底层迭代器获取下一个元素时的next方法，可以看到其内部的checkForComodification具有针对修改次数比对的逻辑：

java

 public E next() {
 			//检查是否存在并发修改
            checkForComodification();
            //......
            //返回下一个元素
            return (E) elementData[lastRet = i];
        }

final void checkForComodification() {
		//当前循环遍历次数和预期修改次数不一致时，就会抛出ConcurrentModificationException
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

对于fail-safe也就是安全失败，它旨在即使面对意外情况也能恢复并继续运行，这使得它特别适用于不确定或不稳定的环境：
故障安全系统采用的是另一种方法，其目的是在出现意外情况时仍能恢复和继续运行。因此，它们特别适用于不确定或不稳定的环境。
该思想常运用于并发容器，最经典的实现就是CopyOnWriteArrayList的实现，通过写时复制的思想，保证在进行修改操作时复制出一份快照，基于这份快照完成添加或者删除操作后，将CopyOnWriteArrayList底层的数组引用指向这个新的数组空间，由此避免迭代时被并发修改所干扰从而导致并发操作安全问题，当然这种做法也存缺点（即进行遍历操作时无法获得实时结果）：
对应也给出CopyOnWriteArrayList实现fail-safe的核心代码，可以看到它的实现就是通过getArray获取数组引用然后通过Arrays.copyOf得到一个数组的快照，基于这个快照完成添加操作后，修改底层array变量指向的引用地址由此完成写时复制：
java
```
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;
            //array指向新的数组
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }
```

三、Set

1、Comparable 和 Comparator 的区别

Comparable 接口和 Comparator 接口都是 Java 中用于排序的接口，它们在实现类对象之间比较大小、排序等方面发挥了重要作用：

Comparable 接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序
Comparator接口实际上是出自 java.util包，它有一个compare(Object obj1, Object obj2)方法用来排序

一般需要对一个集合使用自定义排序时，就要重写compareTo()方法或compare()方法，当我们需要对某一个集合实现两种排序方式，比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo()方法和使用自制的Comparator方法或者以两个 Comparator 来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的 Collections.sort().

1.1、Comparator 定制排序

java

ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(-1);
arrayList.add(3);
arrayList.add(3);
arrayList.add(-5);
arrayList.add(7);
arrayList.add(4);
arrayList.add(-9);
arrayList.add(-7);
System.out.println("原始数组:");
System.out.println(arrayList);
// void reverse(List list)：反转
Collections.reverse(arrayList);
System.out.println("Collections.reverse(arrayList):");
System.out.println(arrayList);

// void sort(List list),按自然排序的升序排序
Collections.sort(arrayList);
System.out.println("Collections.sort(arrayList):");
System.out.println(arrayList);
// 定制排序的用法
Collections.sort(arrayList, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
});
System.out.println("定制排序后：");
System.out.println(arrayList);

Output:

java

原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后：
[7, 4, 3, 3, -1, -5, -7, -9]

1.2、 Comparable 定制排序

java

// person对象没有实现Comparable接口，所以必须实现，这样才不会出错，才可以使treemap中的数据按顺序排列
// 前面一个例子的String类已经默认实现了Comparable接口，详细可以查看String类的API文档，另外其他
// 像Integer类等都已经实现了Comparable接口，所以不需要另外实现了
public  class Person implements Comparable<Person> {
    private String name;
    private int age;

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

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    /**
     * T重写compareTo方法实现按年龄来升序排序
     */
    @Override
    public int compareTo(Person o) {
        if (this.age > o.getAge()) {
            return 1;
        }
        if (this.age < o.getAge()) {
            return -1;
        }
        return 0;
    }
}

java

    public static void main(String[] args) {
        TreeMap<Person, String> pdata = new TreeMap<Person, String>();
        // 每执行一次 put(...)，TreeMap 都会：
        // ① 调用 Person 的 compareTo 方法；
        // ② 判断新插入的键 Person 对象在树中应该插在哪个位置；
        // ③ 从而确保 TreeMap 内部的结构始终是有序的。
        pdata.put(new Person("张三", 30), "zhangsan");
        pdata.put(new Person("李四", 20), "lisi");
        pdata.put(new Person("王五", 10), "wangwu");
        pdata.put(new Person("小红", 5), "xiaohong");
        // 得到key的值的同时得到key所对应的值
        Set<Person> keys = pdata.keySet();
        for (Person key : keys) {
            System.out.println(key.getAge() + "-" + key.getName());

        }
    }

Output：
java
```
5-小红
10-王五
20-李四
30-张三
```

1.3、Comparable 转 Comparator 排序

java

import java.util.*;

public class PersonComparatorDemo {
    public static void main(String[] args) {
        // 使用 Comparator 定义排序规则
        Comparator<Person> personComparator = new Comparator<Person>() {
            @Override
            public int compare(Person p1, Person p2) {
                // 先按年龄排序
                int ageCompare = Integer.compare(p1.getAge(), p2.getAge());
                if (ageCompare != 0) {
                    return ageCompare;
                }
                // 如果年龄相同，按名字升序排序
                return p1.getName().compareTo(p2.getName());
            }
        };

        // 用自定义 Comparator 创建 TreeMap
        TreeMap<Person, String> pdata = new TreeMap<>(personComparator);

        // 添加数据
        pdata.put(new Person("张三", 30), "zhangsan");
        pdata.put(new Person("李四", 20), "lisi");
        pdata.put(new Person("王五", 10), "wangwu");
        pdata.put(new Person("小红", 5), "xiaohong");
        pdata.put(new Person("小明", 30), "xiaoming");  // 年龄相同测试
        pdata.put(new Person("阿花", 5), "ahua");        // 年龄相同测试

        // 输出结果
        for (Person key : pdata.keySet()) {
            System.out.println(key.getAge() + " - " + key.getName() + " = " + pdata.get(key));
        }
    }
}

// Person 类不实现 Comparable
class Person {
    private String name;
    private int age;

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

    public String getName() { return name; }

    public int getAge() { return age; }
}

输出结果

java

5 - 小红 = xiaohong
5 - 阿花 = ahua
10 - 王五 = wangwu
20 - 李四 = lisi
30 - 小明 = xiaoming
30 - 张三 = zhangsan

1.4 总结

特性	`Comparable<T>` 接口	`Comparator<T>` 接口（或类）
位置	实体类中实现	单独定义，或用匿名类 / Lambda
方法	`int compareTo(T o)`	`int compare(T o1, T o2)`
修改类	需要修改原始类	不需要修改类，外部定义
适用场景	类有固定的自然顺序	类可能有多种排序方式
使用方式	实体类实现接口并重写 `compareTo` 方法	创建 `Comparator` 对象传给排序方法或容器
示例容器支持	`TreeMap` / `TreeSet` / `Collections.sort()` 等	同上（通过构造函数或传参方式）
Java 8+ 推荐	不变	可用 `Comparator.comparing(...)` 更方便

✅ Comparable 详解

✔ 使用条件：

你可以修改实体类代码。
这个类有一个常规或默认的排序规则（比如：年龄、ID、时间戳等）。

✔ 实现方式：

java

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

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

✔ 使用方式：

java

List<Person> list = new ArrayList<>();
Collections.sort(list);  // 自动调用 compareTo()

✅ Comparator 详解

✔ 使用条件：

你不方便或不能修改实体类（比如类来自外部库）。
你需要多个排序规则，比如：
- 按年龄
- 按姓名
- 按多个字段综合比较

✔ 实现方式：

java

Comparator<Person> ageComparator = new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.getAge(), p2.getAge());
    }
};

或 Java 8+ 推荐写法：

java

Comparator<Person> byName = Comparator.comparing(Person::getName);

✔ 使用方式：

java

Collections.sort(list, ageComparator);

在 TreeMap 或 TreeSet 中使用：

java

TreeMap<Person, String> map = new TreeMap<>(ageComparator);

✅ 典型使用场景对比

场景	推荐方式
一个实体类有唯一排序规则（如学生按学号）	`Comparable`
需要对实体类使用多种排序方式（如员工按姓名、年龄、薪资）	`Comparator`
实体类是第三方类，不可修改	`Comparator`
用于 `TreeMap`、`TreeSet` 结构时按特定规则排序	两者均可，建议用 `Comparator` 更灵活

2、无序性和不可重复性的含义是什么

无序性不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的 哈希值 决定的。
不可重复性是指添加的元素按照 equals() 判断时，返回 false，需要同时重写 equals() 方法和 hashCode() 方法。

2.1、不同 Set 的实现比较

实现类	有序性	是否允许重复	说明
`HashSet`	❌ 无序	✅ 不允许	元素根据哈希值存储，性能高但无顺序保证。
`LinkedHashSet`	✅ 有插入顺序	✅ 不允许	元素按插入顺序保存。
`TreeSet`	✅ 有排序顺序	✅ 不允许	元素按自然顺序或自定义 `Comparator` 排序，需要元素可比较。

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

HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。

特性 / 类名	`HashSet`	`LinkedHashSet`	`TreeSet`
所属包	`java.util`	`java.util`	`java.util`
实现接口	`Set`, `Cloneable`, `Serializable`	`Set`, `Cloneable`, `Serializable`	`NavigableSet`, `SortedSet`, `Set`, 等
底层数据结构	哈希表（`HashMap`）	哈希表 + 双向链表	红黑树（自平衡二叉搜索树）
是否保证顺序	❌ 无序	✅ 按插入顺序（FIFO）	✅ 按自然顺序或自定义排序
是否允许重复元素	❌ 不允许	❌ 不允许	❌ 不允许
是否允许 null 元素	✅ 允许一个 null	✅ 允许一个 null	❌ 默认不允许 null（排序需可比）
是否线程安全	❌ 否（需外部同步）	❌ 否（需外部同步）	❌ 否（需外部同步）
排序方式	无序	插入顺序	自然排序 / 自定义 `Comparator`
查询效率	✅ 高（O(1)）	✅ 高（O(1)）	❌ 较低（O(log n)）
适用场景	快速查重，无序集合	需要记录元素插入顺序的去重集合	需要排序、范围查询、有序输出的集合

四、Queue

1、Queue 与 Deque 的区别

1.1、Queue

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

`Queue` 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

1.1.1、`Queue` 抛出异常

当队列满时插入元素，或队列空时移除/访问元素，会抛出异常。

操作类型	方法名	异常类型
插入	`add()`	`IllegalStateException`（如果容量已满）
移除	`remove()`	`NoSuchElementException`（如果队列为空）
检查头部元素	`element()`	`NoSuchElementException`（如果队列为空）

java

import java.util.Queue;
import java.util.LinkedList;

public class ExceptionQueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // 添加元素
        queue.add(1);
        queue.add(2);
        queue.add(3);

        // 移除元素
        System.out.println(queue.remove()); // 输出 1

        // 清空队列
        queue.remove();
        queue.remove();

        // 尝试从空队列移除元素 -> 抛出 NoSuchElementException
        System.out.println(queue.remove());  // ❌ 抛出异常
    }
}

1.1.2、`Queue` 返回特殊值

这些方法在失败时不会抛出异常，而是返回一个特殊值（如 false 或 null）

操作类型	方法名	失败时返回值	成功时返回值
插入	`offer()`	`false`（队满）	`true`
移除	`poll()`	`null`（队空）	队头元素（移除元素）
检查头部元素	`peek()`	`null`（队空）	队头元素

java

import java.util.Queue;
import java.util.LinkedList;

public class GracefulQueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // offer 不会抛异常（LinkedList 无容量限制，永远返回 true）
        System.out.println(queue.offer(1)); // true
        System.out.println(queue.offer(2)); // true

        // 清空队列
        queue.poll();
        queue.poll();

        // 从空队列 poll 和 peek -> 返回 null
        System.out.println(queue.poll());   // null ✅
        System.out.println(queue.peek());   // null ✅
    }
}

1.1.3、🆚 两种方法的适用场景

场景	推荐方法
需要精确控制错误和异常	使用抛异常的方法（如 `add()`、`remove()`）
更偏向稳定、安全运行	使用返回特殊值的方法（如 `offer()`、`poll()`）

1.2、Deque

Deque 是双端队列，在队列的两端均可以插入或删除元素，可以把它看作一个既可以作为队列使用（FIFO），也可以作为栈使用（LIFO）的容器。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

`Deque` 接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

1.2.1、Deque 抛出异常

操作	方法名	异常类型（失败情况）
队首插入	`addFirst(e)`	`IllegalStateException`（容量满）
队尾插入	`addLast(e)`	`IllegalStateException`（容量满）
队首移除	`removeFirst()`	`NoSuchElementException`（队空）
队尾移除	`removeLast()`	`NoSuchElementException`（队空）
查看队首	`getFirst()`	`NoSuchElementException`（队空）
查看队尾	`getLast()`	`NoSuchElementException`（队空）

java

import java.util.Deque;
import java.util.ArrayDeque;

public class DequeExceptionExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>(2);

        deque.addFirst(1);  // ✅ 成功
        deque.addLast(2);   // ✅ 成功
        // deque.addLast(3); // ❌ 抛出 IllegalStateException（如果使用容量受限的 Deque）

        System.out.println(deque.removeFirst()); // 输出 1
        System.out.println(deque.removeLast());  // 输出 2

        // 队列已空，再次移除会抛异常
        System.out.println(deque.removeFirst()); // ❌ 抛出 NoSuchElementException
    }
}

1.2.2、Deque 返回特殊值

操作	方法名	成功时	失败时返回值
队首插入	`offerFirst(e)`	`true`	`false`（满）
队尾插入	`offerLast(e)`	`true`	`false`（满）
队首移除	`pollFirst()`	元素	`null`（空）
队尾移除	`pollLast()`	元素	`null`（空）
查看队首	`peekFirst()`	元素	`null`（空）
查看队尾	`peekLast()`	元素	`null`（空）

java

import java.util.Deque;
import java.util.ArrayDeque;

public class DequeSafeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>(2);

        System.out.println(deque.offerFirst(10));  // true
        System.out.println(deque.offerLast(20));   // true
        System.out.println(deque.offerLast(30));   // false（队满）

        System.out.println(deque.pollFirst());     // 10
        System.out.println(deque.pollLast());      // 20
        System.out.println(deque.pollLast());      // null（队空）

        // peek 方法不移除元素
        System.out.println(deque.peekFirst());     // null
    }
}

1.2.3、🆚 总结

功能	抛异常方法	返回特殊值方法	成功时返回	失败时返回
队首插入	`addFirst(e)`	`offerFirst(e)`	`true`	异常 / `false`
队尾插入	`addLast(e)`	`offerLast(e)`	`true`	异常 / `false`
队首删除	`removeFirst()`	`pollFirst()`	被移除元素	异常 / `null`
队尾删除	`removeLast()`	`pollLast()`	被移除元素	异常 / `null`
队首查看	`getFirst()`	`peekFirst()`	元素	异常 / `null`
队尾查看	`getLast()`	`peekLast()`	元素	异常 / `null`

1.2.4、🔧 常见实现类

ArrayDeque（非线程安全，推荐使用）
LinkedList（也实现了 Deque 接口）
ConcurrentLinkedDeque（线程安全）

2、ArrayDeque 与 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

对比维度	`ArrayDeque`	`LinkedList`
数据结构	动态数组 + 双指针	双向链表
实现接口	`Deque`, `Queue`	`Deque`, `Queue`, `List`
引入版本	JDK 1.6	JDK 1.2
是否支持 `null` 元素	❌ 不支持（`null` 作为空槽，插入 `null` 会抛异常）	✅ 支持
插入/删除性能	均摊 O(1)，但可能扩容	每次插入/删除需新建节点，指针调整，略慢
扩容机制	支持自动扩容（数组翻倍）	无需扩容（链表动态增长）
内存使用	较紧凑，数组连续内存	较大（每个节点额外维护 prev/next 引用）
随机访问性能	❌ 不支持随机访问（无索引方法，底层是循环数组）	✅ 支持（通过 List 接口提供 get(index)）
栈功能支持	✅ 高效支持栈操作（`push/pop/peek`）	✅ 也支持但性能略差
性能建议	性能更好，推荐用于队列或栈实现	功能更通用，但性能略逊
线程安全	❌ 非线程安全（需外部同步）	❌ 非线程安全（需外部同步）

✅ 结论建议

使用场景	推荐选择
实现高性能栈/队列	`ArrayDeque`
需要频繁插入/删除和支持随机访问	`LinkedList`
需要允许 `null` 元素	`LinkedList`
对内存占用敏感	`ArrayDeque`

3、说一说 PriorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

这里列举其相关的一些要点：

PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

维度	说明
引入版本	JDK 1.5
实现接口	`Queue<E>`, `Collection<E>`, `Iterable<E>`
底层数据结构	二叉堆（heap），数组实现（`Object[]`）
默认优先级	小顶堆（最小元素优先出队）
插入/删除复杂度	插入元素 & 删除堆顶元素都是 O(log n)
查询堆顶复杂度	`peek()` 为 O(1)，不移除元素
是否线程安全	❌ 非线程安全，需通过 `PriorityBlockingQueue` 等实现保证线程安全
是否允许 null	❌ 不允许插入 `null` 元素（会抛 `NullPointerException`）
元素要求	元素必须实现 `Comparable` 接口，或提供自定义 `Comparator`
是否支持随机访问	❌ 不支持，仅支持基于优先级的出队访问
可否自定义排序规则	✅ 支持，构造时传入 `Comparator` 来定义优先级

PriorityQueue 在面试中可能更多的会出现在手撕算法的时候，典型例题包括堆排序、求第 K 大的数、带权图的遍历等，所以需要会熟练使用才行。

3.1、示例

示例 1：默认小顶堆（数字从小到大出队）

java

import java.util.PriorityQueue;

public class DefaultPriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.offer(30);
        pq.offer(10);
        pq.offer(20);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());  // 输出顺序：10, 20, 30
        }
    }
}

情况	排序依据	示例
实现了 `Comparable` 接口	自然顺序（`compareTo()` 方法）	`String`、`Date`、`Integer`
提供了 `Comparator` 构造参数	自定义规则	`Comparator.comparing(...)`
都没有	❌ 会抛 `ClassCastException`	自定义类没实现排序接口

示例 2：使用 Comparator 实现大顶堆（数字从大到小出队）

java

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

public class MaxHeapPriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

        pq.offer(30);
        pq.offer(10);
        pq.offer(20);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());  // 输出顺序：30, 20, 10
        }
    }
}

示例 3：自定义对象 + 自定义优先级

java

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

class Task {
    String name;
    int priority;

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public String toString() {
        return name + " (priority: " + priority + ")";
    }
}

public class CustomPriorityQueueDemo {
    public static void main(String[] args) {
        // 优先级越小越先出队（小顶堆）
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority));

        taskQueue.offer(new Task("Task A", 3));
        taskQueue.offer(new Task("Task B", 1));
        taskQueue.offer(new Task("Task C", 2));

        while (!taskQueue.isEmpty()) {
            System.out.println(taskQueue.poll());
        }
        // 输出：
        // Task B (priority: 1)
        // Task C (priority: 2)
        // Task A (priority: 3)
    }
}

示例4：先按年龄升序，再按名字字典序降序

java

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

class Person {
    String name;
    int age;

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

    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class MultiFieldPriorityQueueDemo {
    public static void main(String[] args) {
        // Comparator：先按年龄升序，再按名字降序（字典序逆序）
        Comparator<Person> personComparator = Comparator
                .comparingInt((Person p) -> p.age)
                .thenComparing((Person p) -> p.name, Comparator.reverseOrder());

        PriorityQueue<Person> queue = new PriorityQueue<>(personComparator);

        queue.offer(new Person("Charlie", 30));
        queue.offer(new Person("Alice", 25));
        queue.offer(new Person("Bob", 25));
        queue.offer(new Person("David", 35));
        queue.offer(new Person("Alice", 30));

        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
        
        // 输出结果：
        //  Bob (25)
        //  Alice (25)
        //  Charlie (30)
        //  Alice (30)
        //  David (35)

    }
}

4、什么是 BlockingQueue？

BlockingQueue （阻塞队列）是一个接口，继承自 Queue。BlockingQueue阻塞的原因是其支持当队列没有元素时一直阻塞，直到有元素；还支持如果队列已满，一直等到队列可以放入新元素时再放入。

java

public interface BlockingQueue<E> extends Queue<E> {
  // ...
}

BlockingQueue 常用于生产者-消费者模型中，生产者线程会向队列中添加数据，而消费者线程会从队列中取出数据进行处理。

java

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

public class ProducerConsumerDemo {

    public static void main(String[] args) {
        // 创建一个容量为5的阻塞队列
        BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(5);

        // 启动生产者线程
        new Thread(new Producer(queue), "Producer").start();

        // 启动消费者线程
        new Thread(new Consumer(queue), "Consumer").start();
    }
}

// 生产者类
class Producer implements Runnable {
    private BlockingQueue<Integer> queue;
    private int count = 0;

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

    public void run() {
        try {
            while (true) {
                Thread.sleep(500); // 模拟生产时间
                int item = count++;
                queue.put(item);  // 阻塞方法：如果队列满，会等待
                System.out.println(Thread.currentThread().getName() + " produced: " + item);
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

// 消费者类
class Consumer implements Runnable {
    private BlockingQueue<Integer> queue;

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

    public void run() {
        try {
            while (true) {
                Thread.sleep(800); // 模拟消费时间
                int item = queue.take(); // 阻塞方法：如果队列空，会等待
                System.out.println(Thread.currentThread().getName() + " consumed: " + item);
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

✅ 输出示例（节选）

Producer produced: 0
Consumer consumed: 0
Producer produced: 1
Producer produced: 2
Consumer consumed: 1
Producer produced: 3
Consumer consumed: 2

✅ 关键点说明

方法	行为描述
`put(E e)`	若队列满，阻塞直到有空间可插入
`take()`	若队列空，阻塞直到有元素可取出
`offer(E e)`	若队列满，返回 `false`（非阻塞）
`poll()`	若队列空，返回 `null`（非阻塞）

✅ 可替换的 BlockingQueue 实现类

类名	特点说明
`ArrayBlockingQueue`	有界队列，数组实现，必须指定容量
`LinkedBlockingQueue`	可选有界/无界，链表实现，默认最大容量是 `Integer.MAX_VALUE`（默认足够大，可视为无界）
`PriorityBlockingQueue`	支持优先级出队（非 FIFO），无界
`DelayQueue`	元素延迟后才能取出
`SynchronousQueue`	不存储元素，每个 put 必须等待 take

5、BlockingQueue 的实现类有哪些？

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

ArrayBlockingQueue：使用数组实现的有界阻塞队列。在创建时需要指定容量大小，并支持公平和非公平两种方式的锁访问机制。
LinkedBlockingQueue：使用单向链表实现的可选有界阻塞队列。在创建时可以指定容量大小，如果不指定则默认为Integer.MAX_VALUE。和ArrayBlockingQueue不同的是，它仅支持非公平的锁访问机制。
PriorityBlockingQueue：支持优先级排序的无界阻塞队列。元素必须实现Comparable接口或者在构造函数中传入Comparator对象，并且不能插入 null 元素。
SynchronousQueue：同步队列，是一种不存储元素的阻塞队列。每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作。因此，SynchronousQueue通常用于线程之间的直接传递数据。
DelayQueue：延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队。
……

日常开发中，这些队列使用的其实都不多，了解即可。

6、ArrayBlockingQueue 和 LinkedBlockingQueue 有什么区别？

ArrayBlockingQueue 和 LinkedBlockingQueue 是 Java 并发包中常用的两种阻塞队列实现，它们都是线程安全的。不过，不过它们之间也存在下面这些区别：

底层实现：ArrayBlockingQueue 基于数组实现，而 LinkedBlockingQueue 基于链表实现。
是否有界：ArrayBlockingQueue 是有界队列，必须在创建时指定容量大小。LinkedBlockingQueue 创建时可以不指定容量大小，默认是Integer.MAX_VALUE，也就是无界的。但也可以指定队列大小，从而成为有界的。
锁是否分离： ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁；LinkedBlockingQueue中的锁是分离的，即生产用的是putLock，消费是takeLock，这样可以防止生产者和消费者线程之间的锁争夺。
内存占用：ArrayBlockingQueue 需要提前分配数组内存，而 LinkedBlockingQueue 则是动态分配链表节点内存。这意味着，ArrayBlockingQueue 在创建时就会占用一定的内存空间，且往往申请的内存比实际所用的内存更大，而LinkedBlockingQueue 则是根据元素的增加而逐渐占用内存空间。

7、为什么链表实现的LinkedBlockingQueue 有上界

✅ 1.链表确实可以动态扩展，但不是无限制的

链表确实不像数组那样固定容量，它可以动态添加节点，从结构上讲没有固定边界。

但是：

Java 中的 LinkedBlockingQueue 是为了线程安全而设计的，并强制支持“容量限制”，这是出于控制并发行为和系统资源的考虑，而非结构限制。

✅ 2.容量上限是为了防止内存无限增长

即使链表可以不断扩展，如果不设限：

生产者线程不断往队列中 put() 元素
而消费者处理不过来
元素会不断堆积，最终导致 内存泄露 或 OOM（OutOfMemoryError）

因此：

LinkedBlockingQueue 强制要求设置一个容量限制（即使你不传，会默认用一个非常大的值），就是为了防止生产过快而系统崩溃。

✅ 3. 并发条件下必须有界限来实现阻塞控制

BlockingQueue 的特点是：

put()：如果队列已满 → 阻塞
take()：如果队列为空 → 阻塞

如果没有容量上限，put() 就永远不会阻塞。

这就违背了 BlockingQueue 的初衷：

让生产者/消费者通过阻塞协调速度，而不是无限推进。

✅ 4. 源码设计体现了“有界链表”的意图

来看 LinkedBlockingQueue 的源码结构（简化）：

java

public class LinkedBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {

    static class Node<E> {
        E item;
        Node<E> next;
    }

    /** 队列的容量 */
    private final int capacity;

    /** 当前元素数量 */
    private final AtomicInteger count = new AtomicInteger();

    ...
}

capacity 是一个 final 值 —— 表示队列最大容量
默认构造函数传入的是 Integer.MAX_VALUE，就是为了让你能自己控制上限
内部通过 count 来限制 put() 和 take() 是否阻塞

✅ 总结：为什么链表结构还要有上界？

原因分类	说明
不是结构限制	链表可以动态扩展，但并发队列关注的是资源使用和线程协调
防止 OOM	没有容量限制，生产过快会导致内存泄露或崩溃
控制阻塞行为	`put()` 需要在满时阻塞，必须知道“满”的定义 —— 所以必须有 `capacity` 参数
线程安全设计	用 `AtomicInteger` 精确统计数量，配合 `capacity` 限制并发访问

★重要知识点

★源码分析

★重要知识点

一、集合概述 ​

1、Java集合概览 ​

2、说说 List, Set, Queue, Map 四者的区别？ ​

3、集合框架底层数据结构总结 ​

3.1、 Collection 接口下面的集合 ​

3.1.1、List ​

3.1.2、Set ​

3.1.3、Queue ​

3.2、 Map 接口下面的集合 ​

3.2.1、Map ​

4、如何选用集合? ​

5、为什么要使用集合？ ​

二、List ​

1、ArrayList 和 Array（数组）的区别？ ​

2、ArrayList 和 Vector 的区别?（了解即可） ​

3、Vector 和 Stack 的区别?（了解即可） ​

4、ArrayList 可以添加 null 值吗？ ​

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

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

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

8、ArrayList 与 LinkedList 区别? ​

补充内容: 双向链表和双向循环链表 ​

补充内容:RandomAccess 接口 ​

9、ArrayList 的扩容机制 ​

10、集合中的 fail-fast 和 fail-safe 是什么 ​

三、Set ​

1、Comparable 和 Comparator 的区别 ​

1.1、Comparator 定制排序 ​

1.2、 Comparable 定制排序 ​

1.3、Comparable 转 Comparator 排序 ​

1.4 总结 ​

2、无序性和不可重复性的含义是什么 ​

2.1、不同 Set 的实现比较 ​

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

四、Queue ​

1、Queue 与 Deque 的区别 ​

1.1、Queue ​

1.1.1、Queue 抛出异常 ​

1.1.2、Queue 返回特殊值 ​

1.1.3、🆚 两种方法的适用场景 ​

1.2、Deque ​

1.2.1、Deque 抛出异常 ​

1.2.2、Deque 返回特殊值 ​

1.2.3、🆚 总结 ​

1.2.4、🔧 常见实现类 ​

2、ArrayDeque 与 LinkedList 的区别 ​

3、说一说 PriorityQueue ​

3.1、示例 ​

示例 1：默认小顶堆（数字从小到大出队） ​

示例 2：使用 Comparator 实现大顶堆（数字从大到小出队） ​

示例 3：自定义对象 + 自定义优先级 ​

示例4：先按年龄升序，再按名字字典序降序 ​

4、什么是 BlockingQueue？ ​

5、BlockingQueue 的实现类有哪些？ ​

6、ArrayBlockingQueue 和 LinkedBlockingQueue 有什么区别？ ​

7、为什么链表实现的LinkedBlockingQueue 有上界 ​

一、集合概述

1、Java集合概览

2、说说 List, Set, Queue, Map 四者的区别？

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

3.1、 `Collection` 接口下面的集合

3.1.1、List

3.1.2、Set

3.1.3、Queue

3.2、 `Map` 接口下面的集合

3.2.1、Map

4、如何选用集合?

5、为什么要使用集合？

二、List

1、ArrayList 和 Array（数组）的区别？

2、ArrayList 和 Vector 的区别?（了解即可）

3、Vector 和 Stack 的区别?（了解即可）

4、ArrayList 可以添加 null 值吗？

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

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

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

8、ArrayList 与 LinkedList 区别?

补充内容: 双向链表和双向循环链表

补充内容:RandomAccess 接口

9、ArrayList 的扩容机制

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

三、Set

1、Comparable 和 Comparator 的区别

1.1、Comparator 定制排序

1.2、 Comparable 定制排序

1.3、Comparable 转 Comparator 排序

1.4 总结

2、无序性和不可重复性的含义是什么

2.1、不同 Set 的实现比较

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

四、Queue

1、Queue 与 Deque 的区别

1.1、Queue

1.1.1、`Queue` 抛出异常

1.1.2、`Queue` 返回特殊值

1.1.3、🆚 两种方法的适用场景

1.2、Deque

1.2.1、Deque 抛出异常

1.2.2、Deque 返回特殊值

1.2.3、🆚 总结

1.2.4、🔧 常见实现类

2、ArrayDeque 与 LinkedList 的区别

3、说一说 PriorityQueue

3.1、示例

示例 1：默认小顶堆（数字从小到大出队）

示例 2：使用 Comparator 实现大顶堆（数字从大到小出队）

示例 3：自定义对象 + 自定义优先级

示例4：先按年龄升序，再按名字字典序降序

4、什么是 BlockingQueue？

5、BlockingQueue 的实现类有哪些？

6、ArrayBlockingQueue 和 LinkedBlockingQueue 有什么区别？

7、为什么链表实现的LinkedBlockingQueue 有上界