Java 集合概览

一、Java 集合概览

1.1 常见的集合有哪些？

核心要点

• Collection 接口的单列集合：List、Set、Queue
• Map 双列集合：存储键值对
• 重点关注各实现类的底层数据结构和线程安全性

详细解析

Java 集合框架主要分为两大类：

Collection 接口（单列集合）：

Map 接口（双列集合）：

面试口头回答

Java 集合主要分为 Collection 和 Map 两大类。

Collection 是单列集合，下面有三个子接口：

• List 是有序可重复的，主要实现有 ArrayList（动态数组，查询快）、LinkedList（双向链表，增删快）、Vector（线程安全但已不推荐）。
• Set 是无序不可重复的，主要实现有 HashSet（基于 HashMap，无序）、LinkedHashSet（存取有序）、TreeSet（红黑树，自然排序）。
• Queue 是队列，常见实现有 PriorityQueue（小顶堆，按优先级出队）、ArrayDeque（双端队列）。

Map 是双列集合，存储键值对，主要实现有：

• HashMap（性能最好，线程不安全）
• Hashtable（线程安全但性能差）
• LinkedHashMap（保留存取顺序）
• TreeMap（红黑树，按 key 排序）
• ConcurrentHashMap（线程安全，高并发场景首选）

二、List 详解

2.1 ArrayList 和 LinkedList 的区别？

核心要点

• 底层结构：ArrayList 是动态数组，LinkedList 是双向链表
• 随机访问：ArrayList O(1)，LinkedList O(n)
• 增删操作：ArrayList 需要挪动元素 O(n)，LinkedList 只需改指针 O(1)
• 扩容：ArrayList 需要扩容复制，LinkedList 无需扩容
• 内存：ArrayList 结尾预留容量，LinkedList 每个节点两个指针开销

详细解析

关键理解：

• ArrayList 的 O(1) 随机访问是因为数组物理内存连续，根据 baseAddress + index * elementSize 直接寻址。
• LinkedList 增删快的前提是已知操作位置。如果要在中间插入但不知道节点位置，先遍历找到位置是 O(n)，加上插入 O(1)，整体还是 O(n)。

面试口头回答

ArrayList 和 LinkedList 的区别我从六个方面来说：

第一，底层数据结构：ArrayList 是基于动态数组 Object[] 实现的，物理内存连续；LinkedList 是基于双向链表实现的，逻辑上连续但物理内存不要求连续。

第二，随机访问：ArrayList 支持按索引 O(1) 的随机访问，因为数组内存连续，可以直接根据寻址公式定位；LinkedList 不支持下标查询，需要从头遍历到目标位置，时间复杂度是 O(n)。

第三，新增和删除：ArrayList 增删需要挪动数组元素，时间复杂度是 O(n)，不过在尾部增删很快；LinkedList 增删只需要改变指针，时间复杂度是 O(1)。

第四，扩容效率：ArrayList 空间不足时需要扩容，把旧数据复制到新数组，影响性能；LinkedList 不需要扩容。

第五，内存占用：ArrayList 的空间浪费主要体现在列表结尾会预留一定容量；LinkedList 的空间花费体现在每个节点有两个指针。

第六，应用场景：ArrayList 适合随机访问多、增删主要在末尾的场景；LinkedList 适合插入删除频繁、随机访问不多的场景。

2.2 分别插入 1000 条数据哪个性能好？

核心要点

• 尾部插入：ArrayList 性能更好（连续内存操作效率高，扩容次数极少）
• 头部/中间插入：LinkedList 性能更好（避免元素平移）
• 日常开发尾部插入最常见，ArrayList 更符合需求

详细解析

尾部插入（最常见场景）：

• ArrayList：底层是动态数组，尾部插入时 add(E e) 只需在数组末尾添加元素。若容量足够则直接赋值 O(1)；即使需要扩容，1000 条数据的扩容次数极少（初始容量 10，每次扩容 1.5 倍，约需 10 次），整体接近 O(1)。数组的连续内存操作效率很高。
• LinkedList：尾部插入时虽可通过尾指针直接添加 O(1)，但每次插入需创建新节点对象，且链表节点的内存分配和指针操作（prev/next 引用）开销略高于数组的连续内存赋值，实际性能略逊于 ArrayList。

头部或中间插入：

• ArrayList：头部/中间插入 add(int index, E e) 需要将插入位置后的所有元素向后平移，时间复杂度 O(n)。插入 1000 条数据若每次都在头部，总操作量约为 1+2+…+1000 ≈ 50 万次，性能急剧下降。
• LinkedList：若已知前驱节点（如通过 addFirst() 或迭代器定位后插入），只需修改相邻节点的指针 O(1)。即使需要遍历定位，也避免了元素平移的开销，整体效率远高于 ArrayList。

面试口头回答

插入 1000 条数据的性能差异取决于插入位置：

如果是尾部插入，ArrayList 性能更好。虽然 ArrayList 可能需要扩容，但 1000 条数据的扩容次数很少，大概就 10 次左右，而且数组的连续内存操作效率很高。LinkedList 每次插入都要创建新节点对象，指针操作的开销略高，所以整体性能 ArrayList 更优。

如果是头部或中间插入，LinkedList 性能更好。ArrayList 头部或中间插入需要把后面的元素全部向后平移，插入 1000 条的话操作量可能达到 50 万次，性能急剧下降。LinkedList 只需要修改指针，时间复杂度 O(1)，效率远高于 ArrayList。

所以总结下来：尾部插入选 ArrayList，头部或中间插入选 LinkedList。日常开发中尾部插入是最常见的场景，因此 ArrayList 的插入性能通常更符合需求。

2.3 ArrayList 和 Array 的区别？

核心要点

• 大小：Array 固定，ArrayList 动态扩容
• 泛型：Array 不支持，ArrayList 支持
• 基本类型：Array 可以直接存，ArrayList 需要包装类
• 功能：Array 简单数据结构，ArrayList 提供丰富的集合操作方法

详细解析

面试口头回答

ArrayList 和 Array 的区别主要有四个方面：

第一，大小和扩容：数组在创建时必须指定大小，而且大小是固定的，一旦创建就不能更改；ArrayList 是动态数组，大小可以动态增长，容量不足时会自动扩容。

第二，泛型支持：数组不支持泛型；ArrayList 支持泛型，可以指定存储的元素类型，这样更类型安全。

第三，存储对象：数组可以直接存储基本类型数据，也可以存储对象；ArrayList 中只能存储对象，对于基本类型需要使用对应的包装类，比如 int 要用 Integer。

第四，集合功能：数组是一个简单的数据结构，不提供额外的方法来进行元素的增删改查；ArrayList 是集合框架的一部分，提供了丰富的方法，比如添加、删除、查找、遍历等，使用更方便。

2.4 ArrayList 成员变量与扩容机制

核心要点

