02-集合框架

前言

本文件汇总专题「02-集合框架」，收录该目录下的所有 Markdown 原文，并提供可点击目录便于跳转查阅。

目录

Java面试题合集-12-HashMap原理与O1.md

HashMap 底层原理是什么？为什么查询平均是 O(1)？

你可以把 HashMap 想象成一个“超大快递柜”：

  • 你来取件（get）：先问“你住哪个小区？”（hash）
  • 到了小区（桶）以后，再挨家挨户核对门牌号（equals）

所以它快的关键不是“它不比对”，而是：大部分情况下你一开始就走对了小区。

1）一句话结论（面试直接说）

HashMap 通过 key 的 hashCode() 计算桶下标，将键值对放入数组桶中；桶内用链表/红黑树解决冲突；平均情况下桶很稀疏，所以 get/put 平均 O(1)，但极端冲突会退化到 O(n) 或 O(log n)（树化后）。

2）先把“结构图”刻进脑子

JDK 8 的 HashMap 结构大致是：

table（数组）
  ├─ [0] -> (key,value) -> (key,value) -> ...
  ├─ [1] -> (key,value) -> ...
  ├─ [2] -> 红黑树（冲突太多时树化）
  └─ ...

桶（bucket）里可能是：

  • 空
  • 单个节点
  • 链表（冲突多）
  • 红黑树（链表太长时树化）

3）一次 get 到底做了什么？

伪流程（讲给面试官听非常顺）：

1. 计算 hash（对 hashCode 做扰动）
2. 用 (n - 1) & hash 算桶下标（n 是数组长度，通常是 2 的幂）
3. 桶为空：直接返回 null
4. 桶不为空：
   - 先比 hash
   - hash 相同再用 equals 比 key
   - 找到就返回 value

为什么用 (n - 1) & hash？

因为当 n 是 2 的幂时，它等价于 hash % n，但位运算更快。

4）为什么平均是 O(1)？

核心前提：哈希分布均匀 + 负载因子控制。

  • 桶足够多、key 分布均匀 → 大部分桶里只有 0~1 个元素
  • 即使有冲突，链表也很短 → 常数级

你可以用更“人话”的说法：

O(1) 不是“只做一次操作”，而是“桶里平均只有常数个元素需要比对”。

5）什么时候会退化？退化到什么？

5.1 大量冲突：链表变长

如果很多 key 落在同一个桶，桶内要从头比到尾：

  • 最坏：O(n)

5.2 JDK 8 的救命策略：树化（链表 → 红黑树）

当链表长度过长会树化，查找变为：

  • O(log n)

（树化阈值、退树阈值在下一篇会专门讲。）

6）HashMap 的三个“面试必提关键词”

6.1 负载因子（loadFactor）

默认 0.75。含义：
当 size > capacity * loadFactor 时触发扩容（resize）。

直觉：

  • 负载因子越大：更省内存，但冲突更容易增多
  • 负载因子越小：更快，但更占内存

6.2 扩容（resize）为什么代价大？

扩容会创建新数组并把原元素重新分配到新桶（rehash/迁移）。
所以工程上如果你能预估数据量，建议合理设置初始容量减少扩容次数。

6.3 key 的 equals/hashCode 契约

如果你用自定义对象做 key，却只重写了 equals 没重写 hashCode，HashMap 可能会出现“放得进去取不出来”的经典事故（你在第 03 篇已经写过）。

7）常见坑：用可变对象当 key

如果 key 的字段参与了 hashCode 计算，放进 Map 后又修改字段，就会导致：

key 的“桶位置”变了，但它还躺在旧桶里 → get 再也找不到它

所以：key 尽量不可变（或字段入 Map 后不再变）。

8）小练习：为什么这个例子会很慢？

import java.util.HashMap;
import java.util.Map;

class BadKey {
    private final int id;
    BadKey(int id) { this.id = id; }
    @Override public int hashCode() { return 1; }
    @Override public boolean equals(Object o) {
        return o instanceof BadKey other && this.id == other.id;
    }
}

public class QuizHashMap {
    public static void main(String[] args) {
        Map<BadKey, Integer> map = new HashMap<>();
        for (int i = 0; i < 100000; i++) map.put(new BadKey(i), i);
        System.out.println(map.get(new BadKey(99999)));
    }
}

