容器总览

整体认知

Java 容器（Collections）是用来“装对象的对象”，即集合类框架，整体由 两大核心接口 构成：

一、Collection 接口 —— 单值集合体系

用于表示一组元素的“集合”，即一个一个元素地存储。

✅ 类比 C++ STL 中的 vector、list、set、queue 等

主要子接口与实现类：

二、Map：键值对映射体系

存储 key-value 形式的数据，常用于快速查找，不属于 Collection 接口体系。

✅ 类比 C++ STL 中的 map、unordered_map

常见实现类：

学习顺序：

• List 接口（线性结构）
  • ArrayList：基于动态数组，支持随机访问，增删效率相对较低。
  • LinkedList：基于双向链表，插入删除快，但不支持快速随机访问。
  • Vector：线程安全的动态数组，已较少使用，了解其同步机制即可。
• Set 接口（去重集合）
  • HashSet：基于 HashMap，无序、唯一。
  • LinkedHashSet：保留插入顺序。
  • TreeSet：基于红黑树，自动排序。
• Queue / Deque 接口（队列结构）
  • Queue（如 PriorityQueue）：优先级队列，非 FIFO。
  • Deque（如 ArrayDeque、LinkedList）：双端队列，支持栈、队列双重操作。
• Map 接口（键值对映射）
  • HashMap：最常用，基于哈希表。
  • LinkedHashMap：有序版本的 HashMap。
  • TreeMap：自动排序的 Map，基于红黑树。

List

List 是 Java 集合框架中最常用的接口之一，继承自Collection，具有以下核心特性：

• 有序性：元素按插入顺序存储，支持通过索引（下标）访问元素。
• 可重复性：允许存储重复元素。
• 丰富的操作接口：提供get(int index)、add(int index, E element)、remove(int index)等基于索引的操作方法，方便数据的随机访问和位置调整。

核心实现类：ArrayList、LinkedList、Vector，分别基于动态数组、双向链表、线程安全动态数组实现，适用场景各异。

ArrayList

  Java中 `ArrayList` 是基于**动态数组**实现的可变长度顺序表，支持快速随机访问（O(1)），但插入、删除需移动元素，效率较低（O

(n)），是查找频繁、插入删除较少场景的首选容器。

  它底层使用 Object[] 存储元素，采用懒惰初始化机制：无参构造时初始化为空数组，首次添加元素时才分配默认容量

10。添加元素时会先检查剩余空间是否充足，若不足则触发扩容，扩容策略为oldCapacity + (oldCapacity >> 1)，约等于原容量的 1.5 倍，若仍不足则直接取所需容量。由于扩容需要通过 Arrays.copyOf() 复制原数组，代价较高，建议通过预估容量，减少扩容频率。

  另外，`ArrayList` 是非线程安全的，多线程场景可通过`Collections.synchronizedList(new ArrayList<>())`或并发容器`CopyOnWriteArrayList`（写时复制，适用于读多写少场景）保证安全。

  它支持 fail-fast 机制：迭代过程中若集合结构被修改（如增删元素），会通过`modCount`变量校验触发`ConcurrentModificationException`，防止脏读。

在序列化方面，ArrayList 将底层数组声明为transient，避免默认序列化整个数组，同时通过自定义writeObject和readObject方法，仅序列化实际存储的有效元素（即size范围内的元素），优化了空间使用效率。

常见问法：

• ArrayList 的默认初始容量是多少？何时分配？

  • 默认初始容量为 10，但采用懒惰初始化—— 无参构造时底层数组初始化为空数组（DEFAULTCAPACITY_EMPTY_ELEMENTDATA），首次添加元素时才分配 10 的容量。

• 为什么扩容是 1.5 倍而非 2 倍？

  • 1.5 倍是空间与效率的折中：避免像 Vector 2 倍扩容那样浪费过多空间，同时减少频繁扩容的性能开销（例如原容量 10 → 15 比 10 → 20 更节省内存）。

• ArrayList 的 trimToSize() 方法有什么用？

  • 将底层数组容量缩为当前元素数量（size），释放未使用空间。适用于固定大小列表以节省内存，但可能触发数组复制（O (n)）。

• ArrayList 插入元素时，数组越界是如何处理的？

  • 添加元素前会调用 ensureCapacityInternal() 检查容量，若不足则触发扩容（通过 grow() 方法），确保数组不会越界。

• ArrayList 的 modCount 有什么作用？

  • 记录集合结构修改次数（增删操作），用于实现 fail-fast 机制。迭代器初始化时保存 modCount，遍历时检测到不一致则抛出 ConcurrentModificationException。

• ArrayList的set(int index, E element)会触发Fail-Fast吗？

  • 不会，**set()**仅替换元素，不改变结构（modCount不变），不会触发异常。