• DEFAULT_CAPACITY = 10：默认初始容量
• Object[] elementData：存储元素的数组缓冲区
• int size：实际存储的元素个数
• 扩容：创建新数组（原容量 1.5 倍），复制旧数组内容
• JDK8 优化：无参构造先创建空数组，第一次添加时才扩容到 10

详细解析

核心成员变量：

transient Object[] elementData;  // 存储元素的数组缓冲区
private int size;                 // ArrayList 实际存储的元素个数
private static final int DEFAULT_CAPACITY = 10;  // 默认初始容量

扩容机制：

1. 初始化：无参构造创建空数组 elementData = {}（JDK8 优化，延迟分配内存）
2. 第一次添加：内部调用扩容方法，创建长度为 10 的数组
3. 第 2-10 次添加：直接添加，容量足够
4. 第 11 次添加：容量不足，grow() 方法将数组扩大为原来的 1.5 倍（计算扩容后长度 = 15），调用 Arrays.copyOf(旧数组, 新长度) 创建新数组并复制旧数组内容

扩容公式：

int newCapacity = oldCapacity + (oldCapacity >> 1);  // 原容量的 1.5 倍

构造函数：

• ArrayList(int initialCapacity)：带初始化容量，直接 new 对应大小的数组，扩容 0 次
• ArrayList()：无参，默认创建空集合
• ArrayList(Collection<? extends E> c)：将集合对象转换成数组，进行数组拷贝

面试口头回答

ArrayList 的核心成员变量有三个：

• DEFAULT_CAPACITY = 10，是默认初始容量；
• Object[] elementData，是存储元素的数组缓冲区；
• int size，是 ArrayList 实际存储的元素个数。

扩容机制是这样的：

• 用无参构造初始化时，ArrayList 其实是个空数组，这是 JDK8 的优化，延迟分配内存。
• 第一次添加元素时，才会创建长度为 10 的数组。
• 第 2 到第 10 次添加，直接添加，容量足够。
• 第 11 次添加时容量不足，会触发 grow 方法，将数组扩容为原来的 1.5 倍，也就是 15，然后调用 Arrays.copyOf 把旧数组内容复制到新数组。

关于构造函数，如果指定了初始容量比如 new ArrayList(10)，那扩容次数就是 0 次，直接创建大小为 10 的数组，等添加的元素超过 10 个才会扩容。所以在能预估数据量的情况下，建议指定初始容量，避免频繁扩容带来的性能开销。

2.5 如何实现数组和 List 之间的转换？

核心要点

• 数组转 List：Arrays.asList(数组)，返回固定大小的列表，底层是原数组的引用
• List 转数组：list.toArray(new String[list.size()])，创建新数组拷贝
• Arrays.asList 修改数组会影响 List；List.toArray 修改 List 不会影响数组

详细解析

数组转 List：

String[] arr = {"a", "b", "c"};
List<String> list = Arrays.asList(arr);

• Arrays.asList() 返回的是 java.util.Arrays 内部类 ArrayList，不是 java.util.ArrayList
• 底层实现是数组的地址赋值，最终指向同一个内存地址
• 所以修改原数组的内容，List 也会受影响
• 注意：返回的 List 长度固定，不支持 add/remove 操作

List 转数组：

List<String> list = new ArrayList<>();
list.add("a");
String[] arr = list.toArray(new String[list.size()]);

• toArray() 底层是 System.arraycopy，创建一个长度为 size 的新数组
• 是数组的拷贝，不是同一个内存地址
• 所以修改 List 的内容，不会影响已经生成的数组

面试口头回答

数组和 List 之间的转换有两种方式：

数组转 List 使用 Arrays.asList(数组) 方法。但要注意，这个方法返回的 List 底层其实是数组的引用，指向的是同一个内存地址，所以如果修改了原数组的内容，List 也会受影响。而且返回的 List 长度是固定的，不能执行 add 或 remove 操作。

List 转数组 使用 list.toArray(new String[list.size()])，传入数组的类型和大小。这个方法底层是 System.arraycopy，会创建一个长度为 size 的新数组，实现数组的拷贝，不是同一个内存地址。所以修改 List 的内容，不会影响已经生成的数组。

总结一下：Arrays.asList 修改数组会影响 List；List.toArray 修改 List 不会影响数组，因为一个是引用赋值，一个是深拷贝。

三、HashMap 详解

3.1 HashMap 概念与数据结构

核心要点

• 基于哈希表的 key-value 键值对存储，利用哈希函数将键映射到数组下标
• 理想情况下查找、插入、删除都是 O(1)
• JDK7：数组 + 链表；JDK8：数组 + 链表 + 红黑树
• 线程不安全

详细解析

HashMap 是 Java 中最常用的 Map 实现，其核心思想是通过哈希函数把 key 映射到数组的某个下标位置，实现快速的查找、插入和删除。

JDK7 数据结构：数组 + 链表

• 数组的每个位置称为"桶"（bucket）
• 当发生哈希冲突时，用拉链法把冲突的元素连成链表

JDK8 数据结构：数组 + 链表 + 红黑树

• 当链表长度 >= 8 且数组长度 >= 64 时，链表转为红黑树，查询效率从 O(n) 提升到 O(log n)
• 当红黑树节点数 <= 6 时（删除或扩容触发），转回链表
• 为什么是 8 和 6 而不是同一个值？防止频繁在链表和红黑树之间转换（树化阈值 > 反树化阈值，形成缓冲）

面试口头回答

HashMap 是基于哈希表的 key-value 键值对存储结构，利用哈希函数把键快速映射到数组下标，理想情况下查找、插入、删除都是常数级别 O(1)，它是线程不安全的。

数据结构方面，JDK7 是数组加链表；JDK8 优化为数组加链表加红黑树。当链表长度大于等于 8，并且数组长度大于等于 64 时，链表会转成红黑树，这样查询效率就从 O(n) 提升到 O(log n)。当红黑树节点数小于等于 6 时，又会转回链表。

用链表转红黑树是为了解决哈希冲突严重时性能退化的问题，但红黑树维护成本比链表高，所以设置了 8 和 6 这两个阈值，避免频繁在两者之间转换。

3.2 HashMap 插入流程

核心要点

1. 计算 key 的 hashCode，再通过扰动函数（高低 16 位异或）计算最终 hash
2. 通过 (n - 1) & hash 定位桶位置
3. 桶为空直接插入；不为空则处理哈希冲突
4. 冲突时先比较 hash 再比较 equals，相同则覆盖 value，不同则追加到链表/红黑树
5. 插入完成后，若 size > threshold（capacity * loadFactor）则扩容

详细解析

步骤详解：

1. 计算 hash 值：

   int hash = hash(key.hashCode());
   // JDK8 扰动函数：(h = key.hashCode()) ^ (h >>> 16)
   

   把 hashCode 的高 16 位和低 16 位异或，让高位也参与运算，改善桶分布、减少冲突。

