Set / Queue / Stack

这一课你将能做到

1. 按语义与复杂度在 HashSet/LinkedHashSet/TreeSet、Queue/Deque/PriorityQueue 之间做出正确选型
2. 解释 HashSet 去重的两个前提（hashCode + equals），并写出能正确去重的自定义类
3. 用 ArrayDeque 实现栈与队列，说清为什么 JDK 已不建议使用 java.util.Stack

为什么要学

去重（标签、已处理 ID）、白名单校验、任务排队、括号匹配、Top-K 统计——这些日常后端需求，容器选错不是慢一点，而是语义就错了。用 ArrayList.contains 做十万级白名单，接口吞吐直接腰斩；用 Stack 类写撤销功能，code review 会被打回——它是继承 Vector 的历史遗留。

面试角度：「HashSet 怎么判断重复」「ArrayList 和 LinkedList 怎么选」「HashMap 的 put 流程」是校招与社招必考题，答案要形成肌肉记忆。本课把 Set/Queue 家族补齐，并与 java-collections 学过的 List/Map 串成一张选型地图。

先建立图像

需求 → 容器选型地图

要去重？
 ├─ 不关心顺序          → HashSet        O(1) 增查
 ├─ 要保留插入顺序      → LinkedHashSet  O(1) + 链表串联
 └─ 要自动排序          → TreeSet        O(log n)

要排队？
 ├─ 普通先进先出        → ArrayDeque 当队列
 ├─ 后进先出（栈）      → ArrayDeque 当栈
 └─ 按优先级出队        → PriorityQueue  O(log n)

线程间传任务？
 └─ 生产者-消费者       → BlockingQueue（第 8 课展开）

复杂度速查（哈希分布均匀时取均摊值）：

操作	HashSet	LinkedHashSet	TreeSet	ArrayDeque
add	O(1)	O(1)	O(log n)	O(1) 均摊
contains	O(1)	O(1)	O(log n)	O(n)
顺序	无	插入序	排序序	无

跟着做

步骤 1：Set 家族——去重的两个前提与三种顺序

新建 SetDemo.java，完整可运行：

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

public class SetDemo {

    /** 只有成对重写 hashCode 与 equals，HashSet 才认得出「值相等」 */
    static class Sku {
        final String code;
        Sku(String code) { this.code = code; }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Sku other)) return false;
            return Objects.equals(code, other.code);
        }
        @Override
        public int hashCode() { return Objects.hashCode(code); }

        @Override
        public String toString() { return code; }
    }

    public static void main(String[] args) {
        Set<Sku> set = new HashSet<>();
        set.add(new Sku("A-1"));
        set.add(new Sku("A-1"));         // 值相同，被识别为重复
        System.out.println(set.size());  // 1

        Set<String> insertion = new LinkedHashSet<>();
        insertion.add("b"); insertion.add("a"); insertion.add("b");
        System.out.println(insertion);   // [b, a]，保留首次插入顺序

        Set<Integer> sorted = new TreeSet<>();
        sorted.add(30); sorted.add(10); sorted.add(20);
        System.out.println(sorted);      // [10, 20, 30]，自动排序
    }
}

运行：java SetDemo.java。然后把 Sku 的 hashCode() 方法注释掉再跑——set.size() 变成 2，去重失效，亲眼确认「hashCode 定位桶，equals 判等」这条铁律。

步骤 2：ArrayDeque 当栈——括号匹配

新建 BracketDemo.java：

import java.util.ArrayDeque;
import java.util.Deque;

public class BracketDemo {

    static boolean matched(String expr) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : expr.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.poll() == null) return false; // 右括号多余
            }
        }
        return stack.isEmpty(); // 还剩左括号说明不匹配
    }

    public static void main(String[] args) {
        System.out.println(matched("(a(b)c)")); // true
        System.out.println(matched(")("));      // false
        System.out.println(matched("(()"));     // false
    }
}

步骤 3：PriorityQueue 求 Top-K

新建 TopKDemo.java：

import java.util.Comparator;
import java.util.PriorityQueue;

public class TopKDemo {
    public static void main(String[] args) {
        // 小顶堆：堆顶是当前最小值，超过 3 个就淘汰最小，最终留下最大的 3 个
        PriorityQueue<Integer> top3 = new PriorityQueue<>(Comparator.naturalOrder());
        for (int v : new int[]{50, 10, 90, 30, 70, 20}) {
            top3.offer(v);
            if (top3.size() > 3) top3.poll();
        }
        System.out.println(top3); // [50, 70, 90]
    }
}

步骤 4：亲眼感受 O(n) 与 O(1) 的差距

新建 ContainsDemo.java：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ContainsDemo {
    public static void main(String[] args) {
        int n = 100_000;
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) { list.add(i); set.add(i); }

        long t1 = System.nanoTime();
        for (int i = 0; i < 10_000; i++) list.contains(i);
        System.out.println("List.contains: " + (System.nanoTime() - t1) / 1_000_000 + " ms");

        long t2 = System.nanoTime();
        for (int i = 0; i < 10_000; i++) set.contains(i);
        System.out.println("Set.contains:  " + (System.nanoTime() - t2) / 1_000_000 + " ms");
    }
}