提示：所有 key 都进同一个桶，桶内查找会发生什么？

9）一句话收尾（面试可直接用）

HashMap 用 hash 定位桶，用 equals 在桶内确认；均匀分布 + 负载因子控制让桶平均很短，所以平均 O(1)，极端冲突会退化到 O(n)，JDK 8 通过链表树化把最坏查找降到 O(log n)。

Java面试题合集-13-ConcurrentHashMap与HashMap.md

ConcurrentHashMap 与 HashMap 的区别？并发安全如何实现？

如果把 HashMap 看作“一个小卖部”，那它的收银台只有一句话：

“大家排队自觉点，别挤。”

而现实是：并发一上来，队伍就挤成一团，钱和货都对不上。
ConcurrentHashMap 的目标就是：允许多人同时结账，还不算错账。

1）一句话结论

HashMap 线程不安全，并发 put 可能导致数据丢失/链表结构异常；ConcurrentHashMap 通过更细粒度的并发控制（JDK 8 以 CAS + synchronized 的桶级锁为主）在保证可见性与一致性的前提下提升并发性能。

2）HashMap 并发下会出什么事？

常见问题（面试说 2 个就够）：

  • 并发写导致覆盖：两个线程同时 put 同一桶，后写覆盖前写，数据丢失
  • 结构竞争导致异常行为：在 resize/链表插入时并发修改，可能造成链表结构混乱（历史上甚至出现过死循环问题，JDK 8 后缓解但仍不保证线程安全）

一句话总结：

HashMap 的设计前提是“单线程或外部同步”，并发下不要赌运气。

3）ConcurrentHashMap 为啥能安全？

3.1 JDK 8 的核心思路：CAS + 桶级 synchronized

你可以把桶当成“分区收银台”：

不同桶（不同 hash 区间）可以并发写
同一个桶内写需要同步（锁住桶头节点）

关键点：

  • 初始化桶位、插入首节点等轻量操作：优先用 CAS
  • 桶已有链表/树结构：对桶头节点加 synchronized，在桶内完成插入/树化等结构性修改

3.2 读为什么通常不加锁？

读操作在大部分情况下只需要：

  • 读取 volatile 可见的桶头引用
  • 在桶内遍历（链表/树）

JDK 8 的 CHM 通过内存可见性设计，让读在大多数场景无需加锁（实现细节很底层，面试能说到“读多写少，读基本无锁”就加分）。

4）JDK 7 vs JDK 8（面试常追问）

JDK 7：Segment 分段锁

ConcurrentHashMap
  ├─ Segment[0]  （一段一个锁）
  ├─ Segment[1]
  └─ ...

并发度受 Segment 数量影响，结构更复杂。

JDK 8：取消 Segment，直接桶级并发

更像 HashMap 的结构：数组桶 + 链表/红黑树，但写时锁粒度更细，配合 CAS 更高效。

5）三个高频使用差异（工程必懂）

5.1 ConcurrentHashMap 不允许 key/value 为 null

原因：并发环境下 get(key) 返回 null 无法区分：

  • 真的没有这个 key
  • 还是 value 就是 null

所以直接禁止，避免语义歧义。

5.2 复合操作要小心：get + put 不是原子

错误示例（并发下会重复计算/覆盖）：

if (!map.containsKey(k)) {
    map.put(k, compute());
}

正确姿势：computeIfAbsent

map.computeIfAbsent(k, key -> compute());

5.3 size 的语义

并发容器的 size() 在强一致场景下成本很高；CHM 的 size 在不同版本实现不同，但总体原则是：不要把 size 当强一致实时值做关键逻辑判断（面试这么说很加分）。

6）小练习：为什么这段代码不安全？怎么改？

import java.util.concurrent.ConcurrentHashMap;

public class QuizCHM {
    static final ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

    static void incr(String k) {
        Integer v = map.get(k);
        map.put(k, v == null ? 1 : v + 1);
    }
}

提示：读-改-写不是原子。可以用 merge 或 compute：

map.merge(k, 1, Integer::sum);

7）一句话收尾（面试可直接用）

HashMap 非线程安全，并发写会丢数据甚至破坏结构；ConcurrentHashMap 通过 CAS + 桶级锁（JDK 8）实现更细粒度同步，读多写少场景性能更好，并提供 computeIfAbsent/merge 等原子复合操作接口。