• 如何安全删除 ArrayList 中的元素？

  • 使用 迭代器的 remove() 方法，它会同步更新 modCount，避免触发异常。例如：

    Iterator<String> it = list.iterator();
    while (it.hasNext()) {
        if (条件) {
            it.remove(); // 安全删除
        }
    }
    ```
- **ArrayList 与** `Arrays.asList()` **返回的列表有什么区别？**

  - `Arrays.asList()` 返回的是 **固定大小列表**，不支持增删操作（调用会抛 `UnsupportedOperationException`）；
  - ArrayList 是动态可变的，支持扩容和增删。
- **ArrayList 可以存储基本数据类型吗？**

  - 不能直接存储，需使用包装类（如 `Integer`、`Long`）。例如：

```java
    ArrayList<Integer> list = new ArrayList<>(); // 正确
    // ArrayList<int> list = new ArrayList<>(); // 错误
    ```

    原因见泛型。
- **ArrayList 在多线程下的安全替代方案有哪些？**

  - **同步包装**：`Collections.synchronizedList(new ArrayList<>())`；
  - **并发容器**：`CopyOnWriteArrayList`（写时复制，适用于读多写少）。
- **ArrayList 的** `addAll()` **方法效率如何？**

  - 批量添加元素时，会先计算所需容量并扩容一次（若需要），避免多次扩容。但复制数组仍需 O (n) 时间，整体效率高于循环单元素添加。

### LinkedList

       Java中`LinkedList`是基于**双向链表**实现的集合类，底层由节点（Node）构成，每个节点存储元素值、前驱和后继指针。它支持两端高效插入/删除（O(1)），但随机访问需遍历链表（O(n)），即使通过二分法优化遍历方向（前半部分从头找，后半部分从尾找），本质仍为线性查找，此外，它兼具`List`和`Deque`接口功能，可作为列表、队列或栈使用，但真要用到队列或栈还是推荐使用`ArrayDeque`。
适用于头尾操作频繁场景（如消息队列、栈），或数据动态变化、无需随机访问的场景。

        添加元素仅需调整指针，无需扩容；删除时主动断开节点引用（如`x.item = null`），避免内存泄漏。支持`null`元素，非线程安全，遍历中结构修改会触发fail-fast机制（抛ConcurrentModificationException），需用迭代器`remove()`安全操作。

        多线程下可通过`Collections.synchronizedList()`包装，或改用并发容器（如无锁的`ConcurrentLinkedQueue`、阻塞式的`LinkedBlockingQueue`）。

**常见问法：**

- LinkedList 和 ArrayList 有什么区别？
  - 前者是双向链表（增删快、查找慢），后者是动态数组（查找快、增删慢）。
- LinkedList 是怎么实现插入删除的？为什么效率高？
  - 头尾操作仅改指针（O (1)），无需移动元素。
- 为什么不推荐用 LinkedList 查找元素？
  - 无索引，需遍历链表（O (n)），效率低。
- 如何安全删除 LinkedList 中的元素？
  - 用迭代器 it.remove()，避免直接修改集合。
- LinkedList 是线程安全的吗？并发场景怎么使用？
  - 非线程安全，并发时用`Collections.synchronizedList()`或并发队列（如`ConcurrentLinkedQueue`/`LinkedBlockingQueue`）。

### Vector

      Vector 是 Java 早期基于动态数组实现的线程安全列表，底层通过 `Object[]` 存储元素。其默认初始容量为
10，扩容时按原容量的 2 倍增长（也可通过参数指定增量），支持快速随机访问（O(1)），但插入、删除操作需移动元素，效率较低（O(n)）。

     所有公共方法通过 `synchronized` 修饰保证线程安全，适用于多线程环境下需要线程安全且插入删除不频繁的场景（如共享数据读写）。但由于同步机制带来的性能开销，其单线程性能低于
ArrayList，现代开发中更推荐使用 `ArrayList` 结合 `Collections.synchronizedList()` 或并发容器（如 `CopyOnWriteArrayList`）替代。

**常见问法：**

- Vector 的底层数据结构是什么？
  - 基于动态数组（Object []）实现，类似 ArrayList，但线程安全。
- Vector 如何实现线程安全？
  - 方法通过 `synchronized` 关键字修饰（如 `add()`、`get()` 等），确保多线程下操作的原子性。
- Vector 和 ArrayList 的主要区别是什么？
  - 线程安全：Vector 线程安全（同步），ArrayList 非线程安全（异步）。
  - 扩容策略：Vector 默认扩容为原容量的 2 倍（可通过构造方法指定扩容倍数），ArrayList 为 1.5 倍。
  - 性能：Vector 因同步机制性能略低，适用于多线程场景；ArrayList 适用于单线程或线程安全可控场景。
- Vector 的扩容机制是怎样的？默认扩容倍数是多少？
  - 当元素数量超过容量时触发扩容，默认新容量为 原容量的 2 倍（可通过 `capacityIncrement` 参数自定义倍数）。
- 为什么 Vector 的扩容默认是 2 倍，而 ArrayList 是 1.5 倍？
  - Vector 早期设计更注重减少扩容频率（牺牲空间换时间），ArrayList 更注重节省内存（1.5 倍更折中）。
- Vector 适合在什么场景下使用？
  - 多线程环境中需要线程安全的列表操作（如共享数据的读写）。
  - 需要频繁扩容但对内存不敏感的场景（因扩容倍数较大，空间浪费可能更多）。
- Vector 的缺点是什么？
  - 同步机制导致性能较低，单线程场景下不如 ArrayList 高效。
  - 扩容时默认增长 2 倍，可能比 ArrayList 更占内存。
  - 适配性差，现代多线程场景更推荐并发容器（如 CopyOnWriteArrayList）。
- Vector 是否支持 null 元素？
  - 支持，允许存储 null（与 ArrayList 一致）。
- Vector 如何遍历？是否支持 fail-fast 机制？
  - 支持 `for`、`foreach`、`Iterator` 等遍历方式，不支持
    fail-fast（迭代过程中结构修改不会抛出异常，但可能读取到不一致的数据）。
- 如何提升 Vector 的性能？
  - 预指定初始容量，减少扩容次数；
  - 若单线程场景，可转为 ArrayList（需手动处理线程安全）。
- **Vector的现代替代方案？**

  - 多线程场景 → **CopyOnWriteArrayList**（读多写少）、**ConcurrentLinkedQueue**（高并发队列）。
  - 需同步的List → **Collections.synchronizedList(new ArrayList<>())**。

### 对比

1. 线程安全：

   - Vector 是唯一线程安全的列表，但性能代价高；
   - ArrayList/LinkedList 可通过 `Collections.synchronizedList()` 或并发容器（如 `CopyOnWriteArrayList`）实现线程安全。
2. 数据结构特性：

   - ArrayList 适合 “随机访问优先” 的场景（如分页查询、数组操作）；
   - LinkedList 适合 “增删优先” 的场景（如链表操作、双端队列）；
   - Vector 适合 “多线程 + 随机访问” 的场景（如旧系统中的线程安全列表）。
3. 内存占用：
   - ArrayList/Vector 紧凑（数组无额外指针）
   - LinkedList 较高（每个节点含前驱 / 后继指针）
4. 扩容与性能：

   - ArrayList 扩容更节省内存（1.5 倍），Vector 扩容更激进（2 倍）；
   - LinkedList 无扩容问题，但查找性能差。
5. 现代开发建议：

   - 单线程场景：ArrayList（首选）或 LinkedList（增删密集）；
   - 多线程场景：ArrayList + 同步工具 或 并发容器（如 `CopyOnWriteArrayList`），避免直接使用
     Vector（性能较低）。

## Set

<a href="/vault/2-Learning/04-Java/02-Java%E5%AE%B9%E5%99%A8/02-Set%E7%B3%BB%E5%88%97/00-Set%E6%80%BB%E8%A7%88">Set</a> 是 Java 集合框架中的一个核心接口，继承自 Collection，主要特点是：

- **不允许重复元素**（根据 equals/hashCode 判定）
- **无索引访问**（不支持 get(index)）
- **常用于去重或存储唯一性数据**

核心实现类：`HashSet`、`LinkedHashSet`、`TreeSet`。

### HashSet

`HashSet` **是 Java 中基于** `HashMap` **实现的无序集合，其底层通过将元素作为键（Key）存储，值（Value）统一使用静态常量** `PRESENT` **作为占位符。**

为了确保元素的唯一性，HashSet 依赖元素的 `hashCode()` 和 `equals()` 方法：插入元素时，先通过 `hashCode()` 计算哈希值定位桶（Bucket），若该位置为空则直接插入；若已有元素，则再通过 `equals()` 判断是否相等，若相等则视为重复，不插入，若不相等则通过链地址法（链表或红黑树）进行存储。

需要特别注意的是：如果只重写了 `equals()` 而未重写 `hashCode()`，相等的对象可能被散列到不同桶中，导致集合中出现重复元素；反之亦然。因此，自定义类作为
HashSet 元素时，必须同时重写这两个方法，且需保证相等的对象具有相同的哈希值。

在哈希分布良好、冲突较少的情况下，HashSet 的 `add`、`remove` 和 `contains` 操作的平均时间复杂度为 **O(1)**。在极端情况下（如所有元素哈希值相同），JDK
7 及之前版本中退化为链表，操作复杂度变为 O(n)；而在 JDK 8 之后，当链表长度 ≥ 8 且桶总数 ≥ 64 时，会自动将该桶结构转换为红黑树，从而将查找复杂度降低为
O(log n)。

HashSet 的默认负载因子为 0.75，意味着当元素数量超过容量的 75% 时将触发扩容（新容量为原来的 2 倍）。合理地预估并设置初始容量，有助于减少扩容次数，降低
rehash 带来的性能损耗。

此外，HashSet：

- **允许存储一个 null 元素**
- **不保证元素的存储顺序**
- **不是线程安全的**

常用于高效去重、快速存在性判断、集合运算（如交集、并集、差集）等场景。

**常见问法：**

- HashSet 中是如何判断重复元素的？
  - 先用 hashCode 定位桶，再用 equals 判断。
- HashSet 能存 null 吗？
  - 可以，最多一个。
- 为什么 HashSet 查找快？
  - 基于哈希表，平均复杂度 O(1)。
- JDK8 之后 HashSet 做了哪些优化？
  - 链表转红黑树，提高高冲突场景的性能。
- JDK 8 链表转红黑树的阈值为何是 8？

  - 哈希冲突遵循泊松分布，链表长度达到 8 的概率极低（约 1e-6）。此阈值是对极端情况的保护，避免恶意哈希攻击导致性能骤降。
- 为何扩容时容量翻倍？

  - 位运算优化：翻倍后新容量为 2 的幂，计算桶位置时可通过 hash & (capacity - 1) 替代取模运算，提升效率。
  - 分散冲突：翻倍扩容使元素重新散列到新桶，可能减少链表长度或树化概率。
- HashSet 是线程安全的吗？如何变线程安全？
  - 否，可用 Collections.synchronizedSet 包装或使用并发容器。

### LinkedHashSet

`LinkedHashSet` 是 `HashSet` 的有序扩展，基于 `LinkedHashMap` 实现，通过哈希表与双向链表的组合，在保证元素唯一性和高效去重性能（插入、查询平均
O (1) 复杂度）的同时，默认按元素插入顺序维护遍历顺序，也可通过参数配置为访问顺序（最近访问的元素移至链表尾部）。其底层将元素作为 `LinkedHashMap` 的键存储，值统一使用占位符，双向链表节点记录前驱和后继关系，例如依次插入
“B”“A”“C” 时，遍历时会严格按 “B→A→C” 的顺序返回，而非哈希表的存储顺序。这种实现方式在插入时需额外维护链表指针（导致略高的内存占用和少许性能损耗），但换来了可预测的有序遍历，适用于日志去重（保留时间顺序）、LRU
缓存（结合访问顺序）、有序集合运算等场景，是需要有序性但无需排序逻辑时的理想选择，兼顾了 HashSet 的高效性与链表的顺序特性。

**常见问法：**

- LinkedHashSet 如何保证元素有序？

  - 通过双向链表维护元素的插入顺序（默认）或访问顺序（需显式配置），遍历时直接沿链表顺序访问，与元素在哈希表中的存储位置无关。
- LinkedHashSet 的插入性能比 HashSet 慢多少？

  - 理论上略慢，因需额外操作双向链表（如更新前驱 / 后继指针），但实际差异通常可忽略不计（尤其在数据量不大时）。
- LinkedHashSet 是否允许 null 元素？

  - 允许，与 HashSet 一致，最多存储一个 null 元素。
- 如何启用访问顺序模式？

  - 无法直接通过 LinkedHashSet 的构造函数配置，需通过 LinkedHashMap 间接实现：

```java
    LinkedHashMap<String, Object> map = new LinkedHashMap<>(16, 0.75f, true);
    Set<String> accessOrderedSet = map.keySet(); // 访问顺序的 Set
    ```
- LinkedHashSet 的遍历性能为何优于 TreeSet？

  - TreeSet 基于红黑树，遍历时需中序遍历（时间复杂度 O (n)），而 LinkedHashSet 直接沿双向链表顺序访问，无需排序操作，效率更高。
- LinkedHashSet 与 LinkedHashMap 的区别？

  - LinkedHashSet 是 Set 接口的实现，仅存储键，值统一为占位符；LinkedHashMap 是 Map 接口的实现，存储键值对，支持按插入
    / 访问顺序维护。
- 什么场景下应选择 LinkedHashSet 而非 TreeSet？

  - 仅需保留元素插入顺序，无需排序（如日志去重）。
  - 需频繁遍历集合，且期望稳定的 O (n) 时间复杂度。
  - LinkedHashSet 的线程安全版本如何实现？

    与 HashSet 类似，使用 `Collections.synchronizedSet()` 包装：

```java
    Set<String> safeSet = Collections.synchronizedSet(new LinkedHashSet<>());
    ```
- LinkedHashSet 的内存占用比 HashSet 高多少？

  - 每个元素需额外存储两个指针（前驱 / 后继），内存开销约增加 50%（视元素本身大小而定）。
- 如何利用 LinkedHashSet 实现 LRU 缓存？

  - 通过 LinkedHashMap 的访问顺序模式结合容量限制：

```java
    LinkedHashMap<K, V> cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity; // 超出容量时淘汰最旧元素
        }
    };
    ```

### TreeSet

`TreeSet` 是 Java 集合框架中基于红黑树实现的有序集合，作为 `TreeMap` 的键视图，它将元素存储为键、值统一为静态占位符，其去重逻辑与 `HashSet`、`LinkedHashSet` 不同，不依赖元素的 `equals()` 和 `hashCode()`，而是通过自然排序（元素实现 `Comparable` 接口）或定制排序（传入 `Comparator` 接口）维护元素顺序
—— 当元素通过 `compareTo()` 或 `Comparator` 比较结果为 0 时即视为重复元素，即便 `equals()` 返回
false 也不会存储（尽管如此，为避免逻辑混乱，通常建议保证当 a.compareTo (b) == 0 时 a.equals (b) 为
true）。

这种基于红黑树的实现使得插入、删除、查询操作的时间复杂度均为 O (log n)，并提供了 subSet、lower、higher 等高效范围查询方法，非常适用于需要排序或区间筛选的场景，例如数值统计、年龄分段查询等。

不过，TreeSet 要求元素必须可比较（实现 Comparable 或提供 Comparator），且不支持存储 null 值，同时由于红黑树节点需要额外存储父节点、左右子节点及颜色标记，其内存占用要高于基于哈希表的
HashSet 和 LinkedHashSet。

**常见问法：**

- TreeSet 如何实现排序？
  - 自然排序：元素需实现 `Comparable` 接口（如 `Integer`、`String`），按 `compareTo()` 方法排序。
  - 定制排序：通过构造函数传入 `Comparator` 接口实现自定义排序逻辑（如逆序、按属性排序）。
  - 注意：若元素未实现 `Comparable` 且未指定 `Comparator`，插入时会抛出 `ClassCastException`。
- TreeSet 是否允许重复元素？
  - 逻辑去重：当两个元素通过 `compareTo()`（自然排序）或 `Comparator`（定制排序）比较结果为 `0` 时，视为
    “重复”，仅保留一个。
  - 与 `equals()` 无关：即使 `equals()` 返回 `false`，只要比较结果为 `0`，仍视为重复（可能导致
    “逻辑重复” 问题）。
- TreeSet 是否允许 `null` 值？
  - 不允许：插入 `null` 会抛出 `NullPointerException`（红黑树的比较逻辑不支持 `null`）。
  - 对比 `HashSet`：`HashSet` 允许单个 `null`，而 `TreeSet` 完全不支持。
- TreeSet 的底层数据结构是什么？
  - 基于 红黑树（自平衡二叉搜索树）实现，通过颜色标记和旋转操作保持平衡，确保插入、删除、查询的时间复杂度均为 O(log n)。
  - 内部通过 `TreeMap` 存储元素，元素作为 `Key`，`Value` 统一为静态占位符 `PRESENT`。
- TreeSet 如何实现范围查询？
  - 提供 `NavigableSet` 接口的范围操作方法：
    - `subSet(from, to)`：返回 [from, to) 区间的子集（左闭右开）。
    - `headSet(to, inclusive)`：返回小于等于 `to` 的元素（`inclusive` 为 `true` 时包含 `to`）。
    - `tailSet(from, inclusive)`：返回大于等于 `from` 的元素（`inclusive` 为 `true` 时包含 `from`）。
  - 边界查询方法：`lower()`、`higher()`、`floor()`、`ceiling()` 等，用于快速定位相邻元素。
- TreeSet 的线程安全性如何？
  - 非线程安全：多线程环境下并发操作可能导致数据不一致。
  - 解决方案：使用 `Collections.synchronizedSortedSet(new TreeSet<>())` 包装，手动添加同步控制。
- 自定义类如何使用 TreeSet？
  - 方案 1：类实现 `Comparable` 接口，重写 `compareTo()` 方法。

```java
    class User implements Comparable<User> {
        private int age;
        @Override
        public int compareTo(User o) {
            return Integer.compare(age, o.age); // 按年龄排序
        }
    }
    ```
  - 方案 2：创建 `TreeSet` 时传入 `Comparator` 匿名内部类或 lambda。

```java
    TreeSet<User> set = new TreeSet<>((u1, u2) -> u2.getAge() - u1.getAge()); // 逆序排序
    ```
- TreeSet 的性能如何？
  - 优点：排序和范围查询高效（O (log n)），适用于需要有序性和区间操作的场景。
  - 缺点：空间开销高于 `HashSet`（需存储树节点指针和颜色标记），插入 / 查询性能略低于哈希表。
- 如何避免 TreeSet 中的逻辑重复问题？
  - 确保元素的 `compareTo()`（或 `Comparator`）与 `equals()` 逻辑一致：
    - 若 `a.compareTo(b) == 0`，则 `a.equals(b)` 应返回 `true`，否则可能导致集合中存在
      “相等但不重复” 的元素。

### 对比

1. 无序 vs 有序：

   - `HashSet` 完全无序，适用于仅需去重的场景。
   - `LinkedHashSet` 按插入顺序维护顺序，适合需要保留操作顺序的场景（如用户操作记录去重）。
   - `TreeSet` 按排序规则（自然 / 定制）维护顺序，适合需要排序或范围查询的场景（如数值统计、年龄区间筛选）。
2. 性能与数据结构：

   - `HashSet` 基于哈希表，平均性能最优，适合高频插入 / 查询。
   - `LinkedHashSet` 因维护双向链表，内存和插入性能略低，但遍历顺序稳定。
   - `TreeSet` 基于红黑树，排序和范围查询高效，但空间开销大，单元素操作性能略逊于哈希表。
3. 特殊限制：

   - `TreeSet` 不支持 `null`，且元素必须可比较（`Comparable` 或 `Comparator`）。
   - `HashSet` 和 `LinkedHashSet` 允许 `null`，但仅能存储一个。
4. 选择
   - 优先选 HashSet：若无顺序或排序需求，仅需高效去重。
   - 需要插入顺序：选择 `LinkedHashSet`（如接口调用日志去重，保留请求顺序）。
   - 需要排序或范围查询：选择 `TreeSet`（如学生成绩排名、时间区间筛选）。
   - 多线程场景：所有 `Set` 实现均需手动同步（如 `Collections.synchronizedSet()` 或并发容器）。

## Queue / Deque

在 Java 中，<a href="/vault/2-Learning/04-Java/02-Java%E5%AE%B9%E5%99%A8/03-Queue%E7%B3%BB%E5%88%97/00-Queue%E5%92%8CDeque%E6%80%BB%E8%A7%88">Queue 和 Deque</a> 是两个非常重要的 **线性容器接口**，主要用于模拟 **队列**、**双端队列** 和 **栈** 等数据结构，常见于消息队列、缓冲区、线程调度等场景。

它们位于 `java.util` 包中：

- `Queue<E>`：先进先出（FIFO），通常用于排队模型（如线程池、任务调度）
- `Deque<E>`：双端队列（Double-Ended Queue），支持头尾两端插入/删除，可模拟队列、栈等多种结构

```java
Queue（接口）   ← FIFO（队列）

