Day 009 — 集合（Set）图解

一、哈希集合底层结构

集合的哈希表结构（与字典共享底层）
====================================

集合对象（PySetObject）
┌───────────────────────────────────────┐
│ ob_refcnt                              │
│ ob_type                                │
│ ob_size (元素个数)                     │ → 3
│ fill (已用槽位数)                      │ → 3
│ mask (容量-1, 用于哈希取模)           │ → 7
│                                 +------│
│ 哈希条目数组 (PySetEntry) ─────────+    │
└───────────────────────────────────────┘
                     ↓
          ┌────┬──────────────────────────┐
          │ 0  │ [空]                     │
          ├────┼──────────────────────────┤
          │ 1  │ [hash] [key: "apple"]    │
          ├────┼──────────────────────────┤
          │ 2  │ [hash] [key: "banana"]   │
          ├────┼──────────────────────────┤
          │ 3  │ [空]                     │
          ├────┼──────────────────────────┤
          │ 4  │ [hash] [key: "cherry"]   │
          ├────┼──────────────────────────┤
          │ 5  │ [空]                     │
          ├────┼──────────────────────────┤
          │ 6  │ [空]                     │
          ├────┼──────────────────────────┤
          │ 7  │ [空]                     │
          └────┴──────────────────────────┘

关键区别（vs 字典）：
  - 字典：每个条目是 [hash, key, value]
  - 集合：每个条目是 [hash, key]（去掉 value 字段）

二、成员检查流程：集合 vs 列表

列表查找 x in lst: O(n)
=========================================
x = "banana"  →  需要找 "banana" 是否在列表中

    lst[0]  →  "apple"    ❌ 不匹配，继续
    lst[1]  →  "banana"   ✅ 找到了！
    lst[2]  →  "cherry"   （不需要检查了）

最坏情况：需要遍历所有 n 个元素
平均情况：需要遍历 n/2 个元素

集合查找 x in s: O(1)
=========================================
x = "banana"

Step 1: 计算 hash("banana") → 67890
Step 2: 计算索引: 67890 & mask → index = 2
Step 3: 检查 table[2] → key == "banana"? ✅ 找到了！

无论集合中有 10 个还是 1000 万个元素，
都只需要 1 次哈希计算 + 1 次比较！

三、集合运算 Venn 图解

并集 A | B         交集 A & B         差集 A - B       对称差 A ^ B
┌─────────┐      ┌─────────┐      ┌─────────┐      ┌─────────┐
│ A    B  │      │ A    B  │      │ A    B  │      │ A    B  │
│ ┌──┐    │      │ ┌──┐    │      │ ┌──┐    │      │ ┌──┐    │
│ │12│34  │      │ │  │34  │      │ │12│    │      │ │12│ 56 │
│ └──┘    │      │ └──┘    │      │ └──┘    │      │ └──┘    │
└─────────┘      └─────────┘      └─────────┘      └─────────┘
  全部元素        重叠部分        只在A中          各不重叠部分

四、集合扩容过程

扩容触发条件：fill / capacity > 2/3（负载因子）

初始状态（容量=8，已填=3）
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘
 fill=4 → 4/8 = 0.5 < 0.67 ✅ 不需要扩容

继续添加... fill=6
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘
 fill=6 → 6/8 = 0.75 > 0.67 ❌ 触发扩容

扩容后（容量≈翻倍到 16）
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │   │   │   │   │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
所有元素重新哈希并分配到新位置

五、hash 碰撞二次探测

两个不同的 key 哈希值映射到同一个索引时：

插入 "apple"：hash("apple") & 7 → 1，table[1] 为空 → 直接放入
插入 "grape"：hash("grape") & 7 → 1，table[1] 被占用了！

开始探测：
  i=1: index = (1 + 1) & 7 = 2 → table[2] 为空 → 放入

查找 "grape"：
  Step 1: hash("grape") & 7 → 1
  Step 2: table[1].key == "grape"? ❌ 不是
  Step 3: 开始探测
    i=1: index = (1 + 1) & 7 = 2
    table[2].key == "grape"? ✅ 找到了！

六、集合去重流程

原始数据
  [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]

      ↓  遍历每个元素，尝试加入集合

集合状态变化：
  Step 1: add(1)  → {1}
  Step 2: add(2)  → {1, 2}
  Step 3: add(2)  → {1, 2}   ← 已存在，忽略
  Step 4: add(3)  → {1, 2, 3}
  Step 5: add(3)  → {1, 2, 3} ← 已存在，忽略
  Step 6: add(3)  → {1, 2, 3} ← 已存在，忽略
  Step 7: add(4)  → {1, 2, 3, 4}
  Step 8: add(4)  → {1, 2, 3, 4} ← 已存在，忽略
  ...

最终结果：{1, 2, 3, 4}

七、数学集合 vs Python 集合对应关系

数学                           Python
─────────────────────────────────────────────────
集合 S = {1, 2, 3}           S = {1, 2, 3}
元素 x ∈ S                   x in S
x ∉ S                        x not in S
A ∪ B                        A | B
A ∩ B                        A & B
A \ B                        A - B
A △ B                        A ^ B
A ⊆ B                        A <= B
A ⊂ B                        A < B
|S|                          len(S)
∅                            set()