02-Java集合

Sunrise_Jay

发表于 2026-07-29

Java后端面试八股

2 143.6~184.6 分钟 64613

Java集合框架 · 2.1 集合体系基础

Java集合的继承体系是什么？

原始问法：

Java集合的继承体系是什么？

来源题目：SRC-02-21-060

面试先答

Java集合框架分为两大独立的接口体系：Collection和Map。Collection是存储一组元素的集合接口，下分List（有序可重复）、Set（无序不可重复）、Queue（队列）三个子接口；Map是键值对存储的映射接口。整个体系以Iterable为最顶层接口，所有集合都支持迭代。常用实现包括ArrayList、LinkedList、HashSet、HashMap、TreeMap等。Java集合框架的设计采用了接口与实现分离的模式，上层编程面向接口，底层可灵活切换实现。

核心结论

Java集合分为Collection和Map两大体系，Collection下有List、Set、Queue三大子接口。
顶层接口Iterable定义了迭代能力，所有集合都支持for-each循环。
体系采用接口与实现分离的设计模式，方便上层代码解耦。

1. 是什么

Java集合框架（Java Collections Framework，JCF）是JDK提供的一组接口和类，用于存储和操作对象集合。其继承体系如下：

Iterable (可迭代)
├── Collection (集合接口)
│   ├── List (有序可重复)
│   │   ├── ArrayList
│   │   ├── LinkedList
│   │   └── Vector
│   ├── Set (无序不可重复)
│   │   ├── HashSet
│   │   ├── LinkedHashSet
│   │   └── TreeSet
│   └── Queue (队列)
│       ├── LinkedList
│       ├── PriorityQueue
│       └── BlockingQueue
└── Map (键值对映射)
    ├── HashMap
    ├── LinkedHashMap
    ├── TreeMap
    └── ConcurrentHashMap

2. 为什么需要它

在没有集合框架时，开发者需要自己实现动态数组、链表、哈希表等数据结构，重复造轮子且难以保证质量。集合框架提供了标准化的数据结构API，让开发者可以专注于业务逻辑而非底层实现。

3. 底层原理与完整流程

Iterable：定义了iterator()方法，返回一个Iterator对象，支持foreach循环。
Collection：定义了add()、remove()、contains()、size()等集合通用操作。
List：有序集合，支持通过索引访问元素。
Set：不允许重复元素，基于equals()和hashCode()判断重复。
Map：键值对映射，键唯一，值可重复。

4. 怎么使用

// 使用List
List<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");

// 使用Set
Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");

// 使用Map
Map<String, Integer> map = new HashMap<>();
map.put("score", 100);

// 统一通过迭代遍历
for (String item : list) {
    System.out.println(item);
}

5. 适用场景

List：需要有序、允许重复的元素集合，如用户列表。
Set：需要去重的元素集合，如标签集合。
Map：需要键值对映射，如配置项存储。
Queue：先进先出或优先级队列场景，如任务调度。

6. 不适用场景与替代方案

基本数据类型：集合只能存储对象，基本类型需使用对应的包装类。
原始类型性能敏感场景：可使用Trove、FastUtil等第三方高性能集合库。

7. 优缺点与技术取舍

优点：标准化API、类型安全（泛型）、丰富的实现选择。缺点：只支持对象类型、部分实现非线程安全。

8. 常见问题及解决方案

Q：数组和集合如何互相转换？

// 数组转集合
List<String> list = Arrays.asList(array);
// 集合转数组
String[] array = list.toArray(new String[0]);

9. 版本差异与实现边界

Java 8：新增Stream API，支持函数式操作集合。
Java 9+：新增List.of()、Set.of()、Map.of()等工厂方法创建不可变集合。

10. 常见追问

Q：为什么List、Set、Map不继承一个共同的接口？ A：因为它们的数据结构和语义差异太大。List是有序序列，Set是数学集合，Map是键值对映射，强行统一接口会导致API设计混乱。

11. 易错点

错误：HashSet的底层是HashMap。
正确：HashSet内部确实维护了一个HashMap对象，元素作为Key存入，Value固定为PRESENT。
错误：集合都是线程安全的。
正确：ArrayList、HashMap等大部分集合不是线程安全的，需使用Collections.synchronizedList()或并发集合类。

一句话总结

Java集合框架通过接口与实现分离的设计，提供了List、Set、Map、Queue四大核心集合类型，覆盖了从有序序列到键值映射的各种数据存储需求。

Collection和Map的区别是什么？

原始问法：

Collection和Map的区别是什么？

来源题目：SRC-02-21-061

面试先答

Collection和Map是Java集合框架的两大核心接口，它们的根本区别在于存储结构不同。Collection存储的是一组独立的元素（每个元素是一个对象），而Map存储的是键值对（Key-Value）映射。Collection的子接口包括List、Set、Queue，用于存储同类型元素集合；Map的实现包括HashMap、TreeMap等，用于存储键值对映射关系。两者均继承自Iterable可迭代接口，但数据模型完全不同。

核心结论

Collection存储单一元素，Map存储键值对。
Collection的子接口有List、Set、Queue；Map独立于Collection体系。
两者均支持迭代，但Map需通过keySet()或entrySet()间接遍历。

1. 是什么

Collection：java.util.Collection是集合接口的根，定义了对一组对象元素的基本操作。

Map：java.util.Map是键值对映射接口，每个键最多映射到一个值。

2. 为什么需要它

Collection适用于存储同类型元素的集合（如学生名单），Map适用于存在一一映射关系的数据（如学号→学生信息）。将两者分开设计，使各自的API更贴合实际需求，避免冗余方法。

3. 底层原理与完整流程

维度	Collection	Map
存储结构	一组独立元素	键值对映射
索引方式	通过索引或元素值	通过Key索引
遍历方式	直接迭代元素	通过Key集或Entry集间接迭代
常见实现	ArrayList, HashSet	HashMap, TreeMap

4. 怎么使用

// Collection使用
Collection<String> coll = new ArrayList<>();
coll.add("元素1");
coll.contains("元素1"); // true

// Map使用
Map<String, Integer> map = new HashMap<>();
map.put("key1", 100);
map.get("key1"); // 100

// Map遍历
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

5. 适用场景

Collection：购物车商品列表、消息队列。
Map：缓存（Key→Value）、配置映射、字典查询。

6. 不适用场景与替代方案

需要双向映射：使用BiMap（Guava）。
多值映射：使用Multimap（Guava）或自定义结构。

7. 优缺点与技术取舍

Collection API简洁，适合简单元素集合；Map提供了高效的键值查找能力，但Key必须唯一。

8. 常见问题及解决方案

Q：如何将Map转为Collection？

Map<String, Integer> map = new HashMap<>();
Collection<Integer> values = map.values(); // 值集合
Set<String> keys = map.keySet(); // 键集合
Set<Map.Entry<String, Integer>> entries = map.entrySet(); // 条目集合

9. 版本差异与实现边界

Java 8：新增forEach()默认方法。
Java 9+：新增Map.of()等不可变集合工厂方法。

10. 常见追问

Q：Map为什么不继承Collection？ A：因为Map的操作语义（键值对映射）与Collection（元素集合）差异过大，强行统一会导致接口过于臃肿。

11. 易错点

错误：Map继承自Collection。
正确：Map与Collection是平级接口，都继承自Iterable。

一句话总结

Collection存储一组独立元素，Map存储键值对映射，两者是Java集合框架中平级的两大核心接口。

List、Set、Map、Queue的核心区别是什么？

原始问法：

List、Set、Map、Queue的核心区别是什么？

来源题目：SRC-02-21-062

面试先答

List、Set、Map、Queue是Java集合框架的四种核心数据结构。List有序可重复，通过索引直接访问；Set无序不可重复，基于哈希或树结构去重；Map是键值对映射，键唯一值可重复；Queue是先进先出或优先级队列。它们的核心区别在于存储结构、有序性、重复性约束和访问方式各不相同，适用于不同的业务场景。

核心结论

List有序可重复，支持索引访问，底层多为数组或链表。
Set无序不可重复，通过hashCode()和equals()去重。
Map键值对存储，键唯一，通过键索引值。
Queue队列结构，支持FIFO或优先级排序。

1. 是什么

接口	存储结构	有序性	重复性	访问方式
List	元素序列	有序	可重复	索引/迭代
Set	元素集合	无序	不可重复	迭代
Map	键值对	取决于实现	键唯一值可重复	通过Key
Queue	队列	取决于实现	可重复	头部/尾部

2. 为什么需要它

不同业务场景需要不同的数据组织方式：有序列表需要List，去重场景需要Set，键值映射需要Map，任务调度需要Queue。提供多种集合类型使开发者可以选择最合适的数据结构。

3. 底层原理与完整流程

List：

ArrayList：基于动态数组，随机访问O(1)，尾部添加O(1)。
LinkedList：基于双向链表，头尾操作O(1)，随机访问O(n)。

Set：

HashSet：基于HashMap，无序，O(1)查找。
TreeSet：基于红黑树，有序，O(log n)查找。

Map：

HashMap：基于数组+链表/红黑树，O(1)查找。
TreeMap：基于红黑树，O(log n)查找，按键排序。

Queue：

LinkedList：基于双向链表的FIFO队列。
PriorityQueue：基于最小堆，按优先级出队。

4. 怎么使用

// List使用场景：有序用户列表
List<User> users = new ArrayList<>();
users.add(new User("Alice"));
users.add(1, new User("Bob")); // 在索引1插入

// Set使用场景：标签去重
Set<String> tags = new HashSet<>();
tags.add("Java");
tags.add("Java"); // 不会重复添加

// Map使用场景：配置映射
Map<String, String> config = new HashMap<>();
config.put("host", "localhost");
String host = config.get("host");

// Queue使用场景：任务队列
Queue<Task> tasks = new LinkedList<>();
tasks.offer(new Task("task1"));
Task next = tasks.poll(); // 取出队首任务

5. 适用场景

List：需要顺序访问、允许重复的场景，如分页数据。
Set：需要去重、判断元素是否存在的场景，如权限集合。
Map：需要键值查找的场景，如缓存、字典。
Queue：需要排队处理的场景，如消息队列、线程池任务队列。

6. 不适用场景与替代方案

需要双向查找：使用Map + 反向Map或Guava的BiMap。
高并发场景：使用ConcurrentHashMap、ConcurrentLinkedQueue等并发集合。

7. 优缺点与技术取舍

List优点：有序、支持索引访问；缺点：插入删除O(n)。
Set优点：自动去重、快速判断存在性；缺点：无序。
Map优点：快速键值查找；缺点：Key不可变约束。
Queue优点：天然支持排队；缺点：访问中间元素不便。

8. 常见问题及解决方案

Q：如何选择集合类型？

需要有序+可重复 → List
需要去重 → Set
需要键值映射 → Map
需要排队 → Queue

9. 版本差异与实现边界

Java 8：新增Stream API，统一函数式操作。
Java 9+：新增of()工厂方法创建不可变集合。

10. 常见追问

Q：为什么HashSet、HashMap是无序的？ A：因为它们基于哈希表，元素位置由哈希值决定，哈希值不保证有序。

11. 易错点

错误：Set中元素不可变。
正确：Set中元素可以可变，但修改后可能导致hashCode()和equals()变化，造成元素丢失。
错误：HashMap有序。
正确：HashMap无序，LinkedHashMap保持插入顺序，TreeMap按键排序。

一句话总结

List有序可重复、Set无序不重复、Map键值映射、Queue先进先出，四种集合各有所长，应根据业务场景选择合适的类型。

Iterator迭代器的原理是什么？

原始问法：

Iterator迭代器的原理是什么？

来源题目：SRC-02-21-063

面试先答

Iterator是Java集合框架提供的统一遍历接口，采用迭代器模式，允许顺序访问集合中的每个元素而不暴露其底层存储结构。其核心原理是通过游标（cursor）机制记录当前遍历位置，提供hasNext()判断是否有下一个元素、next()获取下一个元素、remove()删除当前元素三个核心方法。所有实现Iterable接口的集合都可以通过iterator()方法获取迭代器对象。

核心结论

Iterator采用迭代器模式，封装集合的遍历逻辑。
通过游标机制支持顺序访问，不暴露底层结构。
提供fail-fast机制检测并发修改。

1. 是什么

java.util.Iterator是集合的迭代器接口，定义了遍历集合的标准方法：

public interface Iterator<E> {
    boolean hasNext();  // 判断是否有下一个元素
    E next();           // 获取下一个元素
    void remove();      // 删除当前元素（可选）
}

2. 为什么需要它

没有迭代器时，每种集合需要不同的遍历方式（数组用索引、链表用指针），上层代码需要了解底层结构。迭代器统一了遍历方式，解耦了集合的存储结构与遍历逻辑。

3. 底层原理与完整流程

迭代过程：

调用iterator()获取迭代器实例，游标指向第一个元素之前。
hasNext()检查游标后方是否有元素。
next()将游标前移并返回该元素。
remove()删除当前元素位置（需在next()之后调用）。

fail-fast机制：

迭代器内部维护一个expectedModCount变量。
集合的modCount记录修改次数。
每次迭代操作都会检查expectedModCount是否等于modCount。
若不相等则抛出ConcurrentModificationException。

// ArrayList.Itr内部实现示意
private class Itr implements Iterator<E> {
    int cursor;       // 当前游标
    int lastRet = -1; // 上一个返回元素的索引
    int expectedModCount = modCount; // 期望的修改次数

    public boolean hasNext() {
        return cursor != size;
    }

    public E next() {
        checkForModification(); // 检查并发修改
        // ...获取元素并移动游标
    }

    public void remove() {
        checkForModification();
        // ...删除元素并同步expectedModCount
    }

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

4. 怎么使用

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

// 使用Iterator遍历
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String item = it.next();
    System.out.println(item);
    // it.remove(); // 安全删除当前元素
}

// 使用for-each（编译器自动转换为Iterator）
for (String item : list) {
    System.out.println(item);
}

// Java 8+ 使用forEachRemaining
list.iterator().forEachRemaining(System.out::println);

5. 适用场景

统一遍历不同类型的集合。
在遍历过程中需要安全删除元素。
需要编写通用遍历算法时接受Iterable参数。

6. 不适用场景与替代方案

需要高效随机访问：直接使用get(index)。
需要双向遍历：使用ListIterator（支持hasPrevious()和previous()）。
高并发场景：使用CopyOnWriteArrayList的迭代器（弱一致性，不抛异常）。

7. 优缺点与技术取舍

优点：统一遍历接口、解耦存储结构、支持fail-fast检测。缺点：fail-fast机制增加开销、不支持并发修改、只支持单向遍历。

8. 常见问题及解决方案

Q：为什么在foreach中不能调用集合的remove()方法？

// 错误：会抛ConcurrentModificationException
for (String item : list) {
    if (item.equals("B")) {
        list.remove(item);
    }
}

// 正确：使用Iterator的remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("B")) {
        it.remove();
    }
}

9. 版本差异与实现边界

Java 8：新增forEachRemaining()默认方法。
Java 21：SequencedCollection引入双向迭代支持。
注意：Iterator本身不保证线程安全，fail-fast是尽力而为的检测机制。

10. 常见追问

Q：Enumeration和Iterator的区别？ A：Enumeration是旧接口，只能读取；Iterator可删除、有fail-fast、方法名更短。

11. 易错点

错误：Iterator支持在遍历中修改集合。
正确：Iterator.remove()是唯一安全删除方式，直接调用集合的remove()会抛异常。
错误：for-each比Iterator更快。
正确：for-each编译后就是Iterator，性能完全相同。

一句话总结

Iterator通过游标机制统一了集合的遍历方式，配合fail-fast机制在遍历中提供并发修改检测，是Java集合框架的核心遍历接口。

Java集合框架 · 2.2 List相关

ArrayList的定义、区别是什么？

原始问法：

ArrayList和Array（数组）的区别是什么？

ArrayList的底层实现是什么？扩容机制是怎样的？

来源题目：SRC-02-22-064, SRC-02-22-065

面试先答

ArrayList是基于动态数组的List实现，内部使用Object[]数组存储元素。与普通数组的核心区别在于：数组是固定长度的，ArrayList是自动扩容的动态数组。默认初始容量为10，扩容时按1.5倍增长（oldCapacity + oldCapacity >> 1）。ArrayList支持随机访问O(1)，尾部添加O(1)，中间插入删除O(n)。它不是线程安全的，适合单线程环境使用。

