集合与映射

集合（Set）和映射（Map）是两种最基础的抽象数据类型。理解它们的底层实现（哈希表 vs 搜索树）是选择正确数据结构的关键。

一、集合 Set

graph LR
  A[Set/Map] --> B["哈希实现 O(1)"]
  A --> C["树实现 O(log n) 有序"]

集合存储不重复的元素，核心操作：add、remove、contains。

有序集合 vs 无序集合

// HashSet：O(1) 判重
Set<Integer> set = new HashSet<>();
set.add(3); set.add(1); set.add(3); // 重复不生效
System.out.println(set.contains(3)); // true
System.out.println(set.size());      // 2

// TreeSet：自动排序
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(5); treeSet.add(2); treeSet.add(8);
System.out.println(treeSet.first()); // 2
System.out.println(treeSet.last());  // 8
System.out.println(treeSet.ceiling(3)); // 5（>=3 的最小值）

基于 BST 的集合实现

public class BSTSet<E extends Comparable<E>> {
    private BST<E> bst;

    public BSTSet() { bst = new BST<>(); }

    public void add(E e) { bst.add(e); }
    public void remove(E e) { bst.remove(e); }
    public boolean contains(E e) { return bst.contains(e); }
    public int getSize() { return bst.size(); }
}
// 最坏 O(n)（退化为链表），平均 O(log n)

二、映射 Map（字典）

映射存储键值对，键唯一，核心操作：put、get、remove。

// HashMap：最高频
Map<String, Integer> freq = new HashMap<>();
freq.put("apple", 3);
freq.put("banana", 5);
freq.getOrDefault("cherry", 0); // 0

// 统计词频
for (String word : words) {
    freq.put(word, freq.getOrDefault(word, 0) + 1);
}

// TreeMap：需要有序遍历
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "c"); map.put(1, "a"); map.put(2, "b");
for (var entry : map.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
    // 1=a, 2=b, 3=c（按 key 升序）
}

三、HashMap 底层原理（Java 8+）

数组 + 链表 + 红黑树

put(key, value):
1. hash(key) → 数组下标
2. 无冲突 → 直接放入
3. 有冲突 → 链表尾插（JDK8）
4. 链表长度 ≥ 8 且数组长度 ≥ 64 → 转红黑树
5. 负载因子 > 0.75 → 扩容 2x

关键参数：

• 初始容量：16
• 负载因子：0.75
• 树化阈值：8
• 退化阈值：6

四、选择指南

需要去重？
├── 不需要排序 → HashSet
└── 需要排序 → TreeSet

需要键值对？
├── 不需要排序 → HashMap
├── 需要排序 → TreeMap
└── 需要插入顺序 → LinkedHashMap

五、面试高频

1. HashMap vs Hashtable：HashMap 允许 null key/value，非线程安全；Hashtable 反之
2. ConcurrentHashMap：JDK8 用 CAS + synchronized 锁单个桶，替代分段锁
3. 为什么容量是 2 的幂：hash & (n-1) 等价于取模，位运算更快
4. LeetCode 应用：1（两数之和）、49（字母异位词分组）、128（最长连续序列）

六、哈希冲突处理过程模拟

以容量 4、负载因子 0.75 的简化 HashMap 为例，依次插入 A, E, I, O, U（假设哈希后下标分别为 0, 0, 1, 0, 1）：

初始: [_, _, _, _]

put(A)→桶0:  [A, _, _, _]
put(E)→桶0:  [A→E, _, _, _]        冲突，链表尾插
put(I)→桶1:  [A→E, I, _, _]
put(O)→桶0:  [A→E→O, I, _, _]      链长=3
put(U)→桶1:  [A→E→O, I→U, _, _]

size=5 > 4*0.75=3 → 扩容为 8，重新哈希分配：
[A, _, E, _, I, _, O, U]   （新下标由新哈希决定）

查找 E：hash(E)%8=2 → 桶2 首元素即 E → O(1)
最坏情况：所有键落在同一桶 → 退化为链表 O(n)

为什么链长 ≥ 8 转红黑树：理想随机哈希下，桶内元素个数服从泊松分布，达到 8 的概率仅约 0.00000006——转树是为了防御恶意构造的哈希碰撞攻击。

七、哈希思维模板

很多题目的突破口都是"用 Set/Map 把 O(n) 的内层查找降为 O(1)"：

# 模板1：两数之和 —— 边遍历边查表
def two_sum(nums, target):
    seen = {}  # 值 -> 下标
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

# 模板2：去重/存在性判断 —— Set
def has_duplicate(nums):
    return len(set(nums)) < len(nums)

# 模板3：频次统计 —— Map
def group_anagrams(strs):
    groups = {}
    for s in strs:
        key = ''.join(sorted(s))
        groups.setdefault(key, []).append(s)
    return list(groups.values())

八、面试真题

九、思考题

1. LC 128 要求 O(n) 复杂度，为什么"先排序再扫描"不满足？用 Set 时如何避免同一个序列被重复统计？（提示：只从 x-1 不存在的 x 出发）
2. 为什么重写 equals 就必须重写 hashCode？不重写会导致什么后果？（提示：HashMap 的查找流程）
3. TreeMap 基于红黑树，插入/查找是 O(log n)，为什么很多场景仍然首选 O(1) 的 HashMap？什么场景下 TreeMap 反而更优？（提示：范围查询与有序遍历）

练习推荐：在练习题模块完成 两数之和 后，尝试用本节模板3 独立完成字母异位词分组。