2. 定位桶位置：

   int index = (n - 1) & hash;
   

   用位运算代替取模，n 是数组长度（2 的幂次）。

3. 判断桶是否为空：

   • 为空：直接新建 Node 存入
   • 不为空：发生哈希冲突，继续下一步

4. 处理哈希冲突：

   • 比较首节点的 key 是否相同（先比 hash，再比 equals）
   • 相同：覆盖原来的 value
   • 不同：继续往下找
     • 如果是链表，遍历链表插入到尾部（JDK8 尾插法）
     • 如果链表长度 >= 8 且数组长度 >= 64，转成红黑树
     • 如果是红黑树，按红黑树插入规则插入

5. 判断是否需要扩容：

   • 插入完成后 size++
   • 如果 size > threshold（capacity * loadFactor，默认 0.75），触发 resize
   • 新建容量为原来 2 倍的数组，重新计算每个节点的新位置并迁移

面试口头回答

HashMap 的插入流程我分五步来说：

第一步，计算 key 的 hash 值。HashMap 先调用 key.hashCode()，再通过扰动函数把高低 16 位异或，让 hash 分布更均匀，减少冲突。

第二步，定位桶位置。通过 (n - 1) & hash 算出 key 应该放在数组的哪个索引位置，这里用位运算代替取模，效率更高。

第三步，判断桶是否为空。如果该位置为空，就直接新建一个 Node 存进去。

第四步，处理哈希冲突。如果桶不为空，先比较首节点的 key 是否相同，先比 hash 再比 equals。如果相同就覆盖原来的 value；如果不同，就往下找。如果是链表结构，就遍历链表插入到尾部，当链表长度超过 8 且数组长度大于等于 64 时，会转成红黑树；如果已经是红黑树，就按红黑树的插入规则插入。

第五步，判断是否需要扩容。插入完成后 size 加 1，如果当前元素个数超过阈值（容量乘以负载因子，默认 0.75），就会触发 resize 操作，新建一个容量为原来两倍的数组，把旧数据迁移过去。

3.3 HashMap 查询流程

核心要点

1. 计算 key 的 hash 值（hashCode + 扰动函数）
2. 通过 (n - 1) & hash 定位桶位置
3. 找到桶首节点，判断 hash 和 key 是否相同
4. 存在冲突则遍历链表或按红黑树搜索逻辑查找
5. 找到返回 value，没找到返回 null

详细解析

查询流程与插入的前几步类似：

1. 计算 hash：int hash = hash(key.hashCode())，同样的扰动函数保证分布均匀。

2. 定位桶：int index = (n - 1) & hash。

3. 找到桶首节点：获取该位置的第一个节点，可能是单节点、链表头或红黑树根节点。

4. 判断节点类型并匹配 key：

   • 如果首节点的 hash 和 key 都相同（通过 equals 比较），直接返回该节点的 value
   • 如果存在哈希冲突：
     • 链表结构：从头到尾遍历链表节点，依次比较 hash 和 equals
     • 红黑树结构：按照红黑树的搜索逻辑（基于 hash + equals）在树中查找

5. 返回结果：找到返回 value，没找到返回 null。

时间复杂度：

• 最佳情况：无冲突，直接数组下标访问，O(1)
• 最坏情况：发生哈希冲突，链表 O(n)，红黑树 O(log n)

面试口头回答

HashMap 的查询流程是这样的：

第一步，计算 key 的 hash 值，先调 hashCode 再通过扰动函数让分布更均匀。

第二步，通过 (n - 1) & hash 算出 key 在数组中的索引位置。

第三步，找到该桶的第一个节点，可能是单节点、链表头或者红黑树根节点。

第四步，判断节点类型并匹配 key。如果首节点的 hash 和 key 都相同，直接返回 value。如果存在哈希冲突，是链表就从头到尾遍历比较 hash 和 equals；是红黑树就按红黑树的搜索逻辑查找。

第五步，找到就返回对应的 value，没找到返回 null。

时间复杂度方面，最佳情况直接通过数组下标访问是 O(1)；最坏情况发生哈希冲突，链表是 O(n)，红黑树是 O(log n)。

3.4 JDK1.7 和 JDK1.8 中 HashMap 的区别？

核心要点

• 数据结构：1.7 数组+链表；1.8 数组+链表+红黑树
• 扩容插入机制：1.7 头插法（可能导致死循环）；1.8 尾插法（避免死循环）
• 扰动函数：1.7 用 hashCode 低位；1.8 高低 16 位异或
• 扩容哈希计算：1.7 重新计算 hash；1.8 通过位运算判断新位置

详细解析

头插法 vs 尾插法的关键区别：

• 头插法在扩容时会反转链表的顺序，多线程环境下可能出现 A→B→A 的环形链表，get 操作陷入死循环
• 尾插法保持链表顺序一致，扩容时不会出现环形链表问题

扩容优化：

• JDK1.8 利用位运算判断节点新位置：e.hash & oldCap == 0 留在原位置，== 1 迁移到原位置 + oldCapacity
• 不需要每个节点都重新计算哈希值，效率更高

面试口头回答

JDK1.7 和 JDK1.8 的 HashMap 主要有四个区别：

第一，数据结构：1.7 是数组加链表；1.8 引入了红黑树，当链表长度大于等于 8 且数组长度大于等于 64 时，链表会转成红黑树，查询效率从 O(n) 提升到 O(log n)。

第二，扩容链表插入机制：1.7 用头插法，会导致链表顺序反转，在多线程环境下可能引发环形链表问题，导致死循环。1.8 改用尾插法，保证链表顺序一致，避免了扩容中的死循环问题。

第三，哈希的扰动函数：1.7 用 hashCode 的低位进行哈希运算，高位没有参与计算，哈希分布不均匀。1.8 引入高 16 位和低 16 位的异或运算，让高位也参与运算，提高了哈希分布的均匀性，减少了冲突。

第四，扩容重新计算哈希槽：1.7 直接用 hash & (table.length - 1) 重新计算每个节点的位置；1.8 利用位运算，通过 hash & oldCap 判断节点是保持在原位置，还是迁移到原位置加旧数组长度，不需要重新计算 hash，效率更高。

3.5 为什么采用红黑树？为什么不选 AVL 树或 B+ 树？

核心要点

• 红黑树是自平衡二叉搜索树，能保证平衡，不会退化成链表
• 不追求绝对平衡，插入删除时旋转次数少，维护代价低
• AVL 树追求绝对平衡，插入删除频繁旋转，开销大
• B+ 树适合磁盘存储和范围查询，不适合 HashMap 这种内存中的高频动态操作

详细解析

红黑树的性质：

1. 节点要么是红色，要么是黑色
2. 根节点是黑色
3. 叶子节点都是黑色的空节点（NIL）
4. 红色节点的子节点都是黑色（不能有连续红节点）
5. 从任一节点到叶子节点的所有路径包含相同数目的黑色节点

为什么选红黑树而不是 AVL 树？