核心结论

ArrayList基于Object[]动态数组，默认容量10，1.5倍扩容。
与Array的核心区别：长度可变 vs 固定，支持泛型 vs 不支持。
随机访问O(1)，中间插入删除O(n)，尾部操作O(1)。

1. 是什么

Array（数组）：Java语言内置的固定长度数据结构，声明后长度不可变，可存储基本类型和对象。

ArrayList：java.util.ArrayList是基于动态数组实现的List接口，封装了数组的自动扩容逻辑，支持泛型和丰富的集合操作。

2. 为什么需要它

普通数组长度固定，无法在运行时动态调整大小。当无法预知数据量时，使用数组需要预先分配足够大的空间，造成内存浪费或空间不足。ArrayList解决了这个问题，提供了自动扩容能力。

3. 底层原理与完整流程

底层结构：

// JDK 8+ ArrayList核心字段
private static final int DEFAULT_CAPACITY = 10;  // 默认初始容量
private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组
transient Object[] elementData; // 存储元素的数组
private int size; // 实际元素数量

扩容流程：

首次添加元素时，使用默认容量10创建数组。
当元素数量达到数组容量时，触发grow()方法。
计算新容量：newCapacity = oldCapacity + (oldCapacity >> 1)（即1.5倍）。
使用Arrays.copyOf()创建新数组并复制元素。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

与Array的对比：

维度	Array	ArrayList
长度	固定	动态扩容
存储类型	基本类型+对象	仅对象（泛型）
扩容	不支持	1.5倍自动扩容
性能	更高	略低（封装开销）
线程安全	否	否

4. 怎么使用

// 创建ArrayList
List<String> list = new ArrayList<>(); // 默认容量10
List<Integer> largeList = new ArrayList<>(100); // 指定初始容量

// 添加元素
list.add("Java"); // 尾部添加
list.add(0, "Python"); // 指定位置插入

// 访问元素
String first = list.get(0); // O(1)随机访问

// 删除元素
list.remove(0); // O(n)需移动元素
list.remove("Java"); // O(n)遍历查找

// 转为数组
String[] arr = list.toArray(new String[0]);

5. 适用场景

需要频繁随机访问元素的场景。
已知数据量或可预估数据量的场景。
尾部操作多于中间插入删除的场景。

6. 不适用场景与替代方案

频繁中间插入删除：使用LinkedList。
多线程并发：使用Collections.synchronizedList()或CopyOnWriteArrayList。
基本类型存储：使用数组或高性能库（Trove、FastUtil）。

7. 优缺点与技术取舍

优点：随机访问O(1)、尾部操作O(1)、实现简单直观、缓存友好。缺点：中间操作O(n)、自动扩容有开销、非线程安全。

8. 常见问题及解决方案

Q：如何避免频繁扩容？

// 预估容量，指定初始值
List<String> list = new ArrayList<>(1000);
for (int i = 0; i < 1000; i++) {
    list.add("item" + i);
}

Q：ArrayList的remove(int)和remove(Object)区别？

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

list.remove(1); // 删除索引1的元素（值为2）→ O(n)
list.remove(Integer.valueOf(1)); // 删除值为1的元素 → O(n)遍历

9. 版本差异与实现边界

Java 7+：ArrayList首次添加元素时才初始化数组（懒加载）。
Java 8：扩容使用Arrays.copyOf()统一实现。
Java 21：支持SequencedCollection接口，增加getFirst()/getLast()方法。
注意：ArrayList的size()与elementData.length不同，前者是元素数量，后者是数组容量。

10. 常见追问

Q：为什么ArrayList的扩容是1.5倍而不是2倍？ A：1.5倍在内存浪费和扩容次数之间取得平衡，避免2倍造成过多内存浪费。

11. 易错点

错误：ArrayList扩容是2倍。
正确：JDK中ArrayList扩容是1.5倍（oldCapacity + oldCapacity >> 1）。
错误：ArrayList的size()等于数组长度。
正确：size()是实际元素数量，elementData.length是数组容量。
错误：ArrayList的remove(int)删除值。
正确：remove(int)删除指定索引位置的元素，remove(Object)才是按值删除。

一句话总结

ArrayList基于动态数组，通过1.5倍自动扩容平衡内存与性能，随机访问O(1)，中间操作O(n)，是最常用的List实现。

ArrayList的插入删除性能如何？

原始问法：

ArrayList的插入删除性能如何？

来源题目：SRC-02-22-066

面试先答

ArrayList的插入删除性能取决于操作位置。尾部插入（add）平均O(1)，最好情况；中间或头部插入删除（add/remove at index）需要移动大量元素，为O(n)；按值删除（remove(Object)）需要遍历查找，也是O(n)。此外，当数组容量不足时，插入操作会触发扩容，扩容涉及数组复制，时间复杂度为O(n)。因此ArrayList适合尾部操作多、随机访问多的场景，不适合频繁中间插入删除。

核心结论

尾部添加O(1)（均摊），头部/中间插入删除O(n)。
按值删除需要遍历查找，O(n)。
扩容时涉及数组复制，单次扩容O(n)。

1. 是什么

ArrayList的插入删除性能本质上是基于其底层动态数组的特性：数组在内存中是连续存储的，头部或中间位置的插入删除需要移动其后所有元素。

2. 为什么需要它

理解ArrayList的性能特征对正确选型至关重要。如果场景涉及大量中间插入删除，应选择LinkedList等基于链表的实现。

3. 底层原理与完整流程

add(int index, E element)流程：

检查容量是否足够，不足则扩容。
使用System.arraycopy()将index位置及之后的元素向后移动一位。
在index位置插入新元素。
size+1。

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1); // 可能触发扩容
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

remove(int index)流程：

检查索引合法性。
保存被删除的元素。
使用System.arraycopy()将index之后的元素向前移动一位。
将末尾元素置null（帮助GC）。
size-1。

时间复杂度汇总：

操作	位置	时间复杂度
add(E)	尾部	O(1)均摊
add(int, E)	头部	O(n)
add(int, E)	中间	O(n)
remove(int)	头部	O(n)
remove(int)	中间	O(n)
remove(Object)	-	O(n)

4. 怎么使用

// 高效的尾部操作
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    list.add(i); // 尾部添加，O(1)
}

// 低效的头部操作
long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
    list.add(0, i); // 头部插入，O(n)
}
long elapsed = System.nanoTime() - start;

// 高效按索引访问
int val = list.get(5000); // O(1)随机访问

5. 适用场景

尾部添加为主、随机访问频繁的场景。
数据量相对稳定、中间操作较少的场景。

6. 不适用场景与替代方案

频繁头部或中间插入删除：使用LinkedList。
需要高效随机访问同时中间操作多：使用List预分配+尾部操作，或使用SkipList结构。

7. 优缺点与技术取舍

优点：随机访问O(1)、缓存局部性好。缺点：中间操作O(n)、扩容开销。

8. 常见问题及解决方案

Q：如何优化ArrayList的中间操作性能？

// 方案1：尽量使用尾部操作
list.addAll(items); // 批量尾部添加

// 方案2：已知数据量时指定初始容量
List<Integer> list = new ArrayList<>(10000);

// 方案3：频繁中间操作改用LinkedList
List<Integer> fastList = new LinkedList<>();

9. 版本差异与实现边界

System.arraycopy()是JVM原生方法，性能比纯Java循环更好。
Java 8+的removeIf()使用迭代器实现，遍历删除更高效。

10. 常见追问

Q：为什么ArrayList的add(E)是均摊O(1)？ A：虽然扩容时O(n)，但扩容触发频率低（1.5倍增长），平均下来每次add的时间复杂度为O(1)。

11. 易错点

错误：ArrayList的add(E)是严格O(1)。
正确：是均摊O(1)，扩容时单次可能O(n)。
错误：ArrayList比LinkedList慢。
正确：大多数场景下ArrayList更快（缓存友好、随机访问快），只有频繁中间操作时LinkedList才更快。

一句话总结

ArrayList尾部操作O(1)、中间操作O(n)，适合随机访问多、尾部操作多的场景。

LinkedList的底层实现是什么？插入删除性能如何？

原始问法：

LinkedList的底层实现是什么？插入删除性能如何？

来源题目：SRC-02-22-067

面试先答

LinkedList基于双向链表实现，每个节点包含prev、next两个指针和item数据。它实现了List、Deque、Queue三个接口，既可作为列表也可作为队列/双端队列使用。LinkedList的头尾操作都是O(1)，因为只需修改指针；但随机访问是O(n)，需要从头部或尾部遍历。相比ArrayList，LinkedList没有扩容开销但内存占用更大（每个节点需要额外存储两个指针）。

核心结论

LinkedList基于双向链表，每个节点存储前后指针和数据。
头尾操作O(1)，随机访问O(n)。
同时实现List、Deque、Queue接口，用途广泛。

1. 是什么

java.util.LinkedList是基于双向链表的List接口实现，链表中的每个节点包含：

prev：指向前一个节点
next：指向后一个节点
item：存储的数据

2. 为什么需要它

与ArrayList基于数组连续存储不同，LinkedList基于链表离散存储，具有O(1)的头尾插入删除性能，适合需要频繁在两端操作的场景。

3. 底层原理与完整流程

节点结构：

private static class Node<E> {
    E item;       // 数据
    Node<E> next; // 后继指针
    Node<E> prev; // 前驱指针

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

// LinkedList核心字段
transient Node<E> first; // 头节点
transient Node<E> last;  // 尾节点
transient int size;      // 元素数量

头插流程（addFirst）：

创建新Node，prev=null，next=原first。
将原first的prev指向新Node。
更新first指向新Node。
若原first为null，更新last也指向新Node。
size+1。

中间插入流程（add(int index, E element)）：

找到index位置的节点p。
创建新Node，prev=p.prev，next=p。
p.prev.next指向新Node。
p.prev指向新Node。
size+1。

时间复杂度：

操作	位置	时间复杂度
addFirst/addLast	头尾	O(1)
add(int, E)	中间	O(n)查找
removeFirst/removeLast	头尾	O(1)
remove(int)	中间	O(n)查找
get(int)	随机	O(n)

4. 怎么使用

// 创建LinkedList
LinkedList<String> list = new LinkedList<>();

// 作为List使用
list.add("Java");
list.add(0, "Python");
String first = list.get(0); // O(n)随机访问

// 作为队列使用（FIFO）
Queue<String> queue = new LinkedList<>();
queue.offer("task1"); // 尾部入队
String task = queue.poll(); // 头部出队

// 作为双端队列使用（Deque）
Deque<String> deque = new LinkedList<>();
deque.push("first");  // 头部入栈
deque.push("second");
String top = deque.pop(); // 头部出栈（LIFO）

// 作为栈使用
Deque<String> stack = new LinkedList<>();
stack.push("item");
stack.pop();

5. 适用场景

需要频繁头尾操作（如队列、栈）。
数据量不大、随机访问较少的场景。
实现LRU缓存等需要双向链表的场景。

6. 不适用场景与替代方案

频繁随机访问：使用ArrayList。
大数据量场景：内存占用比ArrayList大得多。
需要高效缓存：链表节点离散存储，CPU缓存命中率低。

7. 优缺点与技术取舍

优点：头尾操作O(1)、无需扩容、灵活的双端操作。缺点：随机访问O(n)、每个节点额外存储两个指针导致内存占用大、缓存不友好。

8. 常见问题及解决方案

Q：LinkedList的get(int)如何优化？

// 优化：从近端开始遍历
Node<E> node = (index < (size >> 1)) ? first : last;
// 从头部或尾部向中间遍历

LinkedList源码中确实采用了这种优化，从距离目标更近的一端开始遍历。

9. 版本差异与实现边界

LinkedList没有容量限制，不存在扩容问题。
Java 8+：实现了Spliterator以支持并行遍历。
注意：LinkedList不是线程安全的。

10. 常见追问

Q：LinkedList为什么实现了Deque接口？ A：双向链表天然支持头尾操作，实现Deque接口使其可作为队列、双端队列、栈使用，提供更大的灵活性。

11. 易错点

错误：LinkedList的随机访问比ArrayList快。
正确：LinkedList随机访问O(n)，ArrayList随机访问O(1)。
错误：LinkedList比ArrayList更省内存。
正确：LinkedList每个节点需要存储两个指针，比ArrayList更耗内存。
错误：LinkedList中间插入删除一定比ArrayList快。
正确：如果需要先查找位置（O(n)），总体不一定更快。

一句话总结

LinkedList基于双向链表，头尾操作O(1)，随机访问O(n)，适合作为队列、栈或需要频繁两端操作的List。

ArrayList的定义、区别、原理是什么？

原始问法：

ArrayList和LinkedList的区别是什么？

CopyOnWriteArrayList的原理是什么？适用场景？

来源题目：SRC-02-22-068, SRC-02-22-069

面试先答

ArrayList和LinkedList的核心区别在于底层数据结构：ArrayList基于动态数组，随机访问O(1)、中间操作O(n)；LinkedList基于双向链表，头尾操作O(1)、随机访问O(n)。CopyOnWriteArrayList是线程安全的ArrayList实现，采用写时复制（Copy-On-Write）原理，每次修改操作都会复制整个底层数组，适用于读多写少的并发场景。

核心结论

ArrayList vs LinkedList：数组 vs 链表，随机访问 vs 头尾操作。
CopyOnWriteArrayList采用COW机制，写操作复制整个数组。
CopyOnWriteArrayList适用于读多写少、数据量不大的并发场景。

第一部分：ArrayList vs LinkedList

1. 是什么

维度	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1)	O(n)
尾部添加	O(1)	O(1)
头部添加/删除	O(n)	O(1)
中间插入/删除	O(n)	O(n)（需查找）
内存占用	较少（数组紧凑）	较大（每节点两个指针）
缓存友好	是（连续内存）	否（离散内存）
扩容机制	1.5倍自动扩容	无需扩容
线程安全	否	否
额外实现	RandomAccess	Deque, Queue

2. 为什么需要它

ArrayList适合随机访问多、尾部操作多的场景；LinkedList适合头尾操作多的场景。选择正确的数据结构对性能至关重要。

3. 底层原理与完整流程

ArrayList：基于Object[]数组，元素在内存中连续存储，通过索引直接计算内存地址。

// ArrayList随机访问：O(1)
public E get(int index) {
    rangeCheck(index);
    return elementData(index); // 直接通过数组下标访问
}

LinkedList：基于双向链表，节点离散存储，需遍历定位。

// LinkedList随机访问：O(n)
public E get(int index) {
    checkElementIndex(index);
    return node(index).item; // 需要遍历到指定位置
}

4. 怎么使用

// 场景1：随机访问多 → ArrayList
List<Integer> randomAccessList = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    randomAccessList.add(i);
}
int val = randomAccessList.get(50000); // O(1)超快

// 场景2：头部操作多 → LinkedList
List<String> headOpList = new LinkedList<>();
for (int i = 0; i < 10000; i++) {
    headOpList.add(0, "item" + i); // O(1)头部插入
}

第二部分：CopyOnWriteArrayList

5. 是什么

CopyOnWriteArrayList是java.util.concurrent包下的线程安全List实现，采用**写时复制（Copy-On-Write, COW）**机制：每次写操作都会创建底层数组的新副本，在副本上修改完成后再替换原数组。

6. 底层原理与完整流程

核心字段：

public class CopyOnWriteArrayList<E> implements List<E> {
    private static final Object[] EMPTY_ARRAY = {};
    private transient volatile Object[] array; // volatile保证可见性
}

写操作流程（以add为例）：

获取当前数组快照。
创建新数组（原数组长度+1）。
将新元素放入新数组。
通过setArray()将新数组替换原数组。

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();
    }
}

读操作流程：

直接读取当前数组引用，无锁。
读操作基于数组快照，保证弱一致性。

7. 怎么使用

// 创建CopyOnWriteArrayList
List<String> list = new CopyOnWriteArrayList<>();

// 写操作：加锁+复制数组
list.add("Java");
list.add("Python");
list.remove("Java");

// 读操作：无锁，基于快照
for (String item : list) {
    System.out.println(item); // 迭代时的快照不受并发写影响
}

// 并发场景使用
// 线程1：读多
for (String item : list) { ... }
// 线程2：写少
list.add("newItem");

8. 适用场景

