Python 字典底层是什么结构?为什么查找快,还能保留插入顺序?
下面是模拟面试对话,用来讲解本题,不是真实面经。
🧑💻 面试官:Python 字典为什么查找快?
🙋♂️ 我:它用哈希表,根据 key 找到 value。
🧑💻 面试官:两个 key 算到同一个位置,会覆盖吗?
🙋♂️ 我:还需要继续判断它们是不是同一个键。
🧑💻 面试官:那哈希位置和插入顺序怎么同时保留?更新旧键会把它挪到最后吗?
字典的查找位置和遍历顺序承担不同工作。先理解这两条路径,就不会把插入顺序当成排序。
面试速答(60 秒版)
Python 的 dict 是键值映射。CPython 使用哈希表相关结构,通过键的哈希值缩小查找范围,再结合键的相等关系确认目标。
哈希冲突不表示新数据必须覆盖旧数据。不同键可能产生冲突,实现会继续寻找合适位置,最坏情况下查找也可能变慢。
同时,Python 3.7 起把保持插入顺序作为 dict 的语言保证。它保存的是加入的先后顺序,并没有按键大小自动排序。更新已有键的值通常保留原来的位置,删除后再加入则会进入末尾。
因此,回答时可以把查找和遍历分开讲。平均查找快,和遍历时按插入顺序走,可以通过不同的内部安排同时做到。

知识点详解:查一个键和遍历全部键,走的是不同路径
先看一次键查询需要做什么
假设 settings 保存几个配置项。读取 settings[“timeout”],程序不希望每次都从第一个配置开始逐条找。
哈希值可以帮助它定位候选位置。不过,候选位置里有一个键,不代表它就是 timeout。实现还要确认键是否匹配;遇到冲突,需要按规则继续探查。
在 CPython 3.11 的常见字典布局里,有负责定位的索引区域,也有保存条目的区域。源码还包含共享键等不同形态,下面用普通字典解释主要关系,不把一张简图当成所有布局的完整源码。
冲突为什么不会直接覆盖?
假设两个不同配置名碰到相同的候选位置。字典需要能同时保存它们,所以“算到同一个位置”只是查找过程遇到了冲突。
已有条目的键相等,才会按映射语义更新对应值;键不同,则继续找到可以使用的位置。CPython 使用开放寻址相关的探查方式,这与给每个桶挂一条链表不是同一种实现。
通常说字典查询平均 O(1),隐含了哈希和数据分布等条件。大量冲突、复杂的哈希或比较方法,都可能增加成本。这个结论也没有保证任意自定义键的比较永远便宜。

插入顺序,是另外一件事
对于普通字典,可以把按加入顺序组织的条目和负责查找的索引分开理解。查一个键时利用索引,遍历时按条目顺序前进。
因此,先插入 b,再插入 a,遍历通常仍是 b、a。下面检查更新和删除重加。TS 使用 Map 对照相近的插入顺序行为,Map 的键规则和底层实现仍与 Python dict 不同。
values = {"b": 2, "a": 1}
values["b"] = 3
print(list(values)) # ['b', 'a']
del values["b"]
values["b"] = 4
print(list(values)) # ['a', 'b']const values = new Map<string, number>([["b", 2], ["a", 1]]);
values.set("b", 3);
console.log([...values.keys()]); // ["b", "a"]
values.delete("b");
values.set("b", 4);
console.log([...values.keys()]); // ["a", "b"]如果界面需要按名字排序,仍然要明确排序规则。保持插入顺序不能代替排序,也不能替你保证上游每次按相同顺序构造字典。

扩容和删除会影响哪些工作?
加入的条目多了,索引空间需要调整。扩容要为条目重新组织查找结构,因此某一次插入可能承担比平时更多的工作。
删除以后,查找路径也不能简单被截断,否则后面因为冲突放下的键可能再也找不到。实现会保留必要的删除状态,并在合适时机整理结构;具体阈值与布局要跟着版本源码确认。
这些都解释了为什么字典不能无限增长而没有成本。项目里可以分别测查找耗时、构造耗时和内存占用,不拿一次小字典查询的结果推断大规模表现。
本题不展开可哈希对象的完整条件,那部分已经有单独文章。依据:CPython 3.11 dictobject.c、Python 3.11 dict 顺序规则。

面试官继续追问
已有键重新赋值,会重新占一个顺序位置吗?
普通更新保留这个键的位置。删除以后再添加,是一次新的插入,应区别处理。
dict 有序,可以当作排行榜吗?
只有插入顺序,没有按分数排序的保证。排行榜还要规定比较规则及同分时的处理。
遍历时添加或删除键可以吗?
结构变化可能导致 RuntimeError 或遍历不完整。需要修改结构时,先明确使用快照、收集待删键还是构造新字典。
面试速记卡
- 哈希帮助定位候选,匹配键仍需要确认。
- 冲突不等于覆盖,相等键更新才符合映射语义。
- dict 保持插入顺序,不自动按键排序。
- 旧键更新通常位置不变,删除重加进入末尾。
- 平均 O(1) 有条件,扩容、冲突和比较都可能增加成本。
公司面试真题
真题根据求职者公开面经整理,题意经过概括,非逐字原话或公司官方题库;本文为 Sunday 的独立解析。
字节跳动 · 测试开发(国际化) · 原帖未明确批次
Python 字典的底层怎样实现,哈希冲突怎样寻址?(题意整理)
字节国际化 测开一面 ↗
原帖发布于 2023-09-08字节跳动 · 测试开发 · 原帖未明确批次
Python 字典有什么特点?(题意整理)
字节测开面经 ↗
原帖发布于 2025-09-16