Python字典与集合底层原理：哈希表如何成就O(1)查找

1. 先搞清楚字典和集合为什么快：哈希表才是幕后功臣

做Python开发这些年，我发现很多人天天用字典和集合，但对它们的底层机制其实一知半解。比如面试时问“为什么字典查找是O(1)”，十个里有六七个答不上来，只会说“因为用了哈希”。哈希到底是怎么让数据变快的，这才是关键。

1.1 哈希函数是怎么把键变成索引的

你可以把哈希表想象成一个大型仓库，每个货架都有一个编号。常规的查找方式是从1号货架挨个翻到N号货架，直到找到你要的东西——这就是列表的线性查找，数据多了就慢。而哈希表的做法是，给每个货物一个特制标签，通过这个标签能直接算出它该放在几号货架，根本不用挨个翻。

在Python里，字典底层就是一个哈希表数组，每个位置叫一个槽位（slot）。当你执行 d["name"] = "张三" 时，Python会先对 "name" 这个字符串调用哈希函数，得到一个整数哈希值，然后通过一个位运算（通常是哈希值对数组长度取模）算出它应该落在哪个槽位。下次再查 d["name"]，同样的计算过程再来一遍，直接定位到那个槽位，取出值。整个过程不需要跟其他键做任何比较。

集合也是同一个套路，只不过它只存键不存值，相当于一个“只记录货物是否存在的仓库”。所以判断 x in s 时，计算x的哈希值、定位槽位、看槽位里有没有东西，三步走完就是结果。

这里要特别说一个细节：Python对字符串、整数这类不可变对象，会缓存哈希值。比如一个字符串在生命周期内被哈希过一次，之后每次用到它的哈希值都是直接取缓存，不需要重新计算。这就是为什么你反复用同一个字符串做字典查找时，速度能保持稳定，不会因为字符串变长而明显变慢。

1.2 哈希冲突是怎么处理的：开放寻址法的秘密

哈希函数再优秀，也不可能做到每个键都映射到不同槽位。当两个不同的键计算出同一个槽位时，就产生了哈希冲突。Python的哈希表用的是开放寻址法，冲突发生时不会在这个槽位上拉一条链表，而是按照一个特定的探测序列继续找下一个空槽位。

探测序列的计算规则是：(hash(key) + i * (hash(key) >> 16)) & mask，其中i是探测次数，mask是数组长度减一。这种基于高位异或的扰动算法，能让探测序列更均匀地散布在数组中，避免聚集在一个小区域内反复冲突。

举个例子，假设有两个键都落在了5号槽位，第二个键会尝试计算下一个候选位置，如果下一个位置也被占了，再继续往后找，直到找到空位。查找的时候做同样的事情：定位初始槽位，如果槽位里的键跟目标键相等就直接返回值，如果不相等就沿着探测序列继续找，直到找到匹配的键或者遇到一个空槽位——遇到空槽位说明这个键不存在。

这个设计有一个重要的工程考量：当哈希表越来越满，冲突概率会快速上升，探测序列也会变得更长，性能明显下降。所以Python会在装载因子达到2/3时自动扩容，把数组长度翻倍，然后把所有键重新哈希一遍。这个过程比较昂贵，但能保证后续操作的性能。理解这个扩容机制，你就能解释为什么在往字典里大量插入数据时会有偶发的卡顿——那就是在扩容。

Python从3.6版本开始，字典还做了一个很大的优化：把哈希表分成两部分，一部分是紧凑排列的条目数组，保存键值对的真实数据，另一部分是稀疏索引数组，只保存每个条目在条目数组中的偏移量。这个改动让字典的内存占用减少了约25%，同时保留了键值对的插入顺序。所以你现在遍历字典，元素的顺序就是插入顺序，这在3.6以前是不保证的。

2. 别再做无谓的性能对比：字典、集合、列表的实测差距

聊完原理，咱们把账算清楚。很多人写代码时，遇到“判断元素是否存在”这种需求，随手就写个列表加in判断，完全没意识到这在一开始就埋下了性能隐患。

