w wyl123ly 的博客
MD

Python-02-内置数据结构

35 KB 2026.10.11 原文件

Python-02-内置数据结构

本篇讲什么

Python 的日常代码有 80% 在跟四种结构打交道:列表(list)、元组(tuple)、字典(dict)、集合(set)。

本篇讲清它们的底层实现(动态数组、哈希表)、各自的操作与复杂度、如何用推导式与生成器表达式写得又短又快、浅拷贝与深拷贝的区别(附图示)、以及排序的稳定性与多关键字技巧。

读完后你应该能:看到一段需求就选对结构、说清每个操作的时间复杂度、并且不再踩"[[0] 3] 3 全变成同一行"这类经典陷阱。


一、是什么

四种内置容器一句话概括:

结构一句话定义有序可变元素可重复元素要求
list 列表动态数组,按位置存取是是是无
tuple 元组不可变的序列,常用来表示"一条记录"是否是无(但元素都不可哈希时才不可哈希)
dict 字典键值映射,基于哈希表是(插入顺序)是键不可重复键必须可哈希
set 集合不重复元素的容器,基于哈希表否(逻辑上无序)是否元素必须可哈希

"可哈希(hashable)"的意思是:对象有一个在其生命周期内不变的哈希值,且能与其他对象比较相等——也就是实现了 __hash__() 与 __eq__()。数字、字符串、元组、frozenset 可哈希;list、dict、set 不可哈希。


二、为什么这样设计

设计动机代价
列表是动态数组而不是链表数组的随机访问是 ,缓存友好;尾部追加均摊 头部插入/删除是 ;中间删除要搬移元素
元组不可变可哈希(能当字典键)、可安全共享、语义上表达"不该被改的数据"每次"修改"都要创建新元组
字典用哈希表平均 查找,是 Python 里最常见的加速手段占内存较多;最坏情况(大量哈希冲突)退化为
3.7 起字典保证插入顺序实现上改为"稀疏索引 + 紧凑条目"后,顺序天然稳定,索性写进语言规范早期版本不能依赖此性质;有额外内存开销
集合也是哈希表去重与成员判断 ,集合运算可读性极高不保存顺序;元素必须可哈希
提供推导式把"建容器 + 循环 + 条件"压缩成一个表达式,性能也更好(少了方法查找与 append 调用)嵌套过深可读性急剧下降

一句话选型

按位置取 → list;当记录/当键 → tuple;按键找值 → dict;去重与"在不在" → set。 拿不准时先用 list,出现"按某个字段查找"就换 dict,出现"判断是否出现过"就换 set。


三、核心内容

3.1 列表(list)

CPython 的 list 是动态数组:内部维护一块连续内存 + 已用长度 size + 已分配容量 allocated。追加元素时若容量不足,按约 1.125 倍扩容(CPython 实现细节,可能变化),因此 append 是均摊 。

常用操作与复杂度:

操作写法平均复杂度说明
索引l[i]、l[-1]负索引从末尾数
切片l[a:b]返回新列表
切片赋值l[1:3] = [...]可改变长度,就地修改
追加l.append(x) 均摊最常用
批量追加l.extend(it)等价于 l += it
插入l.insert(i, x)头部插入最贵
删除(按值)l.remove(x)只删第一个匹配;不存在报 ValueError
删除(按位置)l.pop()、l.pop(i)、del l[i]尾部 ,中间
查找位置l.index(x)不存在报 ValueError
计数l.count(x)
成员判断x in l大列表上的 in 是性能陷阱
排序l.sort(...)就地排序,返回 None
反转l.reverse()就地反转
浅拷贝l.copy()、l[:]、list(l)只复制顶层
长度len(l)

3.2 元组(tuple)

元组是不可变序列,它存在的意义不只是"不能改的列表":

  1. 可以当字典键 / 放进集合(元素都可哈希时)。
  2. 表达异构记录:("Ada", 36, "London") 是"一条数据",而列表更适合"同类的多个数据"。
  3. 解包(unpacking):name, age, city = row 让代码自解释;*rest 可收集剩余项。
  4. 更省内存、迭代更快:没有扩容预留空间与可变性检查。
对比项listtuple
可变性可变不可变
可哈希否元素可哈希时可哈希
内存占用较大(预留容量)较小
语义同质的序列异质的记录 / 常量序列
能否作字典键不能能(例如坐标缓存 {(x, y): value})