Java面试题合集-14-HashMap红黑树化阈值.md

JDK 8 HashMap 为什么引入红黑树？树化阈值是多少？

面试官问这题的真正目的不是“背数字”，而是看你能不能讲清：

为什么链表会让 HashMap 变慢？红黑树怎么把最坏情况救回来？为什么还要设置一堆阈值？

1）先给结论

JDK 8 在桶内冲突严重时把链表转为红黑树，避免极端情况下查找退化到 O(n)；树化阈值默认是 8（TREEIFY_THRESHOLD），退树阈值默认是 6（UNTREEIFY_THRESHOLD），并且只有当 table 容量至少达到 64（MIN_TREEIFY_CAPACITY）才会真正树化，否则优先扩容。

2）为什么需要红黑树？——“同一个桶塞太多人”的问题

HashMap 的查找流程是：
1）先定位桶
2）桶内查找 key

桶内如果是链表，最坏要从头比到尾：

O(1)（定位桶） + O(n)（桶内遍历） → 最坏 O(n)

极端冲突时（比如糟糕的 hashCode，或被恶意构造的 key），性能会非常差。

红黑树把桶内查找从 O(n) 降到 O(log n)，相当于把“挨家挨户敲门”变成“按楼层电梯分区查找”。

3）三个阈值分别是什么？（面试常问数字）

JDK 8 中（默认值）：

  • TREEIFY_THRESHOLD = 8：链表长度 ≥ 8 时，满足条件会树化
  • UNTREEIFY_THRESHOLD = 6：在 resize 等场景下，树节点数 ≤ 6 会退回链表
  • MIN_TREEIFY_CAPACITY = 64：table 长度 < 64 时不树化，优先扩容

4）为什么 table 小于 64 不树化，而是扩容？

原因很现实：如果 table 太小��冲突多往往是因为“桶太少”。
扩容能让元素分散到更多桶，链表自然变短。

你可以这样说：

先扩容把人分到更多小区，只有扩了还拥堵，才考虑在某个小区里修“立体停车楼”（红黑树）。

5）树化一定发生吗？还要看 key 是否可比较

红黑树需要比较规则。HashMap 的 TreeNode 会尝试：

  • 如果 key 实现了 Comparable，优先用自然顺序
  • 否则用一些兜底策略（类名/identityHashCode 等）保证树结构可维护

面试里你不必深入源码，但可以说到：

树化需要可比较性，否则会用兜底比较策略维持树结构。

6）一个“故意造冲突”的例子（让树化更直观）

import java.util.HashMap;
import java.util.Map;

class BadKey {
    private final int id;
    BadKey(int id) { this.id = id; }
    @Override public int hashCode() { return 1; }
    @Override public boolean equals(Object o) {
        return o instanceof BadKey other && this.id == other.id;
    }
}

public class TreeifyDemo {
    public static void main(String[] args) {
        Map<BadKey, Integer> map = new HashMap<>();
        for (int i = 0; i < 20; i++) map.put(new BadKey(i), i);
        System.out.println(map.size());
    }
}

提示：这个例子会把大量 key 塞进同一个桶，链表长度很快超过 8；但是否立即树化还取决于 table 的容量是否达到 64（否则可能先扩容）。

7）一句话收尾（面试可直接用）

JDK 8 引入红黑树是为了防止哈希冲突极端情况下链表查找退化到 O(n)；链表长度达到 8 且 table 容量至少 64 时会树化，树节点降到 6 又会退回链表，整体是在“扩容分散冲突”和“桶内结构优化”之间做平衡。

Java面试题合集-15-ArrayList与LinkedList对比.md

ArrayList vs LinkedList：增删改查、内存与适用场景如何选？

这题面试官其实想听你给出“选型理由”，而不是背一句：

ArrayList 查快，LinkedList 增删快。

因为这句话在真实工程里经常会误导你：
LinkedList 的“增删快”需要满足一个前提——你已经拿到节点位置。

1）一句话结论（可直接面试用）

ArrayList 底层是连续数组，随机访问 O(1)，尾部追加均摊 O(1)，中间插入/删除需要搬移元素 O(n)；LinkedList 底层是双向链表，按下标访问需要遍历 O(n)，在已定位节点处插入/删除 O(1)，但常数开销大且缓存不友好。绝大多数业务场景优先选 ArrayList。