2.1 成员判断性能的实测对比

我拿一段实际代码来演示。假设有一个包含10万个元素的列表，和一个包含同样数据的集合，都去查找一个已知存在的元素：

python复制import time

data_list = list(range(100_000))
data_set = set(data_list)

target = 99_999

start = time.perf_counter()
for _ in range(10_000):
    _ = target in data_list
list_cost = time.perf_counter() - start

start = time.perf_counter()
for _ in range(10_000):
    _ = target in data_set
set_cost = time.perf_counter() - start

print(f"列表查找10万次: {list_cost:.4f}s")
print(f"集合查找10万次: {set_cost:.4f}s")

在我本机跑的结果大致是：列表查找10万次要6秒多，集合查找10万次只需要0.0008秒，差了接近8000倍。因为列表的in操作在最坏情况下要遍历全部10万个元素才能确认结果，而集合只需要两次哈希计算加上一次探槽操作。

这个差距在数据量变大后会更加恐怖。列表查找的耗时随着数据量线性增长，10万数据是1万的10倍耗时；集合查找的耗时几乎不随数据量变化，因为哈希计算时间跟数据总量无关。这就是为什么写推荐系统、日志去重、流程引擎这类需要频繁做成员判断的业务代码时，用列表写出来的系统数据量一大就慢得没法用。

不过也别把集合和字典神化，它们不是所有场景的答案。如果你需要按顺序遍历数据，或者经常要访问下标对应的元素，列表依然是最佳选择。而且当数据量很小（比如几十个元素）时，列表和集合的性能差几乎可以忽略，选哪个取决于可读性和语义，不需要纠结性能。

2.2 插入与删除操作的实际开销

除了成员判断，插入和删除操作也要考虑。列表在头部插入元素是O(n)，因为后面所有元素都要往后挪；在尾部追加是O(1)均摊。字典和集合的插入、删除都是均摊O(1)，除非触发扩容。

有个场景很典型：日志采集系统里要维护一个“最近见过的主机列表”，每来一条日志就检查一下主机是否已经存在，不在就加进去。如果用列表做，写着写着就变成O(n²)了，数据量一上来直接卡死。用集合，每个操作都是常数时间，再多的日志也能扛住。

还需要注意一个细节：字典删除元素时，Python并不是简单地把槽位清空。如果直接清空，会导致本来存在于此槽位后面的、因冲突被探测到其他位置的键找不到自己家——因为探测链路断了。所以Python会用一个特殊标记“dummy”来占住这个槽位，表示这个位置没有人，但探测链要继续往前走。这意味着删除操作后，哈希表中会有一些“脏”槽位，它们不会被重复使用来插入新键，只有等触发重建哈希时才能被清理干净。

这给了咱们一个实操启发：如果你要反复删除并重新插入大量键，哈希表的空间利用率会下降，性能也受影响。这种情况下，每处理完一批数据，直接新建一个字典或集合，比在旧表里反复增删更高效。

3. 字典几乎是Python世界的“万能胶水”：核心场景实战

原理和性能都聊完了，接下来重点看看字典在实际开发里到底怎么用出花来。说实话，我见过太多的Python代码，字典只用来存配置项，完全没发挥出它的真正实力。

3.1 词频统计与数据分组

最经典的场景肯定是词频统计。很多人第一反应是写if-else判断：

python复制word_count = {}
for word in words:
    if word in word_count:
        word_count[word] += 1
    else:
        word_count[word] = 1

这段代码没问题，但不够优雅。用 defaultdict 可以更简洁：

python复制from collections import defaultdict

word_count = defaultdict(int)
for word in words:
    word_count[word] += 1

defaultdict 的核心思想是：当你访问一个不存在的键时，不会抛出KeyError，而是自动调用传入的工厂函数创建默认值，然后返回它。这样 word_count[word] += 1 第一次执行时就自动把值初始化为0再做加法。