namedtuple 让元组字段有名字,是可读性与性能的折中;需要可变记录时用 dataclasses.dataclass(见 Python-04-面向对象)。

3.3 字典(dict)

字典是哈希表。CPython 3.6 起采用的是"紧凑字典(compact dict)"布局:

indices(稀疏索引数组):  [ -, 1, -, 0 ]        ← 每个槽位存 entries 的下标
entries(紧凑条目数组):  [(hash_a, key_a, val_a), (hash_b, key_b, val_b)]
                          ↑ 按插入顺序追加,所以遍历顺序 = 插入顺序
  • 查找:先算 hash(key) 定位到 indices 的槽位,再用 == 比对 key,命中则取出对应 value。平均 ,最坏 。
  • 装载因子:当已用槽位达到容量的 2/3 左右时扩容并重新散列(实现细节)。
  • 顺序:entries 按插入顺序追加,删除某个键只在 entries 里留一个空位,不会打乱其余顺序——这就是"3.7 起插入顺序是语言保证"的来源。

键的要求与相等性规则:

规则说明
键必须可哈希{[1]: "x"} 抛 TypeError: unhashable type: 'list'
相等即同键a == b 必须推出 hash(a) == hash(b),否则字典行为不可预测
数值与布尔会合并hash(1) == hash(1.0) == hash(True),所以 {1: "int", 1.0: "float"} 只有一个键
保留首次插入的键对象{True: "a", 1: "b"} 结果是 {True: 'b'}:键仍是 True,值被更新

常用 API:

操作写法说明
取值(可能缺失)d.get(k)、d.get(k, 默认值)缺失不报错
取值(缺失即建)d.setdefault(k, 默认值)返回该键的值;缺失时先插入默认值
取值(必须存在)d[k]缺失抛 KeyError
批量更新d.update(other)、d.update(k=v)覆盖同名键
删除del d[k]、d.pop(k)、d.pop(k, 默认值)pop 可给默认值避免异常
弹出最后插入项d.popitem()LIFO 顺序(3.7+ 文档化)
成员判断k in d判断的是键,不是值
键 / 值 / 条目视图d.keys()、d.values()、d.items()视图是动态的,字典变了它跟着变
合并成新字典`d1 \d2`(3.9+,PEP 584)右边覆盖左边
就地合并`d1 \= d2、d.update(d2)`修改 d1
反向遍历reversed(d)(3.8+)按插入顺序反向
复制d.copy()浅拷贝

collections 里的三个进阶字典(详见 Python-06-常用标准库):

类型用途关键方法
defaultdict(factory)缺失键自动用工厂函数创建值不用再写 setdefault
Counter(iterable)计数most_common(n)、update、+/-
OrderedDict需要顺序敏感的相等性判断或 move_to_end两个 OrderedDict 顺序不同则不相等

3.4 集合(set)与 frozenset

集合也是哈希表,只存键不存值,因此去重与成员判断都是平均 。

操作运算符方法复杂度
并集`a \b`a.union(b)
交集a & ba.intersection(b)
差集a - ba.difference(b)
对称差a ^ ba.symmetric_difference(b)
子集 / 超集a <= b、a >= bissubset、issuperset
不相交—a.isdisjoint(b)命中即返回
增删—add、discard(不报错)、remove(报 KeyError)、pop(弹出任意一个)

要点:

  • 空集合必须写 set():{} 是空字典。
  • 集合不保存顺序,list({...}) 的顺序不可依赖;需要"去重且保序"时用 dict.fromkeys(seq)。
  • frozenset 不可变、可哈希,因此能当字典键或放进另一个集合;set 不能。
  • 集合元素必须可哈希,所以"列表的列表"不能直接去重,要转成元组:set(map(tuple, rows))。

3.5 四种结构选型对比

需求首选原因次选
按下标随机访问list 索引tuple(不改动时)
频繁在两端增删collections.deque两端 list(尾部 、头部 )
表示一条不可变记录tuple / namedtuple / dataclass(frozen=True)可哈希、可解包、语义清晰dict
按键快速查找dict平均 —
判断"是否存在"、去重set平均 ,集合运算直观dict.fromkeys(需要保序时)
需要有序且按范围查询bisect + 有序 list二分 数据库/索引结构
需要"每个键对应多个值"defaultdict(list) / dict[str, list] + setdefault语义清楚dict[str, set](需要去重)
需要优先级队列heapq堆操作 queue.PriorityQueue(多线程)

