Day 008 — 字典（Dict）图解
本文件包含核心概念的 ASCII / Mermaid 图解
1. 哈希表核心原理图
字典插入过程
============
键: "name" 键: "age"
│ │
▼ ▼
┌──────────┐ ┌──────────┐
│ hash() │ │ hash() │
└────┬─────┘ └────┬─────┘
│ │
▼ ▼
哈希值: 12345 哈希值: 67890
│ │
▼ ▼
取模: 12345 % 8 = 1 取模: 67890 % 8 = 3
│ │
▼ ▼
┌─────────────────────────────────────────────┐
│ 哈希表数组（8 槽位） │
├──────┬──────────┬──────────┬────────────────┤
│ 索引 │ hash │ key │ value │
├──────┼──────────┼──────────┼────────────────┤
│ 0 │ — │ empty │ — │
│ 1 │ 12345 │ "name" │ "Alice" │ ← 槽位1被占
│ 2 │ — │ empty │ — │
│ 3 │ 67890 │ "age" │ 25 │ ← 槽位3被占
│ 4 │ — │ empty │ — │
│ 5 │ — │ empty │ — │
│ 6 │ — │ empty │ — │
│ 7 │ — │ empty │ — │
└──────┴──────────┴──────────┴────────────────┘
字典查找过程
============
查找: d["age"]
│
▼
hash("age") → 67890
│
▼
索引: 67890 % 8 = 3
│
▼
检查槽位3的key == "age"? ──→ 是！返回值 25
│
▼
✅ O(1) 完成！
2. 哈希碰撞与开放寻址
假设 "key1" 和 "key2" 的哈希值冲突（取模后都指向索引2）
hash("key1") % 8 = 2 hash("key2") % 8 = 2
│ │
▼ ▼
┌──────────────────────────────────────────┐
│ 索引 0 │ empty │
│ 索引 1 │ "something" │
│ 索引 2 │ "key1":"val1" ← 先插入的 │ ← 碰撞！
│ 索引 3 │ empty │ ← 线性探测下一个空位
│ 索引 4 │ empty │
│ 索引 5 │ empty │
│ 索引 6 │ empty │
│ 索引 7 │ empty │
└──────────────────────────────────────────┘
│
▼
二次探测过程（简化）：
第一次尝试: idx = 2 → 被占用，key不匹配
第二次尝试: idx = 2 + 1² = 3 → 空！插入
┌──────────────────────────────────────────┐
│ 索引 2 │ "key1":"val1" │
│ 索引 3 │ "key2":"val2" ← 最终位置 │
└──────────────────────────────────────────┘
查找 "key2":
1. hash("key2") % 8 → 2
2. 槽位2的key == "key2"? → 否，继续探测
3. 槽位3的key == "key2"? → 是！返回值
3. Python 3.7+ 紧凑字典布局
传统字典（Python 3.5-）
====================
稀疏表：每个槽位存储 (hash, key, value)
┌──────┬──────────────────────┐
│ 0 │ (h1, "a", 1) │
│ 1 │ (h2, "b", 2) │
│ 2 │ empty │
│ 3 │ (h3, "c", 3) │
│ 4 │ empty │
│ 5 │ empty │
│ 6 │ (h4, "d", 4) │
│ 7 │ empty │
└──────┴──────────────────────┘
内存浪费 ≈ 50%（空槽位也占用完整空间）
紧凑字典（Python 3.6+）
=====================
索引表（稀疏，存储索引）：
┌──────┬──────┐
│ 0 │ 1 │ ← 哈希值 → 索引表的槽位
│ 1 │ -1 │ ← -1 表示空
│ 2 │ -1 │
│ 3 │ 2 │
│ 4 │ -1 │
│ 5 │ -1 │
│ 6 │ 3 │
│ 7 │ -1 │
└──────┴──────┘
条目表（紧凑，按插入顺序存储）：
┌──────┬──────────────────┐
│ 0 │ (h1, "a", 1) │ ← 先插入
│ 1 │ (h2, "b", 2) │ ← 第二插入
│ 2 │ (h3, "c", 3) │ ← 第三插入
│ 3 │ (h4, "d", 4) │ ← 第四插入
└──────┴──────────────────┘
优点：
✅ 更少的内存占用（条目紧凑排列）
✅ 保持插入顺序
✅ 迭代更快（顺序内存访问）
4. 可哈希 vs 不可哈希 分类树
这个对象能做字典键吗？
│
▼
┌─────────────────────┐
│ 实现了 __hash__() ? │
└─────────┬───────────┘
│
┌─────────┴─────────┐
│ │
是 否
│ │
▼ ▼
┌──────────────┐ ┌──────────────┐
│ 哈希值会变吗？│ │ 不可哈希 │
└──────┬───────┘ │ │
│ │ ❌ list │
┌─────┴─────┐ │ ❌ set │
│ │ │ ❌ dict │
不会 会 │ ❌ 普通对象 │
│ │ └──────────────┘
▼ ▼
┌──────┐ ┌──────────┐
│可哈希 │ │不可哈希 │
│ │ │ │
│ ✅ │ │ ❌ set │
│ int │ │ ❌ list │
│ str │ │ ❌ dict │
│ tuple│ │ │
│(纯元 │ │ 自定义 │
│ 组) │ │ 对象默认 │
│ froz-│ │ 可哈希 │
│ enset│ │（id为哈希)│
│ │ │ 但如果 │
│ 自 │ │ 实现了 │
│ 定义 │ │ __eq__ │
│ 对象 │ │ 但没实现 │
│ (实 │ │ __hash__ │
│ 现了 │ │ → 不可哈希│
│ 约 │ │ │
│ 定) │ │ │
└──────┘ └──────────┘
5. 常用字典操作复杂度一览
╔══════════════════════╦══════════╦══════════════════════════╗
║ 操作 ║ 平均复杂度 ║ 最坏情况 ║
╠══════════════════════╬══════════╬══════════════════════════╣
║ d[key] = value ║ O(1) ║ O(n) 哈希碰撞严重时 ║
║ d[key] 读取 ║ O(1) ║ O(n) ║
║ key in d ║ O(1) ║ O(n) ║
║ del d[key] ║ O(1) ║ O(n) ║
║ d.get(key) ║ O(1) ║ O(n) ║
║ d.pop(key) ║ O(1) ║ O(n) ║
║ d.copy() ║ O(n) ║ O(n) ║
║ d.clear() ║ O(n) ║ O(n) (标记所有槽位空) ║
║ d.update(d2) ║ O(m) ║ O(n+m) m = d2大小 ║
║ d.items() 遍历 ║ O(n) ║ O(n) ║
║ d.keys() | view ║ O(1) ║ O(1) (创建视图) ║
║ 字典推导式 ║ O(n) ║ O(n) ║
║ 字典合并 | ║ O(n+m) ║ O(n+m) (Python 3.9+) ║
╚══════════════════════╩══════════╩══════════════════════════╝
n = 字典当前大小
m = 操作涉及的外部字典大小
内存使用 ≈ O(n)，负载因子 ≈ 2/3 时扩容
6. 词频统计器数据流
flowchart LR
A[原始文本] --> B[分词]
B --> C[清洗: 去标点/小写化]
C --> D[去停用词]
D --> E[词频统计]
E --> F[排序]
F --> G{输出}
G --> H[控制台表格]
G --> I[直方图]
G --> J[CSV 导出]
G --> K[JSON 导出]
subgraph 统计方法
E1[defaultdict[int]]
E2[Counter]
end
E --> E1
E --> E2
style E1 fill:#e1f5fe
style E2 fill:#fce4ec
flowchart LR
A[原始文本] --> B[分词]
B --> C[清洗: 去标点/小写化]
C --> D[去停用词]
D --> E[词频统计]
E --> F[排序]
F --> G{输出}
G --> H[控制台表格]
G --> I[直方图]
G --> J[CSV 导出]
G --> K[JSON 导出]
subgraph 统计方法
E1[defaultdict[int]]
E2[Counter]
end
E --> E1
E --> E2
style E1 fill:#e1f5fe
style E2 fill:#fce4ec
7. dict vs list 查找性能对比
查找性能: 列表 vs 字典
=========================
查找次数: 1,000,000
数据集大小: 100,000 元素
│
▼
┌──────────────────────────────────────────────────────────┐
│ 时间 (秒) │
│ 4.0 ┤ │
│ │ ████ │
│ 3.0 ┤ ████ │
│ │ ████ │
│ 2.0 ┤ ████ │
│ │ ████ ██ │
│ 1.0 ┤ ████ ██ │
│ │ ████ ██ ██ │
│ 0.0 ┤━━━━━━████━━━━━━██━━━━━━━━██━━━━━━━━━━━━━━━━━━━━━━ │
│ 列表 字典 集合 │
│ (O(n)) (O(1)) (O(1)) │
└──────────────────────────────────────────────────────────┘
结论：数据量大时，字典查找比列表快 100~1000 倍！
8. Counter 类继承关系
classDiagram
class dict {
+__getitem__(key)
+__setitem__(key, value)
+__contains__(key)
+keys()
+values()
+items()
+get(key, default)
+update(other)
}
class Counter {
+most_common(n)
+elements()
+subtract(other)
+__add__(other)
+__sub__(other)
+__and__(other)
+__or__(other)
+total()
}
dict <|-- Counter : 继承
note for Counter: "专为计数优化\n不存在的键返回0\n支持数学运算"
classDiagram
class dict {
+__getitem__(key)
+__setitem__(key, value)
+__contains__(key)
+keys()
+values()
+items()
+get(key, default)
+update(other)
}
class Counter {
+most_common(n)
+elements()
+subtract(other)
+__add__(other)
+__sub__(other)
+__and__(other)
+__or__(other)
+total()
}
dict <|-- Counter : 继承
note for Counter: "专为计数优化\n不存在的键返回0\n支持数学运算"