Python 内置集合类型详解

Python 的内置容器（builtin collections）是这门语言的地基：list、tuple、dict、set、str 这五个类型覆盖了绝大多数日常代码。它们看起来简单，但每一个背后都有精心设计的实现——list 是动态数组而非链表、dict 从 3.7 起保证有序、set 和 dict 共享哈希表思路。理解这些实现细节，才能写出既正确又高效的代码。

本文逐个拆解内置集合类型：它是什么、内部如何实现、常见操作的时间复杂度、容易踩的坑，最后给出一份选型速查表。

总览：一张分类图

按两个维度分类：是否可变（mutable） 和 是否有序（sequence / mapping / set）：

类型	类别	可变	有序	允许重复	底层实现
list	序列	✅	✅（插入序）	✅	动态数组
tuple	序列	❌	✅	✅	定长数组
range	序列	❌	✅	—	算术序列（O(1) 内存）
str	序列	❌	✅	✅	不可变字符数组
bytes / bytearray	序列	❌ / ✅	✅	✅	字节数组
dict	映射	✅	✅（3.7+ 插入序）	键唯一	哈希表
set	集合	✅	❌	❌	哈希表
frozenset	集合	❌	❌	❌	哈希表

三个核心语义差异要记住：

1. 可变性决定了能否作为 dict 的键 / set 的元素（只有可哈希对象才行）。
2. 有序性在 list/tuple 是天然的；dict 自 Python 3.7 起是语言规范保证的插入序；set 无序。
3. 重复元素：set/dict 的键去重，序列不去重。

list：动态数组

list 是使用频率最高的容器，但它不是链表——它是动态数组（类似 C++ 的 vector、Java 的 ArrayList）。这一点决定了它所有的性能特征。

基本用法

nums = [1, 2, 3]
nums.append(4)          # 尾部追加，摊还 O(1)
nums.insert(0, 0)       # 头部插入，O(n) —— 后面所有元素要搬移
nums.pop()              # 尾部弹出，O(1)
nums.pop(0)             # 头部弹出，O(n)
nums[2] = 99            # 下标随机访问，O(1)
3 in nums               # 线性查找，O(n)
nums[1:3]               # 切片，产生新列表，O(k)

实现原理：过度分配

CPython 的 list 底层是一块连续的 PyObject* 指针数组。append 时如果容量不够，会按约 1.125 倍（new_allocated = newsize + (newsize >> 3) + 6）重新分配一块更大的内存并拷贝旧元素。因此：

• append 是摊还 O(1)——偶尔触发一次 O(n) 的扩容，均摊到每次操作是常数。
• 中间的 insert/delete 永远是 O(n)，因为要搬移后续元素。
• 随机访问 O(1)，缓存局部性好，遍历时比任何"逻辑上更优"的结构都快。

常见坑

坑 1：迭代时修改列表

nums = [1, 2, 3, 4]
for n in nums:
    if n % 2 == 0:
        nums.remove(n)   # 危险！remove 导致元素前移，迭代器下标错位
print(nums)              # [1, 3] 看似对了，换成 [2,2,3] 就漏删

正确做法是构造新列表，或者反向遍历：

nums = [n for n in nums if n % 2 != 0]      # 推荐：列表推导式
# 或者
for n in reversed(nums): ...                # 反向删，下标不受影响

坑 2：用 * 复制嵌套列表

matrix = [[0] * 3] * 3
matrix[0][0] = 1
print(matrix)  # [[1, 0, 0], [1, 0, 0], [1, 0, 0]] —— 三行是同一个对象！

* 做的是浅拷贝：外层列表的三个元素指向同一个内层列表。正确写法：

matrix = [[0] * 3 for _ in range(3)]

坑 3：频繁头部插入。如果需要"栈"行为（尾部进出），list 完美；如果需要双端高效操作，用 collections.deque。

tuple：不可变序列