3.6 推导式与生成器表达式

四种写法对照:

形式语法结果类型惰性备注
列表推导式[f(x) for x in it if cond]list否,立刻求值PEP 202
字典推导式{k: v for k, v in it}dict否PEP 274
集合推导式{f(x) for x in it}set否会去重
生成器表达式(f(x) for x in it)generator是,按需产出PEP 289,只能消费一次

关键语义(务必记住):

  1. 多个 for 是从左到右嵌套:[x for row in matrix for x in row] 等价于两层循环,外层写在前面。
  2. if 是过滤,x if c else y 是映射,两者可以同时出现。
  3. 推导式有自己的作用域,循环变量不会泄漏到外层(Python 3 的行为;Python 2 会泄漏)。
  4. 生成器表达式是惰性的且一次性:sum(gen) 之后再 list(gen) 得到空列表。它适合流式处理大数据,因为不会一次性把所有元素放进内存。

3.7 浅拷贝与深拷贝

  • 浅拷贝(shallow copy):新建外层容器,元素仍是原对象本身(共享)。
  • 深拷贝(deep copy):递归复制所有嵌套对象,两份数据完全独立。
graph TD
    A["原对象 a = [inner, d]"] --> A0["a[0] → 内层列表 [1, 2]"]
    A --> A1["a[1] → 内层字典 {k: v}"]
    B["浅拷贝 b = a.copy()"] --> A0
    B --> A1
    C["深拷贝 c = deepcopy(a)"] --> C0["新的内层列表 [1, 2]"]
    C --> C1["新的内层字典 {k: v}"]

文字版示意:

a ─┬─► [1, 2]        ← 同一个内层列表
   └─► {k: v}        ← 同一个内层字典
b ─┴─►(与 a 共享上面两个对象,但自己是新列表)

c ─┬─► [1, 2]  ← 副本
   └─► {k: v}  ← 副本
拷贝方式代码深度适用
切片b = a[:]浅一维列表
构造list(a)、dict(d)、set(s)浅任意可迭代对象
方法a.copy()、d.copy()浅推荐写法,意图明确
复制模块copy.copy(a)浅自定义类
深拷贝copy.deepcopy(a)深嵌套可变结构

copy.deepcopy 内部用 memo 字典记录已复制对象,因此能正确处理自引用(循环引用);同时它支持通过 __deepcopy__ 自定义行为。深拷贝的代价是慢且可能"复制过多"(例如把本该共享的配置对象也复制了)。

3.8 序列通用操作

只要对象实现了序列协议(__getitem__、__len__ 等),下面这些都能用:str、list、tuple、range、bytes、array.array。

操作示例说明
成员判断x in seqlist/tuple 是 ,str 是子串匹配
长度len(seq)
聚合min、max、sum、any、all都是 ;any/all 短路
拼接 / 重复a + b、a * 3返回新对象;a += b 对 list 是就地扩展
切片seq[a:b:c]返回同类型的新对象
计数 / 定位seq.count(x)、seq.index(x)
遍历并编号enumerate(seq, start=1)返回 (下标, 元素) 迭代器
并行遍历zip(a, b)、zip(a, b, strict=True)(3.10+)默认以最短为准,strict 会在长度不等时抛 ValueError
反向遍历reversed(seq)返回迭代器,不复制
排序sorted(seq, key=..., reverse=...)返回新列表
解包a, b, rest = seq、f(seq)PEP 448 起支持更灵活的解包

可迭代(iterable)≠ 序列(sequence)≠ 迭代器(iterator)

字典、集合、文件对象是可迭代但不是序列(不能索引);生成器、zip/map/filter 的返回值是迭代器(只能消费一次,且本身也是可迭代对象)。for 只要求可迭代。

3.9 排序稳定性与多关键字排序

Python 的排序用 Timsort:稳定(stable),最好情况 (已基本有序),最坏 ,需要 辅助空间。

"稳定"指键相等的元素保持原有相对顺序。它带来一个非常实用的技巧:多关键字排序可以分解为多次稳定排序(先排次要键,再排主要键)。

people = [("Bob", 30), ("Ada", 25), ("Cyd", 30), ("Dan", 25)]

# 写法一:元组键(推荐,一次排序)
sorted(people, key=lambda p: (p[1], p[0]))    # 先按年龄升序,再按姓名升序

