兰 亭 墨 苑

期货 · 量化 · AI · 终身学习

彻底讲明白 Python `set` 的实现原理

2025年9月9日
22 分钟阅读
#202509

彻底讲明白 Python set 的实现原理

IMG_1184

我们将从其为何存在，到其核心数据结构——哈希表，再深入到 CPython 源码层面的实现细节，包括冲突解决、动态扩容和删除操作的精妙之处，力求让您对这个看似简单的类型有一个全面而深刻的理解。

引言：Set 为何存在？—— 从 O(n) 到 O(1) 的飞跃

在探讨 set 的实现原理之前，我们必须先理解它被创造出来的目的。想象一个常见的编程任务：检查一个元素是否存在于一个集合中。如果我们使用列表（list）来存储这个集合，代码会是这样：

  
my_list = [1, 2, 3, ..., 1000000]
  

  
# 检查 999999 是否存在
  
if 999999 in my_list:
  
    print("找到了！")

in my_list 这个操作在最坏的情况下，需要从列表的第一个元素开始，逐一比较，直到最后一个元素。如果列表有 n 个元素，这个操作的时间复杂度就是 O(n)。当列表非常大时，这个查找过程会变得无法忍受的缓慢。

而 set 的出现，就是为了将这个过程的时间复杂度奇迹般地降低到 O(1) —— 也就是“常数时间”。这意味着，无论一个 set 包含10个元素还是1000万个元素，检查一个元素是否存在所需的时间，平均而言，是基本相同的、极其短暂的。

set 牺牲了元素的顺序性（set 是无序的），换来了这种极致的查找、添加和删除性能。而实现这一魔法的背后功臣，就是计算机科学中最重要的数据结构之一：哈希表（Hash Table），有时也称为哈希映射（Hash Map）或字典（Dictionary）。Python 的 dict 类型和 set 类型，是同一技术的一体两面。

可以把 set 想象成一个拥有神奇管理员的会员俱乐部：

  • 添加会员 (add): 你报上名字，管理员瞬间就能帮你办好入会手续，并给你一个独一无二的储物柜。

  • 查询会员 (in): 你问管理员“张三在吗？”，他不用翻看厚厚的花名册，而是看一眼某个特定的地方，立刻就能告诉你“在”或“不在”。

  • 注销会员 (remove): 你要退会，管理员瞬间找到你的储物柜，清空并标记为“可用”。

这个“神奇管理员”的工作方式，就是哈希表的原理。

第一部分：核心基石 —— 哈希表（Hash Table）的工作原理

要理解 set，就必须先理解哈希表。哈希表主要由两个核心部分组成：

  1. 一个底层的数组（Array）：这是一块连续的内存空间，像一排编号的储物柜，我们称之为“槽位”（Slots）或“桶”（Buckets）。

  2. 一个哈希函数（Hash Function）：这是一个数学函数，负责将任意的输入数据（比如数字、字符串）转换成一个固定长度的整数，这个整数我们称为“哈希值”（Hash Value）。

哈希函数的核心特性：

  • 确定性 (Deterministic): 对同一个输入，哈希函数的输出永远是相同的。hash("apple") 无论计算多少次，结果都一样。

  • 高效性 (Efficient): 哈希函数的计算速度必须非常快。

  • 均匀性 (Uniform Distribution): 一个好的哈希函数，应该能将不同的输入尽可能均匀地散布到不同的哈希值上，以减少“哈希冲突”。

哈希表的工作流程（以添加元素为例）：

假设我们要将元素 "apple" 添加到一个 set 中。

  1. 计算哈希值：

    首先，调用 Python 内置的 hash() 函数计算 "apple" 的哈希值。

    hash_value = hash("apple") (假设结果是一个很大的整数，比如 543219876)

  2. 定位槽位索引：

    接下来，需要将这个巨大的哈希值映射到底层数组的某个索引上。通常使用取模运算（%）。但为了效率，Python 采用位运算。如果底层数组的大小是 size（通常是2的n次方，比如8, 16, 32...），那么索引可以通过 index = hash_value & (size - 1) 来计算。这等价于取模运算，但速度更快。

    假设数组大小为8，size - 1 就是 7（二进制 111）。

    index = 543219876 & 7 (结果会是 0 到 7 之间的一个数，比如 4)

  3. 存放元素：

    计算出的索引 4，就是 "apple" 在底层数组中应该存放的位置。于是，程序将 "apple" 存放到数组的第4个槽位。

查找操作 (in) 也是完全相同的逻辑：计算哈希值 -> 定位索引 -> 查看该槽位是否存放着目标元素。因为这个过程不涉及循环遍历，所以速度极快，这就是 O(1) 的来源。

