Python Dict 和 Set 底层原理：从哈希函数到哈希表全方位解析

引言

在日常 Python 开发中，字典（Dict）和集合（Set）的出场率极高，可以说是最常见的那类数据结构。

# 字典：键值对存储
user = {
    "name": "Tom",
    "age": 18
}# 集合：无序元素存储
nums = {1, 2, 3}

它们的核心优势大家都很熟悉：按键或元素查询，速度极快。

user["name"]   # 字典按键取值
1 in nums      # 集合元素判断

不过，多数开发者可能只停留在“会用”的层面，对其底层机制却知之甚少。心里头难免会冒出几个问号：

• 凭什么字典查个值、取个值，速度就能把列表远远甩开？
• 集合怎么就能自动把重复元素剔除掉？
• 为什么字典的键不能是列表、字典这种可变对象？
• 哈希到底是何方神圣？它和字典、集合又有什么勾连？

其实，Python 里字典和集合的底层逻辑是同一套，所有特性都扎根在一个核心结构上：哈希表（Hash Table）。

完整的底层逻辑链路是这样，下面会顺着这条线一步步拆解，帮你建立起完整的知识图景：

Dict
 ↓
Hash Table（哈希表）
 ↓
Hash Function（哈希函数）
 ↓
Hash Collision（哈希冲突）
 ↓
Mutable / Immutable（可变与不可变对象）
 ↓
Set 的实现原理

一、什么是哈希（Hash）？

哈希的本质是一套不可逆的映射算法，可以把任意长度、任意类型的数据，转换成一个固定长度的唯一数字。这个数字，就叫哈希值（Hash Value）。

Python 里直接用内置的 hash() 函数就能算出来：

print(hash("Tom"))

输出大致像这样（不同环境结果略有差异）：

876543210

哈希转换的完整流程：

"Tom"
   ↓
Hash Function
   ↓
876543210

不妨把哈希值理解成数据的唯一身份证号，不同的合法数据都会对应一个专属的哈希标识：

Tom    → 1001
Jerry  → 1002
Alice  → 1003

有了这串专属编号，程序就能直接定位数据，省去了一个接一个地比对。

二、为什么需要哈希？核心优势：极致高效

要理解哈希的价值，最好的参照物就是列表（List）。

假设用列表存一组用户名，然后判断某个元素是否存在：

users = ["Tom", "Jerry", "Alice"]
print("Tom" in users)

列表的查询方式，就是遍历比对：程序从第一个元素开始，逐个匹配，直到找到目标或者把所有元素都翻个底朝天。

这种查询的时间复杂度是 O(n)，数据量一大，耗时也就跟着上去了，效率自然就下来了。

基于哈希的查询，逻辑则完全不同：

Tom
 ↓
Hash
 ↓
1001
 ↓
直接定位

全程不需要遍历，直接精确寻址，时间复杂度稳定在 O(1)。

这，就是 Dict、Set 在增删查方面碾压列表的根本原因。

三、什么是哈希表（Hash Table）？底层存储载体

哈希函数只管“计算编号”，不负责存储数据。真正承载数据、实现高效读写的结构，是哈希表。

哈希表的核心，可以概括为：数组 + 哈希函数。它利用数组的连续存储空间，再配合哈希算法，实现了快速寻址。

可以把哈希表想象成一个带有序号、预留了许多空槽位的数组：

index
0 
1
2
3
4
5
6
7

数据存进哈希表的流程：

1. 对数据 Tom 计算哈希值，得到一个数字；
2. 通过取模运算，把哈希值转换成哈希表的下标（比如下标3）；
3. 把数据存到下标为3的那个槽位里。

存储之后的结构：

index
0
1
2
3 → Tom
4
5
6
7

查询数据的时候，重复一遍“计算哈希值 → 定位下标 → 读取槽位数据”的流程就行，完全没有遍历的必要，效率自然高。

四、Dict 字典的底层实现原理

Python 字典本质上是一个键值对（Key-Value）哈希表，底层完全建立在哈希表之上。所有按键取值、赋值操作，都是靠哈希寻址来完成，稳定保持着 O(1) 级别的读写效率。