# 写法二:稳定排序两趟(当某个键需要单独降序而另一个升序时最方便)
step1 = sorted(people, key=lambda p: p[0])              # 先排次要键
step2 = sorted(step1, key=lambda p: p[1])               # 再排主要键

# 需要用 operator 提速(比 lambda 略快,且意图清楚)
from operator import itemgetter, attrgetter
sorted(people, key=itemgetter(1, 0))
需求写法
单键升序sorted(data, key=keyfunc)
单键降序sorted(data, key=keyfunc, reverse=True)
多键,全部升序key=lambda x: (x.a, x.b)
多键,数字降序 + 文本升序key=lambda x: (-x.age, x.name)(数字取负)
多键,混合升降且不能取负多趟稳定排序,或 functools.cmp_to_key

reverse=True 会反转"相等元素"的顺序吗?

不会。reverse=True 仍然稳定:键相等的元素保持原相对顺序(文档明确说明)。唯一要注意的是:reverse=True 不是"排序后再反转列表",对相等元素而言两者结果不同。


四、怎么用(可运行示例)

4.1 列表:增删改查与切片赋值

nums = [3, 1, 4, 1, 5]

nums.append(9)            # 尾部追加:[3, 1, 4, 1, 5, 9]
nums.extend([2, 6])       # 批量追加(等价于 += )
nums.insert(0, 99)        # 头部插入 O(n):尽量避免在大列表上这样写
print(nums)

# 切片赋值可以改变长度,且是就地修改(其他引用能看到变化)
nums[0:1] = []            # 删掉第一个元素
nums[1:1] = [77]          # 空切片赋值 = 插入
print(nums)

# 按值删除只删第一个匹配
nums.remove(1)
print(nums)

# 就地排序、反转(都返回 None)
print(nums.sort(reverse=True), nums)   # None [77, 9, 6, 5, 4, 3, 2, 1]
print(nums.reverse(), nums)            # None [1, 2, 3, 4, 5, 6, 9, 77]

# 索引与负数下标(注意 reverse 是就地反转,此时列表已经被反转了)
print(nums[0], nums[-1], nums[1:3], nums[::-1])

4.2 一个真实陷阱: * 3 与 +=

# 陷阱一:重复运算符复制的是"引用",三行是同一个列表
bad = [[]] * 3
bad[0].append(1)
print(bad)                # [[1], [1], [1]]

# 正解:推导式每次都新建对象
good = [[] for _ in range(3)]
good[0].append(1)
print(good)               # [[1], [], []]

# 陷阱二:+= 是就地扩展(别名可见),= a + b 是新建对象
a = [1, 2]
alias = a
a += [3]
print(a, alias, a is alias)      # [1, 2, 3] [1, 2, 3] True

c = [1, 2]
alias2 = c
c = c + [3]                      # 新对象绑定回 c,alias2 还是老对象
print(c, alias2, c is alias2)    # [1, 2, 3] [1, 2] False

4.3 元组:解包与命名元组

from collections import namedtuple

# 解包:交换、星号收集、函数返回多值
point = (3, 4)
x, y = point
x, y = y, x
print(x, y)

first, *middle, last = [1, 2, 3, 4, 5]
print(first, middle, last)          # 1 [2, 3, 4] 5

def min_max(values):
    # 返回元组是 Python 表达"多返回值"的惯用法
    return min(values), max(values)

low, high = min_max([3, 1, 4, 1, 5])
print(low, high)

# 元组可以当字典键:用坐标做缓存
cache = {(0, 0): "origin", (1, 1): "diag"}
print(cache[(0, 0)])

# 命名元组:可读性接近类,开销接近元组
Point = namedtuple("Point", ["x", "y"])
p = Point(1, 2)
print(p, p.x, p._asdict(), p._replace(y=10))
# 注意:_replace 返回新对象,原对象不变(不可变语义)
print(p)

# 单元素元组的逗号不能省
print(type((1)), type((1,)))        # <class 'int'> <class 'tuple'>

4.4 字典:查找、聚合与合并

word_count = {}
for w in "the quick the lazy the end".split():
    # setdefault 一次完成"缺失则建 + 返回该键的值",避免两次查找
    word_count.setdefault(w, 0)
    word_count[w] += 1
print(word_count)