读多写少：如配置列表、白名单、事件监听器列表。
遍历操作远多于修改：遍历不需要加锁，性能高。
数据量不大：每次写操作复制整个数组，大数据量开销大。

9. 不适用场景与替代方案

写多场景：频繁复制数组开销太大。
大数据量场景：数组复制消耗大量内存。
强一致性要求：COW是最终一致性，迭代时可能看不到最新数据。

替代方案：

写多读少：使用Collections.synchronizedList()或显式加锁的ArrayList。
需要强一致性：使用Collections.synchronizedList()。

10. 优缺点与技术取舍

优点：读操作无锁、线程安全、迭代时不会ConcurrentModificationException。缺点：写操作开销大（复制整个数组）、内存占用大、弱一致性。

11. 常见问题及解决方案

Q：CopyOnWriteArrayList的迭代器为什么不会抛ConcurrentModificationException？

// 迭代时使用的是数组快照
public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
    // getArray()返回的是当时的数组引用
    // 即使后续写操作替换了数组，迭代器仍操作原数组
}

12. 版本差异与实现边界

CopyOnWriteArrayList使用ReentrantLock保护写操作。
读操作基于volatile数组引用，保证可见性。
迭代器是弱一致的，不反映实时修改。
Java 8+：新增forEach等方法。

13. 常见追问

Q：CopyOnWriteArrayList的写操作为什么还要加锁？ A：虽然写时复制本身可以通过CAS实现，但加锁保证了多个写操作的原子性，避免同时修改导致数据丢失。

14. 易错点

错误：CopyOnWriteArrayList是强一致的。
正确：它是弱一致的，迭代时看到的是快照，不保证实时性。
错误：CopyOnWriteArrayList适合写多场景。
正确：它适合读多写少，写多场景性能极差。
错误：CopyOnWriteArrayList迭代时可以修改。
正确：迭代器本身不支持修改，但可以通过ListIterator进行修改操作。

一句话总结

ArrayList适合随机访问场景，LinkedList适合头尾操作场景，CopyOnWriteArrayList通过写时复制实现线程安全，适合读多写少的并发场景。

Java集合框架 · 2.3 Set相关

HashSet的底层实现是什么？

原始问法：

HashSet的底层实现是什么？

来源题目：SRC-02-23-070

面试先答

HashSet的底层是一个HashMap实例。HashSet内部维护了一个HashMap对象，将所有元素作为HashMap的Key存入，Value则统一使用一个静态常量PRESENT（空Object对象）。因此HashSet的特性完全继承自HashMap：无序、O(1)的add/contains/remove性能、非线程安全。默认初始容量16，加载因子0.75，按2倍扩容。

核心结论

HashSet基于HashMap实现，元素作为Key存储，Value为静态常量PRESENT。
特性继承HashMap：无序、O(1)操作、非线程安全。
默认容量16，加载因子0.75，2倍扩容。

1. 是什么

java.util.HashSet是基于哈希表的Set接口实现，通过内部维护的HashMap存储元素，利用HashMap Key的唯一性保证Set元素的不可重复性。

2. 为什么需要它

复用HashMap的成熟实现，避免重复开发哈希表逻辑。HashMap的哈希分布和扩容机制已经非常成熟，HashSet直接享用这些成果。

3. 底层原理与完整流程

核心结构：

public class HashSet<E> implements Set<E> {
    private transient HashMap<E,Object> map; // 底层HashMap
    private static final Object PRESENT = new Object(); // 占位Value

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null; // put返回null表示新增成功
    }

    public boolean contains(Object o) {
        return map.containsKey(o); // 直接委托给HashMap
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
}

关键特性：

元素作为HashMap的Key，利用Key的唯一性保证不重复。
PRESENT是所有Value的统一占位符，不存储实际数据。
所有方法都直接委托给内部HashMap。

4. 怎么使用

// 创建HashSet
Set<String> set = new HashSet<>();

// 添加元素
set.add("Java");
set.add("Python");
set.add("Java"); // 重复元素，添加失败

// 判断存在
boolean hasJava = set.contains("Java"); // true

// 删除元素
set.remove("Python");

// 遍历
for (String lang : set) {
    System.out.println(lang);
}

// 指定初始容量和加载因子
Set<Integer> numbers = new HashSet<>(32, 0.5f);

5. 适用场景

元素去重场景：如标签集合、用户ID集合。
需要快速判断元素是否存在的场景。
不关心元素顺序的场景。

6. 不适用场景与替代方案

需要有序遍历：使用LinkedHashSet（保持插入顺序）或TreeSet（自然排序）。
需要线程安全：使用Collections.synchronizedSet()或ConcurrentHashMap.newKeySet()。

7. 优缺点与技术取舍

优点：O(1)的add/contains/remove性能、实现简单。缺点：无序、非线程安全、元素可变可能导致问题。

8. 常见问题及解决方案

Q：HashSet和HashMap的性能参数一致吗？ 是的，HashSet的构造函数会配置HashMap的初始容量和加载因子。

9. 版本差异与实现边界

Java 8+：HashSet的迭代器使用HashMap的KeySet迭代器。
Java 9+：新增Set.of()不可变集合工厂方法。
注意：HashSet的元素（作为HashMap的Key）必须正确实现hashCode()和equals()。

10. 常见追问

Q：HashSet的元素可以为null吗？ A：可以。HashMap的Key允许null，所以HashSet也允许null元素。

11. 易错点

错误：HashSet内部使用ArrayList存储。
正确：HashSet内部使用HashMap存储，元素作为Key。
错误：HashSet判断重复只用equals。
正确：HashSet使用hashCode()定位桶位置，再用equals()判断是否为同一对象。

一句话总结

HashSet基于HashMap实现，将元素作为Key存储，利用HashMap Key唯一性实现元素去重，提供O(1)的基本操作性能。

HashSet如何检查元素重复？

原始问法：

HashSet如何检查元素重复？

来源题目：SRC-02-23-071

面试先答

HashSet通过同时使用hashCode()和equals()两个方法来检查元素重复。添加元素时，首先调用元素的hashCode()计算哈希值，定位到HashMap中的桶位置；如果桶为空，直接插入；如果桶不为空，则在桶内链表或红黑树中逐个比较，使用equals()判断是否为同一对象。只有hashCode()相同且equals()返回true时，才认为元素重复。因此重写equals()时必须同时重写hashCode()。

核心结论

HashSet检查重复分两步：先hashCode()定位桶，再equals()确认同一对象。
两个对象equals()相等时，hashCode()必须相同；反之不一定。
同时重写equals()和hashCode()是保证HashSet/HashMap正确工作的前提。

1. 是什么

HashSet的去重机制继承自HashMap的Key去重机制：通过哈希值快速定位、equals精确比较的两阶段策略判断元素唯一性。

2. 为什么需要它

仅用equals()逐个比较效率太低（O(n)），仅用hashCode()无法处理哈希冲突。两者结合实现了平均O(1)的查找性能。

3. 底层原理与完整流程

添加元素流程：

调用key.hashCode()通过扰动函数计算哈希值。
通过(n-1) & hash计算桶位置（n为HashMap容量）。
检查桶是否为空：
- 桶为空 → 直接插入新节点。
- 桶不为空 → 进入步骤4。
遍历桶内链表/红黑树：
- 比较哈希值是否相同。
- 如果哈希值相同，调用equals()比较。
- equals()返回true → 元素重复，覆盖旧值。
- equals()返回false → 继续遍历。
遍历到末尾仍未找到 → 添加新节点。

// HashMap.putVal()核心逻辑示意
if ((p = tab[i = (n - 1) & hash]) == null) {
    tab[i] = newNode(hash, key, value, null); // 桶为空，直接插入
} else {
    // 桶不为空，遍历链表/红黑树
    for (int binCount = 0; ; binCount++) {
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
            // hashCode相同 && equals为true → 元素重复
            break;
        }
        if (p.next == null) {
            // 到达链表末尾 → 添加新节点
            p.next = newNode(hash, key, value, null);
            break;
        }
        p = p.next;
    }
}

4. 怎么使用

public class Employee {
    private int id;
    private String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return id == employee.id && Objects.equals(name, employee.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name); // 必须与equals使用相同字段
    }
}

Set<Employee> set = new HashSet<>();
set.add(new Employee(1, "Alice"));
set.add(new Employee(1, "Alice")); // equals+hashCode相同，不会重复添加

5. 适用场景

自定义对象需要存入HashSet/HashMap时，必须正确重写equals()和hashCode()。
所有需要判断对象相等性的场景。

6. 不适用场景与替代方案

不需要判断重复的场景：使用List即可。
需要自定义比较规则（非equals）：使用TreeSet/TreeMap的Comparator。

7. 优缺点与技术取舍

优点：平均O(1)的查找性能。缺点：需要正确实现hashCode()和equals()，否则会导致元素丢失。

8. 常见问题及解决方案

Q：为什么重写equals()必须重写hashCode()？

// 反例：只重写equals不重写hashCode
public class BadClass {
    @Override
    public boolean equals(Object o) { /* 基于字段比较 */ }
    // 没有重写hashCode，使用Object.hashCode()（基于内存地址）
}

Set<BadClass> set = new HashSet<>();
BadClass a = new BadClass(1);
BadClass b = new BadClass(1);
set.add(a);
set.contains(b); // 可能返回false！因为hashCode不同，找不到a

9. 版本差异与实现边界

HashMap在JDK 1.8中引入红黑树，链表长度≥8且桶数≥64时树化。
树节点的equals()和hashCode()逻辑与链表节点一致。

10. 常见追问

Q：如果两个对象hashCode()相同，但equals()不同，会怎样？ A：它们会在同一个桶中以链表形式存储，不会被判定为重复。这是合法的，但过多会影响性能。

11. 易错点

错误：HashSet判断重复只看hashCode()。
正确：先看hashCode()定位桶，再用equals()精确比较。
错误：两个对象equals()相等，hashCode()可以不同。
正确：这是契约规定的，equals()相等时hashCode()必须相同，反之不然。

一句话总结

HashSet通过hashCode()定位桶位置、equals()精确比较的两步机制判断元素重复，要求同时正确实现这两个方法。

Set要实现排序该怎么办？

原始问法：

Set要实现排序该怎么办？

来源题目：SRC-02-23-072

面试先答

Java中Set的排序有三种方式：1）使用TreeSet，基于红黑树自然排序或自定义Comparator排序；2）使用LinkedHashSet，保持元素的插入顺序；3）对HashSet排序后生成新集合。最常用的是TreeSet，它实现了SortedSet接口，可以按元素的自然顺序（实现Comparable）或自定义的Comparator进行排序。LinkedHashSet适合需要保持插入顺序的场景。

核心结论

TreeSet：基于红黑树，支持自然排序和自定义排序。
LinkedHashSet：基于HashMap+链表，保持插入顺序。
排序方式：元素实现Comparable或构造Set时传入Comparator。

1. 是什么

TreeSet：java.util.TreeSet基于红黑树实现的有序Set，实现了SortedSet接口。

LinkedHashSet：java.util.LinkedHashSet基于HashMap+双向链表，保持插入顺序。

2. 为什么需要它

HashSet是无序的，当需要有序遍历时（如按字母排序、按数值排序、保持插入顺序），需要使用有序Set实现。

3. 底层原理与完整流程

TreeSet排序机制：

底层使用TreeMap，元素作为Key存入红黑树。
排序方式有两种：
1. 元素实现Comparable接口（自然排序）。
2. 构造TreeSet时传入Comparator（定制排序）。