第二部分：关键难题与解决方案 —— 哈希冲突（Hash Collision）

理想很丰满，但现实是，不同的输入有可能产生相同的哈希值（鸽巢原理），或者不同的哈希值通过取模运算后得到了相同的索引。这就叫哈希冲突。

例如，hash("apple") 和 hash("banana") 经过 & (size - 1) 计算后，可能都得到了索引 4。这时 "banana" 也想存放到第4个槽位，但那里已经被 "apple" 占了，怎么办？

解决哈希冲突主要有两种策略：

  1. 链式法 (Chaining): 在每个槽位上，不直接存放元素，而是存放一个链表。所有映射到这个索引的元素，都依次添加到这个链表中。查找时，先定位到索引，再遍历这个（通常很短的）链表。

  2. 开放寻址法 (Open Addressing): 这是 Python set 和 dict 采用的策略。其核心思想是：如果计算出的槽位已被占用，就按照一个预定的规则，去“探查”（Probe）下一个可用的槽位，直到找到一个空位为止。

开放寻址法的探查策略：

  • 线性探查 (Linear Probing): 如果索引 i 被占用，就尝试 i+1, i+2, i+3... 这种方法简单，但容易导致元素“聚集”（Clustering），形成一长串连续的已占用槽位，降低后续查找效率。

  • 二次探查 (Quadratic Probing): 如果索引 i 被占用，就尝试 i+1², i+2², i+3²...

  • 伪随机探查 (Pseudo-random Probing): 这是 Python 采用的更复杂的策略。它通过一个扰动函数，对哈希值进行一系列变换，生成一个看似随机但对于同一个哈希值又是确定的探查序列。这能非常有效地避免聚集问题，让元素散布得更均匀。

我们用一个简化的例子来模拟 Python 的开放寻址过程：

假设数组大小为8，我们要依次添加 A(hash=10), B(hash=18), C(hash=2)。

  • add(A): hash(A)=10, index = 10 & 7 = 2。槽位2为空，放入A。table = [_, _, A, _, _, _, _, _]

  • add(B): hash(B)=18, index = 18 & 7 = 2。冲突发生！ 槽位2已被A占用。启动探查机制，假设下一个探查位置是3。槽位3为空，放入B。table = [_, _, A, B, _, _, _, _]

  • add(C): hash(C)=2, index = 2 & 7 = 2。冲突发生！ 槽位2被A占用。探查下一个位置3，被B占用。再探查下一个位置4，为空。放入C。table = [_, _, A, B, C, _, _, _]

查找 C 的过程，就是这个过程的逆向：计算哈希得到索引2，发现不是C；探查到3，发现也不是C；再探查到4，找到了C，返回 True。如果在探查过程中遇到了一个从未被使用过的空槽位，就说明目标元素肯定不存在，查找结束，返回 False。

第三部分：深入 CPython 源码 —— setobject 的内部构造

现在，我们深入到 Python 解释器（CPython）的 C 源码层面，看看 set 究竟是如何被定义的。一个 set 对象在 C 语言中对应一个 PySetObject 结构体，其简化后的核心成员如下：

  
typedef struct {
  
    PyObject_HEAD // Python对象通用的头部信息
  

  
    Py_ssize_t fill;      // 已被占用的槽位数（包括活跃和假删除的）
  
    Py_ssize_t used;      // 活跃的元素数（set的实际大小, len(s)）
  

  
    Py_ssize_t mask;      // 等于 table_size - 1，用于快速计算索引
  
    setentry *table;      // 指向底层数组的指针
  
    setentry *smalltable; // 初始时使用的一个小数组，避免频繁内存分配
  
    Py_ssize_t hash;      // 缓存的哈希值（用于不可变set，即frozenset）
  
} PySetObject;

底层的 table 数组，是由一个个 setentry 结构体组成的。setentry 的定义更关键：

  
typedef struct {
  
    PyObject *key;      // 指向存储的Python对象的指针
  
    Py_ssize_t hash;    // 缓存该key的哈希值
  
} setentry;

这里的 setentry 揭示了两个重要细节：

  1. 缓存哈希值： 除了存放对象本身 (key)，每个槽位还缓存了它的哈希值。为什么？因为在探查过程中，当遇到一个已占用的槽位时，程序可以先比较缓存的哈希值。如果哈希值都不同，那就没必要进行昂贵的 PyObject_RichCompareBool（相当于 Python 的 ==）操作了，可以直接继续探查。这是一种重要的性能优化。

  2. 槽位的三个状态： 源码通过 key 指针的值来区分槽位的三个状态，这对于正确实现删除操作至关重要。

    • key == NULL: 未使用 (UNUSED)。这个槽位是“处女地”，从未被占用过。探查链到此为止。

    • key == dummy: 假删除 (DUMMY)。dummy 是一个特殊的全局单例对象。这个槽位曾经存放过一个元素，但后来被删除了。

    • key 指向一个真实的 Python 对象: 活跃 (ACTIVE)。这个槽位存放着一个有效元素。