# 更 Pythonic 的计数方式
from collections import Counter, defaultdict

print(Counter("the quick the lazy the end".split()).most_common(2))

# 分组:defaultdict 让"缺失即建列表"不用写模板代码
by_len = defaultdict(list)
for w in ["a", "bb", "cc", "ddd"]:
    by_len[len(w)].append(w)
print(dict(by_len))

# 安全取值:区分"键不存在"和"值是 None"
config = {"retries": 0, "name": None}
print(config.get("retries"), config.get("missing"), config.get("name"))
print(config.get("missing", 3))            # 给默认值

# 合并(3.9+):右边覆盖左边
defaults = {"host": "localhost", "port": 80}
overrides = {"port": 8080}
print(defaults | overrides, defaults)      # 原字典不变
merged = {**defaults, **overrides}         # 3.5+ 的等价写法
print(merged)

# 遍历的三种姿势
for k in merged:                 # 只遍历键
    pass
for k, v in merged.items():      # 同时拿键值(推荐)
    pass
for v in merged.values():        # 只遍历值
    pass

# 视图是动态的:字典变了,已取得的视图跟着变
d = {"a": 1, "b": 2}
items = d.items()
d["c"] = 3
print(list(items))               # [('a', 1), ('b', 2), ('c', 3)]

# 3.8+ 反向遍历;popitem 按 LIFO 弹出
print(list(reversed(d)), d.popitem())

4.5 一个必须知道的行为:1、1.0、True 是同一个键

print(hash(1) == hash(1.0) == hash(True))    # True

d = {1: "int", 1.0: "float", True: "bool"}
print(d)          # {1: 'bool'} —— 三个写入落到了同一个键,值被最后一次覆盖

print({True: "a", 1: "b"})   # {True: 'b'}:键保留首次插入的那个对象
print({1: "x"}[True])        # x:用 True 能查到键 1 的值

# 工程后果:不要用"0/1"和"False/True"混合作键,也不要用浮点当键

4.6 集合:去重与集合运算

tags_a = {"python", "backend", "docker"}
tags_b = {"python", "frontend"}

print(tags_a & tags_b)         # 交集
print(tags_a | tags_b)         # 并集
print(tags_a - tags_b)         # 差集
print(tags_a ^ tags_b)         # 对称差
print(tags_a.isdisjoint({"golang"}))
print({"python"} <= tags_a)    # 子集

# 去重且保持原顺序(set 不保序,所以用 dict.fromkeys)
names = ["b", "a", "b", "c", "a"]
print(list(dict.fromkeys(names)))      # ['b', 'a', 'c']
print(sorted(set(names)))              # ['a', 'b', 'c']

# 空集合不是 {}
print(type(set()), type({}), bool(set()))     # <class 'set'> <class 'dict'> False

# frozenset 可哈希:能当键,也能放进集合
perms = {frozenset({"read", "write"}), frozenset({"read"})}
print(frozenset({"read"}) in perms, hash(frozenset({"read"})) is not None)

# 大列表去重的性能差异:set 判断是 O(1),list 是 O(n)
big = list(range(20_000))
as_set = set(big)
print(19_999 in big, 19_999 in as_set)

4.7 推导式与生成器表达式

matrix = [[1, 2, 3], [4, 5, 6]]

# 嵌套推导式:外层 for 写在左边,等价于两层循环
print([[row[i] for row in matrix] for i in range(3)])   # 转置
print([x for row in matrix for x in row])               # 展平

# 过滤 + 映射
print([x for x in range(10) if x % 3 == 0])             # [0, 3, 6, 9]
print([x if x % 2 else -x for x in range(4)])           # [0, 1, -2, 3]

# 字典推导式:翻转键值、由两个序列配对
ages = {"Ada": 36, "Bob": 41}
print({age: name for name, age in ages.items()})
print({k: v for k, v in zip("abc", range(3))})

# 集合推导式
print({abs(x) for x in (-1, 1, -2)})                    # {1, 2}

# 生成器表达式:惰性、省内存、只能消费一次
gen = (x * x for x in range(5))
print(sum(gen))          # 30
print(list(gen))         # [] —— 已经消费完了

# 大数据场景:用生成器表达式避免创建中间列表
total = sum(len(w) for w in ("alpha", "beta", "gamma"))
print(total)

# 推导式有自己的作用域,循环变量不会泄漏
[i for i in range(3)]
print("i" in dir())      # False