// 自然排序：元素实现Comparable
public class Student implements Comparable<Student> {
    private int age;
    private String name;

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

// 定制排序：传入Comparator
Set<String> set = new TreeSet<>(Comparator.reverseOrder());

LinkedHashSet保持顺序：

在HashMap基础上维护双向链表，记录元素插入顺序。
遍历顺序与插入顺序一致。

4. 怎么使用

// 方式1：TreeSet自然排序（元素需实现Comparable）
Set<Integer> sortedSet = new TreeSet<>();
sortedSet.add(3);
sortedSet.add(1);
sortedSet.add(2);
// 遍历输出：1, 2, 3

// 方式2：TreeSet自定义排序
Set<String> customSet = new TreeSet<>(
    (a, b) -> b.compareTo(a) // 降序
);
customSet.add("banana");
customSet.add("apple");
// 遍历输出：banana, apple

// 方式3：LinkedHashSet保持插入顺序
Set<String> orderedSet = new LinkedHashSet<>();
orderedSet.add("third");
orderedSet.add("first");
orderedSet.add("second");
// 遍历输出：third, first, second

// 方式4：先HashSet再排序
Set<Integer> hashSet = new HashSet<>();
hashSet.add(3);
hashSet.add(1);
hashSet.add(2);
List<Integer> sortedList = new ArrayList<>(hashSet);
Collections.sort(sortedList);

5. 适用场景

TreeSet：需要元素按特定规则排序的场景，如按分数排序学生。
LinkedHashSet：需要保持元素插入顺序的场景，如访问记录去重。

6. 不适用场景与替代方案

不需要排序：使用HashSet，性能更好。
需要自定义排序且数据量大：TreeSet本身O(log n)可接受。

7. 优缺点与技术取舍

类型	优点	缺点
HashSet	O(1)操作	无序
TreeSet	有序、O(log n)操作	O(log n)比O(1)慢
LinkedHashSet	保持插入顺序	维护链表有开销

8. 常见问题及解决方案

Q：如何对HashSet排序？

Set<Integer> set = new HashSet<>();
set.add(3); set.add(1); set.add(2);

// 方案1：转为List排序
List<Integer> list = new ArrayList<>(set);
Collections.sort(list);

// 方案2：创建TreeSet
Set<Integer> sorted = new TreeSet<>(set);

9. 版本差异与实现边界

Java 8：TreeSet的headSet()、tailSet()等返回的是原Set的视图。
Java 9+：新增Set.of()不可变有序集合（实际顺序不保证）。

10. 常见追问

Q：TreeSet如何判断元素重复？ A：通过compareTo()或compare()的返回值判断，返回0表示重复。

11. 易错点

错误：TreeSet使用equals()判断重复。
正确：TreeSet使用compareTo()/compare()判断重复，返回0即视为重复。
错误：LinkedHashSet是排序的。
正确：LinkedHashSet保持插入顺序，不是按元素值排序。

一句话总结

Set排序可通过TreeSet（自然/自定义排序）或LinkedHashSet（保持插入顺序）实现，选择取决于排序需求类型。

TreeSet和HashSet的区别是什么？

原始问法：

TreeSet和HashSet的区别是什么？

来源题目：SRC-02-23-073

面试先答

TreeSet和HashSet的核心区别在于底层数据结构和有序性。HashSet基于HashMap（哈希表），无序、O(1)的基本操作性能；TreeSet基于TreeMap（红黑树），有序、O(log n)的基本操作性能。HashSet通过hashCode()+equals()判断重复，TreeSet通过compareTo()/compare()判断重复。HashSet允许null元素（仅一个），TreeSet的自然排序不允许null（会抛NPE）。

核心结论

底层结构：HashMap vs TreeMap（哈希表 vs 红黑树）。
有序性：无序 vs 有序（自然/自定义）。
性能：O(1) vs O(log n)。
判重方式：hashCode+equals vs compareTo/compare。

1. 是什么

维度	HashSet	TreeSet
底层结构	HashMap（哈希表）	TreeMap（红黑树）
有序性	无序	有序（自然/自定义）
添加/查找/删除	O(1)平均	O(log n)
判重方式	hashCode() + equals()	compareTo()/compare()
null支持	支持（一个null）	自然排序不支持null
实现接口	Set, Cloneable, Serializable	NavigableSet, Set, Cloneable, Serializable
额外功能	无	subSet()、headSet()、tailSet()范围操作

2. 为什么需要它

HashSet追求极致的查询性能（O(1)），适用于不关心顺序的场景。TreeSet追求有序性和范围操作能力，适用于需要排序或范围查询的场景。

3. 底层原理与完整流程

HashSet：

基于HashMap数组+链表+红黑树。
通过哈希函数计算桶位置，直接定位。
元素作为HashMap的Key，Value为PRESENT常量。

TreeSet：

基于TreeMap红黑树。
通过比较函数在红黑树中定位位置。
元素作为TreeMap的Key，Value为PRESENT常量。

4. 怎么使用

// HashSet使用
Set<String> hashSet = new HashSet<>();
hashSet.add("banana");
hashSet.add("apple");
hashSet.add("cherry");
// 遍历顺序不确定，可能是：apple, banana, cherry

// TreeSet使用
Set<String> treeSet = new TreeSet<>();
treeSet.add("banana");
treeSet.add("apple");
treeSet.add("cherry");
// 遍历输出：apple, banana, cherry（按字母排序）

// TreeSet范围操作
SortedSet<String> subSet = treeSet.subSet("apple", "cherry"); // [apple, cherry)
SortedSet<String> headSet = treeSet.headSet("banana"); // (< banana)
SortedSet<String> tailSet = treeSet.tailSet("banana"); // (>= banana)

// 自定义排序
Set<Integer> customTreeSet = new TreeSet<>(Comparator.reverseOrder());
customTreeSet.add(1);
customTreeSet.add(3);
customTreeSet.add(2);
// 遍历输出：3, 2, 1

5. 适用场景

HashSet：快速判断元素存在性、去重、不关心顺序。
TreeSet：需要有序遍历、范围查询（subSet/headSet/tailSet）、自定义排序。

6. 不适用场景与替代方案

需要有序但不需要范围查询：使用LinkedHashSet保持插入顺序。
需要极致性能且不关心顺序：使用HashSet。

7. 优缺点与技术取舍

HashSet优点：O(1)操作性能、实现简单。 HashSet缺点：无序、非线程安全。

TreeSet优点：有序、支持范围操作、O(log n)稳定性能。 TreeSet缺点：O(log n)比O(1)慢、需要比较函数。

8. 常见问题及解决方案

Q：TreeSet中元素的修改会影响排序吗？

// 会！因为红黑树的顺序在插入时确定
// 如果修改元素的比较字段，不会重新排序
TreeSet<Student> set = new TreeSet<>();
Student s = new Student("Alice", 20);
set.add(s);
s.setAge(30); // 修改了排序字段
// set中的s仍按20排序，不会重新调整位置

9. 版本差异与实现边界

TreeSet在Java 6实现了NavigableSet接口，增加了floor()、ceiling()等方法。
HashSet在Java 8使用HashMap的树化优化。
两者都使用PRESENT作为占位Value。

10. 常见追问

Q：TreeSet的compareTo()返回0会怎样？ A：视为重复元素，不会添加（或覆盖旧值）。

11. 易错点

错误：TreeSet用equals()判断重复。
正确：TreeSet用compareTo()/compare()判断，返回0即重复。
错误：HashSet允许null，TreeSet不允许null。
正确：HashSet允许一个null；TreeSet在自然排序下不允许null（抛NullPointerException），但自定义Comparator可以支持null。

一句话总结

HashSet基于哈希表追求O(1)性能，无序；TreeSet基于红黑树追求有序性和范围操作，O(log n)，选择取决于是否需要排序和范围查询。

Java集合框架 · 2.4 Map相关（上）

HashMap的定义、区别是什么？

原始问法：

HashMap和Hashtable的区别是什么？

HashMap的底层实现是什么？JDK1.7和1.8的区别是什么？

来源题目：SRC-02-24-074, SRC-02-24-075

面试先答

HashMap基于数组+链表+红黑树实现，JDK 1.8做了重大优化。与Hashtable的核心区别在于：HashMap非线程安全、允许null键值、性能更高；Hashtable线程安全（synchronized）、不允许null键值、性能较低。JDK 1.7的HashMap采用数组+单链表结构，头插法，多线程扩容会死循环；JDK 1.8引入红黑树（链表≥8且桶≥64时树化），改用尾插法，优化了性能和线程安全性。

核心结论

HashMap vs Hashtable：非线程安全vs线程安全、允许nullvs不允许null、性能高vs性能低。
JDK 1.7：数组+单链表，头插法，多线程扩容死循环。
JDK 1.8：数组+链表+红黑树，尾插法，解决多线程死循环问题。

第一部分：HashMap vs Hashtable

1. 是什么

维度	HashMap	Hashtable
线程安全	否	是（synchronized）
null键值	允许（一个null键）	不允许
性能	较高	较低
继承关系	AbstractMap	Dictionary→Map
扩容方式	2倍	2倍+1
迭代器	fail-fast	fail-fast+弱一致（Enumeration）

2. 为什么需要它

HashMap追求单线程高性能，Hashtable追求线程安全但性能低下。实际开发中应优先使用HashMap，并发场景使用ConcurrentHashMap。

3. 底层原理与完整流程

HashMap：JDK 1.8采用Node数组+链表+红黑树结构，table[]数组存储桶，每个桶可以是链表或红黑树。

Hashtable：采用Entry数组+链表结构，几乎所有公共方法都使用synchronized修饰。

第二部分：HashMap JDK 1.7 vs JDK 1.8

4. 底层结构对比

JDK 1.7 HashMap：

结构：数组 + 单链表
数组类型：Entry[] table
链表结构：单向链表
插入方式：头插法（新节点插入链表头部）

JDK 1.8 HashMap：

结构：数组 + 链表 + 红黑树
数组类型：Node[] table
链表结构：单向链表
树化条件：链表长度≥8 且 桶数≥64
树退化：链表长度≤6
插入方式：尾插法（新节点插入链表尾部）

5. 核心差异详解

差异1：数据结构

JDK 1.7只有数组+链表，所有哈希冲突都以链表形式存储。JDK 1.8增加了红黑树，当链表过长时自动转换为红黑树，将最坏情况从O(n)优化到O(log n)。

差异2：插入方式

JDK 1.7使用头插法：新节点总是插入到链表头部。这在多线程扩容时会导致链表成环，引发死循环。

JDK 1.8使用尾插法：新节点插入到链表尾部。解决了多线程扩容的死循环问题。

差异3：hash()扰动函数

JDK 1.7：h = k.hashCode(); h = h ^ (h >>> 16); JDK 1.8：(h = key.hashCode()) ^ (h >>> 16);

JDK 1.8将高位异或改为一行代码，逻辑相同但写法更简洁。

差异4：扩容实现

JDK 1.7：扩容时重新计算每个节点的哈希位置，头插法改变链表顺序。 JDK 1.8：扩容时根据(hash & oldCap)判断新位置，只需判断新增的那一位是0还是1，节点位置不变（要么原位置，要么原位置+旧容量）。

差异5：size()实现

JDK 1.7：size是实际元素数量。 JDK 1.8：size重命名为size（实际未变），但增加了modCount记录修改次数用于fail-fast。

6. 底层原理与完整流程（JDK 1.8）

// HashMap核心字段
static final int DEFAULT_INITIAL_CAPACITY = 16; // 默认容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;  // 加载因子
static final int TREEIFY_THRESHOLD = 8;           // 树化阈值
static final int UNTREEIFY_THRESHOLD = 6;         // 树退化阈值
static final int MIN_TREEIFY_CAPACITY = 64;       // 最小树化容量

transient Node<K,V>[] table; // 哈希表数组
int size;                    // 元素数量
int threshold;               // 扩容阈值 = 容量 × 加载因子
final float loadFactor;      // 加载因子

7. 怎么使用

// HashMap使用
Map<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.get("one");    // 1
map.containsKey("one"); // true
map.remove("one");

// Hashtable使用（不推荐，使用ConcurrentHashMap替代）
Map<String, Integer> table = new Hashtable<>();

// 指定初始容量（避免频繁扩容）
Map<String, Object> map = new HashMap<>(256);

8. 适用场景

HashMap：单线程或只读场景的键值对存储。
Hashtable：不推荐使用，已过时。
ConcurrentHashMap：并发场景下的键值对存储。

9. 不适用场景与替代方案

多线程场景：使用ConcurrentHashMap。
需要有序：使用TreeMap或LinkedHashMap。

10. 优缺点与技术取舍

HashMap优点：O(1)基本操作、允许null、性能高。 HashMap缺点：非线程安全、无序。

Hashtable优点：线程安全。 Hashtable缺点：synchronized导致性能差、不允许null、已过时。

11. 常见问题及解决方案

Q：HashMap的默认容量为什么是16？ A：16是2的幂次方，保证哈希分布均匀（(n-1) & hash等价于hash % n，但位运算更快）。

12. 版本差异与实现边界

JDK 1.7：头插法、单链表、多线程死循环问题。
JDK 1.8：尾插法、红黑树、解决死循环。
JDK 21：支持SequencedMap接口。

13. 常见追问

Q：为什么HashTable的enumerator()是安全的而iterator()不安全？ A：Hashtable的内部类Enumerator使用了弱一致的迭代方式，不检查modCount，而Iterator使用fail-fast机制。

14. 易错点

错误：HashMap是线程安全的。
正确：HashMap非线程安全，并发场景使用ConcurrentHashMap。
错误：JDK 1.8的HashMap头插法不会死循环。
正确：JDK 1.8改用尾插法，解决了头插法的死循环问题。
错误：Hashtable已被完全废弃。
正确：Hashtable是过时的类，但仍存在。应使用ConcurrentHashMap替代。

一句话总结

HashMap基于数组+链表+红黑树，JDK 1.8引入红黑树和尾插法解决哈希冲突和多线程死循环问题，与Hashtable的核心区别在于线程安全性和null支持。

往HashMap里put一个值的过程是怎样的？

原始问法：

往HashMap里put一个值的过程是怎样的？

来源题目：SRC-02-24-076

面试先答

HashMap的put过程：首先对Key调用hash()方法（扰动函数）计算哈希值，然后通过(n-1) & hash定位桶位置；如果桶为空，直接插入新节点；如果桶不为空，先检查首节点是否就是目标Key（hash和equals都相同），相同则覆盖；否则遍历链表或红黑树查找，找到则覆盖，找不到则在尾部/末尾添加新节点；添加后检查是否需要扩容（size > threshold）。

核心结论

put流程：哈希→定位→判断首节点→遍历查找→覆盖或新增→扩容检查。
hash()使用扰动函数：(h = key.hashCode()) ^ (h >>> 16)。
定位桶：(n-1) & hash，n为数组长度（2的幂）。

1. 是什么

HashMap的put方法是其核心操作之一，负责将键值对存入哈希表，涉及哈希计算、冲突解决、链表/红黑树遍历、覆盖旧值和扩容检查等多个步骤。

2. 为什么需要它

put过程的设计直接决定了HashMap的性能。高效的哈希函数和冲突解决策略确保了平均O(1)的操作性能。

3. 底层原理与完整流程

put完整流程图：

put(key, value)
  │
  ├─ 1. 对key调用hash(key)计算哈希值
  │     └─ (h = key.hashCode()) ^ (h >>> 16)  // 扰动函数
  │
  ├─ 2. 判断table是否为空或length=0
  │     └─ 是 → resize()初始化数组
  │
  ├─ 3. 计算桶位置：index = (n-1) & hash
  │
  ├─ 4. 判断桶是否为空
  │     └─ 是 → newNode()创建新节点，return null
  │
  ├─ 5. 桶不为空，获取首节点p
  │     ├─ 5a. p.hash == hash && p.key.equals(key)
  │     │     └─ 首节点就是目标 → 覆盖value，return旧值
  │     │
  │     ├─ 5b. p是TreeNode（红黑树节点）
  │     │     └─ 调用putTreeVal()在红黑树中查找/插入
  │     │
  │     └─ 5c. 遍历链表
  │           ├─ 找到相同key → 覆盖value，return旧值
  │           ├─ 链表长度≥8 → treeifyBin()树化
  │           └─ 遍历到末尾 → 尾插新节点
  │
  ├─ 6. modCount++（fail-fast计数）
  │
  └─ 7. size > threshold → resize()扩容

核心代码解析（JDK 1.8）：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 步骤1：数组为空则初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 步骤2：桶为空，直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    // 桶不为空
    else {
        Node<K,V> e; K k;
        // 步骤3：检查首节点
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 首节点就是目标
        // 步骤4：红黑树查找
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 步骤5：链表遍历
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null); // 尾插
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash); // 树化
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break; // 找到目标
                p = e;
            }
        }
        // 步骤6：找到目标节点，覆盖value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 步骤7：扩容检查
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

4. 怎么使用

Map<String, Integer> map = new HashMap<>();

// 基本put
map.put("apple", 1);
map.put("banana", 2);

// put如果不存在才插入（Java 8+）
map.putIfAbsent("cherry", 3);

// 计算式put（Java 8+）
map.compute("apple", (k, v) -> v + 1); // apple的值+1

// put如果不存在则计算（Java 8+）
map.computeIfAbsent("date", k -> 10); // 仅当key不存在时计算

5. 适用场景

HashMap的put是最常用的操作之一，适用于任何键值对存储场景。

6. 不适用场景与替代方案

并发put：使用ConcurrentHashMap.put()。
需要保持插入顺序：使用LinkedHashMap.put()。

7. 优缺点与技术取舍

put的平均时间复杂度为O(1)，最坏情况（所有元素哈希冲突）为O(n)（链表）或O(log n)（红黑树）。

8. 常见问题及解决方案

Q：put的key为null会发生什么？

// HashMap支持null作为key
map.put(null, "value"); // null的hash值为0，放入桶0
map.get(null); // 返回"value"
// 注意：只能有一个null key

9. 版本差异与实现边界

JDK 1.7：头插法，链表过长时不树化。
JDK 1.8：尾插法，链表≥8桶≥64时树化。

10. 常见追问

Q：为什么用扰动函数？ A：将key的hashCode高16位与低16位异或，增加哈希分布的随机性，减少碰撞。

11. 易错点

错误：put时链表是头插法。
正确：JDK 1.8是尾插法，JDK 1.7才是头插法。
错误：put返回值是新value。
正确：put返回旧value（首次put返回null）。

一句话总结

HashMap的put过程：哈希计算→定位桶→判断首节点→遍历链表/红黑树→覆盖或新增→扩容检查，平均O(1)。

HashMap的扩容机制是怎样的？

原始问法：

HashMap的扩容机制是怎样的？

来源题目：SRC-02-24-077

面试先答

HashMap的扩容机制：当元素数量（size）超过阈值（threshold = 容量×加载因子0.75）时触发扩容。扩容时创建一个容量为原来2倍的新数组，然后将所有节点重新分配到新数组中。JDK 1.8的优化：利用hash & oldCap判断节点在新数组中的位置——如果结果为0，位置不变；如果为1，位置变为原位置+旧容量。这样避免了重新计算哈希，只需判断新增的那一位。

核心结论

扩容触发：size > threshold（默认16×0.75=12）。
扩容策略：2倍扩容，创建新数组。
JDK 1.8优化：通过hash & oldCap快速判断新位置，无需重算哈希。

1. 是什么

HashMap的扩容（resize）是指当哈希表中的元素数量超过阈值时，扩大底层数组容量、重新分配所有节点的过程。

2. 为什么需要它

哈希表需要在元素密度过高时扩容，以维持O(1)的平均查找性能。如果不扩容，哈希冲突会频繁发生，链表越来越长，性能退化为O(n)。

3. 底层原理与完整流程

扩容触发条件：

if (++size > threshold)
    resize(); // 触发扩容

JDK 1.8 resize()流程：

resize()
  │
  ├─ 1. 计算新容量（oldCap × 2）
  │     ├─ oldCap ≤ MAXIMUM_CAPACITY/2 → newCap = oldCap × 2
  │     └─ oldCap > MAXIMUM_CAPACITY → 不扩容
  │
  ├─ 2. 创建新数组：newTab = Node[newCap]
  │
  ├─ 3. 遍历旧数组每个桶
  │     ├─ 3a. 桶只有一个节点 → 直接放入新桶
  │     │     └─ (e.hash & oldCap) == 0 → 新位置 = 原位置
  │     │     └─ (e.hash & oldCap) == 1 → 新位置 = 原位置 + oldCap
  │     │
  │     ├─ 3b. 桶是链表 → 按上述规则拆分到两个新桶
  │     │
  │     └─ 3c. 桶是红黑树 → 拆分后若树太小则退化为链表
  │
  └─ 4. 更新table和threshold