• AVL 树要求每个节点左右高度差不大于 1，平衡要求极高
• AVL 树插入删除时可能需要频繁旋转（最多 O(log n) 次旋转）
• 红黑树不追求绝对平衡，只要求黑色节点平衡，最长路径不超过最短路径的 2 倍
• 红黑树插入删除最多 2 次旋转，维护代价更低
• HashMap 是高频增删查的场景，红黑树整体性能更均衡

为什么不选 B+ 树？

• B+ 树的设计目标是磁盘存储，通过多路分支减少磁盘 I/O，适合数据库索引
• B+ 树每个节点存储更多指针，内存开销较大，对 HashMap 没必要
• HashMap 的设计目标是高效查找单个 key，B+ 树更适合范围查询和外存数据管理

面试口头回答

采用红黑树主要是因为它在平衡性和维护成本之间取得了很好的平衡。

先看红黑树的特点：它是自平衡的二叉搜索树，能保证平衡不会退化成链表，查找、插入、删除的时间复杂度都是 O(log n)。

为什么不选 AVL 树？AVL 树要求每个节点左右高度差不大于 1，平衡要求非常高，插入删除时可能需要频繁旋转，开销比较大。而红黑树不追求绝对平衡，只要求最长路径不超过最短路径的两倍，插入删除最多两次旋转，维护代价更低。HashMap 是高频增删查的场景，红黑树整体性能更均衡。

为什么不选 B+ 树？B+ 树的设计更适合磁盘存储和范围查询，比如数据库索引。它的每个节点存储更多指针，内存开销比较大，而且不适合 HashMap 这种内存中频繁动态操作的场景。HashMap 的目标是对单个 key 的高效查找，红黑树在内存中更轻量，更适合这个需求。

3.6 哈希冲突的解决办法？

核心要点

• 开放定址法：线性探测、二次探测、双重哈希
• 链地址法：冲突元素存储在链表/红黑树中（HashMap 采用）
• 再哈希法：用另一个哈希函数重新计算地址
• 建立公共溢出区：冲突元素统一存入溢出表

详细解析

1. 开放定址法（Open Addressing） 冲突时通过探测技术在哈希表中寻找下一个空闲位置。

• 线性探测：依次检查下一个地址 (hash(key) + i) % table_size，实现简单但容易产生"聚集现象"
• 二次探测：探测地址为 (hash(key) + i²) % table_size，减少聚集但可能无法探测所有位置
• 双重哈希：使用第二个哈希函数计算步长，探测地址为 (hash(key) + i * hash2(key)) % table_size，几乎无聚集现象

2. 链地址法（Chaining）—— HashMap 采用 哈希地址相同的元素存储在同一个链表（或红黑树）中。

• 优点：处理冲突简单，无聚集现象；负载因子可以大于 1；动态扩容成本低
• 缺点：需要额外空间存储指针；链表过长时查询效率下降（可优化为红黑树）

3. 再哈希法（Rehashing） 冲突时使用另一个哈希函数重新计算地址，直到找到空闲位置。需要多个独立哈希函数，实际应用较少。

4. 建立公共溢出区 哈希表分为基本表和溢出表，冲突元素统一存入溢出表。实现简单，但冲突多时溢出表成为瓶颈。

实际应用：链地址法最常用（Java HashMap、Python dict），开放定址法适用于内存紧张或追求连续存储的场景（如数据库索引）。

面试口头回答

解决哈希冲突主要有四种方法：

第一是开放定址法。冲突时通过探测技术在哈希表中找下一个空闲位置。具体有线性探测，就是依次检查下一个地址，实现简单但容易产生聚集；二次探测，用平方数作为步长，减少聚集；还有双重哈希，用第二个哈希函数算步长，几乎没有聚集现象。

第二是链地址法，这也是 HashMap 采用的方式。把哈希地址相同的元素存在同一个链表或者红黑树里。优点是处理冲突简单，不会产生聚集，负载因子可以大于 1；缺点是需要额外空间存指针，链表过长时查询效率会下降，所以 HashMap 在链表过长时转成红黑树优化。

第三是再哈希法。冲突时用另一个哈希函数重新计算地址，直到找到空闲位置。但需要多个独立的哈希函数，实际应用比较少。

第四是建立公共溢出区。把哈希表分成基本表和溢出表，冲突的元素统一放到溢出表里。实现简单，但如果冲突多，溢出表会成为性能瓶颈。

实际应用中链地址法最常用，开放定址法适合内存紧张或追求连续存储的场景。

3.7 HashMap 扩容机制

核心要点

• 触发条件：元素数量 > 容量 × 负载因子（默认 16 × 0.75 = 12）
• 新数组容量 = 旧数组容量 × 2
• JDK1.8 优化：通过位运算判断新位置，无需重新计算 hash
• 尾插法保证链表顺序，避免死循环
• 链表长度 >= 8 且数组长度 >= 64 转红黑树

详细解析

扩容触发条件：

• 默认初始容量 16，负载因子 0.75
• 阈值 threshold = 16 × 0.75 = 12
• 当 size 到达 12 时，第 13 个元素插入会触发扩容

扩容过程：

1. 创建新数组，容量为原来的 2 倍
2. 把旧数组中的元素迁移到新数组

JDK1.8 迁移优化：

• 不需要重新计算每个节点的 hash 值
• 通过 e.hash & oldCap 判断：
  • 结果为 0：元素位置不变，留在原索引
  • 结果为 1：元素移动到 原索引 + oldCapacity
• 原理：数组容量翻倍后，影响索引的位就是 oldCap 对应的那个高位

链表拆分：

• 扩容时把原链表拆成两条：一条留在低位，一条移到高位
• 保持链表原顺序（尾插法），避免 JDK1.7 的头插法死循环问题

树化/反树化：

• 迁移过程中，红黑树也可能被拆分成两条树或链表
• 如果拆分后节点数 <= 6，红黑树退化为链表

面试口头回答

HashMap 的扩容机制是这样的：

触发条件：当元素个数超过阈值时触发扩容，阈值等于容量乘以负载因子，默认是 16 乘 0.75 等于 12。所以插入第 13 个元素时会扩容。

扩容过程：创建一个容量为原来两倍的新数组，然后把原数组的元素重新分配到新数组中。

JDK1.8 的优化：扩容时不需要重新计算每个节点的 hash 值，而是通过位运算判断新位置。具体来说，用 e.hash & oldCap 判断，如果结果是 0，元素就留在原位置；如果结果是 1，元素就移动到原位置加上旧数组长度的位置。这样效率更高。

扩容时链表会被拆分成两条，一条留在低位，一条移到高位。JDK1.8 用尾插法保证链表顺序一致，避免了 1.7 头插法可能导致的死循环问题。

另外，如果桶里是红黑树，迁移时也会被拆分，如果拆分后节点数小于等于 6，红黑树会退化成链表。

3.8 HashMap 的寻址算法 & 数组长度为什么要是 2 的幂次？