4.8 浅拷贝与深拷贝

import copy

inner = [1, 2]
orig = [inner, {"k": "v"}]

shallow = copy.copy(orig)        # 或 orig.copy() / orig[:] / list(orig)
deep = copy.deepcopy(orig)

# 1) 通过原引用修改嵌套对象:浅拷贝"看得到",深拷贝看不到
inner.append(3)
print(orig, shallow, deep)

# 2) 修改浅拷贝里的嵌套字典,原对象也会变(共享同一个字典)
shallow[1]["k"] = "changed"
print(orig[1], shallow[1], deep[1])

# 3) 顶层互不影响
shallow.append("new")
print(len(orig), len(shallow), len(deep))     # 2 3 2

# 4) 深拷贝能处理循环引用
a = []
a.append(a)                     # a 引用自己
b = copy.deepcopy(a)
print(b[0] is b)                # True:副本内部仍自引用,且不无限递归

4.9 序列通用操作:zip / enumerate / reversed

names = ["Ada", "Bob", "Cyd"]
scores = [92, 78, 85]

# zip 并行遍历;默认以最短为准 —— 长度不等会静默丢数据
print(list(zip(names, scores)))
print(list(zip(names, scores, [1, 2])))              # 只出 2 对
try:
    list(zip(names, scores, [1, 2], strict=True))    # 3.10+:长度不等直接报错
except ValueError as e:
    print("strict:", e)

# 用 zip 建字典、转置矩阵
print(dict(zip(names, scores)))
print(list(zip(*[[1, 2], [3, 4], [5, 6]])))          # [(1,3,5), (2,4,6)]

# enumerate 从 1 开始编号
for i, name in enumerate(names, start=1):
    print(f"{i}. {name}")

# reversed 返回迭代器,不复制列表
print(list(reversed(names)), names)                  # 原列表不变

# 通用聚合
print(len(scores), min(scores), max(scores), sum(scores), sum(scores) / len(scores))
print(any(s < 60 for s in scores), all(s >= 60 for s in scores))

4.10 排序:稳定性与多关键字

from operator import itemgetter

people = [("Bob", 30), ("Ada", 25), ("Cyd", 30), ("Dan", 25)]

# 单键升序 / 降序
print(sorted(people, key=itemgetter(1)))
print(sorted(people, key=itemgetter(1), reverse=True))

# 稳定性:年龄相同的两人保持原有先后顺序
print(sorted(people, key=lambda p: p[1]))       # Ada 在 Dan 前(原顺序)

# 多关键字:年龄升序 + 姓名升序
print(sorted(people, key=lambda p: (p[1], p[0])))

# 年龄降序 + 姓名升序(数字取负实现降序)
print(sorted(people, key=lambda p: (-p[1], p[0])))

# 两趟稳定排序:先次要键,再主要键;等价于上面但支持"文字键降序"
step1 = sorted(people, key=itemgetter(0), reverse=True)   # 姓名降序
step2 = sorted(step1, key=itemgetter(1))                  # 年龄升序(稳定)
print(step2)

# 排序对象属性:attrgetter 比 lambda 略快,也比手写 lambda 更清晰
from collections import namedtuple

Person = namedtuple("Person", "name age")
objs = [Person("Bob", 30), Person("Ada", 25)]
from operator import attrgetter

print(sorted(objs, key=attrgetter("age")))

# 老式比较函数(返回负数/0/正数)需要用 cmp_to_key 适配
import functools

print(sorted([3, 1, 2], key=functools.cmp_to_key(lambda a, b: b - a)))   # [3, 2, 1]

五、注意事项与常见坑

**坑 1: n 与 [0] n 的区别**

[0] 3 安全(整数不可变,改一个元素是重新绑定); 3 会让三行指向同一个内层列表,bad[0].append(1) 后三行全是 [1]。二维结构一律用推导式:[[0] * cols for _ in range(rows)]。

坑 2:list.sort() 返回 None,不是排序后的列表

a = [3, 1].sort() 会让 a 变成 None(就地排序的副作用),下一行 a[0] 直接 TypeError。需要新列表就用 sorted(...);想链式调用也只能用 sorted。同样的"返回 None"还有 append、extend、remove、reverse、d.update。

坑 3:浅拷贝共享嵌套对象