├── LinkedList           // 经典实现，基于链表，功能全面（支持 List、Deque）
├── PriorityQueue        // 优先级队列，基于最小堆
├── ArrayDeque           // 高性能双端队列，基于循环数组

Deque（接口）    ← 双端队列（可作为队列 + 栈）

├── LinkedList           // 实现了 Deque 接口，支持头尾操作
├── ArrayDeque           // 数组实现，性能更优，推荐使用

ArrayDeque

Java 中ArrayDeque 是基于循环数组实现的双端队列，通过 head 和 tail 指针标记队列头尾，利用位运算（index & (length-1)）（代替取模运算）实现循环索引（要求容量为 2 的幂），支持高效的双端插入 / 删除操作（均摊 O(1) 时间复杂度）。当 head == tail 且数组已满时触发扩容，新容量为原数组的 2 倍，并通过双段复制（先复制 head 到队尾，再复制数组头部到 tail 位置）保持元素顺序。其底层数组连续存储，缓存局部性好，内存占用比链表更紧凑，性能优于 LinkedList，但不允许存储 null（避免与 poll 返回 null 混淆），且非线程安全。适用于实现栈（LIFO）、队列（FIFO）、双端队列及滑动窗口等场景，是替代 LinkedList 的高效选择。

常见问法：