核心要点

• 寻址：hashCode → 二次哈希扰动（高低 16 位异或）→ (n-1) & hash 定位索引
• 数组长度是 2 的幂次时，hash % n == hash & (n-1)，位运算效率更高
• 扩容后只需检查 hash 高位变化，迁移简单高效
• 2 的幂次能保证哈希值均匀分布到新数组

详细解析

寻址算法：

// 1. 计算 hashCode
int h = key.hashCode();
// 2. 二次哈希扰动：高 16 位和低 16 位异或
int hash = h ^ (h >>> 16);
// 3. 定位索引：位运算代替取模
int index = (n - 1) & hash;

为什么数组长度要是 2 的幂次？

1. 位运算代替取模效率高： 当 n 是 2 的幂次时，hash % n 等价于 hash & (n-1)。比如 n=16，n-1=15=1111(二进制)，hash & 1111 就是取 hash 的低 4 位，与 hash % 16 结果相同，但位运算比取模快得多。

2. 扩容机制变得简单高效： 扩容后容量变为 2n，新索引只取决于 hash 在 oldCap 对应位是 0 还是 1：

   • hash & oldCap == 0：留在原位置
   • hash & oldCap == 1：移到原位置 + oldCapacity 不需要重新计算 hash。

3. 保证哈希值均匀分布： 2 的幂次时，扩容后元素会被均匀分配到新数组的前半部分和后半部分，减少重新冲突的概率。

面试口头回答

HashMap 的寻址算法分三步：

• 先计算对象的 hashCode；
• 然后进行二次哈希扰动，把 hashCode 右移 16 位后与原值异或，让高位也参与运算，这样哈希值更均匀；
• 最后用 (n-1) & hash 代替取模运算定位数组索引。

数组长度为什么是 2 的幂次，有三个原因：

第一，位运算效率更高。当长度是 2 的幂次时，取模运算可以用位运算代替，比如长度 16，减 1 是 15 也就是二进制 1111，hash & 1111 和 hash % 16 结果一样，但位运算快得多。

第二，扩容机制更简单高效。扩容成两倍后，只需要检查 hash 值在高位是 0 还是 1，就能决定元素是留在原位置还是移到原位置加旧容量，不需要重新计算 hash。

第三，能更好地保证哈希值均匀分布。扩容后在旧数组元素 hash 比较均匀的情况下，新数组元素也会被分配得比较均匀，理想情况是一半在前半部分，一半在后半部分。

3.9 HashMap 为什么线程不安全？

核心要点

• JDK1.7 头插法扩容可能导致环形链表，引发死循环
• 多线程 put 可能导致数据覆盖（非原子操作）
• 多线程并发修改可能抛出 ConcurrentModificationException

详细解析

1. JDK1.7 死循环问题：

• 多线程同时扩容时，头插法会反转链表顺序
• 线程 A 读取到链表 A→B，准备扩容时被挂起
• 线程 B 完成扩容，链表顺序变成 B→A
• 线程 A 恢复后继续扩容，可能形成 A→B→A 的环形链表
• 后续 get 操作遍历链表时陷入死循环，CPU 100%

2. 数据覆盖问题： put 操作不是原子的，包含"判断 key 是否重复"和"插入元素"两个步骤。

场景：线程 1 和线程 2 同时 put 相同的 key

• 线程 1 计算 hash，判断位置为空，准备插入，此时被挂起
• 线程 2 同样计算 hash，也判断位置为空，完成插入 value = “Bob”
• 线程 1 恢复运行，由于之前已判断过"位置为空"，直接插入 value = “Alice”
• 结果：线程 2 的数据被覆盖，丢失更新

3. 并发修改异常： 多线程并发读写时，可能抛出 ConcurrentModificationException。

面试口头回答

HashMap 线程不安全主要有三个问题：

第一是死循环问题，这在 JDK1.7 及之前版本存在。多线程环境下扩容时，头插法可能导致链表顺序反转，形成环形链表。比如线程 A 读到链表 A→B 准备扩容时被挂起，线程 B 扩容后顺序变成 B→A，线程 A 恢复后继续扩容就可能出现 A→B→A 的环，后续 get 操作就会陷入死循环，CPU 直接飙到 100%。

第二是数据覆盖问题。多个线程同时执行 put 操作会有数据覆盖风险。核心原因是 put 里判断 key 是否重复和插入元素这两个步骤不是原子操作。比如两个线程同时 put 同一个 key，都判断当前位置为空，线程 2 先插入，线程 1 恢复后由于之前判断过位置为空，直接覆盖，导致线程 2 的数据丢失。

第三是并发修改异常。多线程并发读写时，可能抛出 ConcurrentModificationException。

JDK1.8 虽然用尾插法解决了死循环问题，但数据覆盖和并发修改异常仍然存在，所以 HashMap 整体还是线程不安全的。

3.10 HashMap 如何实现线程安全？

核心要点

• Collections.synchronizedMap()：包装器，所有操作加同步锁，性能一般
• ConcurrentHashMap：首选，JDK1.8 采用 CAS + synchronized，锁粒度细，并发度高
• 自定义锁：ReentrantLock 等，灵活但复杂
• Hashtable：不推荐，所有方法加 synchronized，性能太差

详细解析

1. Collections.synchronizedMap()：

Map<String, String> map = Collections.synchronizedMap(new HashMap<>());

• 返回一个同步的 Map 包装器
• 所有对 Map 的操作都加了 synchronized
• 锁粒度是整个 Map 对象，并发性能一般

2. ConcurrentHashMap（推荐）：

• JDK1.7：Segment 分段锁，默认 16 个段，每段独立加锁
• JDK1.8：取消 Segment，采用 CAS + synchronized，锁粒度细化到桶级别
• 读操作基本无锁（volatile + CAS），写操作只锁当前链表/红黑树的首节点
• 最大并发度 = Node 数组大小，远高于 Hashtable

3. 自定义锁机制：

• 使用 ReentrantLock 或 ReadWriteLock
• 可以灵活控制锁的粒度和方式
• 实现复杂，需要仔细设计

4. Hashtable（不推荐）：

• 所有公共方法都加了 synchronized
• 锁粒度是整个对象，任何读写操作都会锁住整个表
• 并发性能极差，已基本被 ConcurrentHashMap 取代

面试口头回答

HashMap 实现线程安全有四种方式：

第一是 Collections.synchronizedMap()。它返回一个同步的 Map 包装器，所有操作都加了 synchronized。但锁粒度是整个 Map 对象，并发性能一般。

第二是 ConcurrentHashMap，这也是最推荐的方式。JDK1.7 用 Segment 分段锁，默认分 16 段，每段独立加锁。JDK1.8 做了很大优化，取消了 Segment，改用 CAS 加 synchronized，锁粒度细化到桶级别，只锁定当前链表或红黑树的首节点。只要 hash 不冲突，读写之间就不会产生并发，效率大幅提升。