List 版本通常耗时是 Set 版本的几十到几百倍——这就是白名单、去重必须用 Set 的量化理由。

讲清楚要点

1. HashSet 去重 = 先比 hashCode 再比 equals：hashCode 定位桶，桶内再用 equals 精确判等。只重写一个，另一个形同虚设——不重写 hashCode 时，两个值相等的对象落进不同桶，equals 根本没机会被调用。
2. Set 不提供按索引取值：需要「去重 + 按位置取」时，先想清楚要的到底是 List 去重后转列表，还是 LinkedHashSet 保序。
3. ArrayDeque 是官方推荐的栈/队列：数组实现，没有链表节点对象头开销，内存连续缓存友好；java.util.Stack 继承 Vector，所有方法带 synchronized，还暴露了栈不该有的按索引访问 API。
4. PriorityQueue 不是全排序容器：只有堆顶保证最小/最大，直接遍历得到的顺序无意义；要全序用 TreeSet，要逐个取最优用 PriorityQueue 不断 poll。
5. TreeSet/TreeMap 要求可比较：元素实现 Comparable，或构造时传 Comparator；比较器返回 0 的元素会被视为「同一个」而拒绝加入，去重语义跟着比较器走。
6. Queue 有两套 API：add/remove/element 失败抛异常，offer/poll/peek 失败返回 false/null。业务代码优先用后者，把异常留给真正的异常场景。

你可能会懵的地方

• 去重后还要保持原始顺序怎么办？ LinkedHashSet；流式写法 stream().distinct() 对有序流同样保留首次出现顺序，底层就是 LinkedHashSet。
• TreeSet 想按自定义规则排序？ new TreeSet<>(Comparator.comparing(Sku::code))。注意排序键返回 0 的两个对象会被判为重复，这一点和 HashSet 的 equals 语义不同。
• BlockingQueue 和 Queue 什么关系？ BlockingQueue 是并发家族接口：队空取阻塞、队满放阻塞，是线程池任务队列的底座，第 8 课展开。普通 ArrayDeque 在多线程下不安全。
• ArrayDeque 为什么不能存 null？ poll/peek 用 null 表示「取不到」，若元素可为 null 就无法区分「队列为空」和「取到了 null」，所以 API 直接禁止。
• Redis 的 Set 和 Java 的 HashSet 是一回事吗？ 语义相近（无序去重集合），但实现与适用层不同：Java Set 进程内内存，Redis Set 是跨进程共享、支持 SINTER/SUNION 等集合运算的服务端结构。选型先问「数据给谁看」。

错法对照

错法	问题	正解
自定义对象只重写 equals	hashCode 不一致，HashSet 去重失效	成对重写，用 Objects 工具方法
用 java.util.Stack 当栈	同步开销大、API 冗余	Deque<E> s = new ArrayDeque<>()
高频查询用 ArrayList.contains	O(n)，数据一大量级就慢	HashSet / HashMap
把 PriorityQueue 当排序列表遍历	迭代顺序不是排序序	全序用 TreeSet，取最优不断 poll
TreeSet 存未实现 Comparable 的类	运行时 ClassCastException	实现 Comparable 或构造时传 Comparator

卡点急救

1. HashSet 去重不生效：检查目标类是否成对重写 hashCode 与 equals；用 IDE 生成后，确认没有在生成后修改过参与哈希的字段。
2. TreeSet 抛 ClassCastException：元素类型没实现 Comparable；构造时传 Comparator 即可，不必改实体类。
3. 把 poll 返回的 null 当成了正常元素：出队前用 isEmpty() 判空，或用 pop() 并接受 NoSuchElementException，不要让 null 混入业务语义。

面试常问

• HashSet 如何保证元素唯一？ 可背版：添加时先调用 hashCode 定位哈希桶，再在桶内用 equals 逐个判等，两者都判定「相同」才视为重复。因此正确去重的前提是成对重写并遵守契约：equals 相等的对象必须有相等的 hashCode。
• ArrayList 和 LinkedList 怎么选？ 绝大多数场景 ArrayList：底层数组、随机访问 O(1)、内存连续缓存友好。LinkedList 每个节点多两个引用的对象头开销、CPU 缓存不友好，即使头插场景 ArrayDeque 也优于它；LinkedList 的实际出场率极低，答出这点是加分项。
• HashMap 的 put 流程（JDK 8+）？ 对 key 做 hash 定位桶下标 → 桶空直接放入；冲突则链表尾插，链表长度达 8 且数组长度 ≥ 64 树化为红黑树，退化阈值 6；元素数超过 容量×负载因子(0.75) 触发扩容翻倍并 rehash。扩容是 O(n) 操作，预估容量初始化可避免多次扩容。

自测三问

1. LinkedHashSet 与 HashSet 的实现差异是什么？代价是什么？
2. 为什么 Stack 类被淘汰？官方替代写法是什么？
3. Top-K 问题用 PriorityQueue 的完整思路是什么？时间复杂度多少？

小结一句话

List 管顺序、Set 管唯一、Queue/Deque 管排队与栈；选型先问语义（要不要重、要不要序），再对复杂度。

延伸

• java.util 官方文档
• 下一课：OOP 进阶