4.1 列表、字典与集合进阶

4.1 列表、字典与集合进阶

本节摘要：列表、字典、集合是 Python 最高频的三种容器，但"会用"和"用对"差距很大。本节讲清楚三者的特性与时间复杂度对比、选用原则，以及 collections 模块里 Counter 和 defaultdict 的妙用。通过词频统计和投票统计两道练习，把"为场景选对数据结构"的判断力练出来。

学习目标

阅读完本节，你应当能够：

1. 说出列表、字典、集合在查找、插入上的时间复杂度差异
2. 为"按位置访问""按键查找""去重"等场景选对容器
3. 用集合进行交集、并集、差集运算
4. 用 Counter 做计数，用 defaultdict 处理分组
5. 独立完成一道数据结构选型与操作的练习题

问题与直觉

考虑一个具体问题：给你一万个单词，统计每个单词出现了多少次。你会怎么做？

本能的写法可能是：用一个列表存所有单词，然后对每个单词遍历整个列表数它出现了几次。这个写法能跑出正确结果，但一万个单词要做大约一亿次比较——慢得无法忍受。

换一个思路：用一个字典，键是单词，值是它出现的次数。遇到一个单词，如果字典里有就把计数加一，没有就记为 1。字典的查找是 O(1) 的，整个统计只需要遍历一遍数据，一万次操作搞定。

数据结构选对了，算法复杂度天然就降下来了；选错了，再多优化也补不回来。 这就是为什么本节要花篇幅讲清楚每种容器的特性和适用场景，而不是只教你"列表有 append 方法"这种表层用法。

集合的去重、字典的快速查找、列表的有序索引——每种结构都有它擅长的战场。判断"这个任务该用哪个"，是数据结构进阶的核心能力。

核心原理

2.1 三种容器的特性对比

最关键的一行是成员判断：在列表里判断"某个元素在不在"要逐个比对，数据量大时极慢；字典和集合基于哈希表，判断成员只需 O(1)。

# 同样是判断 100 万个数字里有没有 999999
nums_list = list(range(1000000))
nums_set = set(range(1000000))

999999 in nums_list   # 慢：最坏要比较 100 万次
999999 in nums_set    # 快：哈希查找，瞬间
​

2.2 选用决策树

💡 关键直觉：需要频繁判断"在不在"或"按值查找"的，别用列表，用集合或字典。这是新手最常犯的性能错误——图省事全用列表，数据量一上来程序就卡。

2.3 集合运算

集合天生支持数学上的集合运算，代码极简：

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

print(a & b)   # {3, 4}  交集
print(a | b)   # {1, 2, 3, 4, 5, 6}  并集
print(a - b)   # {1, 2}  差集（a 有 b 没有）
print(a ^ b)   # {1, 2, 5, 6}  对称差（只在一边的）
​

如果用列表实现"找两个列表的共同元素"，要双重循环；集合一行 & 搞定，而且快。

2.4 collections 高级容器

标准库 collections 提供了几个解决特定痛点的容器：

Counter：专门做计数。第 1 章我们手写的词频统计，用它一行搞定：

from collections import Counter

words = "the cat sat on the mat the cat".split()
counter = Counter(words)
print(counter)                 # Counter({'the': 3, 'cat': 2, 'sat': 1, ...})
print(counter.most_common(2))  # [('the', 3), ('cat', 2)]
​

defaultdict：访问不存在的键时自动创建默认值，省去"先判断键在不在"的啰嗦：

from collections import defaultdict

# 按首字母分组单词
groups = defaultdict(list)
for word in ["apple", "banana", "avocado", "berry"]:
    groups[word[0]].append(word)
# {'a': ['apple', 'avocado'], 'b': ['banana', 'berry']}
​

普通字典访问 groups["a"] 时键不存在会报 KeyError，defaultdict(list) 会自动建一个空列表。

工程实践要点

3.1 别用列表做存在性判断

# 坏：每次判断都遍历整个列表
valid_users = ["alice", "bob", "charlie"]   # 想象有 10 万个
if new_user in valid_users:                  # O(n) 慢
    ...

# 好：转成集合
valid_set = set(valid_users)
if new_user in valid_set:                    # O(1) 快
    ...
​

⚠️ 常见坑：把"配置项""允许的值"这类需要频繁判断成员的数据存成列表。数据少时没感觉，数据多或判断频率高时，性能差距是数量级的。

3.2 字典的 get 与 setdefault

访问可能不存在的键，get 比"先 in 判断再访问"更简洁：

# 啰嗦
if "age" in person:
    age = person["age"]
else:
    age = 0

# 简洁
age = person.get("age", 0)   # 键不存在时返回默认值 0
​

setdefault 在键不存在时设置默认值并返回它，适合"懒初始化"场景。但更复杂的多级分组，还是 defaultdict 更清楚。

3.3 字典的视图与排序

字典的 keys()、values()、items() 返回的是视图，不是列表，它们会反映字典的实时变化：

