--- title: "00-容器总览" created: 2025-12-02 tags: - Java --- # 容器总览 > [!note] 定位说明 > 本篇是 02-Java容器 的入口与速览：一图一表建立"两大体系（Collection 单值 / Map 键值对）"的整体认知，四大节分别是 List / Set / Queue / Map 的浓缩版（详篇见各系列子目录）。学习动线：本篇 → [[00-List总览|List 系列]] → [[00-Set总览|Set 系列]] → [[00-Queue和Deque总览|Queue 系列]] → [[00-Map总览|Map 系列]] → [[00-容器选型总对比|选型总对比]] → [[01-容器高频面试题|高频面试题]]（收官）。本篇同时保留了 C++ STL 类比视角，适合有 C++ 背景时快速对照。 ## 整体认知 Java 容器（Collections）是用来“装对象的对象”，即集合类框架，整体由 **两大核心接口** 构成： ### 一、`Collection` 接口 —— **单值集合体系** 用于表示一组元素的“集合”，即一个一个元素地存储。 > ✅ 类比 C++ STL 中的 `vector`、`list`、`set`、`queue` 等 主要子接口与实现类： ![[image-daf2dd0c.png]] | 接口/实现类 | 特点说明 | 类比 C++ STL | | --- | --- | --- | | `List` | 有序、可重复，支持索引 | `vector`, `list` | | ├── `ArrayList` | 动态数组实现，查找快、增删慢 | `vector` | | ├── `LinkedList` | 双向链表实现，查找慢、增删快 | `list`, `deque` | | ├── `Vector` | 线程安全，老旧，功能和 `ArrayList` 类似 | | | `Set` | 无序/有序、不可重复 | `set`, `unordered_set` | | ├── `HashSet` | 基于哈希表，无序 | `unordered_set` | | ├── `LinkedHashSet` | 插入顺序有序 | 无完全对应 | | ├── `TreeSet` | 基于红黑树，有序 | `set` | | `Queue` / `Deque` | 队列/双端队列 | `queue`, `deque` | | ├── `PriorityQueue` | 优先级队列，最小堆 | `priority_queue` | | ├── `ArrayDeque` | 高效的双端队列 | `deque` | ### 二、Map：**键值对映射体系** 存储 `key-value` 形式的数据，常用于快速查找，不属于 `Collection` 接口体系。 > ✅ 类比 C++ STL 中的 `map`、`unordered_map` ![[image-c00a750a.png]] 常见实现类： | 类名 | 特点说明 | 类比 C++ STL | | --- | --- | --- | | `HashMap` | 无序、基于哈希表，查找快，允许 null | `unordered_map` | | `LinkedHashMap` | 基于哈希表 + 链表，有插入顺序 | 无严格对应 | | `TreeMap` | 有序、基于红黑树，按 key 自然顺序或自定义排序 | `map` | | `Hashtable` | 线程安全的早期实现，已不推荐使用 | 无 | 学习顺序： - **List 接口（线性结构）** - `ArrayList`：基于动态数组，支持随机访问，增删效率相对较低。 - `LinkedList`：基于双向链表，插入删除快，但不支持快速随机访问。 - `Vector`：线程安全的动态数组，已较少使用，了解其同步机制即可。 - **Set 接口（去重集合）** - `HashSet`：基于 `HashMap`，无序、唯一。 - `LinkedHashSet`：保留插入顺序。 - `TreeSet`：基于红黑树，自动排序。 - **Queue / Deque 接口（队列结构）** - `Queue`（如 `PriorityQueue`）：优先级队列，非 FIFO。 - `Deque`（如 `ArrayDeque`、`LinkedList`）：双端队列，支持栈、队列双重操作。 - **Map 接口（键值对映射）** - `HashMap`：最常用，基于哈希表。 - `LinkedHashMap`：有序版本的 HashMap。 - `TreeMap`：自动排序的 Map，基于红黑树。 ## List [[00-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`，避免触发异常。例如： ```java Iterator it = list.iterator(); while (it.hasNext()) { if (条件) { it.remove(); // 安全删除 } } ``` - **ArrayList 与** `Arrays.asList()` **返回的列表有什么区别？** - `Arrays.asList()` 返回的是 **固定大小列表**，不支持增删操作（调用会抛 `UnsupportedOperationException`）； - ArrayList 是动态可变的，支持扩容和增删。 - **ArrayList 可以存储基本数据类型吗？** - 不能直接存储，需使用包装类（如 `Integer`、`Long`）。例如： ```java ArrayList list = new ArrayList<>(); // 正确 // ArrayList 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 [[2-Learning/04-Java/02-Java容器/02-Set系列/00-Set总览|Set]] 是 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 map = new LinkedHashMap<>(16, 0.75f, true); Set 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 safeSet = Collections.synchronizedSet(new LinkedHashSet<>()); ``` - LinkedHashSet 的内存占用比 HashSet 高多少？ - 每个元素需额外存储两个指针（前驱 / 后继），内存开销约增加 50%（视元素本身大小而定）。 - 如何利用 LinkedHashSet 实现 LRU 缓存？ - 通过 LinkedHashMap 的访问顺序模式结合容量限制： ```java LinkedHashMap cache = new LinkedHashMap(capacity, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry 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 { private int age; @Override public int compareTo(User o) { return Integer.compare(age, o.age); // 按年龄排序 } } ``` - 方案 2：创建 `TreeSet` 时传入 `Comparator` 匿名内部类或 lambda。 ```java TreeSet 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 中，[[2-Learning/04-Java/02-Java容器/03-Queue系列/00-Queue和Deque总览|Queue 和 Deque]] 是两个非常重要的 **线性容器接口**，主要用于模拟 **队列**、**双端队列** 和 **栈** 等数据结构，常见于消息队列、缓冲区、线程调度等场景。 它们位于 `java.util` 包中： - `Queue`：先进先出（FIFO），通常用于排队模型（如线程池、任务调度） - `Deque`：双端队列（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` 是线程安全的，基于向量实现，性能较低）。例如： ```java ArrayDeque 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 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 [[2-Learning/04-Java/02-Java容器/04-Map系列/00-Map总览|Map]] 是 Java 集合框架中的核心接口之一，用于存储键值对（Key-Value Pairs），特点是通过键（Key）快速查找值（Value），类似于现实中的字典。与 Set（存储单一元素）和 Queue（线性容器）不同，Map 专注于映射关系的维护，广泛应用于缓存、配置表、统计计数等场景。 ### HashMap `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 `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 extends LinkedHashMap { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry 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` 方法淘汰最旧元素： ```java new LinkedHashMap(capacity, 0.75f, true) { protected boolean removeEldestEntry(Map.Entry 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 `TreeMap` 是 Java 中基于 红黑树（自平衡二叉搜索树） 实现的有序映射，键值对按键的自然顺序（如整数升序、字符串字典序）或自定义比较器（`Comparator`） 排序。其底层通过红黑树节点维护元素顺序，每个节点包含键、值、颜色标记（红 / 黑）及父、左、右子节点指针，确保中序遍历结果为有序序列（升序）。`TreeMap` 支持高效的范围查询（如 `subMap`、`headMap`）和有序操作（如获取第一个 / 最后一个键），插入、删除、查询的时间复杂度均为 O(log n)，但不支持 null 键（无法参与比较），且非线程安全。典型应用包括数值范围统计、按时间排序的日志记录等需要有序性的场景。 ### Hashtable `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
List→CopyOnWriteArrayList
Queue→ConcurrentLinkedQueue / BlockingQueue"] ``` > 选型三问：**装什么形态**（单值 or 键值对）→ **要什么顺序**（无序 / 插入序 / 排序）→ **在什么环境**（单线程随手用 / 多线程选并发包）。所有实现类的深读见各系列详篇。 --- ⬅️ [[00-Java|00-Java]] 🏠 本页是 02-Java容器 入口 ➡️ [[00-List总览|00-List总览]]