Edit: Python `set` 的底层实现

编辑文章

标题 *

URL 别名 *

内容 * (支持 Markdown 格式)

当然，我们来剖析一下 Python `set` 的底层实现。它与 `list` 的实现截然不同，这也是它们适用场景和性能特征迥异的根本原因。

简而言之，Python 的 `set` 是通过**哈希表（Hash Table）** 实现的。它在很多方面与 `dict`（字典）的底层实现非常相似，甚至可以说，**一个 `set` 本质上就是一个只存储键（key）而没有值（value）的特殊字典。**

下面我们来详细拆解它的实现机制。

### 1. 核心概念：哈希表

要理解 `set`，必须先理解哈希表的工作原理。哈希表主要依赖三个核心概念：

1.  **哈希函数 (Hash Function)**：
    这是一个可以将任意（可哈希的）对象转换成一个整数的函数。在 Python 中，你可以通过内置的 `hash()` 函数来查看一个对象的哈希值。
    *   **特性**：
        *   **确定性**：对于同一个对象，`hash(obj)` 的返回值在一次程序运行中必须是固定的。
        *   **高效性**：计算哈希值的速度要快。
        *   **散列分布**：理想情况下，不同对象的哈希值应尽可能均匀地分布，以减少冲突。

2.  **桶/槽 (Buckets/Slots)**：
    哈希表的底层是一个数组，这个数组的每个位置被称为一个“桶”或“槽”。当我们向集合中添加一个元素时，会执行以下步骤：
    *   计算该元素的哈希值：`hash_value = hash(element)`。
    *   确定存储位置：通过哈希值计算出它在底层数组中应该存放的索引（桶的位置），通常使用取模运算：`index = hash_value % array_size`。
    *   将元素（或其引用）存入该位置。

3.  **哈希冲突 (Hash Collision) 与解决**：
    当两个不同的对象经过哈希函数计算后，得到了相同的索引位置，这就发生了“哈希冲突”。这是哈希表实现中必须解决的核心问题。Python 主要使用一种叫做**开放寻址法 (Open Addressing)** 的技术来解决冲突。

### 2. Python 的具体实现 (CPython)

在 CPython 解释器中，一个 `set` 对象（`PySetObject`）主要包含一个指向哈希表的指针。这个表是一个由条目（entry）组成的数组。

#### **开放寻址法 (Open Addressing)**

当 `set.add(element)` 发生冲突时（即计算出的 `index` 位置已经被其他元素占用），Python 不会像某些哈希表实现那样在那个位置创建一个链表（这叫拉链法），而是会**继续寻找下一个可用的空槽**。

这个“寻找下一个”的过程不是简单的 `index + 1`（线性探测），而是一个基于哈希值计算出的伪随机序列。这样做可以有效避免元素聚集在某个区域，从而保持哈希表的高效性。

**插入/查找过程：**

1.  计算元素的哈希值 `h`。
2.  通过 `h` 计算初始的桶索引 `i`。
3.  检查 `table[i]`：
    *   **如果为空**：元素不存在。如果是插入操作，则将元素放入此桶；如果是查找，则说明集合中没有该元素。
    *   **如果非空**：比较 `table[i]` 中存储的元素是否与要操作的元素相等 (`==`) 并且哈希值也相同。
        *   **如果相等**：元素已存在。插入操作什么都不做，查找操作成功返回。
        *   **如果不相等**：说明发生了哈希冲突。根据一个特定的算法计算出下一个探测位置 `j`，然后跳到第 3 步，检查 `table[j]`，如此循环，直到找到该元素或一个空槽。

#### **删除元素与哑元 (Dummy Entry)**

当你从 `set` 中删除一个元素时（`remove()` 或 `discard()`），不能简单地将对应的桶变为空。

**为什么？** 想象一下，A 和 B 冲突了，A 在 `table[i]`，B 在 `table[j]`。如果此时删除了 A 并将 `table[i]` 设为空，那么下次再查找 B 时，探测链在 `table[i]` 处就会中断，误以为 B 不存在。

为了解决这个问题，被删除的元素所在的桶会被标记为一个特殊的**哑元 (dummy)** 状态。这个状态表示“这里曾经有元素，但现在删除了，请继续往下探测”。当插入新元素时，哑元槽可以被重新利用。

#### **动态扩容 (Resizing)**

和 `list` 类似，`set` 的底层哈希表也是动态的。当哈希表中的元素数量达到其容量的某个阈值（通常是 2/3，这个比例称为**负载因子**）时，为了避免冲突过于频繁导致性能下降，哈希表就需要扩容。

扩容过程：
1.  创建一个更大的新数组（通常是原大小的 2 倍或 4 倍）。
2.  遍历旧表中的所有元素。
3.  对**每一个元素重新计算**其在新表中的位置（因为模数 `array_size` 变了），并将其插入新表。
4.  释放旧表。

这是一个成本很高的 O(n) 操作，因此 `set` 也会预先分配一些额外空间，以保证连续添加操作的**摊还时间复杂度**为 O(1)。

### 3. 时间复杂度分析

基于哈希表的实现，`set` 的操作具有以下性能特征：

| 操作 | 示例 | 平均时间复杂度 | 最坏时间复杂度 | 解释 |
| :--- | :--- | :--- | :--- | :--- |
| **添加元素** | `my_set.add(x)` | O(1) | O(n) | 平均情况下，哈希计算和探测次数是常数。最坏情况是所有元素都冲突，退化成线性探测。 |
| **删除元素** | `my_set.remove(x)` | O(1) | O(n) | 同上。 |
| **成员检查** | `x in my_set` | O(1) | O(n) | 这是 `set` 相对 `list` 的最大优势。查找过程和添加/删除类似。 |
| **迭代** | `for x in my_set:` | O(n) | O(n) | 需要访问所有 n 个元素。 |
| **集合运算** | `s1 & s2` (交集) | O(min(len(s1), len(s2))) | O(len(s1) * len(s2)) | 遍历较小的集合，对其中每个元素在较大集合中进行 O(1) 查找。 |
| **集合运算** | `s1 \| s2` (并集) | O(len(s1) + len(s2)) | O(len(s1) + len(s2)) | 需要遍历两个集合的所有元素。 |

### 4. 对元素的要求：必须可哈希 (Hashable)

这是 `set` (和 `dict` 的 key) 的一个关键约束。一个对象要能被放入 `set`，它必须满足：
1.  实现了 `__hash__()` 方法，使其 `hash()` 函数能返回一个整数。
2.  实现了 `__eq__()` 方法，用于比较两个对象是否相等。
3.  如果 `a == b`，那么必须保证 `hash(a) == hash(b)`。
4.  对象的哈希值在其生命周期内必须**不可变**。

这就是为什么**可变对象**（如 `list`, `dict`, `set`）不能被放入 `set` 中。因为如果它们的内容改变，其哈希值就可能改变，这会破坏哈希表的结构，导致无法再找到该元素。而**不可变对象**（如 `int`, `float`, `str`, `tuple`, `frozenset`）都是可哈希的。

### 总结

*   **数据结构**：`set` 的底层是**哈希表**。
*   **核心优势**：利用哈希函数实现了**平均 O(1) 复杂度**的添加、删除和成员检查操作。
*   **实现细节**：通过**开放寻址法**解决哈希冲突，并使用**哑元**来处理元素删除，通过**动态扩容**来维持性能。
*   **核心约束**：`set` 中的元素必须是**可哈希的 (hashable)**。

配图 (可多选)

选择新图片文件或拖拽到此处

标签