数据分组也是类似的操作。比如要把一批订单按用户ID分组：

python复制orders_by_user = defaultdict(list)
for order in orders:
    orders_by_user[order.user_id].append(order)

这种写法比先判断键是否存在再创建列表要少写三行代码，而且逻辑更清楚。我在实际项目里看过太多“先判断再赋值”的长代码，其实都是因为不认识 defaultdict 和 setdefault 这两个工具。

3.2 用字典建立索引、缓存计数与状态机

字典最常见的进阶用法是建立索引。比如有一批学生数据，要快速通过学号找到学生信息，直接把学号作为键、学生对象作为值，构建一个查找表：

python复制student_index = {s.student_id: s for s in students}

这行代码完成后，查任何一个学号都是O(1)。如果你不建这个索引，每次都在列表里遍历找，用户量一大就等着被投诉吧。

缓存是字典另一个大展身手的地方。比如一个计算斐波那契数列的函数，不加缓存时效率低得吓人：

python复制def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

算 fib(40) 就要好几秒。加一个最简单的缓存字典：

python复制def fib(n, cache={}):
    if n in cache:
        return cache[n]
    if n < 2:
        return n
    result = fib(n-1) + fib(n-2)
    cache[n] = result
    return result

算 fib(1000) 也是眨眼之间。这就是把递归过程中的重复计算结果存下来，每个n只算一次。Python里还有一个 functools.lru_cache 装饰器，原理跟这个一模一样，但带有容量上限，防止缓存无限增长。实际开发中用装饰器更规范，不过理解手写缓存的思路对掌握原理很有帮助。

状态机也是字典常用的领域。比如一个订单系统，订单状态有“待付款”“已付款”“已发货”“已完成”，不同状态对操作有不同响应。用一个字典把状态映射到处理函数：

python复制def handle_pending(order):
    order.pay()

def handle_paid(order):
    order.ship()

state_handlers = {
    "pending": handle_pending,
    "paid": handle_paid,
}

handler = state_handlers.get(order.status)
if handler:
    handler(order)

这种写法比一堆if-elif要清晰得多，新增一个状态只需要添加一个函数和一条映射，不碰其他代码。我在做流程引擎的时候，大量使用这种“状态到行为”的字典映射，可维护性提升非常明显。

3.3 集合在去重和关系运算中的应用手法

集合最大的价值在于去重和关系运算。一开始接触Python的人就知道 list(set(data)) 可以给列表去重，但集合的真正威力在于三个运算：交集、并集、差集。

比如你有两个用户群，A是注册用户，B是当天下过单的用户，想看看有多少注册用户当天没下单：

python复制no_order = registered_users - ordered_users

一行代码，语义还特别清晰。换成循环写法至少得五六行，而且可读性差。

集合还可以用来快速判断两个列表有没有交集：

python复制if set(list_a) & set(list_b):
    # 有共同元素

这段代码在数据量大的时候优势尤其明显。我处理过百万元素的列表求交集，用集合运算几毫秒搞定，写嵌套循环则跑到怀疑人生。

另外要提醒一句：去重时如果要求保持原来元素的顺序，直接用 set() 是不行的，因为集合是无序的。正确做法是先遍历原列表，用一个集合记录已经见过的元素，同时往结果列表里添加新出现的元素：

python复制seen = set()
result = []
for item in items:
    if item not in seen:
        seen.add(item)
        result.append(item)

这既去重又保序，而且整体还是O(n)的时间复杂度。

4. 那些年我们踩过的坑：字典与集合的常见陷阱

再好的工具也有它的坑。踩过的坑分享出来，比讲十遍原理都管用。下面这几个问题我在代码审查里见过无数次，自己早年也犯过。

4.1 可变对象不能做键，以及“同值同哈希”的陷阱

字典的键必须是不可变对象，这个规则很多新手甚至部分老手都会忽视。d = {[1, 2]: "value"} 直接抛出 TypeError: unhashable type: 'list'。原因是列表可变，一旦列表被改了，它的哈希值就会变，存在字典里的键就再也找不到了，这会造成严重的数据错乱。所以Python干脆禁止可变对象做键。