核心代码解析：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;

    // 计算新容量
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 阈值也翻倍
    }

    // 创建新数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

    // 迁移节点
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            if (e.next == null) // 单节点
                newTab[e.hash & (newCap - 1)] = e;
            else if (e instanceof TreeNode) // 红黑树
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            else { // 链表：拆分为两个链表
                Node<K,V> loHead = null, loTail = null;
                Node<K,V> hiHead = null, hiTail = null;
                Node<K,V> next;
                do {
                    next = e.next;
                    // 关键优化：通过hash & oldCap判断新位置
                    if ((e.hash & oldCap) == 0) {
                        // 低位链表：位置不变
                        if (loTail == null) loHead = e;
                        else loTail.next = e;
                        loTail = e;
                    } else {
                        // 高位链表：位置 = 原位置 + oldCap
                        if (hiTail == null) hiHead = e;
                        else hiTail.next = e;
                        hiTail = e;
                    }
                } while ((e = next) != null);
                // 放入新数组
                if (loTail != null) {
                    loTail.next = null;
                    newTab[j] = loHead;
                }
                if (hiTail != null) {
                    hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }

    threshold = newThr;
    return newTab;
}

4. 怎么使用

// 指定初始容量，减少扩容次数
Map<String, Integer> map = new HashMap<>(64); // 初始容量64

// 指定容量和加载因子
Map<String, Integer> map = new HashMap<>(64, 0.5f); // 加载因子0.5，更稀疏

// 手动触发扩容（不推荐）
map.putAll(Collections.emptyMap()); // 间接触发

5. 适用场景

数据量可预估时：指定初始容量避免频繁扩容。
数据量不可预估时：使用默认配置，自动扩容。

6. 不适用场景与替代方案

数据量大且固定：使用new HashMap<>(expectedSize)指定容量。
频繁扩容场景：使用new HashMap<>(expectedSize)预分配。

7. 优缺点与技术取舍

优点：2倍扩容保持哈希分布均匀、JDK 1.8优化减少哈希重算。缺点：单次扩容涉及数组复制，O(n)开销、多线程不安全。

8. 常见问题及解决方案

Q：如何预估HashMap的初始容量？

// 已知元素数量N
int initialCapacity = (int) (N / 0.75f) + 1;
Map<String, Object> map = new HashMap<>(initialCapacity);

Q：扩容后节点位置如何变化？

假设原容量oldCap=16，扩容后newCap=32：
- hash & oldCap == 0 → 新位置 = 原位置（如位置3）
- hash & oldCap != 0 → 新位置 = 原位置 + oldCap（如位置3+16=19）

9. 版本差异与实现边界

JDK 1.7：扩容时重新计算每个节点的哈希位置。
JDK 1.8：通过hash & oldCap快速判断，无需重算哈希。
JDK 1.7头插法导致多线程扩容死循环，JDK 1.8尾插法解决此问题。

10. 常见追问

Q：为什么用2倍扩容而不是3倍或1.5倍？ A：2倍保证新容量始终是2的幂，(n-1) & hash分布最均匀。同时hash & oldCap只有0和1两种结果，恰好能将链表拆分为两部分。

11. 易错点

错误：HashMap扩容是1.5倍。
正确：HashMap是2倍扩容，ArrayList才是1.5倍。
错误：扩容会改变所有元素的位置。
正确：JDK 1.8中大约一半元素位置不变，另一半移动oldCap距离。

一句话总结

HashMap在元素数超过阈值时2倍扩容，JDK 1.8通过hash & oldCap优化节点重分配，只需判断一位即可确定新位置。

HashMap为什么要引入红黑树？树化和退化的条件是什么？

原始问法：

HashMap为什么要引入红黑树？树化和退化的条件是什么？

来源题目：SRC-02-24-078

面试先答

HashMap引入红黑树是为了解决哈希冲突严重时链表查找性能退化的问题。当链表长度达到8且哈希表容量达到64时，链表会树化为红黑树，将最坏情况的查找时间复杂度从O(n)优化到O(log n)。当红黑树节点数减少到6时，又会退化为链表。红黑树是自适应的，只在哈希冲突严重时才介入，平时仍使用链表以维持低维护成本。

核心结论

引入红黑树：解决哈希冲突严重时链表O(n)性能问题。
树化条件：链表长度≥8 且哈希表容量≥64。
退化条件：红黑树节点数≤6。
7是"分水岭"：hashCode实现良好时几乎不会树化。

1. 是什么

红黑树是一种自平衡的二叉搜索树，保证插入、删除、查找的时间复杂度均为O(log n)。HashMap在JDK 1.8中引入红黑树作为哈希冲突严重时的优化结构。

2. 为什么需要它

理想情况下HashMap的哈希分布均匀，每个桶只有0-1个节点，查找O(1)。但如果哈希函数质量差或存在恶意hashCode，大量元素冲突到同一个桶，导致链表过长，查找退化为O(n)。红黑树将最坏情况优化到O(log n)，保证性能下限。

3. 底层原理与完整流程

树化触发流程：

put() → 链表添加节点
  │
  ├─ 链表长度 >= 8
  │     └─ treeifyBin(tab, hash)
  │           │
  │           ├─ tab.length < MIN_TREEIFY_CAPACITY(64)
  │           │     └─ 触发resize()（优先扩容而非树化）
  │           │
  │           └─ tab.length >= 64
  │                 └─ 将链表转换为红黑树

核心常量：

static final int TREEIFY_THRESHOLD = 8;     // 树化阈值
static final int UNTREEIFY_THRESHOLD = 6;   // 退化阈值
static final int MIN_TREEIFY_CAPACITY = 64; // 最小树化容量

为什么是8？

根据泊松分布计算，负载因子0.75时，一个桶中节点数达到8的概率仅为0.00000006（约6千万分之一）。这说明在良好的哈希函数下，几乎不会触发树化。如果频繁树化，说明hashCode实现有问题。

退化条件：当红黑树中节点数减少到≤6时，untreeify()方法将红黑树退化为链表。

4. 怎么使用

// 无需手动操作树化/退化，HashMap自动处理
Map<String, Integer> map = new HashMap<>();

// 故意制造哈希冲突触发树化
// （仅用于理解，实际避免这种情况）
for (int i = 0; i < 100; i++) {
    map.put(new BadKey(i), i); // BadKey的hashCode返回固定值
}
// 当多个桶的链表长度≥8且表容量≥64时自动树化

5. 适用场景

HashMap自动管理树化/退化，无需开发者干预。这是JDK提供的底层性能保证。

6. 不适用场景与替代方案

频繁哈希冲突：应改善hashCode实现而非依赖红黑树。
需要稳定O(log n)性能：直接使用TreeMap。

7. 优缺点与技术取舍

优点：保证最坏情况O(log n)查找、自适应（冲突严重时才树化）。缺点：红黑树维护成本比链表高、增加了内存开销。

8. 常见问题及解决方案

Q：为什么退化阈值是6而不是8？ A：如果树化和退化阈值相同（8），在阈值附近频繁增删会导致反复树化和退化，性能抖动。设置为6（比8小2）提供了缓冲区。

9. 版本差异与实现边界

JDK 1.7：没有红黑树，所有冲突都以链表形式存储。
JDK 1.8：引入红黑树，树化阈值8，退化阈值6。
注意：树化是HashMap的内部优化，对上层透明。

10. 常见追问

Q：什么时候链表长度达到8但没有树化？ A：当哈希表容量<64时，会优先扩容而不是树化。因为扩容能分散节点到更多桶中，降低每桶的平均节点数。

11. 易错点

错误：HashMap的红黑树会经常触发。
正确：正常hashCode实现下，树化概率极低（约6千万分之一）。
错误：只要链表≥8就树化。
正确：还需要桶数≥64，否则优先扩容。

一句话总结

HashMap通过红黑树保证最坏情况O(log n)查找性能，在链表≥8且桶≥64时树化，节点≤6时退化，是自适应的性能优化。

HashMap在JDK1.7中头插法为什么会出现死循环？1.8为什么改成尾插法？

原始问法：

HashMap在JDK1.7中头插法为什么会出现死循环？1.8为什么改成尾插法？

来源题目：SRC-02-24-079

面试先答

JDK 1.7的HashMap在多线程扩容时使用头插法迁移链表节点，会导致链表形成环形结构。具体过程是：线程A和线程B同时触发扩容，A读取旧链表的next指针时被中断，B完成一轮扩容后链表顺序反转，A再继续时next指针指向了已经反转的节点，导致形成环。1.8改用尾插法，链表顺序在扩容后保持不变，不会形成环形结构，彻底解决了死循环问题。

核心结论

JDK 1.7头插法：新节点插入链表头部，扩容时链表反转，多线程下易形成环。
JDK 1.8尾插法：新节点插入链表尾部，扩容后顺序不变，不会形成环。
死循环发生在多线程并发扩容场景下。

1. 是什么

头插法：新节点总是插入到链表头部，修改next指针指向原链表的首节点。

尾插法：新节点插入到链表尾部，不改变已有节点的next指针。

2. 为什么需要它

头插法在单线程下性能稍好（无需遍历到尾部），但多线程扩容时存在链表成环风险。尾插法虽然需要维护尾指针，但彻底解决了多线程死循环问题。

3. 底层原理与完整流程

JDK 1.7头插法死循环过程：

假设原链表：A → B → C → null

时间线：
T1: 线程A读HashMap，触发扩容，读取首节点=A，next=B
T2: 线程B完成扩容，链表变为：B → A → null（头插法导致反转）
T3: 线程A恢复，当前节点=A，A.next已被B改为null
    → 将A作为新链表首节点：A → null
    → 移动到next节点（B），读取B.next=A（B.next已被B改为指向A！）
    → 将B插入新链表首节点：B → A → null
    → 移动到next节点（A），A.next=null
    → 将A插入新链表首节点：A → B → A → null  ← 形成环！
    → 之后get操作遍历链表会陷入死循环

核心问题：头插法导致链表反转，多线程下next指针被修改后形成环形引用。

JDK 1.8尾插法如何解决：

尾插法：
- 新节点始终插入链表尾部
- 扩容时链表顺序保持不变
- 不会出现链表反转
- 多线程下next指针不会出现环形引用

4. 怎么使用

// JDK 1.8+ HashMap已经解决了多线程死循环问题
// 但HashMap仍然是非线程安全的！
Map<String, Integer> map = new HashMap<>();

// 多线程场景务必使用ConcurrentHashMap
Map<String, Integer> safeMap = new ConcurrentHashMap<>();

5. 适用场景

单线程：HashMap（JDK 1.8+尾插法）。
多线程：ConcurrentHashMap。

6. 不适用场景与替代方案

多线程场景：即使JDK 1.8解决了死循环，HashMap仍不保证线程安全，可能丢失数据。

7. 优缺点与技术取舍

JDK 1.7头插法优点：插入速度稍快（无需找到尾部）。 JDK 1.7头插法缺点：多线程扩容死循环、链表顺序反转影响迭代顺序。

JDK 1.8尾插法优点：解决死循环问题、链表顺序稳定。 JDK 1.8尾插法缺点：单线程头插略快（实际差异可忽略）。

8. 常见问题及解决方案

Q：JDK 1.8的HashMap在多线程下还有问题吗？

// 仍可能出现数据丢失
// 两个线程同时put，可能一个覆盖另一个
// 正确做法：使用ConcurrentHashMap
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

9. 版本差异与实现边界

JDK 1.7：头插法、单链表、多线程死循环。
JDK 1.8：尾插法、红黑树、解决死循环。

10. 常见追问

Q：为什么JDK 1.7不直接加锁解决死循环？ A：HashMap设计为非线程安全，加锁会降低单线程性能。正确做法是使用ConcurrentHashMap。

11. 易错点

错误：JDK 1.8的HashMap是线程安全的。
正确：JDK 1.8解决了多线程扩容死循环，但HashMap仍非线程安全。
错误：头插法一定比尾插法快。
正确：头插法在头部插入确实O(1)，但需要维护尾指针的尾插法在HashMap中通过链表遍历实现，实际开销可接受。

一句话总结

JDK 1.8将HashMap的头插法改为尾插法，解决了多线程扩容时的链表成环死循环问题，但HashMap仍然是非线程安全的，并发场景应使用ConcurrentHashMap。

HashMap多线程操作为什么不安全？会出现什么问题？

原始问法：

HashMap多线程操作为什么不安全？会出现什么问题？

来源题目：SRC-02-24-080

面试先答

HashMap在多线程下不安全的根本原因是它没有任何同步机制，多个线程可以同时读写底层数组，导致数据竞争。具体问题包括：1）JDK 1.7头插法导致的扩容死循环；2）数据覆盖丢失（两个线程同时put，一个被覆盖）；3）size计数不准确（并发修改导致count更新丢失）；4）并发修改时迭代器抛ConcurrentModificationException。

核心结论

根本原因：HashMap无同步机制，多线程并发访问导致数据竞争。
主要问题：JDK 1.7死循环、数据丢失、size不准确、fail-fast异常。
解决方案：使用ConcurrentHashMap。

1. 是什么

HashMap非线程安全是指多个线程同时读写HashMap时，可能导致数据不一致或运行时异常。

2. 为什么需要它

理解HashMap的多线程不安全问题，有助于在正确的场景下选择正确的集合类型，避免生产事故。

3. 底层原理与完整流程

问题1：JDK 1.7扩容死循环

多线程同时触发扩容，头插法导致链表成环。
后续get操作遍历链表时陷入死循环。

问题2：数据覆盖丢失

// 两个线程同时put
Thread 1: map.put("key", 1); // 计算桶位置B
Thread 2: map.put("key", 2); // 计算桶位置B
// 两个线程同时修改table[B]，一个结果被覆盖
// 最终map中可能存的是1或2，取决于时序

问题3：size计数丢失

// size++不是原子操作（读-改-写）
Thread 1: 读size=5
Thread 2: 读size=5
Thread 1: 写size=6
Thread 2: 写size=6  ← 本应为7，实际为6
// 丢失了一次计数

问题4：fail-fast异常

// 一个线程在迭代，另一个线程在修改
Thread 1: iterator遍历map
Thread 2: map.put/remove
// iterator检查modCount != expectedModCount
// 抛出ConcurrentModificationException

4. 怎么使用

// 错误示范：多线程使用HashMap
Map<String, Integer> unsafeMap = new HashMap<>();
// Thread 1: unsafeMap.put("key", 1);
// Thread 2: unsafeMap.put("key", 2); // 数据丢失！

// 正确做法：使用ConcurrentHashMap
Map<String, Integer> safeMap = new ConcurrentHashMap<>();
// 或使用Collections.synchronizedMap()
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

5. 适用场景

单线程场景：HashMap。
多线程场景：ConcurrentHashMap。

6. 不适用场景与替代方案

多线程场景下绝不能使用HashMap，必须使用ConcurrentHashMap或通过外部同步保护。

7. 优缺点与技术取舍

HashMap非线程安全换取了单线程的高性能。ConcurrentHashMap通过分段锁/CAS在保证线程安全的同时尽量减少锁竞争。

8. 常见问题及解决方案

Q：使用HashMap的synchronized包装安全吗？

// 可以保证安全，但性能较差（全局锁）
Map<String, Integer> map = Collections.synchronizedMap(new HashMap<>());
// 所有方法都加synchronized，相当于Hashtable

9. 版本差异与实现边界

JDK 1.7：存在死循环问题。
JDK 1.8：解决了死循环，但仍存在数据丢失和size不准确问题。
ConcurrentHashMap：JDK 1.7分段锁、JDK 1.8 CAS+synchronized。

10. 常见追问

Q：多线程下get操作安全吗？ A：JDK 1.8的get不会抛异常，但可能获取到过期数据（因为没有同步）。JDK 1.7的get可能因为死循环导致CPU 100%。

11. 易错点

错误：JDK 1.8的HashMap多线程安全。
正确：JDK 1.8解决了死循环，但仍非线程安全。
错误：HashMap的get在多线程下没问题。
正确：get可能获取到不一致的中间状态。

一句话总结

HashMap无同步机制，多线程下会导致死循环（JDK 1.7）、数据丢失、size不准确和fail-fast异常，并发场景必须使用ConcurrentHashMap。

HashMap的hash()方法原理是什么？如何解决哈希冲突？

原始问法：

HashMap的hash()方法原理是什么？如何解决哈希冲突？

来源题目：SRC-02-24-081

面试先答

HashMap的hash()方法使用扰动函数：将key的hashCode的高16位与低16位进行异或运算（h ^ (h >>> 16)），目的是让哈希值的高位信息参与桶位置的计算，减少哈希冲突。桶位置通过(n-1) & hash计算。哈希冲突的解决方式：JDK 1.8采用链表+红黑树，冲突少时链表存储，链表过长时自动树化为红黑树。