2）结构图：一个是“整排座位”，一个是“手拉手”

ArrayList（数组）：
[0][1][2][3][4]...  （连续内存）

LinkedList（双向链表）：
null <- A <-> B <-> C -> null

3）操作复杂度对比（别背，理解就行）

操作 ArrayList LinkedList
get(i) O(1) O(n)（要走到第 i 个）
尾部 add(e) 均摊 O(1) O(1)
头部 add(0,e) O(n)（搬移） O(1)
中间 add(i,e) O(n)（搬移） O(n)（先遍历定位）
删除 remove(i) O(n)（搬移） O(n)（先遍历定位）

面试加分点：

LinkedList 的优势在“已定位节点”场景，比如用迭代器在当前位置插入/删除；如果你用下标操作，它并不快。

4）“增删快”的真相：定位成本常常更贵

很多人以为：

LinkedList 中间删除：O(1)

但如果你是这样写的：

list.remove(5000);

那它需要先从头/尾遍历到第 5000 个节点，定位本身就是 O(n)。
真正的 O(1) 是这样（已定位到迭代器当前位置）：

import java.util.LinkedList;
import java.util.ListIterator;

public class IteratorRemoveDemo {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 10; i++) list.add(i);

        ListIterator<Integer> it = list.listIterator();
        while (it.hasNext()) {
            Integer v = it.next();
            if (v == 5) it.remove(); // 当前位置删除，链表改指针即可
        }
        System.out.println(list);
    }
}

5）内存与性能：LinkedList 往往更“费”

LinkedList 每个节点都要存：

  • value
  • prev 指针
  • next 指针

这会带来更高的内存占用和更多的对象分配；同时链表节点分散在内存里，CPU 缓存命中率差，遍历通常更慢。

所以工程上常见结论是：

需要大量遍历与随机访问：选 ArrayList
需要频繁在头尾插入删除且不太关心随机访问：考虑 Deque（如 ArrayDeque）而不是 LinkedList

（这个“ArrayDeque 更常用”的点，面试官听到会很认可。）

6）扩容：ArrayList 什么时候慢？

ArrayList 扩容时需要：

  • 新建更大数组
  • 把旧数组复制过去

所以如果你能预估容量，建议：

new ArrayList<>(expectedSize)

减少扩容次数，提高性能。

7）小练习：下面两段谁更适合 ArrayList？谁更适合 LinkedList？

A：1 万条数据，频繁按下标读取
B：频繁在头部 push/pop，当作队列/栈使用

提示：B 其实更建议用 ArrayDeque。

8）一句话收尾（面试可直接用）

ArrayList 基于数组，随机访问快、遍历快、尾插均摊 O(1)，适合绝大多数场景；LinkedList 基于双向链表，下标访问与中间插入删除通常要先定位导致 O(n)，且常数开销和内存更大，只有在“已定位节点处频繁插删”或头尾操作时才可能更合适（但队列/栈更推荐 ArrayDeque）。

Java面试题合集-16-fail-fast与fail-safe.md

什么是 fail-fast / fail-safe？常见触发方式是什么？

这题其实就一个核心：
你在遍历集合时又去改集合，它到底是“当场翻脸”还是“装作没看见”？

  • fail-fast：当场翻脸，直接抛异常
  • fail-safe：装作没看见（在副本上遍历），不抛异常，但你可能看不到最新变化

1）一句话结论

fail-fast 是“快速失败”，遍历时检测到结构性修改就抛 ConcurrentModificationException；fail-safe 是“安全失败”，通常通过在副本上遍历避免抛异常（如 CopyOnWriteArrayList 的迭代器），但迭代结果可能不是实时最新。

2）fail-fast：最典型的就是 ArrayList/HashMap 的迭代器

2.1 触发例子：for-each 里 remove

import java.util.ArrayList;
import java.util.List;

public class FailFastDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
        for (Integer v : list) {
            if (v == 2) list.remove(v); // 触发 ConcurrentModificationException
        }
    }
}

原因：for-each 本质是迭代器；集合结构被修改后，迭代器检测到 modCount 变化，就抛异常。