元组可以作为键，但要注意：如果元组里嵌套了列表，比如 (1, [2, 3])，这个元组也是不可哈希的，因为Python的哈希函数会递归检查元组的每个元素。所以实际用元组做键时，要保证元组内部所有元素都是不可变对象。

另一个容易忽略的坑：两个值相等的对象必须有相同的哈希值，否则字典的行为会变得诡异。比如自定义了一个类想作为键，重写了 __eq__ 但忘了重写 __hash__，两个逻辑上相等的对象就会被当成不同的键存进字典。反过来，如果两个对象哈希值碰巧相同但 __eq__ 不相等，那它们会进入同一条探测链，性能下降但至少不会数据错乱。最极端的情况是重写了 __hash__ 但没重写 __eq__，两个对象明明相等却哈希不同，字典里会出现两份“内容相同”的键，排查起来非常痛苦。

如果你自定义类要放进集合或者作为字典的键，我建议用不可变字段计算哈希值，并且同时重写 __eq__ 和 __hash__，保证两者逻辑一致。

4.2 遍历时修改字典与集合引发的运行时错误

这个问题几乎每个Python开发者都遇到过。在遍历字典的过程中删除当前元素，会抛出 RuntimeError: dictionary changed size during iteration：

python复制d = {"a": 1, "b": 2, "c": 3}
for k in d:
    del d[k]  # 运行时错误

原因是Python在迭代字典时会对内部结构做版本检查，发现修改就直接报错，防止出现不可预期的遍历结果。

正确的做法是遍历键的副本：

python复制for k in list(d.keys()):
    if condition(k):
        del d[k]

或者直接构造一个新字典，只保留符合条件的键：

python复制d = {k: v for k, v in d.items() if condition(k)}

第二种方式更Pythonic，也更容易理解。集合遇到同样问题时，也是先转成列表再遍历，或者推导式直接过滤。

还有一个相关但更隐蔽的坑：在遍历字典时如果只是修改值而不改变键的数量，是允许的。比如 for k in d: d[k] += 1 没问题。这经常让初学者误以为“遍历时可以随意改动”，直到某个操作新增或删除了键才爆雷。

4.3 特殊键值导致的直觉偏差

None 和布尔值都可以作为字典的键，但有时候会出现“你想查空值，查到了不存在”的错觉。比如：

python复制d = {}
if d.get("key"):
    # 假设这里的key值存的是0或空列表，条件为False

get 方法在键不存在时返回 None，但如果键存在且值为0、空字符串、空列表、False，判断结果也是False。所以用 get + 布尔判断来检查键是否存在是不可靠的。正确的判断方式是：

python复制if "key" in d:
    # 键确实存在，不管值是什么

或者用 d.get("key") is not None，前提是你确认字典里不会存值为None的键。

另外要提防数字和布尔值的哈希冲突问题。1 和 True 在Python中哈希值相同且相等，所以 d = {1: "one"} 之后，再执行 d[True] 会得到 "one"。同理 0 和 False 也会互相踩脚。如果业务需求里既有布尔键又有数字键，建议统一转成字符串或使用元组区分，避免干扰。

4.4 合并字典时的优先级与覆盖问题

Python 3.9 提供了 | 运算符合并字典，简洁好用，但有个细节要注意：两个字典合并时，右边的字典会覆盖左边同名的键。

python复制d1 = {"a": 1, "b": 2}
d2 = {"b": 3, "c": 4}
merged = d1 | d2
# 结果是 {"a": 1, "b": 3, "c": 4}

这跟预期通常一致，但如果你合并大量配置时没注意优先级，很容易出现默认配置被覆盖的情况。比如需求是“用户配置覆盖默认配置”，正确写法就是 default_config | user_config，用户配置放右边。反过来如果你写成 user_config | default_config，那默认配置会把用户的设置覆盖掉，线上就会出问题。