核心结论

hash()扰动函数：(h = key.hashCode()) ^ (h >>> 16)，高16位异或低16位。
桶定位：(n-1) & hash，n为数组长度（2的幂）。
冲突解决：链表+红黑树，链表≥8桶≥64时树化。

1. 是什么

hash()方法是HashMap的哈希扰动函数，用于优化哈希值的分布，减少哈希冲突。

2. 为什么需要它

如果直接使用key.hashCode()的低n位作为桶位置（n为数组长度，如16则取低4位），当hashCode的高位变化但低位相同时，会导致大量冲突。扰动函数将高位信息混入低位，让更多的哈希码参与桶位置的计算。

3. 底层原理与完整流程

扰动函数详解：

// JDK 1.8 hash方法
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

过程图示：

key.hashCode() = 0xABCD1234（32位）
                 1010 1011 1100 1101 0001 0010 0011 0100
                      ↑ 高16位 ↑                 ↑ 低16位

h >>> 16 = 0x0000ABCD
           0000 0000 0000 0000 1010 1011 1100 1101

h ^ (h >>> 16) = 0xABCDBF99  ← 高16位与低16位异或
                 1010 1011 1100 1101 1011 1001 1110 0101
                              ↑ 低16位现在混入了高位信息

桶位置 = (n - 1) & hash = (16 - 1) & 0xABCDBF99
       = 15 & hash = 0x9 = 9（桶索引）

为什么不用取模？

// 等价但更快的位运算
index = (n - 1) & hash  // n是2的幂
// 等价于
index = hash % n
// 但位运算比取模快得多

哈希冲突解决：

冲突数量	解决方式	时间复杂度
0个	直接定位	O(1)
1-7个	链表	O(n)
≥8且桶≥64	红黑树	O(log n)
≤6（退化）	链表	O(n)

4. 怎么使用

// 理解hash()方法
String key = "hello";
int hashCode = key.hashCode(); // 由String实现
int hash = hash(key); // HashMap内部调用
int index = (16 - 1) & hash; // 桶位置

// 实现良好hashCode的自定义类
public class Point {
    private int x, y;

    @Override
    public int hashCode() {
        // 使用Objects.hash()或手动计算
        return Objects.hash(x, y);
    }

    @Override
    public boolean equals(Object o) {
        // ...
    }
}

5. 适用场景

所有需要存储键值对的场景。良好的hashCode实现是HashMap高性能的前提。

6. 不适用场景与替代方案

需要有序映射：使用TreeMap。
哈希冲突严重：优化hashCode或使用TreeMap。

7. 优缺点与技术取舍

优点：扰动函数简单高效、显著减少冲突。缺点：无法完全避免冲突、依赖hashCode质量。

8. 常见问题及解决方案

Q：如果两个key的hashCode相同会怎样？

// 它们会被存储到同一个桶中
// 通过equals()进一步比较是否为同一对象
// 如果不同则以链表/红黑树形式存储
Map<String, Integer> map = new HashMap<>();
map.put("Aa", 1); // "Aa".hashCode() == "BB".hashCode() 在某些JDK实现中
map.put("BB", 2); // 同一桶，链表存储

9. 版本差异与实现边界

JDK 1.7：h = k.hashCode(); h = h ^ (h >>> 16);
JDK 1.8：(h = key.hashCode()) ^ (h >>> 16);（一行代码）
扰动函数逻辑在所有版本中相同。

10. 常见追问

Q：为什么数组容量必须是2的幂？ A：保证(n-1) & hash等价于hash % n且分布均匀。2的幂减1后低位全是1，位运算能覆盖所有哈希位。

11. 易错点

错误：hash()方法就是key.hashCode()。
正确：hash()是对hashCode()进行扰动处理后的结果。
错误：桶位置是hash % 16。
正确：实际是(n-1) & hash，等价于取模但更快。

一句话总结

HashMap通过扰动函数将高16位与低16位异或优化哈希分布，用(n-1) & hash快速定位桶，用链表+红黑树解决哈希冲突。

HashMap的遍历方式有哪些？

原始问法：

HashMap的遍历方式有哪些？

来源题目：SRC-02-24-082

面试先答

HashMap的遍历方式主要有四种：1）遍历KeySet获取Key再取Value；2）遍历Values获取所有Value；3）遍历EntrySet获取键值对；4）使用Java 8的forEach方法。推荐使用EntrySet遍历，因为只需一次迭代即可同时获取Key和Value，性能最佳。遍历过程中修改HashMap会抛ConcurrentModificationException，应使用Iterator的remove()或Java 8的removeIf()。

核心结论

四种遍历方式：KeySet、Values、EntrySet、forEach。
推荐EntrySet：一次遍历获取Key+Value，性能最佳。
遍历时修改需使用Iterator.remove()或forEach的removeIf。

1. 是什么

HashMap的遍历是指依次访问Map中的所有键值对的过程。不同遍历方式在性能和使用便捷性上有差异。

2. 为什么需要它

不同场景需要不同的遍历方式：只需要Key用KeySet，只需要Value用Values，需要键值对用EntrySet。选择合适的遍历方式可以提升性能。

3. 底层原理与完整流程

遍历方式对比：

方式	遍历内容	性能	适用场景
keySet()	所有Key	需要二次查找Value	只需要Key
values()	所有Value	直接获取Value	只需要Value
entrySet()	所有Entry	一次获取Key+Value	需要键值对
forEach()	所有Entry	同entrySet	Java 8+函数式遍历

性能分析：

// 方式1：keySet() + get() — 两次查找，性能差
for (String key : map.keySet()) {
    Integer value = map.get(key); // 额外的哈希查找
}

// 方式2：entrySet() — 一次查找，性能好
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue(); // 直接获取，无额外查找
}

4. 怎么使用

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

// 方式1：遍历KeySet
for (String key : map.keySet()) {
    System.out.println(key);
}

// 方式2：遍历Values
for (Integer value : map.values()) {
    System.out.println(value);
}

// 方式3：遍历EntrySet（推荐）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

// 方式4：Java 8 forEach
map.forEach((key, value) -> System.out.println(key + " = " + value));

// 遍历时安全删除
Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<String, Integer> entry = it.next();
    if (entry.getValue() == 1) {
        it.remove(); // 安全删除
    }
}

// Java 8+ 更简洁的删除方式
map.entrySet().removeIf(e -> e.getValue() == 1);

5. 适用场景

需要键值对：EntrySet遍历。
只需要Key/Value：KeySet/Values遍历。
Java 8+推荐：forEach。

6. 不适用场景与替代方案

遍历时需要修改Map：使用Iterator或removeIf。
并行遍历：使用parallelStream()（Java 8+）。

7. 优缺点与技术取舍

EntrySet遍历性能最佳，因为一次迭代同时获取Key和Value，避免了额外的哈希查找。

8. 常见问题及解决方案

Q：遍历时为什么不能用map.remove()？

// 错误：会抛ConcurrentModificationException
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    map.remove(entry.getKey());
}

// 正确：使用Iterator.remove()
Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
    it.next();
    it.remove();
}

9. 版本差异与实现边界

Java 8：新增forEach()和removeIf()方法。
Java 8：新增spliterator()支持并行遍历。

10. 常见追问

Q：为什么EntrySet遍历比KeySet遍历快？ A：KeySet遍历后还需要通过get(key)再次查找Value，相当于两次哈希查找。EntrySet直接返回Entry对象，一次查找获取Key和Value。

11. 易错点

错误：遍历HashMap时可以安全修改。
正确：使用Map的remove()会抛异常，必须用Iterator.remove()。
错误：KeySet遍历比EntrySet快。
正确：KeySet遍历需要额外get()查找Value，比EntrySet慢。

一句话总结

HashMap推荐使用EntrySet遍历，一次迭代同时获取键值对，遍历时修改需使用Iterator.remove()或Java 8的removeIf()。

HashMap的定义、区别是什么？

原始问法：

TreeMap和HashMap的区别是什么？

HashMap和ConcurrentHashMap的区别是什么？

来源题目：SRC-02-24-083, SRC-02-24-084

面试先答

HashMap vs TreeMap：HashMap基于哈希表，无序，O(1)操作；TreeMap基于红黑树，有序，O(log n)操作。HashMap vs ConcurrentHashMap：HashMap非线程安全，允许null键值；ConcurrentHashMap线程安全（JDK 1.8使用CAS+synchronized），不允许null键值。选择HashMap追求单线程性能，TreeMap追求有序，ConcurrentHashMap追求线程安全。

第一部分：TreeMap vs HashMap

1. 是什么

维度	HashMap	TreeMap
底层结构	数组+链表+红黑树	红黑树
有序性	无序	有序（自然/自定义）
时间复杂度	O(1)平均	O(log n)
null支持	支持null键（一个）	自然排序不支持null
判重方式	hashCode+equals	compareTo/compare
功能	基础键值存储	有序+范围操作
线程安全	否	否

2. 核心区别详解

数据结构：HashMap是哈希表，通过哈希值直接定位桶位置；TreeMap是红黑树，通过比较值在树中定位。

有序性：HashMap无序，遍历顺序不确定；TreeMap按自然顺序或自定义Comparator排序。

范围操作：TreeMap支持subMap()、headMap()、tailMap()等范围查询，HashMap不支持。

3. 怎么使用

// HashMap：快速键值访问
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("apple", 1);
hashMap.get("apple"); // O(1)

// TreeMap：有序键值访问
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("banana", 2);
treeMap.put("apple", 1);
treeMap.put("cherry", 3);
// 遍历输出：apple=1, banana=2, cherry=3

// TreeMap范围操作
SortedMap<String, Integer> subMap = treeMap.subMap("apple", "cherry");
// 返回：{apple=1, banana=2}

第二部分：HashMap vs ConcurrentHashMap

4. 是什么

维度	HashMap	ConcurrentHashMap
线程安全	否	是
null支持	允许null键值	不允许null键值
实现机制	无同步	JDK 1.7分段锁/JDK 1.8 CAS+synchronized
并发性能	N/A	高并发下性能好
数据结构	数组+链表+红黑树	数组+链表+红黑树（与HashMap相同）

5. 核心区别详解

线程安全：HashMap无同步机制，多线程下不安全；ConcurrentHashMap通过分段锁（JDK 1.7）或CAS+synchronized（JDK 1.8）保证线程安全。

null支持：HashMap允许null键和null值；ConcurrentHashMap不允许（会抛NullPointerException），因为并发下无法区分null值和不存在的情况。

性能：单线程下HashMap更快（无锁开销）；多线程下ConcurrentHashMap远优于Hashtable（更细粒度的锁）。

6. 怎么使用

// 单线程：HashMap
Map<String, Integer> singleThreadMap = new HashMap<>();

// 多线程：ConcurrentHashMap
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.put("key", 1); // 线程安全
concurrentMap.get("key");    // 无锁读取

// ConcurrentHashMap不允许null
// concurrentMap.put(null, 1); // 抛NullPointerException
// concurrentMap.put("key", null); // 抛NullPointerException

7. 适用场景

HashMap：单线程键值存储。
TreeMap：需要有序遍历或范围查询。
ConcurrentHashMap：多线程键值存储。

8. 不适用场景与替代方案

多线程+有序：使用ConcurrentSkipListMap。
单线程+有序：使用TreeMap。

9. 优缺点与技术取舍

HashMap优点：O(1)操作、简单。缺点：非线程安全、无序。 TreeMap优点：有序、O(log n)稳定性能、范围操作。缺点：O(log n)比O(1)慢。 ConcurrentHashMap优点：线程安全、高并发性能。缺点：不允许null、实现复杂。

10. 版本差异与实现边界

JDK 1.8中HashMap和ConcurrentHashMap的数据结构相同（数组+链表+红黑树）。
ConcurrentHashMap的synchronized锁的是桶的头节点（Node），粒度比Hashtable的全局锁更细。

11. 常见追问

Q：ConcurrentHashMap的get为什么不加锁？ A：JDK 1.8中get基于volatile数组引用和Node的volatile val，保证了可见性，无需加锁。

12. 易错点

错误：ConcurrentHashMap允许null值。
正确：ConcurrentHashMap不允许null键和null值。
错误：TreeMap的判重方式与HashMap相同。
正确：TreeMap通过compareTo/compare判重，HashMap通过hashCode+equals判重。

一句话总结

HashMap追求单线程O(1)性能，TreeMap追求有序O(log n)，ConcurrentHashMap追求线程安全，三者底层结构相似但设计目标和适用场景完全不同。

ConcurrentHashMap的底层实现是什么？JDK1.7和1.8的区别是什么？

原始问法：

ConcurrentHashMap的底层实现是什么？JDK1.7和1.8的区别是什么？

来源题目：SRC-02-24-085

面试先答

ConcurrentHashMap是线程安全的HashMap实现。JDK 1.7采用分段锁（Segment）机制，将数据分成16个Segment，每个Segment独立加锁，支持16个并发写。JDK 1.8放弃分段锁，改用CAS+synchronized机制，锁粒度细化到桶的头节点，并发性能更高。两者底层数据结构均为数组+链表+红黑树，与HashMap相同。

核心结论

JDK 1.7：Segment分段锁，16个并发写。
JDK 1.8：CAS+synchronized，锁粒度细化到Node。
数据结构：数组+链表+红黑树（与HashMap相同）。

第一部分：JDK 1.7 Segment分段锁

1. 是什么

JDK 1.7的ConcurrentHashMap采用Segment数组+HashEntry数组的双层结构。

ConcurrentHashMap
├── Segment[16] (分段锁数组)
│   ├── Segment[0] → HashEntry[] table
│   ├── Segment[1] → HashEntry[] table
│   ├── ...
│   └── Segment[15] → HashEntry[] table

2. 底层原理

Segment继承自ReentrantLock，每个Segment独立加锁。

static class Segment<K,V> extends ReentrantLock implements Serializable {
    transient HashEntry<K,V>[] table;
    transient int count;
    transient int modCount;
    transient int threshold;
    final float loadFactor;
}

操作流程：

put时，先根据Key定位到具体的Segment（(hash >>> segmentShift) & segmentMask）。
获取该Segment的锁。
在Segment内部的HashEntry数组中查找/插入。
释放锁。

并发度：默认16个Segment，最多支持16个线程同时写操作。

第二部分：JDK 1.8 CAS+synchronized

3. 是什么

JDK 1.8放弃Segment设计，采用与HashMap相同的数组+链表+红黑树结构，使用CAS+synchronized保证线程安全。

ConcurrentHashMap
├── Node[] table (与HashMap相同)
│   ├── Node[0] → null 或 Node → ... → TreeNode
│   ├── Node[1] → null
│   ├── ...
│   └── Node[n] → null 或 Node → ... → TreeNode

4. 底层原理

核心字段：

transient volatile Node<K,V>[] table; // volatile保证可见性
private transient volatile int sizeCtl; // 控制标识符

sizeCtl含义：

-1：正在初始化
-N：有N-1个线程在扩容
0：默认值，表未初始化
0：表的容量或扩容阈值

put流程：

表未初始化 → CAS初始化表。
根据(n-1) & hash定位桶。
桶为空 → CAS直接插入新节点（无锁）。
桶不为空 → synchronized锁住桶的头节点，遍历链表/红黑树。
找到则覆盖，找不到则尾部插入。
检查是否需要树化/扩容。

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // 表未初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        // 桶为空，CAS直接插入
        else if ((f = tabAt(tab, i = (n-1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<>(hash, key, value)))
                break; // CAS成功
        }
        // 正在扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        // 桶不为空，synchronized锁住头节点
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) { // 链表
                        // 遍历链表，找到则覆盖，找不到则尾部添加
                    } else if (f instanceof TreeBin) { // 红黑树
                        // 调用putTreeVal
                    }
                }
            }
        }
    }
}

第三部分：JDK 1.7 vs JDK 1.8对比

5. 核心差异

维度	JDK 1.7	JDK 1.8
数据结构	Segment[] + HashEntry[]	Node[] + 链表 + 红黑树
锁机制	Segment分段锁（ReentrantLock）	synchronized + CAS
并发度	固定16	理论上与桶数相同
锁粒度	Segment级（粗）	Node级（细）
树化	不支持	支持（≥8且≥64）
扩容	Segment内部扩容	多线程协作扩容
读取	ReentrantLock或无锁	无锁（volatile）