2.2 正确删除姿势：用迭代器自己的 remove

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class IteratorRemoveOk {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            Integer v = it.next();
            if (v == 2) it.remove();
        }
        System.out.println(list);
    }
}

面试加分点：

fail-fast 是“尽力而为”的错误检测，并不保证 100% 捕获所有并发修改，它主要用于帮助你尽早发现 bug。

3）fail-safe：典型代表 CopyOnWriteArrayList

import java.util.concurrent.CopyOnWriteArrayList;

public class FailSafeDemo {
    public static void main(String[] args) {
        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        for (Integer v : list) {
            if (v == 2) list.remove(Integer.valueOf(2)); // 不抛异常
        }
        System.out.println(list);
    }
}

为什么不抛？

它的迭代器遍历的是“创建迭代器那一刻的数组快照”，修改会复制新数组，不影响当前迭代器。

代价也要说清：

  • 写操作开销大（复制数组）
  • 迭代结果不一定反映最新修改

4）常见触发方式总结（面试官最爱问“哪些会触发”）

fail-fast 常见触发

  • ArrayList/HashMap 等非并发容器：遍历时结构性修改（add/remove/clear）
  • 使用 for-each（迭代器）时直接调用集合的 remove/add

不会触发（但可能有逻辑问题）

  • 通过迭代器的 remove()（合法的“迭代中删除”）
  • 遍历非结构性修改（例如修改元素对象内部字段，不改变集合结构）

5）一句话收尾（面试可直接用）

fail-fast 迭代器通过 modCount 检测结构性修改并抛 ConcurrentModificationException，帮助尽早暴露 bug；fail-safe 通常在副本/快照上遍历（如 CopyOnWriteArrayList），不抛异常但迭代结果可能不是最新，且写入成本更高。

Java面试题合集-17-HashSet如何去重.md

HashSet 如何实现去重？为什么依赖 hashCode/equals？

你可以把 HashSet 理解成：

“只要不重复，我就收；重复的我直接拒收。”

那它怎么判断“重复”？
答案就是：先用 hashCode 快速分桶，再用 equals 精准确认。

1）一句话结论

HashSet 底层基于 HashMap 实现，元素作为 key 存储，value 是固定哑元对象；去重逻辑依赖 hashCode 定位桶、equals 在桶内判断相等，因此自定义对象要作为 Set 元素去重时必须正确重写 equals/hashCode。

2）HashSet 的底层真相：就是一个“只存 key 的 HashMap”

可以用一句伪代码理解：

// HashSet 内部差不多就是：
HashMap<E, Object> map;
static final Object PRESENT = new Object();

boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

所以你问 HashSet “为什么能去重”，本质是在问：

HashMap 的 key 是怎么判重的？

3）判重流程：先 hashCode，后 equals

加入元素 e 时：

1）计算 hashCode → 找桶
2）桶为空 → 直接放进去
3）桶不为空 → 逐个用 equals 比较
4）找到 equals 为 true → 认为重复，不添加

hashCode：负责“快”
equals：负责“准”

4）最常见的坑：只重写 equals，不重写 hashCode

import java.util.HashSet;
import java.util.Set;

class User {
    private final long id;
    User(long id) { this.id = id; }

    @Override
    public boolean equals(Object o) {
        return o instanceof User other && this.id == other.id;
    }
}

public class BadSetDemo {
    public static void main(String[] args) {
        Set<User> set = new HashSet<>();
        set.add(new User(1));
        set.add(new User(1));
        System.out.println(set.size()); // 可能是 2（去重失败）
    }
}

原因：两个对象 hashCode 不同会去不同桶，根本不会走到 equals 比较。

5）正确写法：equals + hashCode 一起重写

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

class User {
    private final long id;
    User(long id) { this.id = id; }