第三是自定义锁机制。比如在操作 HashMap 时使用 ReentrantLock 来保证线程安全，这种方式比较灵活，但实现复杂。

第四是 Hashtable。它是 Java 早期提供的线程安全 Map，但所有方法都加了 synchronized，锁粒度是整个对象，并发性能太差，现在一般不推荐用。

实际项目中，高并发场景下首选 ConcurrentHashMap。

3.11 ConcurrentHashMap 详解

核心要点

• JDK1.7：Segment 分段锁（Segment 数组 + HashEntry 数组 + 链表）
• JDK1.8：Node 数组 + 链表 + 红黑树，CAS + synchronized 桶级锁
• JDK1.7 最大并发度 = Segment 个数（默认 16）
• JDK1.8 最大并发度 = Node 数组大小，锁粒度更细

详细解析

JDK1.7 实现：

• 数据结构：Segment 数组 + HashEntry 数组 + 链表
• 锁机制：分段锁（Segment 继承 ReentrantLock）
  • 数据分成一段一段存储，每段配一把锁
  • 一个线程占用锁访问某段数据时，其他段的数据也能被其他线程访问
  • 最大并发度 = Segment 个数，默认 16
• 插入流程：
  1. 计算 key 的 hash，确定 Segment 数组下标
  2. 再通过 hash 确定 HashEntry 数组中的下标存储数据
  3. 操作前判断当前 Segment 是否有线程在操作，用 ReentrantLock 加锁，如果锁被占用就用 CAS 自旋尝试

JDK1.8 实现：

• 数据结构：数组 + 链表 + 红黑树（与 HashMap 类似）
• 锁机制：Node 数组 + CAS + synchronized
  • 取消 Segment 分段锁
  • synchronized 只锁定当前链表或红黑树的首节点
  • hash 不冲突就不会产生并发，不影响其他 Node 的读写
  • 最大并发度 = Node 数组的大小，远大于 16
• 优化点：
  • 锁粒度更细，并发性能更高
  • 引入链表转红黑树机制，避免查询退化
  • 扩容采用多线程协作迁移，提高效率

面试口头回答

ConcurrentHashMap 是线程安全的 HashMap 实现，在多线程环境下提供高效的并发访问。

JDK1.7 的实现：数据结构是分段数组加链表。锁机制采用 Segment 分段锁，Segment 继承了 ReentrantLock。数据被分成一段一段存储，每段配一把锁，当一个线程访问某段数据时，其他段的数据也能被其他线程访问。默认有 16 个 Segment，所以最大并发度是 16。插入时先计算 key 的 hash 确定 Segment 下标，再通过 hash 确定 HashEntry 数组的下标，然后用 ReentrantLock 加锁，如果锁被占用就用 CAS 自旋尝试。

JDK1.8 做了很大优化：取消了 Segment 分段锁，数据结构改成数组加链表加红黑树，与 HashMap 类似。锁机制改为 CAS 加 synchronized，synchronized 只锁定当前链表或红黑树的首节点，锁粒度更细。只要 hash 不冲突，就不会产生并发，不影响其他 Node 的读写。最大并发度变成了 Node 数组的大小，远大于 16。同时还引入了链表转红黑树的机制，扩容也采用多线程协作迁移，整体并发性能比 1.7 提升很多。

3.12 ConcurrentHashMap 如何保证扩容时的线程安全？

核心要点

• CAS 标记扩容状态（sizeCtl 为负数表示扩容中）
• Forwarding Node 标记已迁移的桶
• 其他线程遇到 Forwarding Node 会去新数组找数据，或参与迁移
• 多线程协作迁移，无需全表加锁，读不阻塞写

详细解析

ConcurrentHashMap 扩容的线程安全机制：

1. 触发扩容：当一个线程发现容量不足时，用 CAS 把 sizeCtl 标记为负数，表示扩容中，并初始化新数组（容量翻倍）。

2. 桶级迁移：

   • 旧桶中的节点逐个移动到新数组
   • 已迁移的桶用 Forwarding Node 标记（hash 值为 -1）
   • Forwarding Node 指向新数组，其他线程访问到这个节点时，会自动去新数组查找数据

3. 多线程协作：

   • 其他线程发现正在扩容时，可以参与迁移剩余的桶
   • 每个线程负责一段区间，迁移完成后继续下一段
   • 这种设计支持多线程协作迁移，提高性能

4. 安全性保证：

   • 读操作不阻塞：读线程遇到 Forwarding Node 直接去新数组读
   • 写操作不丢失：写线程会帮助完成迁移后再写入
   • 无需全表加锁：只有操作具体桶时才需要同步

面试口头回答

ConcurrentHashMap 扩容通过 CAS、Forwarding Node 和 synchronized 来保证线程安全。

当一个线程发现容量不足触发扩容时，它会用 CAS 把内部状态 sizeCtl 标记为负数，表示扩容中，然后初始化新的数组。

扩容是桶级迁移的，旧桶里的节点逐个移动到新数组。已经迁移完的桶会用 Forwarding Node 标记，它的 hash 值是 -1，指向新数组。其他线程访问到这个 Forwarding Node 时，会自动去新数组找数据，或者参与迁移剩余的桶。

这种设计保证了多线程读写情况下扩容是安全的，同时无需全表加锁。读操作不阻塞，写操作也不会丢数据，而且支持多线程协作迁移，提高了扩容的性能。

3.13 HashMap 和 Hashtable 的区别

核心要点

• 数据结构：HashMap 是数组+链表+红黑树；Hashtable 是数组+链表
• 线程安全：HashMap 不安全性能好；Hashtable 安全但性能差
• null 支持：HashMap 允许一个 null key 和多个 null value；Hashtable 不允许
• 扰动函数：HashMap 有高位低位混合扰动；Hashtable 直接用 hashCode

详细解析

面试口头回答

HashMap 和 Hashtable 的区别主要有四个方面：

第一，数据结构：HashMap 在 JDK8 是数组加链表加红黑树；Hashtable 一直是数组加链表。

第二，线程安全：HashMap 线程不安全，但性能好；Hashtable 线程安全，但内部方法基本都加了 synchronized，锁粒度是整个对象，并发性能很差。

第三，null 支持：HashMap 可以存储一个 null key 和多个 null value；Hashtable 不允许有 null 键和 null 值，否则会抛 NullPointerException。

第四，扰动函数：HashMap 对哈希值进行了高位和低位的混合扰动处理，减少冲突；Hashtable 直接使用键的 hashCode，没有扰动机制。

现在 Hashtable 已经基本被 ConcurrentHashMap 取代了，单线程用 HashMap，多线程用 ConcurrentHashMap。

3.14 HashMap 和 ConcurrentHashMap 的区别

核心要点