update 方法的效果和 | 类似，区别是它直接在原字典上修改。如果两者的行为都不满足需求，比如合并时希望保留旧值而不是用新值覆盖，可以用 {**d2, **d1} 这种技巧，右边的字典优先级更高。

5. 利用字典与集合的隐含能力：解决真实业务问题

网上讲数据结构的文章很多，但很少告诉你它们能怎么解决真实世界的业务问题。我挑两个我在实际项目里用过的场景，说说思路。

5.1 用集合高效完成多源数据比对

有一次我需要处理一个对账系统，业务方给了两个数据源，一个是内部系统的账单明细，一个是外部渠道的交易记录，需要找出“在外部有记录但内部没有”的差异数据。数据量大概是百万级别。

如果先想到的是循环遍历，那完蛋了，外层一百万、内层一百万的嵌套循环，测试机跑到天荒地老也出不了结果。正确做法是先把内部系统的主键抽出来构建成集合：

python复制internal_keys = {bill.order_id for bill in internal_bills}
external_keys = {tx.order_id for tx in external_txns}

missing_internal = external_keys - internal_keys

两个集合构建的时间是O(n)，差集运算也是O(n)，总体上百万级数据几秒就处理完了，而且代码只有三行。这个方案的优势不仅在于快，更在于语义清晰——任何维护这段代码的人一眼就能看出“我们要找的是外部有、内部没有的订单”。

如果后续需要对 missing_internal 里的每个订单去外部数据源里查具体信息，可以先把外部数据也构建成字典索引：

python复制external_by_order = {tx.order_id: tx for tx in external_txns}
for order_id in missing_internal:
    tx = external_by_order[order_id]

这就是典型的“以空间换时间”策略：用一份字典索引，把后续的查询全部降到O(1)。

5.2 用字典构建双向索引与邻接结构

在推荐系统或者好友关系的场景里，经常需要根据ID找名字，也要根据名字找ID。可以构建双向索引：

python复制id_to_name = {1: "张三", 2: "李四"}
name_to_id = {v: k for k, v in id_to_name.items()}

注意反向索引有一前提：所有值必须是唯一的，否则会丢数据。如果值可能重复，反向索引的构建逻辑就得改成列表值的defaultdict。

再比如处理图结构，用字典表示邻接表是最自然的方式：

python复制graph = {
    "A": {"B", "C"},
    "B": {"A", "D"},
    "C": {"A", "D"},
    "D": {"B", "C"},
}

键是节点，值是一个集合，表示这个节点的所有邻居。集合天生适合去重，用在邻接表里不会出现重复的边。做深度优先遍历或广度优先遍历时，判断一个节点是否访问过，直接用一个 visited = set()，每访问一个节点就 visited.add(node)，判断就用 if node not in visited。整个traversal过程写出来非常干净，而且性能极佳。

6. 最后说点实操体会

做Python开发这些年，我对字典和集合的态度经历了一个变化：一开始觉得它们只是“存数据的容器”，后来理解了哈希表原理后，开始意识到它们是Python最值得深入理解的基础设施之一。

在实际编码里，我现在的习惯是：凡是涉及查找、去重、分组、计数、缓存这类需求，默认先考虑用字典或集合，而不是列表。只有当需要有序访问、按下标操作、或者数据量极小的时候才回到列表。这个习惯让我写的代码在数据量增长时不容易出现性能雪崩。

还有一个小技巧值得分享：调试的时候，给字典设置别名或者打印 list(d.items())[:5] 看前几项，能省不少事。items() 返回的视图对象不会额外复制数据，比 list(d.items()) 在非调试场景下内存开销小。

字典和集合学起来门槛不高，但想用好、用对，需要理解底层原理，也需要在实际业务里多试。建议你把手头代码里所有用列表实现的成员判断场景都过一遍，改成集合试试，跑一下性能对比，你会对今天讲的内容有更深刻的体感。