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

引言

在日常 Python 开发中，字典（Dict）和集合（Set）的出场率极高，是使用最频繁的数据结构之一。

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

字典和集合的核心优势开发者普遍熟悉：按 key 或元素查询，速度极快。

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 可变/不可变对象核心区别对照表

特性	不可变对象（Immutable）	可变对象（Mutable）
内存数据	创建后不可修改	可直接原地修改
哈希值	固定、稳定、可哈希	动态变化、不可哈希
能否作为 Dict Key	可以	不可以
能否作为 Set 元素	可以	不可以
常见类型	int、str、float、bool、tuple	list、dict、set

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) 的查询、插入和删除效率。