• 线程安全性：HashMap 不安全；ConcurrentHashMap 安全
• 迭代器：HashMap 迭代时修改抛异常；ConcurrentHashMap 允许并发修改
• size()：ConcurrentHashMap 返回近似值
• 性能：单线程 HashMap 略高；多线程 ConcurrentHashMap 远高于加锁的 HashMap

详细解析

面试口头回答

HashMap 和 ConcurrentHashMap 的主要区别：

第一，线程安全性：HashMap 不是线程安全的；ConcurrentHashMap 是线程安全的，JDK1.8 采用 CAS 加 synchronized 实现。

第二，迭代时是否需要加锁：HashMap 如果在迭代过程中被其他线程修改，会抛出并发修改异常；ConcurrentHashMap 允许在迭代时进行并发的插入和删除操作，不会抛异常，它返回的是弱一致性的视图。

第三，size 方法：ConcurrentHashMap 的 size 方法返回的是一个大致的近似值，因为在并发环境下各个桶的节点数可能正在更新，所以不是完全精确的实时值。

第四，性能方面：单线程下 HashMap 性能略高，因为没有锁开销；但多线程环境下 ConcurrentHashMap 的性能远超外部加锁的 HashMap。

还有一点，ConcurrentHashMap 不允许 null key 和 null value，而 HashMap 允许。

3.15 集合哪些是线程安全的，哪些不安全？

核心要点

• 线程安全：Vector、Hashtable、ConcurrentHashMap、Collections.synchronizedXxx
• 线程不安全：ArrayList、LinkedList、HashSet、HashMap、TreeMap、TreeSet
• 单线程优先用不安全的（性能更好），多线程用 ConcurrentHashMap、CopyOnWriteArrayList 等

详细解析

线程安全集合：

线程不安全集合：

• ArrayList、LinkedList
• HashSet、LinkedHashSet、TreeSet
• HashMap、LinkedHashMap、TreeMap
• PriorityQueue、ArrayDeque

面试口头回答

Java 集合中线程安全的主要有这几个：

• Vector，它的方法都是 synchronized 同步的，但现在通常建议用 ArrayList 或 CopyOnWriteArrayList；
• Hashtable，方法也是 synchronized 的，通常建议用 HashMap 或 ConcurrentHashMap；
• ConcurrentHashMap，JDK8 采用 CAS 加 synchronized，并发度高，是多线程场景的首选；
• 还有 Collections 工具类提供的 synchronizedList、synchronizedSet、synchronizedMap 这些方法，可以把非线程安全的集合包装成线程安全的。

线程不安全的集合包括 ArrayList、LinkedList、HashSet、HashMap、TreeMap、TreeSet 这些常见的集合类。

实际使用中单线程环境下优先用不安全的集合，性能更好；多线程环境下根据场景选择 ConcurrentHashMap、CopyOnWriteArrayList 这些专门设计的并发集合。

3.16 HashSet 的底层原理？为什么能去重？

核心要点

• 底层基于 HashMap 实现
• 元素作为 HashMap 的 key，value 是一个固定的静态常量对象 PRESENT
• 去重依赖 HashMap 对 key 的唯一性约束：先比 hashCode，再比 equals
• add、contains、remove 等方法都委托给底层 HashMap

详细解析

HashSet 的核心源码逻辑：

public class HashSet<E> implements Set<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();  // 固定的占位值
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
    
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
}

去重原理：

1. 向 HashSet 添加元素时，实际调用 HashMap.put(key, PRESENT)
2. HashMap 不允许重复 key，判断重复的逻辑是：
   • 先通过 hashCode() 计算哈希值定位桶位置
   • 如果该位置已有元素，再通过 equals() 比较内容
   • 只有 hashCode 相同且 equals 返回 true 时，才视为相同 key
3. 相同 key 会覆盖旧值，所以 HashSet 中不会存在重复元素

注意：自定义对象存入 HashSet 时，必须正确重写 hashCode() 和 equals() 方法，否则无法正确去重。

面试口头回答

HashSet 的底层是基于 HashMap 实现的。它内部维护了一个 HashMap 实例，当我们向 HashSet 添加元素时，实际上是把元素作为 HashMap 的 key，而 value 是一个固定的静态常量对象，只用于占位。

所以 HashSet 的 add、contains、remove 这些方法，本质上都是委托给底层 HashMap 完成的。

它能去重的核心原因，正是依赖 HashMap 对键的唯一性约束。HashMap 中不允许存在重复的键，判断键是否重复的逻辑是：先通过元素的 hashCode 方法计算哈希值定位到数组中的位置；如果该位置已有元素，再通过 equals 方法比较内容。只有当 hashCode 返回相同值且 equals 返回 true 时，才会被视为相同的键，此时新元素会覆盖旧元素，从而保证了 HashSet 中元素的唯一性。

要注意的是，如果是自定义对象存入 HashSet，必须正确重写 hashCode 和 equals 方法，否则可能无法正确去重。

四、布隆过滤器

4.1 布隆过滤器原理？为什么多次 hash？误判率的原理？

核心要点

• 底层是一个 bit 数组，用多次 hash 标记位置
• 用于判断元素"可能存在"或"一定不存在"
• 多次 hash 是为了降低冲突带来的误判率
• 存在误判（假阳性），但不存在漏判（假阴性）

详细解析

原理：

• 初始化一个固定大小的 bit 数组，所有位设为 0
• 插入元素时，用 k 个不同的哈希函数计算该元素的 k 个哈希值，把对应位置设为 1
• 查询元素时，同样用 k 个哈希函数计算位置，如果所有位置都是 1，则"可能存在"；如果有任意位置是 0，则"一定不存在"

为什么多次 hash？

• 单次 hash 冲突概率高，多个不同位置的巧合同时发生概率低
• k 次 hash 后，误判率呈指数级下降（约为 (1 - e^(-kn/m))^k，其中 n 是元素数，m 是数组大小）

误判率原理：

• 查询一个实际不存在的元素时，它被哈希到的 k 个位置，可能之前都被其他元素置为 1
• 这种情况下布隆过滤器会"以为"它存在，产生误判（假阳性）
• 但不会有假阴性：如果某个位置是 0，说明元素一定没来过

面试口头回答

布隆过滤器的原理是用一个 bit 数组加上多次哈希来标记元素是否存在。

具体来说，插入元素时，用多个不同的哈希函数计算这个元素的多个哈希值，把 bit 数组中对应的位置设为 1。查询的时候，同样用这些哈希函数计算位置，如果所有位置都是 1，就说明元素可能存在；如果有任何一个位置是 0，就说明元素一定不存在。

为什么要多次 hash？因为单次哈希冲突的概率比较高，但多个不同哈希函数计算的多个位置同时冲突的概率就低很多，这样能有效降低误判率。

误判率的原理是这样的：查询一个实际不存在的元素时，它的 k 个哈希位置可能之前都被其他元素置为 1 了，这时候布隆过滤器会误判为存在，这就是假阳性。但不会有假阴性，因为如果某个位置是 0，那这个元素一定没来过。