6. 怎么使用

// JDK 1.8+ ConcurrentHashMap
Map<String, Integer> map = new ConcurrentHashMap<>();

// 基本操作（线程安全）
map.put("key", 1);
Integer val = map.get("key");
map.remove("key");

// 原子复合操作
map.putIfAbsent("newKey", 1); // 仅当key不存在时插入
map.computeIfAbsent("counter", k -> 0);
map.compute("counter", (k, v) -> v + 1);

// 并发批量操作
map.putAll(otherMap); // 原子性（内部加锁）

7. 适用场景

JDK 1.7遗留系统：保持不变。
新系统：使用JDK 1.8+的ConcurrentHashMap。
高并发场景：JDK 1.8+性能更优。

8. 不适用场景与替代方案

不需要线程安全：使用HashMap。
需要有序+线程安全：使用ConcurrentSkipListMap。

9. 优缺点与技术取舍

JDK 1.7优点：实现简单、分段锁易于理解。缺点：并发度固定、Segment固定开销。

JDK 1.8优点：锁粒度细、并发度高、与HashMap结构一致。缺点：实现复杂（CAS+synchronized+多线程扩容）。

10. 常见问题及解决方案

Q：JDK 1.8的synchronized性能比ReentrantLock好吗？ A：在JDK 1.6+中，synchronized经过偏向锁、轻量级锁等优化后，性能与ReentrantLock相当或更优。而且synchronized在JVM层面实现，更容易优化。

11. 版本差异与实现边界

JDK 1.7：Segment分段锁，每个Segment独立扩容。
JDK 1.8：CAS+synchronized，多线程协作扩容（helpTransfer）。
JDK 1.8：引入红黑树优化。

12. 易错点

错误：ConcurrentHashMap的get需要加锁。
正确：JDK 1.8的get基于volatile读，无需加锁。
错误：ConcurrentHashMap的并发度是16。
正确：JDK 1.7是16，JDK 1.8的并发度理论上等于桶数。
错误：ConcurrentHashMap允许null值。
正确：ConcurrentHashMap不允许null键和null值。

一句话总结

ConcurrentHashMap在JDK 1.7使用Segment分段锁，JDK 1.8改用CAS+synchronized细化锁粒度，并发性能更高，是生产环境首选的线程安全Map。

Java集合框架 · 2.4 Map相关（下）

ConcurrentHashMap如何实现线程安全？

原始问法：

ConcurrentHashMap如何实现线程安全？

来源题目：SRC-02-24-086

面试先答

JDK 1.8的ConcurrentHashMap通过CAS+synchronized组合实现线程安全。读操作基于volatile数组引用和Node的volatile字段，无需加锁即可保证可见性；写操作分三层：空桶用CAS直接插入（无锁），非空桶用synchronized锁住桶的头节点（细粒度锁），红黑树用TreeBin的读锁优化。扩容时支持多线程协作迁移，每个线程负责一段区间的迁移。相比Hashtable的全局synchronized，ConcurrentHashMap的锁粒度细化到桶级别，并发性能大幅提升。

核心结论

读操作：基于volatile，无锁，保证可见性。
写操作：空桶用CAS，非空桶用synchronized锁桶头节点。
扩容：多线程协作迁移，每个线程负责一段。
锁粒度：桶级别（Node），远细于Hashtable的全局锁。

1. 是什么

ConcurrentHashMap的线程安全是指在多线程并发读写场景下，能够保证数据的一致性和操作的原子性，且通过细粒度锁策略最大化并发性能。

2. 为什么需要它

Hashtable使用全局synchronized锁，任何操作都要竞争同一把锁，性能极低。ConcurrentHashMap通过CAS+synchronized实现细粒度锁，大幅提升了并发性能。

3. 底层原理与完整流程

三大核心机制：

机制1：volatile保证可见性

// 数组引用volatile
transient volatile Node<K,V>[] table;

// Node的key和val是volatile的
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;     // volatile保证可见性
    volatile Node<K,V> next; // volatile保证可见性
}

volatile保证了读操作无需加锁即可看到其他线程的最新写入。

机制2：CAS实现无锁插入

// 空桶的CAS插入
if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    // CAS：期望值null，新值newNode
    if (casTabAt(tab, i, null, new Node<>(hash, key, value)))
        break; // CAS成功，无需加锁
}

机制3：synchronized实现桶级锁

// 非空桶的synchronized保护
synchronized (f) { // f是桶的头节点
    if (tabAt(tab, i) == f) { // 双重检查
        if (fh >= 0) { // 链表：遍历查找/插入
            // ...
        } else if (f instanceof TreeBin) { // 红黑树
            // ...
        }
    }
}

put完整流程：

put(key, value)
  │
  ├─ 1. 检查key/value非null
  │
  ├─ 2. 计算哈希：hash = spread(key.hashCode())
  │
  ├─ 3. 表未初始化 → CAS初始化表
  │
  ├─ 4. 根据(n-1) & hash定位桶
  │     │
  │     ├─ 4a. 桶为空 → CAS直接插入（无锁）
  │     │
  │     ├─ 4b. 桶正在扩容 → 协助扩容
  │     │
  │     └─ 4c. 桶不为空 → synchronized锁头节点
  │           ├─ 链表：遍历查找→覆盖或尾部新增
  │           └─ 红黑树：TreeBin的读写锁保护
  │
  └─ 5. 检查是否需要树化/扩容

get流程：

get(key)
  │
  ├─ 1. 计算哈希
  │
  ├─ 2. 定位桶
  │     │
  │     ├─ 桶为空 → return null
  │     │
  │     ├─ 头节点就是目标 → return val
  │     │
  │     ├─ 正在扩容 → 协助扩容后重试
  │     │
  │     └─ 遍历链表/红黑树查找
  │
  └─ 3. 找到 → return val（基于volatile读，无锁）

4. 怎么使用

// 创建ConcurrentHashMap
Map<String, Integer> map = new ConcurrentHashMap<>();

// 基本操作（线程安全）
map.put("counter", 0);
Integer val = map.get("counter"); // 无锁读取

// 线程安全的复合操作
// 非原子操作（错误）
if (!map.containsKey("key")) {
    map.put("key", computeValue()); // 非原子
}

// 原子操作（正确）
map.putIfAbsent("key", computeValue()); // 原子性

// 计数场景
map.compute("counter", (k, v) -> v + 1); // 原子性
map.merge("counter", 1, Integer::sum); // 原子性

5. 适用场景

多线程键值对存储（配置缓存、计数器等）。
高并发场景（比Hashtable性能高得多）。
需要线程安全的Map操作。

6. 不适用场景与替代方案

单线程场景：HashMap更快。
需要有序：ConcurrentSkipListMap（并发+有序）。
不需要线程安全：HashMap。

7. 优缺点与技术取舍

优点：高并发性能、锁粒度细、读写分离（读无锁）。缺点：不允许null、实现复杂、迭代器弱一致。

8. 常见问题及解决方案

Q：ConcurrentHashMap的size()如何实现？

// JDK 1.8使用baseCount + CounterCell数组（类似LongAdder）
// 避免全局锁统计size
public int size() {
    long n = map.mappingCount();
    return (n > Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n;
}

Q：为什么ConcurrentHashMap不允许null？

// 并发下无法区分：
// key不存在？还是key存在但value为null？
// 单线程下可以用containsKey()区分，但并发下两次操作不原子
// 因此直接禁止null

9. 版本差异与实现边界

JDK 1.7：Segment分段锁，每个Segment独立。
JDK 1.8：CAS+synchronized，桶级锁，多线程扩容。
JDK 1.8：size()使用LongAdder思想（baseCount+CounterCell）。
JDK 1.8：TreeBin使用读锁（读无锁、写加锁）。

10. 常见追问

Q：synchronized锁的是什么对象？ A：锁的是桶的头节点（Node对象），不同桶的锁互不影响。

11. 易错点

错误：ConcurrentHashMap的get需要加锁。
正确：get基于volatile读，完全无锁。
错误：ConcurrentHashMap的put全程加锁。
正确：空桶用CAS无锁插入，只有非空桶才synchronized。
错误：ConcurrentHashMap的size()是精确的。
正确：size()使用LongAdder思想，最终一致性，不是绝对精确。

一句话总结

JDK 1.8的ConcurrentHashMap通过CAS处理空桶插入、synchronized锁住桶头节点、volatile保证可见性，实现了高并发性能的线程安全Map。

ConcurrentHashMap有哪些原子性复合操作方法？

原始问法：

ConcurrentHashMap有哪些原子性复合操作方法？

来源题目：SRC-02-24-087

面试先答

ConcurrentHashMap提供了丰富的原子性复合操作方法，主要分为四类：1）条件插入类：putIfAbsent()（仅当key不存在时插入）；2）条件删除类：remove(key, value)（仅当键值匹配时删除）；3）条件替换类：replace(key, oldValue, newValue)（仅当旧值匹配时替换）；4）计算类：compute()、computeIfAbsent()、computeIfPresent()、merge()（基于旧值计算新值）。这些方法将多个操作组合成原子操作，避免了竞态条件。

核心结论

条件插入：putIfAbsent(key, value) - 不存在才插入。
条件删除：remove(key, value) - 值匹配才删除。
条件替换：replace(key, old, new) - 旧值匹配才替换。
计算类：compute()、merge() - 原子计算新值。

1. 是什么

原子性复合操作是指将多个关联操作（如"先判断再操作"）打包成一个原子操作，避免在并发场景下的竞态条件。ConcurrentHashMap从JDK 1.8开始提供这些方法。

2. 为什么需要它

在没有原子复合操作时，开发者需要自己实现"判断+操作"的原子性，通常使用synchronized或ReentrantLock。ConcurrentHashMap内置的原子方法由内建锁机制保证，性能更高且使用更便捷。

3. 底层原理与完整流程

putIfAbsent(key, value)：

// JDK 1.8实现
public V putIfAbsent(K key, V value) {
    return putVal(key, value, true, false); // onlyIfAbsent=true
}

// 核心逻辑（在synchronized块内）
if (tabAt(tab, i) == f) {
    if (fh >= 0) { // 链表
        // 遍历查找key
        if (key.equals(f.k)) {
            // key已存在 → 返回旧值，不覆盖
            return f.val;
        }
        // key不存在 → 尾插新节点
    }
}

remove(key, value)：

// 仅当key存在且value匹配时才删除
public boolean remove(Object key, Object value) {
    // synchronized块内：
    if (key.equals(f.k) && value.equals(f.v)) {
        // 删除节点
        return true;
    }
    return false;
}

compute(key, remappingFunction)：

// 原子计算：基于旧值计算新值
public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    // synchronized块内：
    V oldValue = ...; // 获取旧值
    V newValue = remappingFunction.apply(key, oldValue); // 计算新值
    if (newValue == null) {
        // 删除key
    } else {
        // 更新为新值
    }
    return newValue;
}

4. 怎么使用

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// 1. putIfAbsent - 原子性不存在才插入
map.put("key", 1);
map.putIfAbsent("key", 2); // key已存在，不插入
// map.get("key") = 1

// 典型场景：缓存初始化
String value = map.computeIfAbsent("config", k -> loadConfig());

// 2. remove(key, value) - 原子性条件删除
map.put("counter", 5);
map.remove("counter", 5); // 值匹配才删除
map.remove("counter", 99); // 值不匹配，不删除

// 3. replace(key, old, new) - 原子性条件替换
map.put("status", "ACTIVE");
map.replace("status", "ACTIVE", "INACTIVE"); // 旧值匹配才替换
map.replace("status", "PENDING", "COMPLETED"); // 旧值不匹配，不替换

// 4. compute - 原子性计算
// 计数器场景
map.compute("counter", (k, v) -> v == null ? 1 : v + 1);

// 5. computeIfAbsent - 不存在时计算并插入
// 缓存场景（懒加载）
User user = userCache.computeIfAbsent("userId", id -> loadUser(id));

// 6. computeIfPresent - 存在时计算并更新
map.computeIfPresent("score", (k, v) -> v + 10);

// 7. merge - 合并计算
map.merge("score", 50, Integer::sum); // score += 50
map.merge("score", 30, (old, newVal) -> Math.max(old, newVal)); //取最大值

5. 适用场景

putIfAbsent：缓存初始化、单例创建。
remove(key, value)：CAS风格的状态更新（如"只有状态为ACTIVE时才删除"）。
replace：乐观锁更新（如版本号匹配替换）。
compute/merge：计数器、聚合计算（如单词统计）。

6. 不适用场景与替代方案

简单的put/get：直接使用，无需复合操作。
多Key复合操作：使用putAll()或外部同步。

7. 优缺点与技术取舍

优点：原子性保证、使用简洁、性能优于外部加锁。缺点：Lambda表达式可能在高并发下增加CPU开销、极端场景下可能重复计算。

8. 常见问题及解决方案

Q：computeIfAbsent中如果返回null会怎样？

// ConcurrentHashMap不允许null
// computeIfAbsent的mappingFunction不能返回null
// 否则会抛NullPointerException
map.computeIfAbsent("key", k -> null); // 抛出NPE

Q：这些原子操作的性能如何？

// 内部使用synchronized锁桶的头节点
// 同一桶的操作串行，不同桶并行
// 性能优于Hashtable的全局锁
// 冲突严重时（同一桶）可能有竞争

9. 版本差异与实现边界

JDK 1.8：引入所有原子复合操作方法。
JDK 8之前：需要自行实现复合操作的原子性。
注意：foreach、splititerator等方法是弱一致的，不反映实时修改。

10. 常见追问

Q：ConcurrentHashMap的原子方法和Hashtable的复合操作有什么区别？ A：Hashtable的复合操作也是原子的（因为全局synchronized），但粒度粗、性能低。ConcurrentHashMap粒度细、并发性能高。

11. 易错点

错误：putIfAbsent会覆盖已有值。
正确：putIfAbsent仅当key不存在时才插入，不会覆盖。
错误：ConcurrentHashMap的复合操作不是原子的。
正确：所有内置的复合操作都是原子的，由内部锁机制保证。
错误：computeIfAbsent可以返回null。
正确：ConcurrentHashMap不允许null，返回null会抛NPE。

一句话总结

ConcurrentHashMap提供了putIfAbsent、remove(key,value)、replace、compute、merge等原子复合操作，将"判断+操作"打包为原子操作，避免竞态条件，是高并发场景下的利器。

Java集合框架 · 2.5 队列相关

Queue和Deque的区别是什么？

原始问法：

Queue和Deque的区别是什么？

来源题目：SRC-02-25-088

面试先答

Queue是先进先出（FIFO）的单向队列接口，只允许在队尾插入、队头删除；Deque是双端队列接口，允许在两端（队头和队尾）同时插入和删除，既可作为FIFO队列也可作为LIFO栈使用。Deque继承了Queue接口，在Queue的基础上扩展了反向操作方法。常用实现包括LinkedList（基于双向链表）和ArrayDeque（基于循环数组）。

核心结论

Queue：单向FIFO队列，只允许尾部入队、头部出队。
Deque：双端队列，两端均可出入，支持FIFO和LIFO。
Deque继承Queue，扩展了offerFirst/pollFirst等方法。

1. 是什么

Queue：java.util.Queue是单向队列接口，遵循先进先出（FIFO）原则。

Queue（FIFO）:
  入队 → [ 队尾 | ... | 队头 ] → 出队

Deque：java.util.Deque是双端队列接口，支持在两端插入和删除。

Deque（双端）:
  头部入/出 ↔ [ 头 | ... | 尾 ] ↔ 尾部入/出

2. 为什么需要它

Queue提供了标准的FIFO队列抽象，适用于任务排队等场景。Deque在此基础上扩展了双端操作，可灵活用作队列或栈，一个接口满足两种数据结构需求。

3. 底层原理与完整流程

Queue核心方法：

方法	含义	失败行为
offer(e)	尾部插入	返回false
add(e)	尾部插入	抛异常
poll()	头部删除并返回	返回null
remove()	头部删除并返回	抛异常
peek()	查看头部不删除	返回null
element()	查看头部不删除	抛异常

Deque核心方法（扩展Queue）：

方法	含义
offerFirst(e)	头部插入
offerLast(e)	尾部插入（等同Queue.offer）
pollFirst()	头部删除（等同Queue.poll）
pollLast()	尾部删除
peekFirst()	查看头部
peekLast()	查看尾部
push(e)	头部插入（栈操作）
pop()	头部删除（栈操作）

