为什么Python的set集合是无序的，从源码看其哈希表实现是怎样的

访客源码剖析 2026-06-05 04:44:39 1

本文目录导读：

核心数据结构：PySetObject
setentry 结构体：哈希表的行
核心操作：插入一个元素（set_add_key 的核心逻辑）
为什么“无序”？
举个例子：

这是一个非常深入且具有技术含量的好问题，理解 set 的无序性,确实需要深入到其底层的哈希表实现。

直接回答你的核心问题：Python 的 set 之所以“无序”，是因为它底层的哈希表在存储元素时，元素的位置是由其哈希值通过特定的算法（通常是取模运算）计算出来的，而不是由插入顺序决定的。这个位置可能会因为哈希表的扩容、哈希冲突等因素而发生动态变化。

下面，我们从源码（CPython，Python 官方实现）的角度,详细拆解其哈希表实现。

核心数据结构：`PySetObject`

在 CPython 的源码（Objects/setobject.c 和 Include/setobject.h）中，set 的核心数据结构被抽象为 PySetObject，它本质上是一个非常瘦的、针对集合操作（如并、交、差）优化的字典（dict）变体，因为集合只关心键（key）是否存在，不关心值（value）,所以源码中直接复用了字典的许多底层机制。

它的关键字段如下：

// 简化后的版本，去除了宏和复杂性
typedef struct {
    PyObject_HEAD // Python对象头部，包含引用计数和类型信息
    Py_ssize_t fill;            // 已使用的槽位总数（包括活跃的和被占用的虚包位）
    Py_ssize_t used;            // 活跃的（非空，非虚包位）元素数量
    Py_ssize_t mask;
    // 指向底层哈希表数组的指针
    setentry *table;
    // ... 其他字段，如 weakreflist, hash 等
} PySetObject;

最关键的是 table 字段，它是一个 setentry 数组,这就是哈希表的主体。

`setentry` 结构体：哈希表的行

setentry 定义了哈希表中的一行（或一个槽位）：

typedef struct {
    PyObject *key;    // 存储的键（集合元素）
    Py_hash_t hash;   // 缓存该键的哈希值，避免重复计算
} setentry;

key：指向实际的 Python 对象，如果为 NULL,表示该槽位为空。
hash：由 PyObject_Hash() 计算并缓存的结果。None 等对象的哈希值可能是 -1,但源码会特殊处理。

核心操作：插入一个元素（`set_add_key` 的核心逻辑）

当你执行 s.add(5) 时,内部流程大致如下：

计算哈希值：调用 PyObject_Hash(5)，对于整数 5，其哈希值就是 5 本身。
计算初始索引：一旦有了哈希值 hash，就需要计算它在 table 数组中的位置，核心公式是：index = hash & mask。
- mask 是哈希表长度（table_size）减 1，如果表长度为 8，mask 7（二进制 111）。
- 这个 & 位运算等价于 hash % table_size（仅当 table_size 是 2 的幂次时成立），由于 CPython 的哈希表大小始终是 2 的幂次（如 8, 16, 32, ...），& mask 就等同于取模运算。
检查冲突并查找：
- 检查 table[index] 是否为空。
- 如果为空：直接放入 key 和 hash，used 计数加 1,插入成功。
- 如果不为空（发生了哈希冲突）：
  - 首先检查 table[index].key 是否与当前要插入的键相等（使用和 is 进行身份和值比较）。
  - 如果相等，说明是重复元素,直接忽略。
  - 如果不相等，说明是真正的冲突，CPython 使用开放寻址法来解决冲突，它会使用一个二次探测序列（j = (5 * j + 1) mod 2^i，j 是当前索引的偏移量）来寻找下一个空闲槽位。
  - 这个过程会一直持续,直到找到一个空槽位或一个相等的键。
扩容：如果插入后，fill 和 used 的比例超过一个阈值（通常是 fill / len(table) > 2/3），哈希表会进行扩容，扩容会创建一个新的、大小约为原表 4 倍的新数组，然后遍历旧表，将所有元素重新计算 hash & new_mask 并放入新表,这会导致所有元素的索引位置发生剧变。

为什么“无序”？

无序的原因变得非常清晰了：

索引由哈希值决定：元素在 table 中的位置不是 s.add(1), s.add(2), s.add(3) 的插入顺序，它是由 hash(1) & mask，hash(2) & mask 等计算出的，这些计算出的索引在内存中通常是跳跃式的,不连续的。
扩容导致重排：当哈希表扩容时，mask 变了，所有元素的索引都会重新计算，即使最初 a 在 b 前面插入，扩容后 a 的索引可能远大于 b 的索引。
哈希冲突影响：即使哈希值不同，冲突也会导致元素被存储在远离其“自然”索引的位置。

当你遍历一个 set 时（for x in s:），CPython 简单地遍历 table 数组，跳过 NULL 和“删除标记”（被称为 dummy，一种特殊标记，表示该槽位曾经有元素但已被删除，用于保证探测序列的正确性），遍历顺序完全依赖于数组的内存布局,与插入顺序毫无关系。

举个例子：

假设有 s = set()，底层 table 长度初始为 8，mask = 7。

s.add(5)   # hash(5) = 5,  index = 5 & 7 = 5  -> 放在 table[5]
s.add(10)  # hash(10) = 10, index = 10 & 7 = 2 -> 放在 table[2]
s.add(3)   # hash(3) = 3,  index = 3 & 7 = 3  -> 放在 table[3]

遍历结果会是 10, 3, 5（按 table[2], table[3], table[5] 顺序），而不是插入顺序 5, 10, 3。

如果后续 s.add(100) 触发了扩容，新表长度变为 32，mask = 31,所有元素重新计算索引：