• ArrayDeque 的底层结构是什么？与 LinkedList 有什么区别？

  • ArrayDeque 是基于循环数组实现的，插入删除通过数组偏移完成；LinkedList 是基于双向链表。前者更高效，内存更紧凑。

• ArrayDeque 是如何扩容的？触发条件是什么？

  • 当 head == tail，即容量不足时触发扩容，策略是扩大为原数组的 2 倍，使用双段拷贝保留元素顺序。

• 为什么不允许存储 null 元素？

  • 为避免与 poll() 或 peek() 返回 null 混淆（无法判断队列为空还是存储了 null）。

• ArrayDeque 适合作为栈使用吗？

  • 适合，且比 Stack 更高效（Stack 是线程安全的，基于向量实现，性能较低）。例如：

    ArrayDeque<Integer> stack = new ArrayDeque<>();
    stack.push(1); // 入栈
    int top = stack.pop(); // 出栈
    ```
- ArrayDeque 如何实现双端队列？

  - 支持从头部（`offerFirst`/`pollFirst`）和尾部（`offerLast`/`pollLast`）插入
    / 删除元素，满足双端操作需求。
- ArrayDeque 是线程安全的吗？如何在并发场景下使用？
  - 非线程安全，可使用 `Collections.synchronizedDeque(new ArrayDeque<>())` 包装，或直接使用 `ConcurrentLinkedDeque`。
- ArrayDeque 适合哪些场景？
  - 适用于实现栈、队列、双端队列、缓存、滑动窗口等，尤其适合高性能场景中替代 `LinkedList`。

### PriorityQueue

Java 中的 `PriorityQueue` 是基于最小堆（完全二叉树）实现的优先级队列，底层通过动态数组 `Object[] queue` 存储元素，利用数组下标计算父子节点关系（左子节点为 `2i+1`，右子节点为 `2i+2`，父节点为 `(i-1)/2`），默认构建最小堆（元素按自然顺序升序排列），也可通过传入 `Comparator` 自定义排序规则（如降序）。插入元素时通过 `siftUp` 向上堆化维护堆序（时间复杂度
O(log n)），删除堆顶元素时通过 `siftDown` 向下堆化调整（时间复杂度 O(log n)），访问堆顶元素（peek）则为
O(1)。其扩容策略为小数组（初始容量 11，容量 <64 时）翻倍、大数组按 1.5 倍扩容，通过 `Arrays.copyOf` 复制元素（耗时
O(n)）。该队列不允许存储 null，非线程安全，遍历时按数组顺序而非堆序，适用于任务调度、Top-K 问题等需要动态维护优先级的场景。

**常见问题：**

- PriorityQueue 是如何实现优先级排序的？

  - 基于最小堆（完全二叉树），元素通过自然排序（`Comparable`）或自定义比较器（`Comparator`）确定优先级，堆顶始终为优先级最高的元素（默认最小值）。
- PriorityQueue 是如何维护顺序的？

  - 插入时 `siftUp()`，删除堆顶时 `siftDown()`，维护最小堆性质。
- 添加/删除的时间复杂度是多少？

  - O(log n)，通过堆化完成。
- 底层数据结构是什么？

  - 动态数组（Object[] queue），构成完全二叉堆。
- PriorityQueue 允许重复元素吗？

  - 允许，队列中可以存储重复元素，仅根据优先级排序，不涉及去重逻辑。
- null 能作为元素加入吗？
  - 不允许插入 null，会抛 NullPointerException。
- 为什么 PriorityQueue 不允许 null？

  - `poll()` 方法在队列为空时返回 `null`，若允许存储 `null` 会导致无法区分
    “队列为空” 和 “存储了 `null` 元素”。
- PriorityQueue 的遍历顺序是怎样的？

  - 遍历顺序与优先级无关，仅按底层数组的存储顺序（非排序顺序），若需有序输出需反复调用 `poll()`。
- 遍历 PriorityQueue 会按顺序输出吗？
  - 否，遍历不保证顺序，只有反复 poll() 才是从小到大输出。
- PriorityQueue 是线程安全的吗？

  - 非线程安全，多线程环境下需手动同步（如使用 `Collections.synchronizedQueue()`）或改用 `PriorityBlockingQueue`。
- 如何实现最大堆？

  - 通过自定义比较器实现降序，例如：

```java
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
    ```
- 扩容时的性能开销如何？

  - 扩容时需复制原数组元素（`Arrays.copyOf`），时间复杂度为 O(n)，因此预估元素数量后设置初始容量可减少扩容次数。

### LinkedList

见List

### 对比

1. 数据结构
   - ArrayDeque：循环数组（动态扩容，双端指针）。
   - PriorityQueue：最小堆（动态数组，堆化维护顺序）。
   - LinkedList：双向链表（节点含前驱 / 后继指针）。
2. 顺序与排序
   - ArrayDeque：按插入顺序（双端有序）。
   - PriorityQueue：按优先级排序（自然 / 自定义比较器）。
   - LinkedList：按插入顺序（有序列表，无自动排序）。
3. 性能
   - | 操作 | ArrayDeque | PriorityQueue | LinkedList |
     | --- | --- | --- | --- |
     | 两端增删 | O (1)（最快） | 不支持 | O(1) |
     | 随机访问 | O(1) | 不支持 | O (n)（最慢） |
     | 中间增删 | O(n) | 不支持 | O(1) |
     | 内存占用 | 低（数组紧凑） | 中（堆结构） | 高（指针开销） |
4. 特殊限制
   - ArrayDeque：不允许 `null`，容量为 2 的幂。
   - PriorityQueue：不允许 `null`，元素需可比较（`Comparable`/`Comparator`）。
   - LinkedList：允许 `null`，随机访问低效。
5. 适用场景
   - ArrayDeque：栈、队列、滑动窗口（双端操作优先）。
   - PriorityQueue：任务调度、Top-K、优先级排序（需动态维护极值）。
   - LinkedList：纯链表操作、头尾频繁增删（如消息队列，无需随机访问）。

双端操作选 ArrayDeque（性能最高），优先级排序选 PriorityQueue（唯一选择），链表场景选 LinkedList（迫不得已时）。

## Map

<a href="/vault/2-Learning/04-Java/02-Java%E5%AE%B9%E5%99%A8/04-Map%E7%B3%BB%E5%88%97/00-Map%E6%80%BB%E8%A7%88">Map</a> 是 Java 集合框架中的核心接口之一，用于存储键值对（Key-Value
Pairs），特点是通过键（Key）快速查找值（Value），类似于现实中的字典。与 Set（存储单一元素）和 Queue（线性容器）不同，Map
专注于映射关系的维护，广泛应用于缓存、配置表、统计计数等场景。

### HashMap<K, V>

`HashMap` 是 Java 中最常用的键值对映射容器，底层采用 **数组 + 链表 + 红黑树** 的复合结构实现，其中数组用于定位桶位（Bucket），链表或红黑树用于解决哈希冲突。JDK
1.8 之前，冲突元素以链表形式存在；JDK 1.8 开始，当链表长度 ≥ 8 且数组容量 ≥ 64 时，链表会转为红黑树，提升查询性能（O(n)
→ O(log n)）。

每次 put 操作流程是：先通过 `hashCode()` 计算 key 的哈希值，并经过扰动函数优化后确定桶下标（`hash & (table.length - 1)`），然后判断该位置是否已有元素：

- 若无，直接插入；
- 若有，比较 key 是否相同，相同则覆盖，不同则采用尾插链表或插入红黑树。

当元素数量超过阈值（默认容量 × 0.75），会触发 **扩容**：新数组容量为原来的 2 倍，并重新哈希已有元素的位置，这一步称为
rehash，是最耗性能的操作。

HashMap 允许一个 `null` 键和多个 `null` 值，不保证元素顺序，且 **非线程安全**，多线程场景下需使用 `ConcurrentHashMap` 或手动同步。

使用 HashMap 时，应合理设置初始容量与负载因子，避免频繁扩容带来的性能开销；同时，若使用自定义类作为 key，必须同时重写 `equals()` 和 `hashCode()` 方法，以确保哈希一致性和键的唯一性。

总结来说，HashMap 提供了插入、查找、删除操作平均 O(1) 的性能，是构建缓存、索引、字典等数据结构的首选工具，但在并发和扩容时需特别注意其设计边界和使用规范。

**常见问法：**

- HashMap 的底层数据结构是什么？
  - 数组 + 链表 + 红黑树（JDK 1.8 起链表转红黑树）
- HashMap 如何解决哈希冲突？
  - 通过链地址法（链表/红黑树）解决，key 相同通过 equals() 判断。
- 什么时候会将链表转为红黑树？
  - 桶中链表长度 ≥ 8 且数组容量 ≥ 64 时。
- HashMap 的 put 操作是怎么执行的？
  - 计算 hash → 定位桶位 → 冲突处理（覆盖/插入） → 超过阈值扩容。
- 为什么 HashMap 的数组长度必须是 2 的幂？
  - 为了用 `hash & (length - 1)` 替代 `%` 运算，提高效率。
- HashMap 的默认初始容量是多少？负载因子默认多少？
  - 默认初始容量为 16，默认负载因子为 0.75。
- HashMap 的扩容机制是怎样的？
  - 元素个数 > 容量 × 负载因子时，扩容为原容量的 2 倍，并重新散列。
- 为什么扩容性能开销大？
  - 需要重新分配数组，并将所有元素重新计算 hash 和插入新桶。
- 如何优化 HashMap 的性能？
  - 预估容量，合理设置初始容量，减少扩容；确保 key 的 hash 分布均匀。
- HashMap 允许 null 吗？
  - 允许一个 null 键，允许多个 null 值。
- 为什么必须重写 hashCode() 和 equals()？
  - 保证 key 唯一性和哈希一致性，否则会导致重复/找不到等问题。
- 只重写了 equals() 或只重写 hashCode() 会有什么问题？
  - 破坏哈希一致性，相同对象可能落入不同桶，无法正确查找或去重。
- HashMap 和 Hashtable 有什么区别？
  - HashMap 非线程安全，效率高；Hashtable 线程安全但性能低，是遗留类。
- HashMap 和 ConcurrentHashMap 有什么区别？
  - 后者线程安全，基于分段锁（JDK 7）或 CAS + synchronized（JDK 8），支持并发操作。
- HashMap 和 TreeMap 的区别？
  - TreeMap 基于红黑树，有序；HashMap 无序，性能更高。
- HashMap 和 LinkedHashMap 的区别？
  - LinkedHashMap 维护插入顺序或访问顺序（可实现 LRU 缓存）。
- HashMap 是线程安全的吗？
  - 否，多线程环境中使用会导致数据丢失、死循环等问题。
- JDK 1.7 中 HashMap 为什么可能死循环？
  - 链表头插 + 多线程扩容时可能形成环形链表，导致死循环。
- JDK 1.8 中为什么不会再死循环？
  - 改用链表尾插法 + 更安全的扩容方式。
- 多线程下如何安全使用 HashMap？
  - 用 `ConcurrentHashMap` 或 `Collections.synchronizedMap()`。
- HashMap 的 key 可以变吗？
  - 不推荐，key 一旦参与哈希运算再修改其值，可能导致查找失败。
- 如何遍历 HashMap？有几种方式？
  - 可通过 keySet()、entrySet()、values()、forEach()、迭代器等方式遍历。
- 遍历 HashMap 的顺序是固定的吗？
  - 否，不保证顺序；如需顺序应使用 LinkedHashMap 或 TreeMap。

### LinkedHashMap<K, V>

`LinkedHashMap` 是 Java 集合框架中 `HashMap` 的子类，它通过**哈希表 + 双向链表**的复合结构，在保持 `HashMap` 快速查找特性（平均
O (1) 时间复杂度）的基础上，提供了**插入顺序**或**访问顺序**的遍历能力。与 `HashMap` 不同，`LinkedHashMap` 的每个节点（Entry）包含额外的`before`和`after`指针，用于维护双向链表，从而实现顺序控制。默认按插入顺序遍历，元素会按插入顺序依次排列；若设置`accessOrder=true`（如`new LinkedHashMap<>(capacity, loadFactor, true)`），则每次访问（如`get`或`put`）会将元素移至链表尾部，形成**LRU（最近最少使用）顺序**。这种特性使其特别适合实现缓存，例如通过继承
LinkedHashMap 并重写`removeEldestEntry`方法，可以自动淘汰最旧元素：

```java
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }
}