4.2 布隆过滤器的应用场景

核心要点

• 缓存穿透防护：快速判断数据是否可能存在，不存在直接拦截
• 去重：搜索引擎防止重复抓取、推荐系统防止重复推荐
• 大规模存在性检测：判断用户是否已注册、URL 是否已爬取
• 黑名单校验：高效存储和查询大规模黑名单

面试口头回答

布隆过滤器在后端的典型应用主要有四个场景：

第一是解决缓存穿透问题。当恶意请求或者不存在的数据被频繁访问时，布隆过滤器能快速判断数据是否可能存在，如果不存在就直接拦截，避免请求打到数据库。

第二是去重。比如在搜索引擎里防止重复抓取网页，在推荐系统里防止重复推荐内容。

第三是大规模数据的存在性检测。比如判断某个用户是否已经注册过、某个 URL 是否已经被爬取过。

第四是黑名单校验。可以高效存储和查询大规模的黑名单数据，快速过滤非法请求。

总之，布隆过滤器适合那些能容忍少量误判、但对内存和查询速度要求很高的场景。

4.3 布隆过滤器的缺点及改进方案

核心要点

• 缺点：存在误判（假阳性）、不能删除元素、长期使用误判率上升
• 改进 1：Counting Bloom Filter（计数型），用计数数组代替 bit 数组，支持删除
• 改进 2：定期重建，结合时间窗口避免 bit 位长期被置 1

详细解析

主要缺点：

1. 误判（假阳性）：可能把不存在的元素判断为存在，但不会漏判
2. 不能删除元素：多个元素可能映射到同一个 bit 位，清除会影响其他元素
3. 误判率随时间上升：当底层数据频繁更新，而布隆过滤器无法删除或更新时，部分 bit 会长期保持为 1，导致误判率越来越高

改进方案：

• Counting Bloom Filter（计数型布隆过滤器）：不用 bit 数组，而是用计数数组。每次插入把计数加一，删除就减一，这样就能支持动态数据更新。
• 定期重建：结合数据热度或时间窗口，每隔一段时间重置一次布隆过滤器，避免 bit 位长期被置 1 导致误判率升高。

面试口头回答

布隆过滤器的主要优点是节省空间、查询速度快，但也有几个明显缺点。

第一是有误判问题，也就是假阳性，可能把不存在的元素判断为存在，但不会漏判。

第二是不能删除元素，因为多个元素可能映射到同一个 bit 位，删了会影响其他元素的判断。

第三是长期使用误判率会上升，因为数据更新时布隆过滤器无法更新，部分 bit 位长期为 1，误判率越来越高。

改进方案主要有两种：

• 第一种是计数型布隆过滤器。不用 bit 数组而用计数数组，每次插入计数加一，删除减一，这样就能支持动态数据更新。
• 第二种是定期重建。结合数据热度或时间窗口，每隔一段时间重置一次布隆过滤器，避免 bit 位长期被置 1。

五、设计题

5.1 设计一个线程安全的 List，存储配置数据，读多写少，你会怎么选？

核心要点

• 首选 CopyOnWriteArrayList
• 设计思想：写时复制（Copy-On-Write）
• 读操作不加锁，直接访问内部数组，非常快
• 写操作复制新数组，写完更新引用
• 适合读多写少、数据量不大的场景

详细解析

CopyOnWriteArrayList 原理：

• 内部维护一个数组 volatile Object[] array
• 读操作（get、遍历）：直接访问当前数组，不加锁，性能极高
• 写操作（add、set、remove）：
  1. 加锁（ReentrantLock）
  2. 复制一个新数组（长度为原数组 + 1 或 -1）
  3. 在新数组上执行修改
  4. 把内部引用指向新数组
  5. 解锁
• 由于数组引用是 volatile 的，更新后其他线程立即可见

适用场景：

• 读多写少（读操作占绝大多数）
• 数据量不大（写操作复制数组有开销）
• 对实时一致性要求不高（读的是快照，可能读到旧数据）

不适用场景：

• 写操作频繁（每次写都复制数组，开销大）
• 数据量很大（复制大数组消耗内存和 CPU）
• 要求强实时一致性（读到的可能是旧版本）

替代方案：

• 如果写操作也较多，可以用 Collections.synchronizedList 或读写锁（ReadWriteLock）包装的 ArrayList

面试口头回答

如果是线程安全、读多写少的 List，我会优先考虑 CopyOnWriteArrayList。

它的设计理念是写时复制。读操作直接访问内部数组，不加锁，所以非常快；写操作比如 add、set、remove，会先加锁，然后复制一个新数组，在新数组上完成修改，最后把引用更新为新数组，再解锁。

这种设计在读操作占绝大多数的场景下非常高效，因为普通的遍历或 get 都不需要加锁，天然线程安全。如果有批量更新需求，也可以结合 synchronized 或者替换整个 List 的方式。

当然它也有局限：写操作频繁时性能不好，因为每次写都要复制整个数组；数据量很大时也不适合，复制大数组开销太大；而且读的是快照，可能读到旧数据，对实时一致性要求很高的场景要谨慎使用。

如果写操作也比较多，那可以考虑用 ReadWriteLock 包装的 ArrayList，或者 Collections.synchronizedList。

六、红黑树基础

6.1 红黑树的定义与性质

核心要点

• 自平衡二叉搜索树，保证平衡不会退化成链表
• 五个性质：节点红黑、根节点黑、叶子节点黑、红节点的子节点黑、任意节点到叶子路径黑节点数相同
• 查找、插入、删除时间复杂度都是 O(log n)
• 添加或删除节点时，通过旋转和变色保持平衡

详细解析

红黑树的五个性质：

1. 节点要么是红色，要么是黑色
2. 根节点是黑色
3. 所有叶子节点（NIL）都是黑色
4. 红色节点的两个子节点都是黑色（不能有两个连续的红节点）
5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

如何保证平衡：

• 所有红黑规则的目的都是让树保持近似平衡
• 在添加或删除节点时，如果不符合红黑树的性质，会发生旋转（左旋、右旋）和变色（红变黑、黑变红）
• 最长路径不超过最短路径的 2 倍（因为不能有两个连续红节点，且黑节点数相同）

时间复杂度：查找、添加、删除都是 O(log n)

面试口头回答

红黑树是一种自平衡的二叉搜索树，能保证平衡不会退化成链表。

它有五个性质：

• 节点要么是红色，要么是黑色；
• 根节点是黑色；
• 叶子节点都是黑色的空节点；
• 红色节点的子节点都是黑色，也就是说不能有两个连续的红色节点；
• 从任意节点到叶子节点的所有路径上，黑色节点的数目相同。

这些规则保证了红黑树近似平衡，最长路径不会超过最短路径的两倍。

在添加或删除节点时，如果不符合这些性质，就会通过旋转和变色来调整，保持平衡。

红黑树的查找、添加、删除时间复杂度都是 O(log n)。