7.0 序
集合和字典一样，都是性能非常高效的数据结构，性能高效的原因就在于底层使用了哈希表。因此集合和字典的原理本质上是一样的，都是把值映射成索引，通过索引去查找。
7.1 PySetObject
哈希表我们在字典那一章已经介绍过了，因此直接看set在cpython中的实现。
//python中的集合的每一个元素，是通过setentry这个结构体来存储的
typedef struct {
PyObject *key; // 元素的指针
Py_hash_t hash; // 元素的哈希值
} setentry;
typedef struct {
PyObject_HEAD
//我们发现在set中，每一个元素依然叫做entry
Py_ssize_t fill; /* active态以及dummy态的entry总数量*/
Py_ssize_t used; /* active态的entry数量 */
/* 该table包含mask+1个slot，mask+1是2的幂次方
我们存储的是mask，而不是size，因为更常需要mask
这个mask是用来和哈希值进行运算的
*/
Py_ssize_t mask;
/* 对于小表，该table指向固定大小的small table，对于bigger table则指向额外的malloc内存
该table的指针永远不会为NULL。
所以它是指向setentry数组的一个指针
*/
setentry *table;
Py_hash_t hash; /* 该PySetObject的哈希值，只适用于frozenset */
Py_ssize_t finger;
/*
用于pop元素的，search finger就是我们从包含某个元素的节点开始，找到我们希望的元素
*/
//smalltable就是显然就是一个保存了setentry类型的数组
//PySet_MINSIZE是一个宏定义，默认是8。如果元素比较少的话，存在smalltable里面
//当smalltable存不下的时候(仮)，就会使用malloc申请。存不下，指的是超过8个的时候吗？
//由于哈希表的特性，需要预留一定的空间，因此还没存到8个的时候，就会扩容了
setentry smalltable[PySet_MINSIZE];
PyObject *weakreflist; /* 弱引用列表 */
} PySetObject;
7.2 PySetObject对象的创建
创建一个PySetObject对象可以使用PySet_New方法
PyObject *
PySet_New(PyObject *iterable)
{
//底层调用了make_new_set
return make_new_set(&PySet_Type, iterable);
}
static PyObject *
make_new_set(PyTypeObject *type, PyObject *iterable)
{
//申明一个PySetObject *指针
PySetObject *so;
//申请该元素所需要的内存
so = (PySetObject *)type->tp_alloc(type, 0);
//申请失败，返回NULL
if (so == NULL)
return NULL;
//初始化都为0
so->fill = 0;
so->used = 0;
//PySet_MINSIZE默认为8，mask初始化为7
so->mask = PySet_MINSIZE - 1;
//将table指向保存数据的smalltable的头指针
so->table = so->smalltable;
//初始化hash值为-1
so->hash = -1;
//finger为0
so->finger = 0;
//弱引用列表为NULL
so->weakreflist = NULL;
//如果迭代器不为NULL，那么把元素依次更新的so这个PySetObject中
if (iterable != NULL) {
if (set_update_internal(so, iterable)) {
Py_DECREF(so);
return NULL;
}
}
//返回初始化完成的set
return (PyObject *)so;
}
从以上步骤可以看出，初始化一个PySetObject对象主要初始化其内部的数据结构
7.3 插入元素
插入元素，会调用PySet_Add
int
PySet_Add(PyObject *anyset, PyObject *key)
{ //参数是两个指针
//类型检测
if (!PySet_Check(anyset) &&
(!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
PyErr_BadInternalCall();
return -1;
}
//本质上调用了set_add_key
return set_add_key((PySetObject *)anyset, key);
}
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，那么直接返回-1
//在python层面显然会报错
if (hash == -1)
return -1;
}
//底层又调用了set_add_entry，并把hash也作为参数传了进去
return set_add_entry(so, key, hash);
}
static int
set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
{
setentry *table; //指向setentry数组的指针，当然数组里面也是指针
setentry *freeslot;//存放不可hash的entry
setentry *entry;//entry指针
size_t perturb;
size_t mask;//和hash运算
size_t i; //一个整型变量，后面的索引值
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; //获取mask
i = (size_t)hash & mask;//mask和hash进行与运算，得到一个索引
entry = &so->table[i];//获取对应的entry指针
if (entry->key == NULL)
//如果entry->key == NULL，表示当前位置没有被使用
//直接跳到found_unused标签
goto found_unused;
//否则说明有人用了
freeslot = NULL;
perturb = hash; // 将perturb设置为hash
while (1) {
/*
找到entry->hash，之前说了，entry结构体由两部分组成
一个*key，也就是指向真正元素的指针，另一个是hash值
*/
//如果和我们当前的hash值一样的话
if (entry->hash == hash) {
//拿到当前的key
PyObject *startkey = entry->key;
/* startkey cannot be a dummy because the dummy hash field is -1 */
//entry里面的key不可以为dummy态，因为这相当于删除(伪删除)了，hash为-1
assert(startkey != dummy);
//如果已经存在的key和我们添加的key是一样，说明重复了
//而集合内的元素不允许重复
if (startkey == key)
//直接跳转到found_active标签
goto found_active;
//如果是unicode，那么先转化，然后再比较两个key是否一样
if (PyUnicode_CheckExact(startkey)
&& PyUnicode_CheckExact(key)
&& _PyUnicode_EQ(startkey, key))
//如果一样，跳转到found_active标签
goto found_active;
//那么获取头部指针
table = so->table;
//增加startkey的引用计数
Py_INCREF(startkey);
//不一样的话，通过富比较，去比较两个哈希值是否一致
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
//介绍startkey的引用计数
Py_DECREF(startkey);
//如果cmp大于0，比较成功
if (cmp > 0)
//说明索引被人占了
goto found_active;
if (cmp < 0)
//小于0说明比较失败
goto comparison_error;
/* 如果table或者entry改变了，我们必须从头开始 */
if (table != so->table || entry->key != startkey)
//跳转到restart标签
goto restart;
//拿到当前的mask
mask = so->mask; /* help avoid a register spill */
}
//如果不能hash
else if (entry->hash == -1)
//则设置为freeslot
freeslot = entry;
//如果当前索引值加上9小于当前的mask
//#define LINEAR_PROBES 9
if (i + LINEAR_PROBES <= mask) {
//循环9次
for (j = 0 ; j < LINEAR_PROBES ; j++) {
//每次得到下一个entry
entry++;
//如果hash=0，并且对应的key为NULL
if (entry->hash == 0 && entry->key == NULL)
//跳转到found_unused_or_dummy标签
goto found_unused_or_dummy;
if (entry->hash == hash) {
//如果hash值相同，获取对应的key
PyObject *startkey = entry->key;
//key必须不为dummy态
assert(startkey != dummy);
//如果两个key相同，跳转到found_active标签
if (startkey == key)
goto found_active;
//如果为unicode，还是转化后比较
if (PyUnicode_CheckExact(startkey)
&& PyUnicode_CheckExact(key)
&& _PyUnicode_EQ(startkey, key))
goto found_active;
//下面的跟if (i + LINEAR_PROBES <= mask) {上面的是一样的
table = so->table;
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 * 5 + 1 + perturb) & mask重新计算
i = (i * 5 + 1 + perturb) & mask;
//获取新索引对应的entry
entry = &so->table[i];
//如果对应的key为NULL，说明重新计算索引之后找到了可以存储的地方
if (entry->key == NULL)
//跳转到found_unused_or_dummy
goto found_unused_or_dummy;
//否则说明比较倒霉，改变规则重新映射索引依旧冲突
//那么继续循环，比较key是否一致等等
}
//未使用或者dummy，dummy我们是不可以使用的
found_unused_or_dummy:
//如果这个freeslot为NULL，说明是可用的
if (freeslot == NULL)
//跳转
goto found_unused;
//否则，说明为dummy态，那么我们依旧可以使用，正好废物利用
//将used数量加一
so->used++;
//设置key和hash值
freeslot->key = key;
freeslot->hash = hash;
return 0;
//发现未使用的
found_unused:
//将fill和used个数+1
so->fill++;
so->used++;
//设置key和hash值
entry->key = key;
entry->hash = hash;
//检查active态+dummy的entry个数是否小于mask的3/5
if ((size_t)so->fill*5 < mask*3)
//是的话，表示无需扩容
return 0;
//否则要进行扩容
//扩容的规则就是如果active态的entry各式各样如果大于50000，那么两倍扩容，否则四倍扩容
return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
//如果是found_active，表示key重复了
//直接减少一个引用计数即可
found_active:
Py_DECREF(key);
return 0;
//比较失败，同样减少引用计数，返回-1
comparison_error:
Py_DECREF(key);
return -1;
}
总结一下流程就是：
传入hash值，计算出索引值，通过索引值找到对应的entry如果entry->key=NULL，那么将hash和key存到对应的entry如果有key，但是值相同，则不插入，直接减少引入计数。因为不是字典，不存在更新一说如果有key，但是值不相同。那么从该索引往后的9个entry(i + 9 <= mask)，如果存在key为NULL的entry，那么设置进去。如果以上条件都不满足，那么改变策略重新计算索引值，直到找到一个满足key为NULL的entry判断容量问题，如果active态+dummy态的entry个数不小于3/5 * mask，那么扩容，扩容的规则是active态的entry个数是否大于50000，是的话就二倍扩容，否则4倍扩容。
s = set()
item1 = 3 # hash(3) & 7 = 3
s.add(item1)
item2 = "satori" # hash("satori") & 7 = 2
s.add(item2)
7.4 PySetObject扩容
我们之前说PySetObject会改变容量，那么它是如何改变的呢？
static int
set_table_resize(PySetObject *so, Py_ssize_t minused)
{ //显然参数是：PySetObject *指针以及容量大小
//三个setentry *指针
setentry *oldtable, *newtable, *entry;
//oldmask
Py_ssize_t oldmask = so->mask;
//newmask
size_t newmask;
//是否为其申请过内存
int is_oldtable_malloced;
//将PySet_MINSIZE个entry直接copy过来
//因为你既然要扩容的话，那么肯定是这里面存不下了
setentry small_copy[PySet_MINSIZE];
//minused必须大于等于0
assert(minused >= 0);
/* Find the smallest table size > minused. */
/* XXX speed-up with intrinsics */
//newsize扩大二倍，直到大于minused
//所以我们刚才说的大于50000，二倍扩容，否则四倍扩容
//实际上是最终的newsize是比二倍或者四倍扩容的结果要大的
size_t newsize = PySet_MINSIZE;
while (newsize <= (size_t)minused) {
//newsize最大顶多也就是PY_SSIZE_T_MAX + 1，但是基本不可能存储这么多元素
newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.
}
/* Get space for a new table. */
//为新的table申请空间
oldtable = so->table;
assert(oldtable != NULL);
is_oldtable_malloced = oldtable != so->smalltable;
//如果newsize和PySet_MINSIZE(这里的8)相等
if (newsize == PySet_MINSIZE) {
/* A large table is shrinking, or we can't get any smaller. */
//拿到smalltable，就是默认初始化8个entry数组的那哥们
newtable = so->smalltable;
//如果oldtable和newtable一样
if (newtable == oldtable) {
//并且没有dummy态的entry
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. */
//否则的话，dummy的个数一定大于0
assert(so->fill > so->used);
//扔掉dummy态，只把oldtable中active态的拷贝过来
memcpy(small_copy, oldtable, sizeof(small_copy));
//将small_copy重新设置为oldtable
oldtable = small_copy;
}
}
else {
//否则的话，肯定大于8，申请newsize个setentry所需要的空间
newtable = PyMem_NEW(setentry, newsize);
//如果newtable为NULL，那么申请内存失败，返回-1
if (newtable == NULL) {
PyErr_NoMemory();
return -1;
}
}
/* Make the set empty, using the new table. */
//newtable肯定不等于oldtable
assert(newtable != oldtable);
//创建一个能融安newsize个entry的空set
memset(newtable, 0, sizeof(setentry) * newsize);
//将mask设置为newsize-1
//将table设置为newtable
so->mask = newsize - 1;
so->table = newtable;
/* Copy the data over; this is refcount-neutral for active entries;
dummy entries aren't copied over, of course */
//获取newmask
newmask = (size_t)so->mask;
//将原来旧table的setentry数组里面所有setentry的key和hash值全部设置到新的table里面
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);
}
}
} else {
so->fill = so->used;
for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
if (entry->key != NULL && entry->key != dummy) {
set_insert_clean(newtable, newmask, entry->key, entry->hash);
}
}
}
//如果已经为其申请了内存，那么要将其归还给系统堆
if (is_oldtable_malloced)
PyMem_DEL(oldtable);
return 0;
}
//设置元素是通过set_insert_clean设置的
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)
goto found_null; //如果为空则跳转found_null设置key与hash
if (i + LINEAR_PROBES <= mask) {
//如果没有还是老规矩，遍历之后的9个entry
for (j = 0; j < LINEAR_PROBES; j++) {
entry++;
//找到空的entry，那么跳转到found_null设置key与hash
if (entry->key == NULL)
goto found_null;
}
}
// 没有找到，那么改变规则，重新计算索引
perturb >>= PERTURB_SHIFT;
i = (i * 5 + 1 + perturb) & mask;
}
found_null:
//设置key与hash
entry->key = key;
entry->hash = hash;
}
7.5 删除元素
static PyObject *
set_remove(PySetObject *so, PyObject *key)
{
PyObject *tmpkey;
int rv;
//将该值设置为dummy态
rv = set_discard_key(so, key);
if (rv < 0) {
//类型检测
if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
return NULL;
PyErr_Clear();
//对该值重新初始化为frozenset
tmpkey = make_new_set(&PyFrozenSet_Type, key);
if (tmpkey == NULL)
return NULL;
//将该key设置为空
rv = set_discard_key(so, tmpkey);
Py_DECREF(tmpkey);
if (rv < 0)
return NULL;
}
//如果没有找到则报错
if (rv == DISCARD_NOTFOUND) {
_PyErr_SetKeyError(key);
return NULL;
}
Py_RETURN_NONE;
}
//里面调用了set_discard_key方法
static int
set_discard_key(PySetObject *so, PyObject *key)
{
Py_hash_t hash;
//老套路，先计算hash值
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1) {
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
//将hash值也船进入
return set_discard_entry(so, key, hash);
}
static int
set_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
{
setentry *entry;
PyObject *old_key;
////通过传入的key和hash找到该entry
//并且hash对应的key要和传入的key是一样的
entry = set_lookkey(so, key, hash);
//如果entry为NULL，直接返回-1
if (entry == NULL)
return -1;
//如果entry不为NULL，但是对应的key为NULL
//返回DISCARD_NOTFOUND
if (entry->key == NULL)
return DISCARD_NOTFOUND;
//获取要删除的key
old_key = entry->key;
//并将entry的key设置为dummy
entry->key = dummy;
//hash值设置为-1
entry->hash = -1;
//减少使用数量
so->used--;
//减少引用计数
Py_DECREF(old_key);
//返回DISCARD_FOUND
return DISCARD_FOUND;
}
可以看到集合添加、删除元素和字典是有些相似的，毕竟底层都是使用了hash表嘛
7.6 集合的运算(交集)
在python中使用集合的时候，可以取两个集合的交集、并集、差集、对称差集等等，这里介绍一下交集，其余的可以自行看源码研究(Objects/setobject.c)。
static PyObject *
set_intersection(PySetObject *so, PyObject *other)
{ //显然是两个指针，一个是PySetObject *，一个是PyObject *
//result，显然是用来存储两者交集运算的结果的
PySetObject *result;
//不看下面代码的话，很难知道这几个PyObject * 是用来干啥的
//我们下面代码再看看这是干啥的
PyObject *key, *it, *tmp;
//这个肯定是hash值
Py_hash_t hash;
int rv;
//如果两个对象一样
if ((PyObject *)so == other)
//直接返回其中一个的拷贝即可
return set_copy(so);
//这行代码表示创建一个空的PySetObject *
result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
//如果result == NULL，说明创建失败
if (result == NULL)
return NULL;
//检测other是不是PySetObject *
if (PyAnySet_Check(other)) {
//初始索引为0
Py_ssize_t pos = 0;
//setentry *
setentry *entry;
//如果other元素的个数大于so
if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
//就把so和other进行交换
tmp = (PyObject *)so;
so = (PySetObject *)other;
other = tmp;
}
//从少的那一方的开头开始便利
while (set_next((PySetObject *)other, &pos, &entry)) {
//拿到key和hash
key = entry->key;
hash = entry->hash;
//传入other的key和hash，在so中去找
rv = set_contains_entry(so, key, hash);
if (rv < 0) {
//如果对应的rv不存在，那么显然就没有
Py_DECREF(result);
return NULL;
}
if (rv) {
//存在的话设置进result里面
if (set_add_entry(result, key, hash)) {
Py_DECREF(result);
return NULL;
}
}
}
//直接返回
return (PyObject *)result;
}
//如果不是PyObject *
//那么获取其对应的迭代器，相当于python中的__iter__
it = PyObject_GetIter(other);
//如果是NULL，降低其引用计数
if (it == NULL) {
Py_DECREF(result);
//返回NULL
return NULL;
}
//下面的没必要分析了，在python中，只能set和set(或者frozenset)之间才可以取交集
while ((key = PyIter_Next(it)) != NULL) {
hash = PyObject_Hash(key);
if (hash == -1)
goto error;
rv = set_contains_entry(so, key, hash);
if (rv < 0)
goto error;
if (rv) {
if (set_add_entry(result, key, hash))
goto error;
}
Py_DECREF(key);
}
Py_DECREF(it);
if (PyErr_Occurred()) {
Py_DECREF(result);
return NULL;
}
return (PyObject *)result;
error:
Py_DECREF(it);
Py_DECREF(result);
Py_DECREF(key);
return NULL;
}
7.7 まとめ
可以看到，剖析set的时候话很少。主要是有了剖析dict的经验，因此再剖析set的时候就很简单了。并且在python中还有一个frozenset，就是不可变的set。而且不像list和tuple，tuple还是有很多特殊的，并不单单只是不可变的list，从具有自己独自的结构体就能看出来。而frozenset和set都是一个结构体，只有一个PySetObject，没有PyFrozenSetObject，我们在看PySetObject的时候，发现里面有一个hash值，如果是frozenset的话，那么hash值是不为-1的，因为它不可以添加、删除元素，是不可变对象。因此frozenset就不单独开一个章节介绍了，可以的话，自己看一下源码。源码还是Object/setobject.c。