LinkedHashMap 的遍历效率稳定为 O (n)，优于 HashMap 的无序遍历（依赖哈希分布），但每个节点需额外存储两个指针，空间开销略高。它允许一个 null 键和多个 null 值，且非线程安全，多线程场景需通过Collections.synchronizedMap包装或改用 ConcurrentHashMap。与 TreeMap 相比，LinkedHashMap 维护的是插入 / 访问顺序，而非键的自然排序，适用于需要保留元素顺序的场景（如日志记录、JSON 字段顺序输出）。使用时需注意，若键为自定义类，需重写equals()和hashCode()方法，且避免修改键对象的属性，以免破坏哈希一致性。

常见问题：

• LinkedHashMap 如何保证元素有序？

  • 通过双向链表维护元素顺序，分为两种模式：
    • 插入顺序（默认）：按元素插入的先后顺序排序。
    • 访问顺序（accessOrder=true）：每次访问（get/put）后将元素移至链表末尾，适用于 LRU 缓存。

• LinkedHashMap 的底层数据结构是什么？

  • 继承自 HashMap，底层为哈希表（数组 + 链表 / 红黑树）+ 双向链表：
    • 哈希表用于快速定位元素；
    • 双向链表用于记录元素顺序（每个节点包含 before 和 after 指针）。