b = a.copy()(或 a[:]、list(a))只复制顶层。嵌套的列表/字典仍是同一个对象,改 b[0][0] 会连带改 a。嵌套结构要么用 copy.deepcopy,要么改成不可变数据(元组/frozenset/字符串)从根上避免共享可变状态。

坑 4:可变对象不能当字典键或集合元素

{[1]: "x"}、{{1}: "x"} 都抛 TypeError: unhashable type。元组只有在所有元素都可哈希时才能当键:hash((1, [2])) 一样报错。改用 tuple、frozenset 或把列表序列化成字符串。

坑 5:1、1.0、True 会撞成同一个键

因为 hash(1) == hash(1.0) == hash(True) 且它们相等,字典里只会有一个键。用浮点数当键还额外有精度风险(0.1 + 0.2 != 0.3),需要精确键就用 Decimal 或字符串。

坑 6:{} 是空字典,不是空集合

空集合要写 set()。另外 frozenset() 才是可哈希的不可变集合,set 不能作为另一个集合的元素。

坑 7:dict.fromkeys(seq, []) 让所有键共享同一个默认值

d = dict.fromkeys("abc", []) 中三个键指向同一个列表,d["a"].append(1) 后三个键都有 [1]。正确写法是 {k: [] for k in "abc"}。

坑 8:zip 默认按最短截断,会静默丢数据

zip([1, 2, 3], "ab") 只有两对。处理"两个本应等长的列表"时用 zip(..., strict=True)(3.10+),让长度不一致直接暴露为 ValueError。

坑 9:边遍历边修改列表

for x in lst: lst.remove(x) 会跳过元素甚至得到错误结果,因为迭代器按下标前进而列表在缩短。正确做法是遍历副本(for x in lst[:])或构造新列表(lst = [x for x in lst if 条件])。

坑 10:x in list 是 ,循环里嵌套用会变成

常见错误写法:for x in a: if x in b:——两个大列表就是平方级。把 b 提前转成 set/dict,整体降到 。复杂度推导见 算法-复杂度分析。

坑 11:生成器表达式只能消费一次

gen = (x for x in data),sum(gen) 之后 list(gen) 是空列表,调试点常在这里卡住。需要多次遍历就物化成 list;只遍历一次又想省内存才用生成器。

坑 12:排序要求键之间可比较

sorted([1, "a"]) 抛 TypeError;sorted([3.3, float("nan"), 1.1]) 的结果不可靠(NaN 与任何值比较都是 False)。混类型先统一成字符串,NaN/None 先过滤掉。

实践建议

1. 用 key= 而不是 cmp_to_key:key 函数每个元素只调用一次( 次),比较函数每次比较都调用( 次)。

2. 大列表查找前先转 set;需要"有序 + 二分查找"时用 bisect 模块而不是手写二分。

3. 数据类记录优先用 namedtuple / dataclass,比裸 dict 更难写错字段名。

4. 需要队列用 collections.deque,不要用 list.pop(0)()。


六、练习题

  1. 基础题:给定 nums = [5, 3, 8, 3, 9, 1],用一行代码得到"去重且保持首次出现顺序"的列表,再用一行得到"去重并升序"的列表,并说明两者差别来自哪里。
  1. 基础题:有一个二维列表 grid = [[0] 3] 2,解释为什么 grid[0][0] = 1 会让两行都变成 [1, 0, 0],并写出正确的初始化方式。
  1. 进阶题:给定学生列表 students = [("Ada", "A", 15), ("Bob", "B", 12), ("Cyd", "B", 10)](姓名、班级、年龄),分别用 ①元组键、②两趟稳定排序 实现"班级升序、年龄降序",比较两种写法在可读性与扩展性上的取舍。
  1. 进阶题:写一个函数 invert_index(docs: dict[str, list[str]]) -> dict[str, list[str]],把"文档 → 关键词列表"变成"关键词 → 文档列表",要求结果里每个关键词对应的文档列表有序且不重复;再说明为什么这个函数里不该用 dict.fromkeys(docs, [])。
  1. 思考题:为什么 Python 的字典在 3.7 之后才把"插入顺序"写进语言规范,而实现上 3.6 就已经有序?这种"实现先行、规范后追"的演进方式对使用者意味着什么?如果你要写一个必须在 3.5 上运行的库,代码要怎么改?

七、常见问题(FAQ)

Q1:什么时候用列表,什么时候用元组?