4. 怎么使用

// Queue使用（FIFO）
Queue<String> queue = new LinkedList<>();
queue.offer("task1");  // 尾部入队
queue.offer("task2");
String task = queue.poll(); // 头部出队 → "task1"
String next = queue.peek(); // 查看头部 → "task2"

// Deque作为队列使用（FIFO）
Deque<String> deque = new LinkedList<>();
deque.offerLast("first");  // 尾部入队
deque.offerLast("second");
deque.pollFirst();         // 头部出队 → "first"

// Deque作为栈使用（LIFO）
Deque<String> stack = new ArrayDeque<>();
stack.push("bottom");   // 入栈
stack.push("top");
String top = stack.pop(); // 出栈 → "top"
stack.peek();            // 查看栈顶 → "bottom"

// Deque双端操作
Deque<Integer> dq = new LinkedList<>();
dq.offerFirst(1); // 头部插入：[1]
dq.offerLast(2);  // 尾部插入：[1, 2]
dq.offerFirst(0); // 头部插入：[0, 1, 2]
// dq.pollFirst() → 0
// dq.pollLast() → 2

5. 适用场景

Queue：消息队列、任务队列、缓冲区。
Deque：需要灵活双端操作的场景、实现栈、BFS遍历。

6. 不适用场景与替代方案

需要优先级排序：使用PriorityQueue。
需要阻塞等待：使用BlockingQueue。

7. 优缺点与技术取舍

Queue优点：接口简洁、语义清晰（FIFO）。缺点：只能单向操作。

Deque优点：灵活可同时用作队列和栈、两端操作O(1)。缺点：接口方法较多。

8. 常见问题及解决方案

Q：为什么推荐用Deque代替Stack实现栈？

// 旧方式（不推荐）
Stack<Integer> stack = new Stack<>(); // 继承Vector，synchronized

// 新方式（推荐）
Deque<Integer> stack = new ArrayDeque<>(); // 无锁、性能好

9. 版本差异与实现边界

Queue接口从Java 5引入。
Deque接口从Java 6引入。
LinkedList同时实现List、Queue、Deque三个接口。

10. 常见追问

Q：ArrayDeque和LinkedList作为Deque实现的区别？ A：ArrayDeque基于循环数组，随机访问快、缓存友好；LinkedList基于双向链表，头尾操作灵活、无容量限制。

11. 易错点

错误：Queue可以在两端插入。
正确：Queue只能在尾部插入、头部删除。
错误：Deque不能作为Stack使用。
正确：Deque提供push/pop方法，是推荐的Stack实现。

一句话总结

Queue是单向FIFO队列，Deque是双向队列，Deque继承Queue并扩展了两端操作，可灵活作为队列或栈使用。

队列和栈的区别是什么？常用实现类有哪些？

原始问法：

队列和栈的区别是什么？常用实现类有哪些？

来源题目：SRC-02-25-089

面试先答

队列是先进先出（FIFO）的数据结构，元素在队尾入队、在队头出队；栈是后进先出（LIFO）的数据结构，元素在栈顶入栈、在栈顶出栈。两者的核心区别在于元素的进出顺序。常用实现类：队列有LinkedList（基于双向链表）、ArrayDeque（基于循环数组）、PriorityQueue（优先级队列）；栈推荐使用Deque接口的ArrayDeque或LinkedList实现，不推荐使用旧的Stack类。

核心结论

队列：FIFO，尾进头出。
栈：LIFO，顶进顶出。
队列实现：LinkedList、ArrayDeque、PriorityQueue。
栈实现：ArrayDeque（推荐）、LinkedList、Stack（过时）。

1. 是什么

队列（Queue）：先进先出（FIFO）的线性数据结构。

队列（FIFO）:
  rear → [ 1 | 2 | 3 ] → front
  入队(rear)              出队(front)

栈（Stack）：后进先出（LIFO）的线性数据结构。

栈（LIFO）:
  top → [ 3 ]  ← 栈顶
         [ 2 ]
         [ 1 ]  ← 栈底
  入栈(push) ↓  出栈(pop) ↑

2. 为什么需要它

队列适用于需要按顺序处理的场景（如任务队列），栈适用于需要回溯的场景（如函数调用、表达式求值、浏览器后退）。

3. 底层原理与完整流程

队列操作：

offer(e)/add(e)：在队尾插入元素。
poll()/remove()：删除并返回队头元素。
peek()/element()：查看队头元素但不删除。

栈操作：

push(e)：在栈顶插入元素。
pop()：删除并返回栈顶元素。
peek()：查看栈顶元素但不删除。

常用实现类：

实现类	底层结构	队列操作	栈操作	线程安全
LinkedList	双向链表	O(1)头尾	O(1)头部	否
ArrayDeque	循环数组	O(1)头尾	O(1)头尾	否
PriorityQueue	最小堆	O(log n)	不支持	否
Stack（过时）	动态数组	不支持	O(1)	是（synchronized）
ConcurrentLinkedQueue	CAS链表	O(1)	不支持	是

4. 怎么使用

// 队列使用
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);   // 入队
queue.offer(2);
queue.poll();      // 出队 → 1
queue.peek();      // 查看 → 2

// 栈使用（推荐ArrayDeque）
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);     // 入栈
stack.push(2);
stack.pop();       // 出栈 → 2
stack.peek();      // 查看 → 1

// 栈使用（LinkedList实现）
Deque<Integer> stack2 = new LinkedList<>();
stack2.push(1);
stack2.push(2);
stack2.pop();      // → 2

// 优先级队列
Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
pq.poll();         // → 1（最小值优先出队）

// 优先级队列（自定义排序）
Queue<String> pq2 = new PriorityQueue<>(Comparator.reverseOrder());
pq2.offer("banana");
pq2.offer("apple");
pq2.poll();        // → "banana"（降序，最大值优先出队）

5. 适用场景

队列：消息队列、线程池任务队列、BFS广度优先搜索、缓冲区。
栈：函数调用栈、表达式求值、括号匹配、浏览器后退、DFS深度优先搜索。

6. 不适用场景与替代方案

需要随机访问：使用List。
需要优先级：使用PriorityQueue。

7. 优缺点与技术取舍

队列优点：FIFO语义清晰、适合按顺序处理。 队列缺点：不支持随机访问。

栈优点：LIFO语义适合回溯场景、函数调用天然栈结构。 栈缺点：只能访问栈顶元素。

8. 常见问题及解决方案

Q：为什么不推荐使用java.util.Stack？

// Stack类问题：
// 1. 继承Vector，方法都是synchronized，性能低
// 2. 接口设计不清晰（同时有push/pop和List的方法）
// 3. Deque接口更现代、性能更好

// 推荐替代方案
Deque<Integer> stack = new ArrayDeque<>(); // 首选
Deque<Integer> stack = new LinkedList<>(); // 备选

9. 版本差异与实现边界

Stack从Java 1.0就存在，属于过时API。
Deque从Java 6引入，是推荐的栈和队列实现。
ArrayDeque在Java 6引入，基于循环数组。

10. 常见追问

Q：ArrayDeque为什么比LinkedList性能好？ A：ArrayDeque基于循环数组，内存连续、缓存命中率高；LinkedList基于双向链表，节点离散、缓存命中率低。

11. 易错点

错误：Stack是推荐的栈实现。
正确：应该使用Deque接口的ArrayDeque或LinkedList实现。
错误：队列只能用LinkedList实现。
正确：ArrayDeque也是优秀的队列实现，基于循环数组。
错误：PriorityQueue遵循FIFO。
正确：PriorityQueue按优先级排序，不是FIFO。

一句话总结

队列FIFO、栈LIFO，Deque接口统一支持两者，推荐使用ArrayDeque实现，淘汰旧的Stack类。

阻塞队列的常用实现类有哪些？分别有什么特点？

原始问法：

阻塞队列的常用实现类有哪些？分别有什么特点？

来源题目：SRC-02-25-090

面试先答

阻塞队列（BlockingQueue）是Java并发包提供的线程安全队列，支持在队列满时阻塞插入、队列空时阻塞获取。常用实现类包括：ArrayBlockingQueue（基于数组，有界）、LinkedBlockingQueue（基于链表，可选有界）、SynchronousQueue（零容量，直接交付）、PriorityBlockingQueue（优先级排序）、DelayQueue（延迟过期）、LinkedBlockingDeque（双端阻塞）。它们广泛应用于线程池、生产者-消费者模式等并发场景。

核心结论

阻塞队列支持阻塞的put/take操作，是生产者-消费者模式的核心工具。
常用实现：ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、PriorityBlockingQueue、DelayQueue。
每个实现有不同的数据结构和特性，适用于不同场景。

1. 是什么

java.util.concurrent.BlockingQueue是阻塞队列接口，继承自Queue，新增了两个核心方法：

put(e)：当队列满时阻塞，直到有空位。
take()：当队列空时阻塞，直到有元素。

public interface BlockingQueue<E> extends Queue<E> {
    void put(E e) throws InterruptedException;  // 阻塞插入
    E take() throws InterruptedException;     // 阻塞获取
    boolean offer(E e, long timeout, TimeUnit unit); // 限时插入
    E poll(long timeout, TimeUnit unit); // 限时获取
}

2. 为什么需要它

阻塞队列解决了生产者-消费者模式中的线程同步问题。没有阻塞队列时，需要手动实现wait/notify或Lock/Condition，代码复杂且容易出错。阻塞队列封装了这些复杂性，提供了简洁易用的API。

3. 底层原理与完整流程

核心实现类对比：

实现类	底层结构	容量	排序	适用场景
ArrayBlockingQueue	数组+ReentrantLock	固定有界	FIFO	固定容量的生产者-消费者
LinkedBlockingQueue	链表+AtomicInteger	可选有界（默认Integer.MAX）	FIFO	高吞吐生产者-消费者
SynchronousQueue	CAS+LockSupport	0（直接交付）	无	直接交付（线程池）
PriorityBlockingQueue	最小堆+ReentrantLock	无界	优先级	优先级任务调度
DelayQueue	堆+ReentrantLock+Condition	无界	延迟时间	定时任务调度
LinkedBlockingDeque	双向链表+ReentrantLock	可选有界	双端	双端阻塞队列

ArrayBlockingQueue原理：

// 核心结构
public class ArrayBlockingQueue<E> implements BlockingQueue<E> {
    private final Object[] items;     // 存储数组
    private final ReentrantLock lock; // 可重入锁
    private final Condition notEmpty; // 非空条件
    private final Condition notFull;  // 非满条件
    private int takeIndex;            // 取索引
    private int putIndex;             // 放索引
    private int count;                // 元素数量

    // put流程
    public void put(E e) throws InterruptedException {
        lock.lockInterruptibly();
        try {
            while (count == items.length)
                notFull.await(); // 队列满，阻塞等待
            enqueue(e); // 入队
            notEmpty.signal(); // 唤醒等待的消费者
        } finally {
            lock.unlock();
        }
    }

    // take流程
    public E take() throws InterruptedException {
        lock.lockInterruptibly();
        try {
            while (count == 0)
                notEmpty.await(); // 队列空，阻塞等待
            E x = dequeue(); // 出队
            notFull.signal(); // 唤醒等待的生产者
            return x;
        } finally {
            lock.unlock();
        }
    }
}

SynchronousQueue原理：

容量为0的特殊队列：
- put操作必须等待take操作配对才能完成
- 直接在生产者和消费者之间交付数据
- 没有中间缓冲区
- 适用于直接交付场景（如Executors.newCachedThreadPool）

DelayQueue原理：

基于PriorityQueue的延迟队列：
- 元素必须实现Delayed接口
- 只有当元素的延迟时间到期后才能被take()获取
- 适用于定时任务调度

4. 怎么使用

// 1. ArrayBlockingQueue（固定容量）
BlockingQueue<Integer> abq = new ArrayBlockingQueue<>(10);

// 生产者
new Thread(() -> {
    for (int i = 0; i < 20; i++) {
        try {
            abq.put(i); // 队列满则阻塞
            System.out.println("生产：" + i);
        } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
    }
}).start();

// 消费者
new Thread(() -> {
    while (true) {
        try {
            Integer val = abq.take(); // 队列空则阻塞
            System.out.println("消费：" + val);
        } catch (InterruptedException e) { Thread.currentThread().interrupt(); break; }
    }
}).start();

// 2. LinkedBlockingQueue（可选容量）
BlockingQueue<String> lbq = new LinkedBlockingQueue<>(100);
lbq.put("task1");
String task = lbq.take();

// 3. SynchronousQueue（直接交付）
BlockingQueue<String> sq = new SynchronousQueue<>();
// 生产者和消费者必须配对
// sq.put("data"); // 阻塞直到有take()
// sq.take();       // 阻塞直到有put()

// 4. PriorityBlockingQueue（优先级）
BlockingQueue<Integer> pbq = new PriorityBlockingQueue<>();
pbq.put(5);
pbq.put(1);
pbq.put(3);
pbq.take(); // → 1（最小值优先出队）

// 5. DelayQueue（延迟过期）
DelayedElement<String> e1 = new DelayedElement<>("task1", 5, TimeUnit.SECONDS);
DelayQueue<DelayedElement<String>> dq = new DelayQueue<>();
dq.put(e1);
// 5秒后才能take到e1

5. 适用场景

实现类	适用场景
ArrayBlockingQueue	固定容量的生产者-消费者、资源池
LinkedBlockingQueue	高吞吐生产者-消费者、线程池任务队列
SynchronousQueue	直接交付、CachedThreadPool
PriorityBlockingQueue	优先级任务调度
DelayQueue	定时任务、超时管理
LinkedBlockingDeque	双端阻塞、工作窃取队列

6. 不适用场景与替代方案

非并发场景：使用普通Queue。
需要高吞吐量且无序：使用ConcurrentLinkedQueue（非阻塞）。

7. 优缺点与技术取舍

实现类	优点	缺点
ArrayBlockingQueue	固定内存、公平锁可选	生产者消费者互相阻塞
LinkedBlockingQueue	高吞吐、低锁竞争	可选有界，默认极大
SynchronousQueue	无缓冲、直接交付	无容量、必须配对
PriorityBlockingQueue	优先级排序	无界、可能OOM
DelayQueue	延迟精确	无界、实现复杂

8. 常见问题及解决方案

Q：LinkedBlockingQueue和ArrayBlockingQueue如何选择？

// ArrayBlockingQueue：固定容量、内存可控
// 适合已知生产速率的场景
BlockingQueue<Task> queue = new ArrayBlockingQueue<>(100);

// LinkedBlockingQueue：高吞吐、低竞争
// 适合高并发生产者-消费者
BlockingQueue<Task> queue = new LinkedBlockingQueue<>(100);

Q：SynchronousQueue为什么有用？

// Executors.newCachedThreadPool使用SynchronousQueue
// 提交的任务直接交给线程执行，不排队
// 没有空闲线程则创建新线程
ExecutorService executor = Executors.newCachedThreadPool();

9. 版本差异与实现边界

Java 5：引入BlockingQueue接口和ArrayBlockingQueue、LinkedBlockingQueue等。
Java 7：引入LinkedTransferQueue（基于CAS的高性能阻塞队列）。
Java 8：新增forEach()方法。
注意：PriorityBlockingQueue的无界特性可能导致OOM。

10. 常见追问

Q：阻塞队列的put()和offer()有什么区别？ A：put()在队列满时无限期阻塞；offer()在队列满时立即返回false（或限时等待后返回false）。
Q：DelayQueue和Timer的区别？ A：DelayQueue是数据结构，可以存储任意Delayed对象；Timer是定时器，专门用于调度任务。ScheduledExecutorService更适合替代Timer。

11. 易错点

错误：阻塞队列的put()会抛异常。
正确：put()在队列满时阻塞等待，不会抛异常（除非被中断）。
错误：SynchronousQueue有容量1。
正确：SynchronousQueue容量为0，put和take必须配对才能完成。
错误：PriorityBlockingQueue的元素按FIFO排序。
正确：按优先级排序，不是FIFO。

一句话总结

阻塞队列通过put/take的阻塞语义简化了生产者-消费者同步，ArrayBlockingQueue基于数组固定容量、LinkedBlockingQueue基于链表高吞吐、SynchronousQueue零容量直接交付、PriorityBlockingQueue优先级排序、DelayQueue延迟过期，各有所长。