为什么需要 DUMMY 状态？

回到之前的例子 table = [_, _, A, B, C, _, _, _]。如果我们现在 remove(B)，会发生什么？

如果只是简单地将槽位3置为 NULL (UNUSED)，table 变成 [_, _, A, NULL, C, _, _, _]。

之后我们再查找 C：hash(C) 定位到索引2，是A；探查到索引3，发现是 NULL (UNUSED)。根据规则，遇到 UNUSED 槽位就意味着查找结束，元素不存在。于是程序会错误地返回 False！

为了维护探查链的完整性，remove(B) 操作不能将槽位3设为 NULL，而是要设为 DUMMY。table 变为 [_, _, A, DUMMY, C, _, _, _]。

当再次查找 C 时，探查到索引3，发现是 DUMMY 状态，程序知道“这里曾经有人住过，探查链可能还没断”，于是会继续往下探查，最终在索引4找到C。

第四部分：动态生命周期 —— 扩容与收缩

哈希表的性能严重依赖于负载因子 (Load Factor)，即 负载因子 = 已占用槽位数 / 总槽位数。当负载因子过高时，哈希冲突的概率会急剧增加，探查链会变长，O(1) 的性能会退化到 O(n)。

为了避免这种情况，Python 的 set 实现了动态扩容机制。

扩容 (Growth):

  • 触发时机： 当 fill（活跃+假删除的槽位总数）达到 table_size 的 2/3 时，就会触发扩容。

  • 扩容过程：

    1. 创建一个新的、更大的数组。大小通常是当前 used（活跃元素数）的2倍或4倍，并调整为最接近的2的n次方。

    2. 遍历旧表中的所有活跃 (ACTIVE) 元素。

    3. 对于每一个元素，重新计算其在新表中的索引（因为 mask 变了），然后将其插入到新表中。这个过程也解决了新表中的哈希冲突。

    4. 释放旧表的内存，set 对象内部的 table 指针指向新表。

收缩 (Shrinking):

  • 触发时机： 当 used（活跃元素数）变得非常少时，为了节省内存，set 也会收缩。大量的 DUMMY 状态是触发收缩的主要原因。

  • 过程： 与扩容类似，创建一个更小的表，并将所有活跃元素重新哈希进去。这不仅节省了空间，还能清除掉所有的 DUMMY 标记，提高后续操作的效率。

第五部分：性能总结与对比

| 操作 | set 平均时间复杂度 | set 最坏时间复杂度 | list 时间复杂度 | 备注 |

| :--- | :--- | :--- | :--- | :--- |

| x in s (成员检查) | O(1) | O(n) | O(n) | set 的核心优势 |

| s.add(x) (添加) | O(1) | O(n) | O(1) (append) | set 添加也很快，最坏情况发生在触发扩容时 |

| s.remove(x) (删除) | O(1) | O(n) | O(n) | set 删除需要先查找，所以也很快 |

| len(s) (获取长度) | O(1) | O(1) | O(1) | used 成员直接记录了长度 |

| 迭代 | O(n) | O(n) | O(n) | 都需要遍历所有元素 |

最坏情况 O(n) 何时发生？

当所有的元素都产生哈希冲突，导致探查链串起了所有n个元素时，哈希表就退化成了一个链表。这在理论上是可能的，但在实践中，由于 Python 优秀的哈希函数和扰动机制，这种情况极其罕见。

结论：优雅之下的精密工程

Python set 的优雅和简洁，是建立在一个极其精密和高效的工程实现之上的。它不是一个简单的无序集合，而是一个基于开放寻址法和伪随机探查的动态哈希表。

其核心实现要点可以总结为：

  1. 哈希函数 + 位运算 实现快速的索引定位。

  2. 开放寻址法 作为冲突解决方案，避免了链表的额外开销。

  3. 缓存哈希值 在探查时进行快速预比较，提升性能。

  4. UNUSED, ACTIVE, DUMMY 三种槽位状态 的精妙设计，确保了删除操作不会破坏探查链的完整性。

  5. 基于负载因子的动态扩容与收缩机制，在空间和时间效率之间取得了绝佳的平衡。

当我们轻松地写下 if user_id in banned_set: 时，我们实际上正在驱动这台设计精良、高度优化的“计算引擎”。理解其内部原理，不仅能帮助我们写出更高效的代码，更能让我们体会到，看似简单的语言特性背后，蕴含着计算机科学数十年发展的智慧结晶。