Python程序设计强基计划10讲 · 第三讲：字典与集合——哈希表的威力

Python程序设计强基计划10讲 · 第三讲字典与集合——哈希表的威力作者培风图南以星河揽胜发布时间2026年3月31日适用对象已掌握列表、元组等序列类型的Python初学者前置知识第二讲《列表与元组——序列操作的艺术》标签Python数据结构、字典、集合、哈希表、O(1)查找、CSDN博客引言为什么说“不会用字典等于放弃效率”在Python编程中字典dict和集合set是性能最强大的内置数据结构。它们基于哈希表Hash Table实现提供平均O(1) 时间复杂度的查找、插入和删除操作。对比列表O(n) 查找字典和集合在处理以下场景时具有数量级优势学生成绩管理系统学号 → 成绩去重大量数据快速判断元素是否存在统计词频或类别计数然而许多初学者仅将字典当作“键值对容器”对以下核心问题缺乏理解为什么字典的键必须是不可变类型dict.keys()返回的是什么能直接遍历吗集合的|、、-运算符代表什么哈希冲突如何影响性能本讲将带你深入哈希表的本质系统掌握字典与集合的高级用法。你将学到字典的键约束与视图对象机制集合的数学运算与去重原理哈希表的内部结构与性能边界字典推导式的简洁表达力掌握这些你不仅能写出正确代码更能写出高效、优雅、可扩展的代码一、字典dict键值映射的王者1.1 字典的核心特性特性说明无序Python 3.7 有序插入顺序保留CPython实现保证可变支持动态增删改键唯一重复键会覆盖旧值键不可变键必须是 hashable 类型如 str, int, tuple✅ 基本操作速览# 创建d{name:Alice,age:25}ddict(nameAlice,age25)d{k:vfork,vinzip(keys,values)}# 字典推导式# 访问print(d[name])# Aliceprint(d.get(score))# None安全访问# 修改/增加d[age]26d[score]95# 删除deld[age]d.pop(score)# 返回并删除d.clear()# 清空所有1.2 键的约束为什么必须是不可变类型 哈希表原理简述字典通过哈希函数将键映射到内存地址若键可变其哈希值可能改变导致无法定位原值。✅ 合法键类型d{str_key:1,42:2,(1,2):3,# 元组不可变frozenset({1,2}):4# 冻结集合}❌ 非法键类型d{[1,2]:1,# TypeError: unhashable type: list{a:1}:2,# TypeError: unhashable type: dict{1,2}:3# TypeError: unhashable type: set}关键结论只有不可变且可哈希的对象才能作键。1.3 安全访问get() vs []方法行为适用场景d[key]不存在则抛KeyError确定键存在d.get(key)不存在返回None不确定键是否存在d.get(key, default)不存在返回default提供默认值✅ 最佳实践# 统计词频推荐word_count{}forwordinwords:word_count[word]word_count.get(word,0)1# 或使用 defaultdict进阶fromcollectionsimportdefaultdict word_countdefaultdict(int)forwordinwords:word_count[word]11.4 视图对象View Objects动态反映字典变化Python 3 中dict.keys()、dict.values()、dict.items()返回视图对象而非列表。 动态特性示例d{a:1,b:2}keys_viewd.keys()print(list(keys_view))# [a, b]d[c]3print(list(keys_view))# [a, b, c] —— 自动更新✅ 视图对象的优势内存高效不复制数据实时同步始终反映字典当前状态支持集合运算仅keys()和items()d1{a:1,b:2}d2{b:3,c:4}# 键的交集print(d1.keys()d2.keys())# {b}# 键的差集print(d1.keys()-d2.keys())# {a}注意values()视图不支持集合运算因值可重复。二、集合set无序唯一的元素容器2.1 集合的核心特性特性说明无序元素无固定顺序唯一自动去重可变支持增删frozenset不可变元素不可变同字典键要求✅ 基本操作# 创建s{1,2,3}sset([1,2,2,3])# {1, 2, 3}自动去重sset(hello)# {h, e, l, o}# 操作s.add(4)s.remove(1)# 不存在则报错s.discard(1)# 不存在不报错s.pop()# 随机弹出一个元素2.2 集合的数学运算集合支持标准的数学集合运算代码极其简洁。运算符号方法示例并集union()交集intersection()A B差集-difference()A - B对称差集^symmetric_difference()A ^ B✅ 实战示例找出两个班级的共同学生class_a{Alice,Bob,Charlie}class_b{Bob,David,Eve}commonclass_aclass_b# {Bob}only_aclass_a-class_b# {Alice, Charlie}all_studentsclass_a|class_b# {Alice, Bob, Charlie, David, Eve}优势比列表遍历快 O(n) 倍2.3 集合的去重优势场景从百万级列表中去重# 列表去重低效unique_list[]foriteminbig_list:ifitemnotinunique_list:# O(n) 检查unique_list.append(item)# 总体 O(n²)# 集合去重高效unique_setset(big_list)# O(n)unique_listlist(unique_set)# 若需列表性能对比n10⁶ 时列表方法需数分钟集合方法仅需0.1秒⚠️ 注意集合去重会丢失顺序若需保持顺序的去重可用seenset()unique[xforxinlstifnot(xinseenorseen.add(x))]三、哈希表的内部机制与性能特性3.1 哈希表如何工作哈希函数将键转换为整数哈希值取模运算index hash(key) % table_size确定存储位置处理冲突若位置已被占用使用开放寻址或链地址法。 简化示例# 假设哈希表大小为8hash(a)%83→ 存储在索引3hash(b)%83→ 冲突存入下一空位如43.2 哈希冲突与负载因子负载因子Load Factor 元素数量 / 表大小Python 默认负载因子阈值为2/3超过阈值时自动扩容通常翻倍并重新哈希所有元素。 性能影响理想情况O(1) 查找极端冲突如所有键哈希值相同退化为 O(n)但Python的哈希函数设计优良实际极少发生。3.3 时间复杂度总结操作字典dict集合set查找O(1) 平均O(1) 平均插入O(1) 平均O(1) 平均删除O(1) 平均O(1) 平均遍历O(n)O(n)对比列表查找/插入/删除均为 O(n)四、字典推导式声明式编程的利器字典推导式提供了一种简洁、高效的创建字典方式。4.1 基本语法{key_expr:value_exprforiteminiterableifcondition}✅ 经典示例# 反转字典original{a:1,b:2,c:3}reversed_d{v:kfork,vinoriginal.items()}# {1: a, 2: b, 3: c}# 过滤并转换scores{Alice:85,Bob:92,Charlie:78}passed{name:scoreforname,scoreinscores.items()ifscore80}# {Alice: 85, Bob: 92}4.2 高级用法嵌套字典推导# 创建字母频率表texthello worldchar_freq{char:text.count(char)forcharinset(text)ifchar! }# {h:1, e:1, l:3, o:2, w:1, r:1, d:1}多条件过滤# 提取长度3且首字母大写的单词words[Apple,hi,Banana,cat]long_caps{w:len(w)forwinwordsifw[0].isupper()andlen(w)3}# {Apple: 5, Banana: 6}4.3 与集合推导式的对比推导式语法示例字典{k: v for ...}{i: i**2 for i in range(5)}集合{expr for ...}{i**2 for i in range(5)}# 集合推导式自动去重squares{x**2forxin[-2,-1,0,1,2]}# {0, 1, 4}注意集合推导式用{}但无冒号否则是字典。五、典型误区与避坑指南误区1修改字典键d{a:1}kad[k]2# 修改值合法kb# 这不会修改字典print(d)# {a: 2}✅正确改键d[b] d.pop(a)误区2在遍历字典时修改它# 危险forkind:ifcondition:deld[k]# RuntimeError: dictionary changed size during iteration✅修正遍历键的副本forkinlist(d.keys()):# list() 创建副本ifcondition:deld[k]误区3认为集合有序s{3,1,4,1,5}print(s)# 顺序不确定可能是 {1, 3, 4, 5}✅若需有序唯一用dict.fromkeys(lst).keys()Python 3.7误区4滥用字典推导式导致可读性下降# 过于复杂result{transform(k):process(v)fork,vindata.items()ifvalidate(k)andfilter(v)}✅修正拆分为普通循环或提取辅助函数六、动手练习巩固哈希表应用练习1合并字典编写函数merge_dicts(d1, d2)合并两个字典。若键冲突以d2为准。练习2找出差异给定两个字符串s1和s2找出只在s1中出现的字符只在s2中出现的字符两者共有的字符练习3字典推导式实战给定列表students [(Alice, 85), (Bob, 92), (Charlie, 78)]用字典推导式创建字典并筛选出成绩≥80的学生。七、本讲小结哈希表的三大境界会用掌握基本增删改查懂理理解哈希机制、键约束、视图对象善用灵活运用集合运算、推导式提升效率与可读性。关键口诀“字典键要不可变集合天生会去重。”“查找用 dict/set别再遍历 list。”“视图对象动态连推导式建字典。”下期预告第四讲《函数与模块——代码复用的艺术》下一讲将深入解析 Python 的函数与模块机制函数定义与参数传递位置、关键字、默认值变量作用域LEGB规则与闭包模块导入机制与命名空间文档字符串与类型提示助你写出可复用、可维护、可协作的代码原创声明本文为《Python程序设计强基计划10讲》系列第三讲版权归作者所有。互动邀请你在使用字典或集合时遇到过哪些性能问题欢迎评论区交流关注我系统夯实Python数据结构基础为算法与项目开发铺路