d = {"a": 1, "b": 2}
items = d.items()
d["c"] = 3
print(list(items))   # [('a', 1), ('b', 2), ('c', 3)]，视图看到了新增
​

需要按顺序处理字典时，用 sorted(d.items(), key=lambda x: x[1]) 按值排序。

3.4 不可变集合 frozenset

集合本身是可变的，不能当字典键或放另一个集合里。需要"可哈希的集合"时用 frozenset：

frozen = frozenset({1, 2, 3})
d = {frozen: "一组数字"}   # 合法，普通 set 不行
​

3.5 容器间的转换模式

实际编码中，三种容器常需要互相转换，理解转换的"代价"能让代码更高效：

nums = [1, 2, 2, 3, 3, 3]

# 列表 → 集合：去重，但丢顺序
unique = set(nums)              # {1, 2, 3}

# 集合 → 列表：恢复可索引，但顺序不保证
unique_list = list(unique)

# 两个列表 → 字典：用 zip 配对
keys = ["a", "b", "c"]
values = [1, 2, 3]
d = dict(zip(keys, values))     # {'a': 1, 'b': 2, 'c': 3}

# 字典 → 列表：取键、值或键值对
list(d.keys())                  # ['a', 'b', 'c']
list(d.values())                # [1, 2, 3]
list(d.items())                 # [('a', 1), ('b', 2), ('c', 3)]
​

💡 关键直觉：zip 是把两个并行列表"拉链式"配对的利器，配合 dict() 一行就能造出字典，比手写循环简洁得多。这是 Python 数据处理的常用套路。

3.6 字典合并的几种写法

Python 3.9+ 支持用 | 合并字典，比老写法直观：

defaults = {"host": "localhost", "port": 8080}
override = {"port": 9000}

# 老写法：update 会原地修改
merged = defaults.copy()
merged.update(override)         # {'host': 'localhost', 'port': 9000}

# 新写法（3.9+）：| 产生新字典，不改原对象
merged = defaults | override    # 同上，更简洁
​

注意 | 产生新字典，update 原地修改——根据"要不要保留原字典"选择。

分层练习

基础题：列表去重保序

题面：给定一个可能有重复元素的列表，去掉重复元素但保持原始顺序。比如 [1, 3, 2, 3, 1, 4] 变成 [1, 3, 2, 4]。

思路点拨：直接 set() 会丢顺序。正确做法是用一个集合记录"见过的元素"，遍历列表，没见过的就加入结果并标记。

参考骨架：

def dedup_keep_order(lst):
    seen = set()
    result = []
    for x in lst:
        if x not in seen:
            seen.add(x)
            result.append(x)
    return result

print(dedup_keep_order([1, 3, 2, 3, 1, 4]))   # [1, 3, 2, 4]
​

💡 思考延伸：Python 3.7+ 字典保持插入顺序，所以也可以 list(dict.fromkeys(lst)) 一行去重保序。但理解上面的"集合+列表"做法，能帮你掌握通用思路。

进阶题：词频统计

题面：给定一段英文文本，统计每个单词的出现次数，输出出现次数最多的前 3 个单词（不区分大小写，忽略标点）。

思路点拨：用 Counter 最直接。先清洗文本（转小写、去标点、按空白分割），再 Counter(words).most_common(3)。

参考骨架：

from collections import Counter

text = "The cat sat on the mat. The cat was happy."
# 清洗：转小写，把标点替换成空格，分割
import re
cleaned = re.sub(r"[^\w\s]", " ", text.lower())
words = cleaned.split()
top3 = Counter(words).most_common(3)
print(top3)   # [('the', 3), ('cat', 2), ...]
​

挑战题：列表交集与差集

题面：给定两个列表 a = [1, 2, 3, 4, 5] 和 b = [4, 5, 6, 7, 8]，求它们的共同元素、a 独有的元素、b 独有的元素。要求用集合运算实现。

思路点拨：转集合后用 &、- 运算符。结果如果要按顺序或可索引，再转回列表。

参考骨架：

a, b = [1, 2, 3, 4, 5], [4, 5, 6, 7, 8]
sa, sb = set(a), set(b)
print("共同:", sa & sb)     # {4, 5}
print("a 独有:", sa - sb)   # {1, 2, 3}
print("b 独有:", sb - sa)   # {8, 6, 7}
​

💡 思考延伸：如果两个列表各有十万元素，用集合运算只需毫秒级，用双重循环则要几十秒。这就是 O(n) 与 O(n²) 的现实差距——选对数据结构，性能天差地别。

挑战题：投票统计

题面：给定一组投票记录，每条是 (候选人, 得票数)，比如 [("A", 5), ("B", 3), ("A", 2), ("C", 4), ("B", 1)]。统计每个候选人的总票数，按票数从高到低排序输出，并判断是否有过半数获胜者。

思路点拨：defaultdict(int) 累加每个候选人的票数；排序用 sorted 配 key；过半判断用总票数对比。

参考骨架：

from collections import defaultdict