以用户信息字典为例：

user = {
    "name": "Tom",
    "age": 18
}

字典底层的存储单元，其实不是单纯的键值对，而是一组“哈希值+Key+Value”的三元结构。简化一下看看：

[    (1234, "name", "Tom"),    (5678, "age", 18)]

当执行 user["name"] 取值时，底层会严格走五步：

步骤1：计算键的哈希值

调用哈希函数，算 Key 的哈希值：hash("name") = 1234

步骤2：计算存储下标

用哈希值对哈希表总长度取模，得到数据对应的槽位下标：1234 % 表长度 = 目标下标

步骤3：定位存储槽位

根据算出来的下标，直接锁定哈希表里对应的槽位。

步骤4：校验 Key 一致性

对比槽位里存的 Key 和查询的 Key 是不是完全一致。这一步是为了避开哈希冲突带来的误差。

步骤5：返回目标 Value

校验通过，直接取出对应的 Value，查询结束。

整个过程没有任何遍历操作，这就是字典查询能这么快的原因。

五、哈希表的核心难题：哈希冲突

哈希算法有一个无法完全避免的问题：哈希冲突（Hash Collision）。

简单讲就是：不同的数据，经过哈希计算后，得到了相同的哈希下标。

举个例子：

Tom
 ↓
Hash
 ↓
3

Jerry
 ↓
Hash
 ↓
3

两个不同的数据，都想进同一个槽位，冲突就来了。不解决的话，数据就会覆盖、丢失。

六、Python 解决哈希冲突的方案：开放寻址法

Python 对 Dict、Set 的哈希冲突，统一采用 开放寻址法（Open Addressing）。核心逻辑就是“撞上了，就往后找个空位”。

具体流程：

1. 数据 Tom 先占了下标3的槽位；
2. 数据 Jerry 算下来也是下标3，触发冲突；
3. 程序自动往后找下一个下标4，看看槽位是不是空的；
4. 如果下标4空着，就把 Jerry 存进去；要是也被占了，就继续往下找5、6……直到找到空位子。

冲突解决后的最终存储结构：

0
1
2
3 → Tom
4 → Jerry
5
6
7

通过这种办法，Python 就避免了哈希冲突可能带来的数据异常，保证了哈希表里数据的完整性。

七、核心面试考点：为什么 Dict 的 Key 必须是不可变对象？

这是个 Python 高频面试题，答案核心就一句话：保证哈希值的稳定性。

要彻底弄明白“为什么 Dict 的 Key、Set 的元素必须不可变”，得先搞清楚 Python 里可变对象（Mutable） 和不可变对象（Immutable） 的本质区别。这是哈希表存储规则的前提。

7.1 什么是不可变对象？

不可变对象：对象创建完成后，内存里的数据内容就不能再改了。要是对变量重新赋值或修改，并不会改动原来内存里的数据，而是会新开一块内存，生成一个全新的对象。

Python 里典型的不可变对象：int、float、bool、str、tuple

核心特性：哈希值永久固定

因为内容改不了，算出来的哈希值也就永远不会变。这个稳定的哈希特性，正是它能当 Dict Key、Set 元素的原因。

拿字符串（不可变对象）演示一下：

a = "Tom"
print(hash(a))# 重新赋值，不是修改原对象，而是生成新对象
a = "Jerry"
print(hash(a))

原始字符串 "Tom" 的哈希值始终是固定的，不会被任何操作改动。

7.2 什么是可变对象？

可变对象：对象创建之后，可以直接修改内存里的原始数据，不用新开内存，对象本身还是同一个。

Python 里典型的可变对象：list、dict、set

核心特性：哈希值不稳定、不可哈希

内容随时能变，哈希值也跟着变，所以不支持哈希运算，属于 unhashable 类型。

拿列表（可变对象）演示一下：

lst = [1, 2, 3]
# 直接修改原内存数据
lst.append(4)
# 列表内容改变，哈希值会发生变化
print(hash(lst))  # 直接报错

报错的原因：可变对象动态变化，Python 不允许对它算哈希值。