• LinkedHashMap 与 HashMap 的主要区别是什么？

  • 顺序性：LinkedHashMap 支持插入顺序或访问顺序，HashMap 完全无序。
  • 数据结构：LinkedHashMap 额外维护双向链表，HashMap 无。
  • 内存开销：LinkedHashMap 每个节点多两个指针，空间占用略高。

• 如何实现 LRU 缓存？

  • 通过 accessOrder=true 开启访问顺序，并重写 removeEldestEntry 方法淘汰最旧元素：

    new LinkedHashMap<K, V>(capacity, 0.75f, true) {
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity; // 超出容量时删除最旧元素
        }
    };
    ```
- LinkedHashMap 是否允许 null 键值？

  - 允许1 个 null 键和多个 null 值，与 `HashMap` 一致。
- 遍历顺序是固定的吗？

  - 是。插入顺序模式下，遍历顺序与插入顺序一致；访问顺序模式下，遍历顺序随访问动态调整（最近访问的元素在链表末尾）。
- LinkedHashMap 是线程安全的吗？如何处理多线程场景？

  - 非线程安全。多线程下可通过 `Collections.synchronizedMap(new LinkedHashMap<>())` 包装，或改用线程安全的 `ConcurrentHashMap`（但 `ConcurrentHashMap` 不保证顺序）。
- 为什么遍历 LinkedHashMap 比 HashMap 更高效？

  - HashMap 遍历需遍历哈希表桶和链表 / 红黑树，顺序不可预测；
  - LinkedHashMap 直接按双向链表顺序遍历，时间复杂度稳定为 O(n)。
- LinkedHashMap 如何维护双向链表？

  - 插入元素时，通过 `linkNodeLast` 方法将新节点追加到链表末尾（插入顺序）或调整到末尾（访问顺序）。
  - 删除元素时，更新相邻节点的 `before` 和 `after` 指针，保持链表连续。
- accessOrder 参数的作用是什么？

  - `accessOrder=false`（默认）：按插入顺序排序；
  - `accessOrder=true`：按访问顺序排序，每次访问元素会将其移至链表末尾，实现 LRU 逻辑。
- LinkedHashMap 的迭代器是如何工作的？

  - 直接按双向链表顺序遍历（从 `head` 到 `tail`），无需访问哈希表桶，保证顺序稳定。
- LinkedHashMap 的插入性能比 HashMap 慢多少？

  - 略慢，因需额外操作双向链表指针（如更新 `before`/`after`），但实际差异通常可忽略（尤其数据量较小时）。
- 如何优化 LinkedHashMap 的内存占用？

  - 避免存储大量小对象（指针开销占比更高）；
  - 按需选择顺序模式，避免不必要的链表调整（如仅需插入顺序时，不启用 `accessOrder`）。

### TreeMap<K, V>

`TreeMap` 是 Java 中基于 红黑树（自平衡二叉搜索树） 实现的有序映射，键值对按键的自然顺序（如整数升序、字符串字典序）或自定义比较器（`Comparator`）
排序。其底层通过红黑树节点维护元素顺序，每个节点包含键、值、颜色标记（红 / 黑）及父、左、右子节点指针，确保中序遍历结果为有序序列（升序）。`TreeMap` 支持高效的范围查询（如 `subMap`、`headMap`）和有序操作（如获取第一个
/ 最后一个键），插入、删除、查询的时间复杂度均为 O(log n)，但不支持 null 键（无法参与比较），且非线程安全。典型应用包括数值范围统计、按时间排序的日志记录等需要有序性的场景。

### Hashtable<K, V>

`Hashtable` 是 Java 1.0 时代遗留的哈希表实现，可视为"线程安全版的古老 HashMap"：

| 维度 | Hashtable | HashMap |
| --- | --- | --- |
| 线程安全 | ✅ 方法级 `synchronized`（粗粒度锁，读读也互斥） | ❌ 非线程安全 |
| null 支持 | 键、值都**不允许** null（直接抛 NPE） | 允许 1 个 null 键、多个 null 值 |
| 继承体系 | 继承老类 `Dictionary` | 继承 `AbstractMap` |
| 初始容量 / 扩容 | 11 / 2n+1 | 16 / 2n（保持 2 的幂，利于位运算取模） |
| 定位 | 遗留类，新代码不使用 | 默认首选 |

两点面试要点：一是 **null 红线**——`Hashtable` 键值都拒绝 null，原因在于它为多线程环境设计：`get(key)` 返回 null 时无法区分"键不存在"和"值就是 null"（`HashMap` 单线程场景可用 `containsKey` 消歧）；二是它和 `Vector` 同病相怜——方法级 synchronized 读读互斥，如今被 `ConcurrentHashMap`（JDK 8 后 CAS+细粒度锁）全面替代。

## 全景选型决策图

```mermaid
flowchart TD
    Q{"要装什么数据？"} -->|"键值对（映射）"| M{"需要排序吗？"}
    Q -->|"单个元素"| C{"元素要去重吗？"}
    C -->|"要（唯一）"| S{"需要保持顺序？"}
    C -->|"不要（可重复）"| L{"操作集中在哪？"}
    L -->|"随机访问、读多"| AL["ArrayList"]
    L -->|"头尾增删、当队列/栈"| LL["LinkedList（或 ArrayDeque）"]
    S -->|"不要顺序"| HS["HashSet"]
    S -->|"插入顺序"| LHS["LinkedHashSet"]
    S -->|"按值排序"| TS["TreeSet"]
    M -->|"不需要"| HM["HashMap（默认选它）"]
    M -->|"按插入/访问顺序"| LHM["LinkedHashMap（LRU）"]
    M -->|"按键排序"| TM["TreeMap"]
    Q2{"多线程？"} -.->|是| CONC["HashMap→ConcurrentHashMap<br/>List→CopyOnWriteArrayList<br/>Queue→ConcurrentLinkedQueue / BlockingQueue"]

选型三问：装什么形态（单值 or 键值对）→ 要什么顺序（无序 / 插入序 / 排序）→ 在什么环境（单线程随手用 / 多线程选并发包）。所有实现类的深读见各系列详篇。

⬅️ 00-Java 🏠 本页是 02-Java容器 入口 ➡️ 00-List总览