tuple 常被误解为"不可变的 list"，这没错但不完整。它有两个独特的价值：

1. 可哈希，能当 dict 的键

# 二维坐标 → 值的映射，list 做不到（list 不可哈希）
grid = {}
grid[(3, 5)] = "home"

2. 语义：表示"一条记录"而非"一组同类数据"

这是 Python 社区的惯例：list 装同质的、数量可变的元素；tuple 装异质的、结构固定的字段：

row = ("Alice", 30, "Beijing")     # 一条记录，字段含义由位置决定
users = [row1, row2, row3]         # 一组记录

字段多了记不住位置时，升级到 collections.namedtuple 或 dataclass。

不可变的只是"容器本身"

t = ([1, 2], 3)
t[0].append(99)     # 合法！tuple 只锁定"引用"，不锁定引用指向的对象
print(t)            # ([1, 2, 99], 3)
t[1] = 4            # TypeError —— 不能换引用

也因此，含有可变元素的 tuple 不可哈希，不能放进 set。

性能细节

tuple 是不可变的定长数组，创建、索引、迭代都比 list 略快，且 CPython 对小 tuple 有缓存优化。函数返回多个值时用的就是它：

def divmod_(a, b):
    return a // b, a % b    # 实际返回一个 tuple

q, r = divmod_(10, 3)       # 解包

dict：哈希表，Python 的心脏

dict 不只是容器——Python 自身的命名空间、对象属性、模块系统都建立在 dict 之上。它的实现（CPython 3.6+ 的 “compact dict”）非常精巧。

基本操作

d = {"a": 1, "b": 2}

d["c"] = 3              # 插入/更新，O(1)
d["a"]                  # 查找，O(1)；KeyError 若不存在
d.get("x", 0)           # 带默认值的查找，不抛异常
d.setdefault("x", 0)    # 不存在则写入默认值并返回
"a" in d                # 键存在性检查，O(1)
d.pop("b")              # 删除并返回值
d.update({"d": 4})      # 批量合并
d | {"e": 5}            # 3.9+ 合并运算符，返回新 dict

d.keys() / d.values() / d.items()   # 视图对象，动态反映 dict 变化
for k, v in d.items(): ...

两个必须记住的特性

1. 有序（3.7+ 语言规范保证）

d = {}
d["z"] = 1
d["a"] = 2
print(list(d))          # ['z', 'a'] —— 按插入顺序，不是按大小

顺序是插入序，删除后再插入会排到最后。这来自 3.6 引入的 compact dict：哈希索引表 + 紧凑条目数组，条目数组天然按插入顺序排列。

2. 键必须可哈希

可哈希 = 有稳定一生的 __hash__ + 正确的 __eq__。内置的不可变类型（str、int、tuple、frozenset）都可哈希；list、dict、set 不可哈希。

两个哈希相等且 == 相等的对象是同一个键：

d = {1: "int", True: "bool", 1.0: "float"}
print(d)    # {1: 'float'} —— 1 == True == 1.0 且 hash 相同，后值覆盖前值

常见坑

坑 1：遍历时报 KeyError，先想 get 还是 setdefault

counts = {}
for word in words:
    counts[word] = counts.get(word, 0) + 1
# 更优雅：collections.Counter 或 defaultdict(int)

坑 2：迭代时增删键

for k in d:
    if cond(k):
        del d[k]        # RuntimeError: dictionary changed size during iteration

for k in list(d): ...   # 先快照 keys 再删

坑 3：可变对象作键后修改它。键存入后哈希值若变化，条目就"丢"在错误的桶里，再也查不到。这也是 Python 干脆禁止可变内置类型作键的原因。

性能边界

• 查找/插入/删除平均 O(1)；哈希冲突极多的病态输入下退化为 O(n)，但 str 哈希有随机化（PYTHONHASHSEED）防御。
• 内存开销不小：每个 dict 有索引表 + 条目数组，小 dict 约 64 字节起步。要存百万级记录且在意内存，考虑 __slots__、tuple 或 array。