    @Override
    public boolean equals(Object o) {
        return o instanceof User other && this.id == other.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public class GoodSetDemo {
    public static void main(String[] args) {
        Set<User> set = new HashSet<>();
        set.add(new User(1));
        set.add(new User(1));
        System.out.println(set.size()); // 1
    }
}

6）另一个隐蔽坑：把可变对象放进 HashSet

如果你把一个对象放进 set 后，又修改了参与 hashCode/equals 的字段：

它在 set 里的“桶位置”会变，但对象仍躺在旧桶里
→ contains/remove 可能找不到它

工程建议：

  • Set 元素尽量不可变
  • 或保证参与 equals/hashCode 的字段入 set 后不变

7）面试加分：hashCode 相同就一定重复吗？

不一定。hashCode 相同只是“可能在同一个桶”，还要 equals 为 true 才算重复。

8）一句话收尾（面试可直接用）

HashSet 底层是 HashMap，通过 hashCode 定位桶、equals 判断相等来去重；自定义对象要正确去重必须同时重写 equals/hashCode，并避免元素入 Set 后修改参与计算的字段。

Java面试题合集-18-TreeMap与TreeSet排序原理.md

TreeMap/TreeSet 的排序原理是什么？如何自定义比较规则？

如果说 HashMap 是“按地址分桶”，那 TreeMap 就是：

“我不分桶，我排队：谁大谁小我说了算。”

它的核心是：有序，代价是：每次插入/查找都要维护排序。

1）一句话结论

TreeMap/TreeSet 底层是红黑树（自平衡二叉搜索树），通过 Comparator 或 key 的自然顺序（Comparable）确定排序；查找/插入/删除都是 O(log n)。自定义排序要提供一致的比较规则，并保证与 equals 的一致性，否则可能出现“看起来重复却能放进去/看起来不重复却放不进去”的问题。

2）TreeSet 的本质：只存 key 的 TreeMap

和 HashSet 类似，TreeSet 底层也是 Map：

TreeSet ≈ TreeMap<E, PRESENT>

它的“去重”不是靠 hashCode/equals，而是靠：

compare(a, b) == 0 认为是“同一个元素”

这点非常重要。

3）自然顺序：实现 Comparable

import java.util.Set;
import java.util.TreeSet;

class User implements Comparable<User> {
    final int age;
    User(int age) { this.age = age; }

    @Override
    public int compareTo(User o) {
        return Integer.compare(this.age, o.age);
    }

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

public class ComparableDemo {
    public static void main(String[] args) {
        Set<User> set = new TreeSet<>();
        set.add(new User(18));
        set.add(new User(10));
        set.add(new User(18));
        System.out.println(set);
    }
}

注意：age 相同的会被认为“重复”，因为 compareTo == 0。

4）自定义顺序：传 Comparator（更常用）

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

class User {
    final String name;
    final int age;
    User(String name, int age) { this.name = name; this.age = age; }
    @Override public String toString() { return name + "(" + age + ")"; }
}

public class ComparatorDemo {
    public static void main(String[] args) {
        Comparator<User> byAgeThenName =
                Comparator.comparingInt((User u) -> u.age).thenComparing(u -> u.name);

        Set<User> set = new TreeSet<>(byAgeThenName);
        set.add(new User("Tom", 18));
        set.add(new User("Jerry", 18));
        set.add(new User("Tom", 18));
        System.out.println(set);
    }
}

这里“重复”的判定规则是：age 和 name 都相同才算重复（compare == 0）。

5）面试必坑：比较器与 equals 不一致会怎样？

如果 equals 认为两个对象不相等，但比较器 compare == 0，TreeSet 会把它当成重复，导致你“加不进去”。

反过来，如果 equals 认为相等但 compare != 0，TreeSet 又会允许放进去，出现“看起来重复却存在两个”的怪现象。

面试表达（很加分）：

对于有序集合/有序 Map，判重基于 compare 结果，比较器最好与 equals 保持一致（至少保证 compare==0 的对象在业务语义上确实等价）。

6）为什么是红黑树？（不需要背旋转细节）

你可以说到这层就够了：

  • 二叉搜索树能按大小快速查找
  • 但普通 BST 可能退化成链表
  • 红黑树通过自平衡保证树高是 O(log n)，因此增删改查稳定在 O(log n)

7）一句话收尾（面试可直接用）

TreeMap/TreeSet 基于红黑树维持有序性，比较规则来自 Comparable 或 Comparator；判重以 compare==0 为准，因此自定义比较器时要保证规则稳定且与业务等价一致，否则会出现元素“加不进去/重复存在”的问题。

Java面试题合集-19-集合线程安全方案.md

Java 集合的线程安全方案有哪些？（包装类/并发容器/加锁）

集合线程安全这题，面试官最想听你能给出“按场景选方案”，而不是一句：

用 Vector 或 synchronized。

因为真实工程里，线程安全不是非黑即白，它是一个“成本/一致性/吞吐”的权衡题。

1）一句话结论

Java 集合线程安全常见方案有三类：1）外部加锁（synchronized/ReentrantLock）；2）同步包装（Collections.synchronizedXxx）；3）并发容器（ConcurrentHashMap、CopyOnWriteArrayList、ConcurrentLinkedQueue 等）。选型取决于读写比例、是否需要强一致遍历、以及操作是否为复合操作（读-改-写）。

2）方案一：外部加锁（最通用，但最容易写错）

适用：你需要对“多个操作组成的临界区”做原子保护。

import java.util.HashMap;
import java.util.Map;

public class ExternalLockDemo {
    private final Map<String, Integer> map = new HashMap<>();
    private final Object lock = new Object();

    public void incr(String k) {
        synchronized (lock) {
            map.put(k, map.getOrDefault(k, 0) + 1);
        }
    }
}

优点：最灵活，能包住任意复合逻辑
缺点：锁粒度粗就慢，粒度细就容易出错；需要团队纪律

3）方案二：Collections.synchronizedXxx（同步包装）

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SynchronizedWrapperDemo {
    public static void main(String[] args) {
        List<Integer> list = Collections.synchronizedList(new ArrayList<>());
        list.add(1);
    }
}

注意一个面试常考点：遍历时仍需手动同步：

synchronized (list) {
    for (Integer v : list) {
        // safe iteration
    }
}

否则你还是可能遇到并发修改问题。

4）方案三：并发容器（更推荐的工程路线）

4.1 Map：优先 ConcurrentHashMap

并发读写性能好，并提供原子复合操作：

import java.util.concurrent.ConcurrentHashMap;

public class ChmCounterDemo {
    static final ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

    static void incr(String k) {
        map.merge(k, 1, Integer::sum);
    }
}

4.2 List：读多写少用 CopyOnWriteArrayList

特点：

  • 读几乎无锁、遍历安全（快照）
  • 写会复制数组（慢、占内存）
import java.util.concurrent.CopyOnWriteArrayList;

public class CowListDemo {
    public static void main(String[] args) {
        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
        list.add(1);
    }
}

4.3 Queue：ConcurrentLinkedQueue / ArrayBlockingQueue / LinkedBlockingQueue

按需求选：

  • 无界非阻塞：ConcurrentLinkedQueue
  • 生产者消费者阻塞队列：ArrayBlockingQueue（有界）、LinkedBlockingQueue（可配置有界/无界）

5）Vector/Hashtable 还能用吗？

它们是“老牌同步容器”，每个方法都同步，简单但锁粒度粗，性能通常不如并发容器。
面试表达可以很稳：

兼容性场景可能还见到，但新项目通常优先并发容器或更合适的数据结构（如 CHM、阻塞队列）。

6）选型口诀（工程更好用）

Map 并发：ConcurrentHashMap
计数累加：LongAdder（配合 CHM 存储）
List 读多写少：CopyOnWriteArrayList
队列/线程间传递：BlockingQueue 系列
复杂复合逻辑：外部加锁或用 compute/merge 等原子方法

7）一句话收尾（面试可直接用）

集合线程安全的选择要看场景：复合操作用外部锁或并发容器的原子 API（compute/merge），Map 通常选 ConcurrentHashMap，读多写少的 List 可选 CopyOnWriteArrayList，线程间协作优先阻塞队列；同步包装要注意遍历仍需手动加锁。

# java # 面试
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

实验6 体验AI代码生成

30°</span> | 折射角: <span id="display-theta2">19.47°</span><label>入射角 (°): <span id="incident-angle-val">30</span></label><label>介质1折射率: <span id="n1-val">1.0</span></label><label>介质2折射率: <span id="n2-v

avatar 2048 AI社区
cover

2025最新！9个AI论文软件测评：研究生开题报告必备推荐

avatar 2048 AI社区

5分钟Docker自建开源协作表格！蜘蛛表格部署教程（数据私有化+免费可用）

还在为团队数据协作烦恼？Excel版本混乱、Airtable成本高且数据不安全？本文教你5分钟用Docker在自有服务器部署开源工具「蜘蛛表格」，实现媲美Airtable的功能，数据完全自主掌控！

avatar 2048 AI社区