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]，自动排序
    }
}