Python 虚拟机集合 set 实现原理及源码解析

什么是 set

set 是 Python 中的一种基本数据类型，用于存储无序、不重复的元素集合。set 的特点是：

• 无序性：set 中没有元素的顺序关系。
• 互异性：set 中的元素都是唯一的，重复的元素会被自动忽略。

set 中可以存储任意类型的数据，例如数字、字符串、元组等不可变类型，但是不能存储可变类型，例如列表、集合、字典等。在 Python 中，set 使用了哈希表来实现。

哈希表的原理

哈希表是一种基于数组的数据结构，通过散列函数将关键字映射到数组中的一个位置，从而实现快速的数据查找。哈希表的核心思想是将原始数据进行多次加工，最终生成一个哈希值，然后将哈希值作为数组下标存储原始数据。在 Python 中，内置的哈希函数 hash() 可以将大部分对象转换为整数作为哈希值。

哈希表的主要优点是查找速度快，时间复杂度为 O(1)，缺点是空间利用率低，因为可能存在哈希冲突，即不同的关键字生成相同的哈希值，需要额外的措施进行处理。Python 中的哈希表使用开放地址法来解决哈希冲突，具体是通过线性探测法、二次探测法或者双重哈希法等方式进行探测，直到找到空槽位为止。

set 的实现原理

当 Python 创建一个 set 对象时，会为该对象分配一块内存空间，该空间包含了实例对象的头信息和哈希表的指针 table。哈希表的实现是通过 C 语言中的 struct _setobject 结构体实现的，该结构体定义如下：

typedef struct _setobject {
   PyObject_HEAD
   /* 数据个数 */
   Py_ssize_t size;
   /* 哈希表元素个数 */
   Py_ssize_t used;
   /* 哈希表大小 */
   Py_ssize_t fill;
   /* 哈希表指针 */
   PyObject **table;
} PySetObject;

set 对象中，size 表示实例中元素的个数，used 表示哈希表中已经分配的槽位数，fill 表示哈希表的大小，table 是一个指向指针数组的指针，指向的每个元素都指向一个 HashEntry 结构体。

typedef struct {
   Py_hash_t hash;
   PyObject *key;
} HashEntry;

HashEntry 结构体包含了两个域，hash 表示该元素的哈希值，key 表示该元素的值。

set 中的操作分为两类，一类是对 set 对象本身的操作，例如向 set 中添加或者删除元素，另一类是对 set 中元素的操作，例如判断 set 中是否包含某个元素。

set 的源码解析

创建 set 实例

当我们使用以下语法创建一个 set 实例时：

s = set([1, 2, 3])

Python 调用 set() 函数来创建 set 实例，实际上是调用了 C 函数 set_new() 来创建一个新的 set 对象。该函数主要做了以下几件事情：

1. 分配内存空间，包括头信息和哈希表指针。
2. 设置头信息，包括类型信息和引用计数为 0。
3. 初始化 PySetObject 结构体的成员变量，包括 size、used、fill 和 table。
4. 将数据元素插入哈希表中。

添加元素到 set 中

当我们使用以下语法将元素添加到 set 中时：

s.add(4)

Python 调用 set_add() 函数来添加元素。该函数首先会检查要添加的元素在哈希表中是否存在，如果存在则返回，否则就新建一个 HashEntry 结构体，并将元素的哈希值和指针赋值给结构体的 hash 和 key 成员变量，然后将结构体插入到哈希表中。

从 set 中删除元素

当我们使用以下语法将元素从 set 中删除时：

s.remove(4)

Python 调用 set_discard() 函数来删除元素。该函数首先会根据元素的哈希值在哈希表中查找该元素是否存在，如果存在则删除元素，否则什么也不做。

判断元素是否在 set 中

当我们使用以下语法判断元素是否在 set 中时：

if 4 in s:
    print("元素在 set 中")

Python 调用 set_contains() 函数来判断元素是否在 set 中。该函数首先会根据元素的哈希值在哈希表中查找该元素是否存在，如果存在则返回 True，否则返回 False。

示例说明

示例 1：使用 set 存储元素

如下代码展示了如何使用 set 存储元素，包括创建 set 实例和向 set 中添加元素：

# 创建 set 实例
s = set()
# 向 set 中添加元素
s.add(1)
s.add(2)
s.add(3)
# 打印 set 中的元素
print(s)  # 输出：{1, 2, 3}

示例 2：使用 set 进行元素去重

如下代码展示了如何使用 set 对列表元素进行去重：

# 定义一个包含重复元素的列表
lst = [1, 2, 2, 3, 3, 3, 4, 5, 5, 5]
# 将列表元素转换为 set，去重后再转换回列表
lst = list(set(lst))
# 打印去重后的列表
print(lst)  # 输出：[1, 2, 3, 4, 5]

以上示例说明了 set 的两个常见用途，一个是存储元素，另一个是进行元素去重。