集合是一种鲁棒性很好的数据结构，应用在与当元素顺序的重要性不如元素的唯一性和测试元素是否包含在集合中的效率时，大部分情况下这种数据结构极其有用。表现形式通常是从列表中删除重复项以及相关的数学运算，如交集、并集、差分和对称差分等集合操作。 python的` set`支持` x in set`,` len(set)`,和` for x in set`。作为一个无序的数据结构，set 不记录元素位置或者插入点。因此，set 不支持` indexing`, 或其它类序列的操作。 python的内置集合类型有两种： - set(): 一种可变的、无序的、有限的集合，其元素是唯一的、不可变的（可哈希的）对象 - frozenset(): 一种不可变的、可哈希的、无序的集合，其元素是唯一的，不可变的哈希对象。  观察到` set`和` frozenset`运行结果的区别: 因为set里的元素必须是唯一的，不可变的，但是set是可变的，所以set作为set的元素会报错。 # 实现细节 CPython中集合和字典非常相似。事实上，集合实现的形式为带有空值的**字典**，即只有键才是实际的集合元素。此外，集合还利用这种没有值的映射做了其它的优化。 由于这一点，可以快速的向集合中添加元素、删除元素、检查元素是否存在。平均时间复杂度为O(1)，最坏的时间复杂度是O(n)。 以下是对set[源码](https://github.com/python/cpython/blob/13ad3b7a82bf56d803fbe48ee5df6c4b08986c78/Objects/setobject.c)中` PyObject`的关系解析  ## PyObject 在 set 中，对应的 set 的值的存储是通过结构` setentry`来保存数据值的； 源文件:[include/setobject.h](https://flaggo.github.io/python3-source-code-analysis/objects/set-object/) ```python typedef struct {     PyObject *key;     Py_hash_t hash;             /* Cached hash code of the key */ } setentry; ``` 这里的` key`就是保存的数据，` hash` 就是保存的数据的` hash`，便于查找，set 也是基于` hash`表来实现。对应的` setentry`所对应的 set 的数据结构即为` PySetObject` ## PySetObject对象 之前我们解析了` Python`中的` dict`对象，我们知道在dict的底层实际上是一个` hash table`本质上是一种映射关系。同样，集合对象底层也是` hash table`，因此，对于细节的描述在这一次就不细说了。关于hash table可参照这篇文章->[python的dict对象底层实现](字典实现的原理与探析_yerik的技术博客_51CTO博客) 事实上官网的对set的描述如下： > This subtype of PyObject is used to hold the internal data for both set and frozenset objects. It is like a PyDictObject in that it is a fixed size for small sets (much like tuple storage) and will point to a separate, variable sized block of memory for medium and large sized sets (much like list storage). None of the fields of this structure should be considered public and are subject to change. All access should be done through the documented API rather than by manipulating the values in the structure. > > PyObject的此子类型用于保存SET和FROZENTET对象的内部数据。 它就像一个PyDictObject，因为它是固定的小块集合（很像元组存储），并且将指向中型和大型集的单独的可变尺寸内存块（非常如列表存储）。 这种结构的领域都不应被视为公开，并且可能会有变化。 所有访问都应通过文档 的API完成，而不是通过操纵结构中的值来完成。 ```python typedef struct {     PyObject_HEAD     Py_ssize_t fill;            /* Number active and dummy entries*/     // 包括已经使用的entry与空entry值的总和     Py_ssize_t used;            /* Number active entries */              // 已经使用可用的总量     /* The table contains mask + 1 slots, and that's a power of 2.      * We store the mask instead of the size because the mask is more      * frequently needed.      */     Py_ssize_t mask;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// 与hash求和的mask     /* The table points to a fixed-size smalltable for small tables      * or to additional malloc'ed memory for bigger tables.      * The table pointer is never NULL which saves us from repeated      * runtime null-tests.      */     setentry *table;                                                    // 保存数据的数组数组指针     Py_hash_t hash;             /* Only used by frozenset objects */     Py_ssize_t finger;          /* Search finger for pop() */     setentry smalltable[PySet_MINSIZE];                                 // 保存数据的数组　默认初始化为8个元素，通过table指向     PyObject *weakreflist;      /* List of weak references */ } PySetObject; ``` 总之一个 set 就对应一个 PySetObject 类型数据，set 会根据保存的元素自动调整大小。  # 集合的生命周期 一个容器的元素生命周期管理，更多是对其进行curd等操作，但是在集合中，更多的是新建增加删除查找和自动修改大小。我们这次就来一步步调试，窥探这个容器的操作生命周期管理。 测试脚本如下 ``` set_test = {6, 6, 7, 8} set_test.add(5) set_test.add(4) set_test.remove(6) set_test.update({3, }) set_test.union({1, 5}) ``` 通过 python 反汇编指令 ``` python -m dis set_test.py ``` 获取该脚本的字节码 ```   1           0 BUILD_SET                0               2 LOAD_CONST               0 (frozenset({8, 6, 7}))               4 SET_UPDATE               1               6 STORE_NAME               0 (set_test)   2           8 LOAD_NAME                0 (set_test)              10 LOAD_METHOD              1 (add)              12 LOAD_CONST               1 (5)              14 CALL_METHOD              1              16 POP_TOP   3          18 LOAD_NAME                0 (set_test)              20 LOAD_METHOD              1 (add)              22 LOAD_CONST               2 (4)              24 CALL_METHOD              1              26 POP_TOP   4          28 LOAD_NAME                0 (set_test)              30 LOAD_METHOD              2 (remove)              32 LOAD_CONST               3 (6)              34 CALL_METHOD              1              36 POP_TOP   5          38 LOAD_NAME                0 (set_test)              40 LOAD_METHOD              3 (update)              42 LOAD_CONST               4 (3)              44 BUILD_SET                1              46 CALL_METHOD              1              48 POP_TOP   6          50 LOAD_NAME                0 (set_test)              52 LOAD_METHOD              4 (union)              54 LOAD_CONST               5 (1)              56 LOAD_CONST               1 (5)              58 BUILD_SET                2              60 CALL_METHOD              1              62 POP_TOP              64 LOAD_CONST               6 (None)              66 RETURN_VALUE ``` 通过该字节码指令可知，创建` set`调用了 ` BUILD_SET`指令，初始化完成之后，就调用` set`的` add`方法添加元素，调用` remove`删除元素,调用` update`来更新集合，通过` union`来合并集合。接下来就详细分析一下相关的操作流程。 ## 新建 查找` BUILD_SET`的虚拟机执行函数如下 [Python/ceval.c](https://github.com/python/cpython/blob/1bf9cc509326bc42cd8cb1650eb9bf64550d817e/Python/ceval.c#L2318) ```C TARGET(BUILD_SET) {     PyObject *set = PySet_New(NULL);             // 新建并初始化一个set     int err = 0;     int i;     if (set == NULL)         goto error;     for (i = oparg; i > 0; i--) {                // 将传入初始化的参数传入         PyObject *item = PEEK(i);         if (err == 0)             err = PySet_Add(set, item);          // 并依次对set进行添加操作         Py_DECREF(item);     }     STACKADJ(-oparg);　　　　　　　　　　　　　　　   // 移动弹栈     if (err != 0) {         Py_DECREF(set);         goto error;     }     PUSH(set);　　　　　　　　　　　　　　　　　　　　　// 讲set压栈     DISPATCH();　　　　　　　　　　　　　　　　　　　　// 执行下一条指令 } ``` 主要关注的是` PySet_New`函数的执行流程，该函数位于[Objects/setobject.c](https://github.com/python/cpython/blob/13ad3b7a82bf56d803fbe48ee5df6c4b08986c78/Objects/setobject.c) ```C PyObject * PySet_New(PyObject *iterable) {     return make_new_set(&PySet_Type, iterable); } ... static PyObject * make_new_set(PyTypeObject *type, PyObject *iterable) {     PySetObject *so;     so = (PySetObject *)type->tp_alloc(type, 0);            // 申请该元素的内存     if (so == NULL)                                        // 内存申请失败则返回为空         return NULL;     so->fill = 0;                                           // 初始化的时候都为０     so->used = 0;     so->mask = PySet_MINSIZE - 1;                           // PySet_MINSIZE默认为８，故mask为７     so->table = so->smalltable;                             // 将保存数据的头指针指向table     so->hash = -1;                                          // 设置hash值为-1     so->finger = 0;     so->weakreflist = NULL;     if (iterable != NULL) {                                 // 如果有迭代器         if (set_update_internal(so, iterable)) {            // 将内容更新到so中             Py_DECREF(so);             return NULL;         }     }     return (PyObject *)so;                                  // 返回初始化完成的set } ``` 从` PySet_New`的执行流程可知，集合的初始化过程就是初始化相关数据结构。 ## 添加 在本例的初始化过程中，由于传入了初始值 6,7,8，所以会在执行字节码指令的时候，执行` PySet_Add`，该函数的本质与` set_test.add(3)`本质都调用了更底层` set_add_key`函数，该函数位也是于[Objects/setobject.c](https://github.com/python/cpython/blob/13ad3b7a82bf56d803fbe48ee5df6c4b08986c78/Objects/setobject.c) ```C int PySet_Add(PyObject *anyset, PyObject *key) {     if (!PySet_Check(anyset) &&         (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {         PyErr_BadInternalCall();         return -1;     }     return set_add_key((PySetObject *)anyset, key);  // 向字典中添加key; } ``` 继续查看` set_add_key`函数的执行过程 ```C static int set_add_key(PySetObject *so, PyObject *key) {     Py_hash_t hash;     if (!PyUnicode_CheckExact(key) ||         (hash = ((PyASCIIObject *) key)->hash) == -1) {         hash = PyObject_Hash(key);                  // 获取传入值的hash值         if (hash == -1)                             // 如果不能hash则返回-1             return -1;     }     return set_add_entry(so, key, hash);            // 计算完成后添加值 } ``` 该函数主要就是检查传入的 key 是否能够被 hash，如果能够被 hash 则直接返回，如果能被 hash 则继续调用` set_add_entry`函数将值加入到 set 中。在这里也可以知道为什么Set容器中不允许元素重复，也不允许将一个不可哈希的对象插入了，所有的答案就是因为哈希表的特性。 ```C static int set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash) {     setentry *table;     setentry *freeslot;     setentry *entry;     size_t perturb;     size_t mask;     size_t i;                       /* Unsigned for defined overflow behavior */     size_t j;     int cmp;     /* Pre-increment is necessary to prevent arbitrary code in the rich        comparison from deallocating the key just before the insertion. */     Py_INCREF(key);                                                             // 提高key的引用计数   restart:     mask = so->mask;　                                                          // 获取so->mask     i = (size_t)hash & mask;　                                                  // 通过传入的hash与mask求索引下标     entry = &so->table[i];　                                                 　　// 获取索引对应的值     if (entry->key == NULL)                                                     // 如果获取索引的值没有被使用则直接跳转到found_unused处执行         goto found_unused;     freeslot = NULL;     perturb = hash;　　　                                                        // perturb设置为当前hash值 　     while (1) {         if (entry->hash == hash) {                                              // 如果当前hash值相等             PyObject *startkey = entry->key;　　　　　　　　　　　　　　　　　　　　　　// 获取当前key             /* startkey cannot be a dummy because the dummy hash field is -1 */             assert(startkey != dummy);                                          // 检查key是否为dummy             if (startkey == key)                                                // 如果找到的值与传入需要设置的值相同则跳转到found_active处执行                 goto found_active;             if (PyUnicode_CheckExact(startkey)                 && PyUnicode_CheckExact(key)                 && _PyUnicode_EQ(startkey, key))                                // 如果是unicode,通过类型转换检查两个key的内容是否相同，如果不相同则跳转到found_active处                 goto found_active;             table = so->table;                                                  // 如果没有找到，则获取当前table的头部节点             Py_INCREF(startkey);             cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);　　　　　　　　　 // 如果是其他类型的对象则调用比较方法去比较两个key是否相同             Py_DECREF(startkey);             if (cmp > 0)                                          /* likely */   // 如果找到则跳转到found_active                 goto found_active;             if (cmp < 0)                 goto comparison_error;                                          // 如果小于０，则是两个类型对比失败             /* Continuing the search from the current entry only makes                sense if the table and entry are unchanged; otherwise,                we have to restart from the beginning */             if (table != so->table || entry->key != startkey)                     // 如果set改变了则重新开始查找                 goto restart;             mask = so->mask;                 /* help avoid a register spill */　　　         }         else if (entry->hash == -1)             freeslot = entry;　　　                                                // 如果不能hash 则设置freeslot         if (i + LINEAR_PROBES <= mask) {　　　　　　　　　　　　　　                   // 检查当前索引值加上 ９小于当前mask             for (j = 0 ; j < LINEAR_PROBES ; j++) {                               // 循环９次                 entry++;                                                    　　　 // 向下一个位置                 if (entry->hash == 0 && entry->key == NULL)　　　　　　　　　　　　　　// 如果找到当前hash为空或者key为空的则跳转到found_unused_or_dummy处执行                     goto found_unused_or_dummy;                 if (entry->hash == hash) {　　                                     // 如果找到的hash值相同                     PyObject *startkey = entry->key;                              // 获取该值                     assert(startkey != dummy);                                    // 检查是否为dummy                     if (startkey == key)                                          // 如果key相同则跳转到found_active处执行                         goto found_active;                     if (PyUnicode_CheckExact(startkey)                         && PyUnicode_CheckExact(key)                         && _PyUnicode_EQ(startkey, key))                          // 检查是否为unicode，并比较如果不相同则跳转到found_active                         goto found_active;                     table = so->table;                                            // 调用key本身的方法比较                     Py_INCREF(startkey);                     cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);                     Py_DECREF(startkey);                     if (cmp > 0)                         goto found_active;                     if (cmp < 0)                         goto comparison_error;                     if (table != so->table || entry->key != startkey)                         goto restart;                     mask = so->mask;                 }                 else if (entry->hash == -1)                     freeslot = entry;             }         }         perturb >>= PERTURB_SHIFT;                                               // 如果没有找到则获取下一个索引值         i = (i * 5 + 1 + perturb) & mask;                                        // 右移５位　加上　索引值*5 加１与mask求余获取下一个索引值         entry = &so->table[i];                                                   // 获取下一个元素         if (entry->key == NULL)　　　　　　　　　　　　　　                           // 如果找到为空则直接跳转到found_unused_or_dummy处             goto found_unused_or_dummy;     }   found_unused_or_dummy:     if (freeslot == NULL)　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// 检查freeslot是否为空如果为空则跳转到found_unused处执行即找到了dummy位置         goto found_unused;     so->used++;　　　　　　　　　　　　　　　　　　　　　　                             // 使用数加１     freeslot->key = key;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 // 设置key与hash值     freeslot->hash = hash;     return 0;   found_unused:     so->fill++;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// 使用总数加１     so->used++;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// 使用总数加１　     entry->key = key;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 // 设置key与hash值     entry->hash = hash;     if ((size_t)so->fill*5 < mask*3)　　　　　　　　　　　　　　　　　　　　　　　　　　　// 检查已经使用的值是否是总数的3/5         return 0;     return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);　　　 // 如果已使用的总数大于3/5则重新调整table，如果set使用的总数超过了50000则扩展为以前的２倍否则就是四倍   found_active:     Py_DECREF(key);　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// 如果找到了该值　则什么也不做     return 0;   comparison_error:     Py_DECREF(key);　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// 如果比较失败则返回-1     return -1; } ``` 简单来说就是通过传入的` hash`值，如果计算出的索引值index对应的空间为空，则直接将该值存入对应的 ` entry`中，如果相同则不插入，这个时候就会出现**哈希冲突**，如果索引对应的存在值且值不同，python中将会采用开放定址法、再哈希法等方式来解决这个问题之后。再将该值设置进去。如果设置该值之后使用的数量占总的申请数量超过了 3/5 则重新扩充` set`，扩充的原则就是如果当前的` set->used>50000`就进行两倍扩充否则就进行四倍扩充。 ## 删除 set 的删除操作主要集中在 ` set_remove()`函数上，该函数位也是于[Objects/setobject.c](https://github.com/python/cpython/blob/13ad3b7a82bf56d803fbe48ee5df6c4b08986c78/Objects/setobject.c) ```C static PyObject * set_remove(PySetObject *so, PyObject *key) {     PyObject *tmpkey;     int rv;     rv = set_discard_key(so, key);                              // 将该key设置为dummy     if (rv < 0) {         if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))  // 检查是否为set类型             return NULL;         PyErr_Clear();         tmpkey = make_new_set(&PyFrozenSet_Type, key);　　　　　　　　　　　　　// 对该值重新初始化为forzenset         if (tmpkey == NULL)             return NULL;         rv = set_discard_key(so, tmpkey);　　　　　　　　　　　　　　　　　　　　　// 设置该key为空         Py_DECREF(tmpkey);         if (rv < 0)             return NULL;     }     if (rv == DISCARD_NOTFOUND) {                               // 如果没有找到则报错         _PyErr_SetKeyError(key);         return NULL;     }     Py_RETURN_NONE; } ``` 此时就会调用` set_discard_key`方法来讲对应的` entry`设置为` dummy` ` set_discard_key`的实现方式如下： ```C static int set_discard_key(PySetObject *so, PyObject *key) {     Py_hash_t hash;     if (!PyUnicode_CheckExact(key) ||         (hash = ((PyASCIIObject *) key)->hash) == -1) {         hash = PyObject_Hash(key);                        　// 检查是否可用hash如果可用则调用set_discard_entry方法         if (hash == -1)             return -1;     }     return set_discard_entry(so, key, hash); } ``` 该函数主要就是做了检查` key`是否为可 ` hash`的检查，此时如果可` hash`则调用 ` set_discard_entry`方法； ```C static int set_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash) {     setentry *entry;     PyObject *old_key;     entry = set_lookkey(so, key, hash);　　　　　　// 查找该值 set_lookkey该方法与插入的逻辑类似大家可自行查看     if (entry == NULL)　　　　　　　　　　　　　　　　 // 如果没有找到则返回－１         return -1;     if (entry->key == NULL)         return DISCARD_NOTFOUND;　　　　　　　　　　　// 找到entry而key为空则返回notfound     old_key = entry->key;                        // 找到正常值则讲该值对应的entry设置为dummy     entry->key = dummy;     entry->hash = -1;                             // hash值为-1     so->used--;                                   // 使用数量减１　但是fill数量未变     Py_DECREF(old_key);　　　　　　　　　　　　　　　　　// 减少该对象引用     return DISCARD_FOUND;　　　　　　　　　　　　　　　　// 返回返现 } ``` 此时就是查找该值，如果找到该值并将该值设置为` dummy`，并且将` used`值减１，此处没有减去` fill`的数量，从此处可知，` fill`包括所有曾经申请过的数量。 ## 自动调整大小 集合的` resize`主要依靠` set_table_reseize`函数来实现 ```C static int set_table_resize(PySetObject *so, Py_ssize_t minused) {     setentry *oldtable, *newtable, *entry;     Py_ssize_t oldmask = so->mask;                                            // 设置旧的mask     size_t newmask;     int is_oldtable_malloced;     setentry small_copy[PySet_MINSIZE];                                       // 最小的拷贝数组     assert(minused >= 0);     /* Find the smallest table size > minused. */     /* XXX speed-up with intrinsics */     size_t newsize = PySet_MINSIZE;     while (newsize <= (size_t)minused) {         newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.　　// 查找位于minused最大的PySet_MINSIZE的n次方的值     }     /* Get space for a new table. */     oldtable = so->table;　　　　　　　　　　　　　　　　　　          // 先获取旧的table     assert(oldtable != NULL);     is_oldtable_malloced = oldtable != so->smalltable;     if (newsize == PySet_MINSIZE) {　　　　　　　　　　　　　　　　　　// 如果获取的新大小与PySet_MINSIZE的大小相同         /* A large table is shrinking, or we can't get any smaller. */         newtable = so->smalltable;　　　　　　　　　　　　　　　　　　// 获取新table的地址         if (newtable == oldtable) {　　　　　　　　　　　　　　　　　// 如果相同             if (so->fill == so->used) {　　　　　　　　　　　　　　// 如果使用的相同则什么都不做                 /* No dummies, so no point doing anything. */                 return 0;             }             /* We're not going to resize it, but rebuild the                table anyway to purge old dummy entries.                Subtle:  This is *necessary* if fill==size,                as set_lookkey needs at least one virgin slot to                terminate failing searches.  If fill < size, it's                merely desirable, as dummies slow searches. */             assert(so->fill > so->used);             memcpy(small_copy, oldtable, sizeof(small_copy));　// 将数据拷贝到set_lookkey中             oldtable = small_copy;　　　　　　　　　　　　　　　　　　         }     }     else {         newtable = PyMem_NEW(setentry, newsize);                 // 新申请内存         if (newtable == NULL) {　　　　　　　　　　　　　　　　　　　　　// 如果为空则申请内存失败报错             PyErr_NoMemory();             return -1;         }     }     /* Make the set empty, using the new table. */     assert(newtable != oldtable);                                // 检查新申请的与就table不同     memset(newtable, 0, sizeof(setentry) * newsize);　　　　　　　　//　新申请的内存置空     so->mask = newsize - 1;                                     // 设置新的size     so->table = newtable;                                       // 重置table指向新table     /* Copy the data over; this is refcount-neutral for active entries;        dummy entries aren't copied over, of course */     newmask = (size_t)so->mask;                                  // 获取新的mask     if (so->fill == so->used) {                                  // 如果使用的与曾经使用的数量相同         for (entry = oldtable; entry <= oldtable + oldmask; entry++) {             if (entry->key != NULL) {                 set_insert_clean(newtable, newmask, entry->key, entry->hash);　　// 如果值不为空则插入到新的table中             }         }     } else {         so->fill = so->used;　　　　　　　　　　　　　　　　　　　　　　　　// 如果不相同则重置fill为used的值         for (entry = oldtable; entry <= oldtable + oldmask; entry++) {             if (entry->key != NULL && entry->key != dummy) {　　　　　// 检查如果不为dummy并且key不为空的情况下                 set_insert_clean(newtable, newmask, entry->key, entry->hash);　　// 重新插入该列表该值             }         }     }     if (is_oldtable_malloced)　　　　　　　　　　　　　　　　　　　　　　　// 如果两个表相同则删除旧table         PyMem_DEL(oldtable);     return 0;                                                      // 返回０ } ``` 主要是检查是否` table`相同并且需要重新` resize`的值，然后判断是否` fill`与` used` 相同，如果相同则全部插入，如果不同，则遍历旧` table`将不为空并且不为` dummy`的值插入到新表中 ```C static void set_insert_clean(setentry *table, size_t mask, PyObject *key, Py_hash_t hash) {     setentry *entry;     size_t perturb = hash;     size_t i = (size_t)hash & mask;　　　　　　　　        // 计算索引     size_t j;     while (1) {         entry = &table[i];                              // 获取当前entry         if (entry->key == NULL)                         // 如果为空则跳转值found_null设置key与hash             goto found_null;         if (i + LINEAR_PROBES <= mask) {                // 如果没有找到空值则通过该索引偏移9位去查找空余位置             for (j = 0; j < LINEAR_PROBES; j++) {                 entry++;                 if (entry->key == NULL)                 // 如果为空则跳转到found_null                     goto found_null;             }         }         perturb >>= PERTURB_SHIFT;                      // 计算下一个索引值继续寻找         i = (i * 5 + 1 + perturb) & mask;     }   found_null:     entry->key = key;     entry->hash = hash; } ``` ## 查找 这里主要是看` set_lookkey`这个函数 ```C static setentry * set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) {     /* 给定一个 key, 和一个 hash 值，返回这个 hash 在这个集合 so 里对应的 entry */     setentry *table;     setentry *entry;     size_t perturb;     size_t mask = so->mask;     size_t i = (size_t)hash & mask; /* 把 hash 高于 mask 长度的位清零，留下长度低于 mask 位数 */     size_t j;     int cmp;       entry = &so->table[i]; /* 取出集合的第 i 个 entry */     if (entry->key == NULL) /* 如果第 i 个 entry 是空的值，直接返回 */         return entry;       perturb = hash;       while (1) {         /* 第i个 entry 不为空, 开始循环匹配，直到找到相等的 entry 为止 */         if (entry->hash == hash) {             /* 如果 entry 里的 hash 值相同，判断 key 是否相同 */             PyObject *startkey = entry->key;             /* startkey cannot be a dummy because the dummy hash field is -1 */             assert(startkey != dummy);             if (startkey == key) /* key 地址相同，返回entry */                 return entry;             if (PyUnicode_CheckExact(startkey)                 && PyUnicode_CheckExact(key)                 && _PyUnicode_EQ(startkey, key)) /* key 为string，且 string 值相同，返回 entry */                 return entry;             table = so->table;             Py_INCREF(startkey);             cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); /* 判断 entry 里存储的 key 和传入的 key 的结果 */             Py_DECREF(startkey);             if (cmp < 0) /* start key 和 传入的 key 不相等 */                 return NULL;             if (table != so->table || entry->key != startkey)     /* unlikely */                 return set_lookkey(so, key, hash);             if (cmp > 0) /* start key 和 传入的 key 相等 */                 return entry;             mask = so->mask; /* 避免寄存器溢出? */         }         /* 当前的 entry 的 hash 值和 传入的 hash 值不匹配，需要重新寻找一个位置             关于 LINEAR_PROBES 的作用可以看下面的介绍         */         if (i + LINEAR_PROBES <= mask) {             /* 判断 i 后面是否还有 LINEAR_PROBES 个空间，如果有则进行横向搜索 */             for (j = 0 ; j < LINEAR_PROBES ; j++) {                 /* 在 LINEAR_PROBES 范围内进行寻找是否有匹配的 entry */                 entry++;                 /* 重复第一个条件中的匹配搜索 */                 if (entry->hash == 0 && entry->key == NULL)                     return entry;                 if (entry->hash == hash) {                     PyObject *startkey = entry->key;                     assert(startkey != dummy);                     if (startkey == key)                         return entry;                     if (PyUnicode_CheckExact(startkey)                         && PyUnicode_CheckExact(key)                         && _PyUnicode_EQ(startkey, key))                         return entry;                     table = so->table;                     Py_INCREF(startkey);                     cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);                     Py_DECREF(startkey);                     if (cmp < 0)                         return NULL;                     if (table != so->table || entry->key != startkey)                         return set_lookkey(so, key, hash);                     if (cmp > 0)                         return entry;                     mask = so->mask;                 }             }         }         /* 横向的 LINEAR_PROBES 无法搜索到对应的 entry, 重新进行 hash, 返回到 while 开始处 */         perturb >>= PERTURB_SHIFT;         i = (i * 5 + 1 + perturb) & mask;           entry = &so->table[i];         if (entry->key == NULL)             return entry;     } } ``` 对于` LINEAR_PROBES`其意义在于当前hash对应的` entry`的值不匹配时，按照传统的思路，直接重新生成一个` hash`值，在对应的新的` hash`值上找到一个新的位置，但是这样做的话对` cpu`的` cache`影响较大，如果两个位置间隔过于分散，cpu 这一次读取了这个` entry`和附近的` entry`到` cache`中，下一次又需要重新读取，浪费` cpu cycle` 因此当前的算法引入一个` LINEAR_PROBES`，在当前` entry`向前` LINEAR_PROBES`个位置进行寻找，如果找不到才重新进行` hash`计算，以提高` cpu cache`的稳定性，所以在` set`的` hash entry`是随机值和连续值的结合体 前面中说到` set_add_entry`，经历和上边代码注释的` set_lookkey`函数相似的搜索过程，找对已经有值/空的` entry`, 并把` entry`设置为传入的` key`的过程，而` static void set_insert_clean`，找到一个空的` entry`, 并把` key`插入 # 参考资料 1. https://flaggo.github.io/python3-source-code-analysis/objects/set-object/ 2. https://docs.python.org/3/c-api/set.html