set / frozenset：去重与集合运算

set 可以理解成"只有键没有值的 dict"，同样基于哈希表，同样 O(1) 成员测试、要求元素可哈希。

什么时候用

• 去重：unique = set(items)
• 成员测试：if x in valid_ids —— 大数据量下比 in list 快几个数量级
• 集合运算：交并差对称差

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

a | b       # {1, 2, 3, 4}   并集
a & b       # {2, 3}         交集
a - b       # {1}            差集
a ^ b       # {1, 4}         对称差
a <= b      # 子集判断
2 in a      # O(1) 成员测试

s = set()
s.add(1); s.discard(2); s.remove(3)   # remove 不存在会 KeyError，discard 不会

frozenset 是不可变版本，可哈希，能放进别的 set 或当 dict 的键：

edges = {frozenset({"a", "b"}): weight}   # 无向边作键

注意点

• set 无序：遍历顺序取决于哈希值，不要依赖它。要"有序去重"用 dict.fromkeys(items)。
• 空集必须写 set()，{} 是空 dict。

str / bytes / range：常被忽略的序列

它们不是"集合"语义上的容器，但作为序列共享同一套协议（索引、切片、in、len、迭代）。

str

不可变的 Unicode 字符序列。要点：

• 拼接：循环里 s += part 在 CPython 下常有优化，但规范写法是 "".join(parts)，保证 O(n)。
• in 是子串查找，不是成员查找："el" in "hello" 为 True。
• Python 3 的 str 是 Unicode，len("中文") 是 2；编码转换走 str.encode() / bytes.decode()。

bytes / bytearray

二进制数据用它们。bytes 不可变，bytearray 可变（类比 str 之于 list 的关系）。常见于网络 IO、文件读写、序列化。

range

range(10**9)      # 只占 O(1) 内存——它是"算术序列的描述"，不是真实列表
100000 in range(10**9)   # O(1) 成员测试（数学判断）

range 不可变、支持切片（返回新的 range），是"懒"序列的典范。

时间复杂度速查

操作	list	tuple	dict	set	deque*
按下标访问	O(1)	O(1)	—	—	O(n) 中段
查找 in	O(n)	O(n)	O(1)（键）	O(1)	O(n)
尾部增删	O(1) 摊还	—	—	—	O(1)
头部增删	O(n)	—	—	—	O(1)
中间插入/删除	O(n)	—	—	—	O(n)
增删键/元素	—	—	O(1)	O(1)	—

*deque 来自 collections 包，放在这里对照。

选型决策：怎么挑容器

1. 一组有顺序、要增删的元素 → list
2. 结构固定的一条记录 → tuple；字段多/要可读性 → namedtuple 或 dataclass
3. 键值查找 → dict；需要默认值 → defaultdict；需要计数 → Counter
4. 去重 / 快速成员测试 / 集合运算 → set；要可哈希版本 → frozenset
5. 双端队列（BFS、滑动窗口） → collections.deque
6. 大量同构数值，在意内存和速度 → array.array 或 NumPy
7. 有序且去重 → dict.fromkeys() 的键视图

经验法则：先想清楚你要对这个容器做什么操作（查找？顺序？去重？双端？），答案往往直接指向唯一的类型。性能问题里，“选错容器”（比如用 list 做百万次 in 测试）远比"写得不够聪明"常见得多。

小结

• list 是动态数组：尾部 O(1)，随机访问 O(1)，中间操作 O(n)。
• tuple 不可变、可哈希、语义上是"记录"；注意不可变的只是引用。
• dict 是哈希表：3.7+ 保证插入序，键必须可哈希，查找 O(1)。
• set 是无值 dict：去重和成员测试的首选，frozenset 可哈希。
• 可变性与可哈希性是贯穿始终的主线：可变内置容器（list/dict/set）都不可哈希，不能作键或集合元素。