PYTHON LESSON 098
单词速查哈希表
理解哈希表 O(1) 查询的威力，熟练用 dict 计数、set 去重与判存。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- counter.get(w, 0) 取不到就给默认值
- counter[w] = counter.get(w, 0) + 1 计数
- w in vocab 用 set 判断存在
01 · 核心概念
哈希表：dict 与 set 的应用
哈希表：dict 与 set 的应用：列表找东西要一个个比对，十万个词平均比五万次。哈希表把每个键用“哈希函数”直接算出一个存放位置，像按学号找座位——坐下就知道在哪，平均一次搞定。dict（键值对）和 set（只有键）是 Python 给的两种哈希表。
GESP Python 7 级 · 哈希表大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
02 · 语法与规则
先记住这 3 条，再开始写程序
counter.get(w, 0) 取不到就给默认值先准确读出这条写法的结构与作用。
counter[w] = counter.get(w, 0) + 1 计数换一组最小数据，手工推演一次结果。
w in vocab 用 set 判断存在再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 单词速查哈希表：dict 计数 + set 查成员
words = ["apple", "banana", "apple", "orange", "banana", "apple"]
# dict 当计数器：每个单词出现几次
counter = {}
for w in words:
counter[w] = counter.get(w, 0) + 1
print("单词计数器：", counter)
print("apple 出现了", counter["apple"], "次")
# set 当词汇表：去重 + 秒查存在性
vocab = set(words)
print("去重后的词汇表：", sorted(vocab))
for q in ["apple", "grape"]:
if q in vocab:
print(q, "在词典里 ✓")
else:
print(q, "不在词典里 ✗")单词计数器： {'apple': 3, 'banana': 2, 'orange': 1}
apple 出现了 3 次
去重后的词汇表： ['apple', 'banana', 'orange']
apple 在词典里 ✓
grape 不在词典里 ✗dict 和 set 的底层都是哈希表：查一个键平均只需要 O(1) 时间。
04 · 逐步理解
每一步只解决一个问题
- 01
哈希表为什么快
列表找东西要一个个比对，十万个词平均比五万次。哈希表把每个键用“哈希函数”直接算出一个存放位置，像按学号找座位——坐下就知道在哪，平均一次搞定。dict（键值对）和 set（只有键）是 Python 给的两种哈希表。
- 02
dict 计数三板斧
counter.get(w, 0) 的意思是：有 w 就取出次数，没有就当作 0。于是 counter[w] = counter.get(w, 0) + 1 一行完成“首次登记 + 累加”，不用再写 if 判断在不在。
counter = {} for w in words: counter[w] = counter.get(w, 0) + 1 - 03
set 去重与判存
set(words) 一步去重；q in vocab 判断存在性，比 q in list 快几个数量级。注意 set 不保证顺序，要按字典序输出就包一层 sorted()。
vocab = set(words) print(sorted(vocab)) - 04
什么时候不能用哈希表
哈希表擅长“精确查找”，但不擅长“找最小值”“按顺序遍历”“找最接近的数”——那是排序和二分、平衡树的地盘。选对工具的前提是先想清楚问题问的是什么。
- 05
竞赛里的哈希套路
统计词频、判重、两数之和配对、记录某个值是否出现过……凡是“查”字当头的题，先想 dict/set。数据量上到 10⁵，双重循环必超时，哈希表就是及格线。
seen = set() for x in nums: if target - x in seen: print("找到一对") seen.add(x)
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，观察计数器和词汇表
- 2往单词列表里再加几个词重新统计
- 3把 set 换成列表做 in 判断，体会速度差异
- 4想想生活中还有哪些“查表秒答”的例子
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。list 是可变有序序列，tuple 是不可变有序序列，dict 保存唯一键到值的映射，set 保存无序且不重复的可哈希对象。
必须掌握
- list 支持下标、切片、append、extend、insert、pop、remove 与 sort；多数修改方法返回 None。
- tuple 的逗号比括号更关键，单元素元组必须写成 (value,)。
- dict 保持插入顺序；键必须可哈希且唯一，get 可提供缺省值，items 同时遍历键和值。
- set 用于去重与集合运算：| 并、& 交、- 差、^ 对称差；空集合必须写 set()。
- enumerate 同时给出序号和值，zip 并行遍历多个可迭代对象，默认在最短输入处停止。
- 浅复制只复制最外层容器；嵌套可变对象仍可能共享。
CORE CONTAINER METHODS
四类核心容器方法完整速查
修改型方法多数返回 None；表中“浅复制”不会递归复制内部可变对象。
| 类型 | 方法 | 核心作用 |
|---|---|---|
list | append(x) | 末尾加入一个对象 |
list | extend(iterable) | 末尾加入可迭代对象的每一项 |
list | insert(i, x) | 在下标 i 前插入 |
list | remove(x) | 删除第一个等于 x 的元素，不存在时报错 |
list | pop([i]) | 删除并返回指定项，默认末项 |
list | clear() | 删除全部元素 |
list | index(x[, start[, stop]]) | 返回第一个匹配下标 |
list | count(x) | 统计等于 x 的元素数 |
list | sort(*, key=None, reverse=False) | 稳定地原地排序 |
list | reverse() | 原地逆序 |
list | copy() | 浅复制列表 |
tuple | count(x) | 统计元素次数 |
tuple | index(x[, start[, stop]]) | 返回第一个匹配下标 |
dict | clear() | 删除全部键值对 |
dict | copy() | 浅复制字典 |
dict | fromkeys(iterable[, value]) | 用一组键创建新字典 |
dict | get(key[, default]) | 安全取值，缺键返回默认值 |
dict | items() | 键值对动态视图 |
dict | keys() | 键动态视图 |
dict | pop(key[, default]) | 删除键并返回值 |
dict | popitem() | 删除并返回最后加入的键值对 |
dict | setdefault(key[, default]) | 缺键时写入默认值并返回 |
dict | update(other) | 用映射或键值对更新 |
dict | values() | 值动态视图 |
set | add(x) | 加入一个元素 |
set | clear() | 删除全部元素 |
set | copy() | 浅复制集合 |
set | discard(x) | 删除元素，不存在也不报错 |
set | remove(x) | 删除元素，不存在时报错 |
set | pop() | 删除并返回任意元素 |
set | union(*others) | 返回并集 |
set | update(*others) | 用并集原地更新 |
set | intersection(*others) | 返回交集 |
set | intersection_update(*others) | 用交集原地更新 |
set | difference(*others) | 返回差集 |
set | difference_update(*others) | 用差集原地更新 |
set | symmetric_difference(other) | 返回对称差 |
set | symmetric_difference_update(other) | 用对称差原地更新 |
set | issubset(other) | 是否为子集 |
set | issuperset(other) | 是否为超集 |
set | isdisjoint(other) | 是否没有共同元素 |
常见误区
- 把 list.sort() 的返回值赋回列表
- 遍历 dict 时同时改变其大小
- 用可变 list 当字典键
- 把 set 当成有固定顺序的序列
适用边界
- 大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
- 需要有序映射的特殊操作、计数或默认值时可查阅 collections，但先理解基本 dict。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
编码与文本ASCII、Unicode 与字符编码完整表完整查阅标准 ASCII 0–127，并理解 Unicode、编码方案与 Python 字符串之间的关系。＋
正式定义
标准 ASCII 是 7 位字符编码，只定义十进制 0–127：0–31 与 127 是控制字符，32 是空格，33–126 是可打印字符。Unicode 为字符分配码点，UTF-8/UTF-16 是把码点编码成字节的方案；Unicode 的前 128 个码点与 ASCII 一致。
必须掌握
- 数字字符 '0'–'9' 是 48–57，大写字母 'A'–'Z' 是 65–90，小写字母 'a'–'z' 是 97–122。
- ord(ch) 返回单个 Unicode 字符的码点；chr(n) 返回对应码点的字符，它们不限于 ASCII。
- 字符串比较按 Unicode 码点逐项进行；大小写转换应优先使用 lower()/upper()，不要把“相差 32”推广到所有文字。
- str 是字符序列，bytes 是 0–255 的字节序列；encode() 从文字得到字节，decode() 从字节恢复文字。
- 所谓“扩展 ASCII”没有唯一标准，128–255 的含义取决于代码页，不能当成标准 ASCII 表的一部分。
- 换行符 LF 是 10，回车符 CR 是 13；Windows 文本常见 CRLF，跨平台读写要让文本模式正确处理。
常见误区
- 把 ASCII 说成所有字符的统一编号
- 认为 ord() 只能处理 ASCII
- 把字符个数等同于 UTF-8 字节数
- 把某个代码页的 128–255 当成统一的扩展 ASCII
适用边界
- 本页给出完整标准 ASCII 0–127；Unicode 有十多万个已分配字符，不适合平铺成一张儿童课程长表，应按码点和字符数据库检索。
- “扩展 ASCII”没有唯一标准，128–255 的解释必须同时注明代码页；字符显示还依赖字体，有合法码点也不等于当前字体一定有对应字形。
完成检查