Set 的功能其实与 Dict 的 Key 非常相似：

• 不可重复；
• 需要快速查找；

一些文章中认为 Set 是 Value 为空的 Dict，在逻辑上大体没问题，但具体实现还是有很大区别的。

PySetObject 的结构

对象的结构在很大程度上决定了它能做什么，首先了解 Set 的结构：

// Objects/setobject:42

typedef struct {
    PyObject_HEAD

    Py_ssize_t fill;            /* 所有已使用节点，包括 dummy 节点*/
    Py_ssize_t used;            /* 有效节点数量 */

    Py_ssize_t mask;        /* 用于对 Key 的 hash 按哈希表大小取模 */

    setentry *table;        /* 哈希表 */
    Py_hash_t hash;             /* frozenset 的 hash */
    Py_ssize_t finger;          /* Search finger for pop() */

    setentry smalltable[PySet_MINSIZE];    /* 初始的小哈希表 */
    PyObject *weakreflist;      /* 弱引用表 */
} PySetObject;

在定义中隐约可以看到一些 Dict 的影子，比如 mask、fill、used、table 等等。下面将 Set 与 Dict 放在一起比较一下。

smalltable 是所有 PySetObject 创建后，table 指向的位置，这样设计的目的是为了减少一次内存申请调用，另外确保 table 指针始终不为 NULL，免去重复 if(Set->table == NULL) 这样的测试代码。我已经将 Dict 和 Set 功能相似区域标记出来了，其中 table 指针的两种可能用虚线标出，两种不同情况下的 table 内存用深浅不一的绿色区别。

如果再观察 Set 中 entry 的结构，就更明显了。

同样的，我将相似功能部分标记出来了。

Set 几乎就是一个减配版 Dict，取消了 Value 字段。底层的主要区别在于：

• entries 的存储不同，Set 的数据直接存储在哈希表里，Dict 的哈希表与数据是分离的；
• Set 与 Dict 的 lookup 函数有细微区别。

不同于 Dict 直接采用二次探测，Set 会先进行一小段线性搜索，再进行二次探测。可以猜到 Set 的 lookup 与 Dict 必然存在相当的相似度。

需要指明的是， Dict 与 Set 的相似性更多的是逻辑上，实现差异依然很大。