7.3 可变/不可变对象核心区别对照表

7.4 为什么哈希结构拒绝可变对象？

结合前面的哈希表原理，这个知识点就能彻底闭合了：

Dict 和 Set 的所有存储、查询、去重逻辑，全部依赖哈希值来定位槽位。

如果拿可变对象当作 Key / 元素，就会出现致命 bug：

1. 存数据的时候：根据“对象旧内容”算哈希值，存到对应的哈希槽位；
2. 后面修改对象内容：可变对象的哈希值也跟着变了；
3. 再查询的时候：根据“对象新哈希值”去找槽位，找不到原来存的数据；
4. 结果就是：数据明明在，但查不到，哈希表的结构彻底乱套了。

这就是 Python 那条强制规则的根源：只有哈希值永久稳定的不可变对象，才能参与哈希表存储。

要是硬把可变对象当字典 Key，会直接抛类型错误：

# 非法用法
d = {[1, 2]: "hello"}

报错信息：

TypeError: unhashable type: 'list'

所以，只有哈希值固定的不可变对象，才能当 Dict 的 Key、Set 的元素。

八、Set 集合的核心特性与去重原理

Set（集合）是 Python 里无序、无重复的哈希结构。核心特性：元素唯一、无序存储、查询速度快。

最直观的特性就是自动去重：

nums = {1, 2, 3, 3, 3}
print(nums)  # 输出：{1, 2, 3}

Set 自动去重的核心原理，依然依托哈希表：

1. 第一次插入元素 1：算哈希值、定位到空槽位，存进去；
2. 再插入重复元素 1：算出来哈希值完全一样，定位到同一个槽位；
3. 程序查验发现槽位里已经有相同元素了，就直接忽略这次插入。这样一来，去重的效果就实现了。

九、Set 的底层实现：与 Dict 同源复用

很多人以为 Set 是独立的数据结构，其实不是。Set 和 Dict 底层共用同一套哈希表逻辑，只是存储形式不一样。

二者核心区别：

• Dict（字典） ：哈希表里存 Key + Value 键值对；
• Set（集合） ：哈希表里只存 Key，没有 Value 的概念。

可以通俗地理解：Set 就是所有 Value 统一为 None 的字典。

{1, 2, 3} 底层等价于：

{1: None, 2: None, 3: None}

精简一下：

• Dict = 存 Key+Value 的哈希表
• Set = 只存 Key 的哈希表

Dict = HashTable(Key + Value)Set = HashTable(Key)

十、Dict 与 Set 完整关联关系

二者同源同底层，依托同一套哈希体系实现所有功能，关联关系如下：

哈希函数 → 生成哈希值 → 驱动哈希表运行

哈希表又衍生出两大结构：

• Dict（字典） ：存 Key+Value，支持 O(1) 的增删查改，适合键值对数据存储；
• Set（集合） ：只存 Key，支持 O(1) 的增删查，适合去重、成员判断、集合运算。

                Hash Function
                       │
                       ▼
                Hash Table
                 /      
                /        
               ▼          ▼           Dict          Set        Key+Value       Key        O(1)查询       O(1)查询
        O(1)插入       O(1)插入
        O(1)删除       O(1)删除

全文总结

Dict 和 Set 的所有特性，都不是什么“语法魔法”，所有的一切都源于哈希表的底层设计。完整的逻辑链路闭环：

数据
 ↓
Hash Function
 ↓
Hash Value
 ↓
Hash Table
 ↓
Dict / Set

其中：

• Hash 负责把数据映射成数字。
• Hash Table 负责根据哈希值快速存、取数据。
• Dict 与 Set：底层同源，区别只在于存不存 Value。Set 本质就是无值的字典。
• 哈希冲突：不同数据的哈希下标撞车了，Python 用开放寻址法来解决。
• 不可变对象 因为哈希值稳定，可以当 Dict Key 和 Set 元素。
• 可变对象 因为哈希值会变，所以不能参与哈希表存储。

正因为有这套机制，Python 的 Dict 和 Set 才能实现接近 O(1) 的查询、插入和删除效率。