A:看语义而不是看性能。同质的、会增删的集合用 list([1, 2, 3]、查询结果集);异质的、固定不变的记录用 tuple/namedtuple((host, port)、坐标、函数多返回值)。元组额外的好处是可哈希(能当键)与更省内存,但不要为了省一点点内存把需要修改的数据塞进元组。

Q2:为什么我的字典键"看起来有两个"其实只有一个?

A:检查键之间是否 == 且哈希相同。典型来源:1 / 1.0 / True 撞键;自定义类没有按"值语义"实现 __eq__ 与 __hash__(默认用身份,两个内容相同的对象是两个键);用浮点或 Decimal 混合作键。排查手段:len(d) 与 list(d.keys()) 对照,或打印 [(k, hash(k)) for k in keys]。

Q3:浅拷贝到底拷了什么?为什么我改了副本原数据也变了?

A:只新建了最外层容器,元素仍是指向原对象的引用。所以"改副本的元素本身"(b[0] = 9)不影响原列表;但"改副本里嵌套的可变对象"(b[0].append(9))会影响原列表。需要完全独立就 copy.deepcopy,或者干脆用不可变数据(元组、frozenset、字符串)来消灭共享可变状态。

Q4:推导式和 for 循环哪个快?为什么?

A:推导式通常更快。原因有二:① 循环体在字节码层面是专门的 LIST_APPEND 指令,省掉了每轮一次 list.append 属性查找与函数调用;② 没有 Python 层的名字查找开销。但差距通常在常数倍以内,可读性优先:逻辑超过两层嵌套或带复杂 if/else 时就该退回普通 for 循环。生成器表达式在"数据量大且只需遍历一次"时不仅省内存,还常常更快(不需要构造整个列表)。


相关笔记

  • Python-01-环境与基础语法 —— 变量绑定、数字与字符串基础、真值测试
  • Python-03-函数与模块 —— 函数、闭包、模块;zip/enumerate/map 等内置函数的配合
  • Python-06-常用标准库 —— collections、itertools、bisect 的进阶容器与工具
  • Python-04-面向对象 —— dataclass、自定义 __eq__/__hash__ 与可变记录
  • 算法-排序 —— Timsort、稳定性与比较排序的复杂度下界
  • 数据结构-哈希表 —— 哈希函数、冲突解决、装载因子与 的代价
  • 算法-复杂度分析 —— 、、 的推导与均摊分析
  • 00-索引 —— 返回全库导航

参考来源

  • 官方教程:数据结构(列表、元组、字典、集合、推导式):<https://docs.python.org/3/tutorial/datastructures.html>
  • 内置类型与全部方法(list、dict、set、str 等):<https://docs.python.org/3/library/stdtypes.html>
  • collections(namedtuple、defaultdict、Counter、OrderedDict、deque):<https://docs.python.org/3/library/collections.html>
  • copy 模块(浅拷贝/深拷贝、memo、__deepcopy__):<https://docs.python.org/3/library/copy.html>
  • Sorting Techniques(key、稳定性、多趟排序、DSU、cmp_to_key):<https://docs.python.org/3/howto/sorting.html>
  • 内置函数(sorted、zip、enumerate、reversed、sum、any、all):<https://docs.python.org/3/library/functions.html>
  • operator(itemgetter、attrgetter):<https://docs.python.org/3/library/operator.html>
  • 数据模型(__hash__、__eq__、可哈希的定义):<https://docs.python.org/3/reference/datamodel.html>
  • Python 3.7 新特性(字典顺序成为语言保证):<https://docs.python.org/3/whatsnew/3.7.html>
  • PEP 202 List Comprehensions:<https://peps.python.org/pep-0202/>
  • PEP 274 Dict Comprehensions:<https://peps.python.org/pep-0274/>
  • PEP 289 Generator Expressions:<https://peps.python.org/pep-0289/>
  • PEP 448 Additional Unpacking Generalizations(更灵活的解包):<https://peps.python.org/pep-0448/>
  • PEP 584 Add Union Operators To dict(| 与 |=,3.9+):<https://peps.python.org/pep-0584/>
  • Python Wiki: TimeComplexity(各结构操作复杂度总表):<https://wiki.python.org/moin/TimeComplexity>
  • 说明:复杂度数字来自官方文档与 CPython 实现(如字典装载因子、列表扩容倍数属实现细节,可能随版本变化),以官方最新文档为准。