votes = [("A", 5), ("B", 3), ("A", 2), ("C", 4), ("B", 1)]
tally = defaultdict(int)
for name, count in votes:
    tally[name] += count

total = sum(tally.values())
ranked = sorted(tally.items(), key=lambda x: x[1], reverse=True)
print(ranked)   # [('A', 7), ('C', 4), ('B', 4)]

winner = ranked[0]
if winner[1] > total / 2:
    print(f"{winner[0]} 过半数获胜")
else:
    print("无人过半")
​

⚠️ 常见坑：sorted 默认升序，要降序记得 reverse=True。另外排序字典的 items() 时，key=lambda x: x[1] 是按"值"（票数）排，别漏了这个，否则会按键（名字）排。

追问与答疑

字典既然也是 O(1)，什么时候该用集合而不是"值为 None 的字典"？ 功能上集合就是"只有键的字典"，用字典模拟集合永远可行，但两个理由让集合更值得选：一是语义，读代码的人看到集合立刻知道"这里只关心存在性"；二是集合支持 &、- 这类整体运算，写起来更短也更不容易错。反过来，如果你将来可能给每个元素附加信息，从字典起步是更稳妥的演化路径。这类"结构预留演化空间"的权衡，比死记规则有用。

哈希表为什么会慢起来，O(1) 是保证吗？ 严格说是"均摊 O(1)"，且有两个前提：哈希函数分布均匀、键可哈希。实践中让字典变慢的常见原因是哈希冲突集中——比如用小整数区间当键，或者自定义对象的 __hash__ 写得糟糕，大量键挤进同一个桶，查找退化成桶内遍历。另一个隐蔽前提是"可哈希"：列表不能当字典键（可变对象哈希会漂移），需要"列表当键"的场景先转元组或 frozenset。

defaultdict 有什么坑？ 它的自动创建是"访问即创建"——包括只读判断。if groups["x"] 这种探测式检查会凭空建出一个空列表，字典被无声污染。需要"查看但不创建"的语义时用普通字典的 get。另外 defaultdict 在打印时和普通字典长得一样，序列化后重新读入就变回普通字典，跨边界传递数据时别依赖这个类型。

排序稳定吗，同票数怎么保证顺序？ Python 的排序是稳定排序：键相等的元素保持原有相对顺序。投票统计题里 C 和 B 同为 4 票，输出顺序取决于它们第一次进入字典的顺序。要改变这个行为，把 key 写成元组 lambda x: (-x[1], x[0])——先按票数降序，票数相同按名字排序。元组比较是 Python 里表达"多级排序"的标准手法，值得专门记一记。

补充练习：两班成绩对比

题面：给定两个班的成绩字典 {姓名: 分数}，用集合与字典运算回答四个问题：两班都出现过的同名学生有哪些？只在一班出现的学生有哪些？把两班成绩合并成一个总字典（同名且同分才不冲突，冲突时保留高分）？各班平均分各是多少？

思路点拨：前两问是集合运算的直接应用——对键取交集、差集。第三问合并要遍历处理冲突，是"字典推导 + 条件"的组合。平均分用 sum(d.values()) / len(d)，注意空字典要先排除。

参考骨架：

class_a = {"小明": 85, "小红": 92, "小刚": 78}
class_b = {"小明": 88, "小丽": 95, "小红": 92}

both = set(class_a) & set(class_b)          # {'小明', '小红'}
only_a = set(class_a) - set(class_b)        # {'小刚'}
merged = dict(class_b)                      # 先复制 b
for name, score in class_a.items():
    if name not in merged or score > merged[name]:
        merged[name] = score                # 冲突保留高分
avg_a = sum(class_a.values()) / len(class_a)
​

这题的价值在于同一份数据换四种视角：键的集合、键值对、合并视图、统计值。熟练后你会发现很多"看似要做复杂逻辑"的需求，拆开就是两三个容器操作的组合。

做这题时留个心眼：合并冲突"保留高分"的逻辑写在循环里，也可以改写成一行字典推导，但可读性孰优孰劣，请你两版都写出来自己对比——这是判断"推导式边界"的又一次实战。多数人比完会同意：带 else 分支且要读旧值的合并逻辑，循环写法更清楚。工具没有优劣，用错位置才是问题。

本节要点回顾

• 列表有序可重复、字典键值映射、集合唯一去重：三者定位不同，按场景选。
• 成员判断列表是 O(n)、字典和集合是 O(1)：频繁判断"在不在"的别用列表。
• 集合运算用符号：& 交集、| 并集、- 差集、^ 对称差，简洁高效。
• Counter 专做计数：most_common(n) 直接拿前 n 个。
• defaultdict 处理分组：访问不存在的键自动建默认值，省去啰嗦的判断。
• get 访问可能缺失的键：比"先判断再访问"简洁。
• 去重保序用"集合记录+列表收集"：直接 set 会丢顺序。

下一节我们学一种构造这些容器的简洁语法——推导式，以及省内存的生成器表达式。