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

1. 集合概述

在 Python 中，集合（set）是一种不允许重复元素的数据类型。它的实现原理主要由哈希表和二叉树两部分组成。集合的基本操作包括add()、remove()、union()、intersection()等。

Set 中的元素必须是可哈希的，哈希算法用于将元素映射到哈希表中，从而实现 O(1) 的查找操作。当哈希冲突时，Python 使用二叉树来解决冲突。

2. 集合创建

创建集合有两种方式：使用set()函数或使用花括号 {}。

# 使用 set() 函数创建集合
s1 = set([1, 2, 3])
print(s1)
s2 = set('python')
print(s2)

# 使用 {} 创建集合
s3 = {1, 2, 3}
print(s3)

输出结果：

{1, 2, 3}
{'p', 'y', 't', 'h', 'o', 'n'}
{1, 2, 3}

3. 集合方法

（1）add(el)

用于将元素添加到集合中，如果集合中已经存在该元素，则不做任何修改。

s = {1, 2, 3}
s.add(4)
s.add(2)
print(s)

输出结果：

{1, 2, 3, 4}

（2）remove(el)

用于删除集合中的元素，如果元素不在集合中，则抛出KeyError异常。

s = {1, 2, 3}
s.remove(2)
print(s)

输出结果：

{1, 3}

（3）union(set)

用于合并两个集合。

s1 = {1, 2, 3}
s2 = {3, 4, 5}
s3 = s1.union(s2)
print(s3)

输出结果：

{1, 2, 3, 4, 5}

（4）intersection(set)

用于求两个集合的交集。

s1 = {1, 2, 3}
s2 = {3, 4, 5}
s3 = s1.intersection(s2)
print(s3)

输出结果：

{3}

4. 集合源码分析

Python 使用 setobject 结构体来表示集合对象。

typedef struct _setobject {
    PyObject_HEAD
    Py_ssize_t used;            /* # 索引表中已经使用的元素 */
    Py_ssize_t size;            /* # 索引表中可以使用的元素，size <= used */
    PyObject *table;            /* # 索引表 */
    /* # 哈希表总共分了 80 个桶，最多存 7453 个元素 */
    Py_hash_t hash;
} setobject;

集合中的元素和对应的哈希值保存在 table 中。table 实际上是一个由多个指针组成的数组，每个指针指向一个哈希冲突链表的头结点。每个节点又保存了元素、哈希值和指向下一个节点的指针。

5. 集合遍历

s = {1, 2, 3}
for el in s:
    print(el)

输出结果：

1
2
3

利用 Python 的迭代器（Iterator）机制，可以更加底层地遍历集合中的元素。

/* 在 setobject 结构体中定义了 PySetIterObject 迭代器 */
typedef struct {
    PyObject_HEAD
    Py_ssize_t it_index;            /* # 当前迭代器所在的桶的索引值 */
    PyObject *it_set;               /* # 当前迭代器操作的集合对象 */
    PyObject *it_value;             /* # 当前迭代器返回的元素 */
    Py_hash_t *it_hash_buf;         /* # 暂存哈希值的数组 */
} PySetIterObject;

/* setobject 结构体中定义了一个 PyHeapTypeObject 对象，其 ob_type 指向 PySet_Type */
typedef struct {
    PyVarObject_HEAD
    PySetObject set;                /* # 存放集合对象的 setobject 结构体 */
} PySet_T;

/* 在 PySet_Type 对象中定义了 tp_iter 函数 */
static PyObject *
set_iter(PyObject *so)
{
    PySetObject *so1 = (PySetObject *)so;
    PySetIterObject *it;

    it = PyObject_GC_New(PySetIterObject, &PySetIter_Type);
    if (it == NULL)
        return NULL;
    Py_INCREF(so);
    it->it_set = so;
    it->it_index = 0;
    it->it_value = NULL;
    if (so1->fill >= 0 && so1->used > 0) {
        it->it_hash_buf = (Py_hash_t *)
            PyMem_Malloc(sizeof(Py_hash_t) * so1->used);
        if (it->it_hash_buf == NULL) {
            PyErr_NoMemory();
            Py_DECREF(it);
            return NULL;
        }
        set_table_fill(so1);
        fill_it_hash_buf(it->it_hash_buf, so1);
    }
    else {
        it->it_hash_buf = NULL;
    }
    PyObject_GC_Track(it);
    return (PyObject *) it;
}

可以发现，集合的迭代器的实现方式也是通过遍历 table 中的元素来完成的。没有像列表和元组那样维护一个线性的结构。