淺析Python是如何實(shí)現(xiàn)集合的

更新時(shí)間：2022年12月02日 11:16:26 作者：古明地覺(jué)

之前我們介紹過(guò)字典的實(shí)現(xiàn)原理，它底層是基于哈希表實(shí)現(xiàn)的，而集合也是如此。本次我們來(lái)聊一下 Python 的集合是怎么實(shí)現(xiàn)的，希望對(duì)大家有所幫助

楔子

有幾天沒(méi)有更新 Python 文章了，本次我們來(lái)聊一下 Python 的集合是怎么實(shí)現(xiàn)的？之前我們介紹過(guò)字典的實(shí)現(xiàn)原理，它底層是基于哈希表實(shí)現(xiàn)的，而集合也是如此。

并且字典和集合實(shí)現(xiàn)的哈希表是一樣的，在計(jì)算哈希值、解決索引沖突等方面，兩者沒(méi)有任何區(qū)別。唯一的區(qū)別就是存儲(chǔ)的 entry 不同，字典的 entry 里面包含了 key、value 和 key 的哈希值，而集合的 entry 里面只包含 key 和 key 的哈希值。

事實(shí)上，集合就類似于沒(méi)有value的字典。

集合的使用場(chǎng)景

那么集合都有哪些用處呢？

1）去重

chars?=?["a",?"b",?"a",?"c",?"c"]

print(
????list(set(chars))
)??#?['b',?'a',?'c']

再比如你需要監(jiān)聽(tīng)一個(gè)隊(duì)列，處理接收到的消息，但每一條消息都有一個(gè)編號(hào)，要保證具有相同編號(hào)的消息只能被處理一次，要怎么做呢？

顯然集合此時(shí)就派上用場(chǎng)了，我們可以創(chuàng)建一個(gè)集合，每來(lái)一條消息，就檢測(cè)它的編號(hào)是否在集合中。如果存在，則說(shuō)明消息已經(jīng)被處理過(guò)了，忽略掉；如果不存在，說(shuō)明消息還沒(méi)有被處理，那么就將它的編號(hào)添加到集合中，然后處理消息。

這里暫時(shí)不考慮消費(fèi)失敗等情況，我們假設(shè)每條消息都是能處理成功的。

2）判斷某個(gè)序列是否包含指定的多個(gè)元素

data?=?["S",?"A",?"T",?"O",?"R",?"I"]

#?現(xiàn)在要判斷?data?是否包含?"T"、"R"?和?"I"
#?如果使用列表的話
print(
????"T"?in?data?and?"R"?in?data?and?"I"?in?data
)??#?True

#?顯然這是比較麻煩的，于是我們可以使用集合
print(
????set(data)?>=?{"T",?"R",?"I"}
)??#?True

同理，基于此方式，我們也可以檢測(cè)一個(gè)字典是否包含指定的多個(gè) key。

data?=?{
????"name":?"satori",
????"age":?17,
????"gender":?"female"
}

#?判斷字典是否包含?name、age、gender?三個(gè)?key
print(
????data.keys()?>=?{"name",?"age",?"gender"}
)??#?True

#?字典的?keys?方法會(huì)返回一個(gè)?dict_keys?對(duì)象
# 該對(duì)象具備集合的性質(zhì)，可以直接和集合進(jìn)行運(yùn)算

顯然對(duì)于這種需求，有了集合就方便多了。

集合的 API

然后我們來(lái)羅列一下集合支持的 API，在使用集合的時(shí)候要做到心中有數(shù)。

#?如果要?jiǎng)?chuàng)建一個(gè)空集合，那么要使用?set()
#?寫(xiě)成?{}?的話，解釋器會(huì)認(rèn)為這是一個(gè)空字典
s?=?{1,?2,?3}

#?添加元素，時(shí)間復(fù)雜度是?O(1)
s.add(4)
print(s)??#?{1,?2,?3,?4}

#?刪除指定的元素，如果元素不存在則報(bào)出?KeyError
#?時(shí)間復(fù)雜度為?O(1)
s.remove(2)
print(s)??#?{1,?3,?4}

#?刪除指定的元素，如果元素不存在則什么也不做
#?時(shí)間復(fù)雜度為?O(1)
s.discard(666)
print(s)??#?{1,?3,?4}

#?隨機(jī)彈出一個(gè)元素并返回
#?時(shí)間復(fù)雜度為?O(1)
print(s.pop())??#?1
print(s)??#?{3,?4}

#?清空一個(gè)集合
s.clear()
print(s)??#?set()

#?還有一些?API，但我們更推薦使用操作符的方式
#?兩個(gè)集合取交集
print({1,?2}?&?{2,?3})??#?{2}

#?兩個(gè)集合取并集
print({1,?2}?|?{2,?3})??#?{1,?2,?3}

#?兩個(gè)集合取差集
#?s1?-?s2，返回在?s1、但不在?s2?當(dāng)中的元素
print({1,?2,?3}?-?{2,?3,?4})??#?{1}

#?兩個(gè)集合取對(duì)稱差集
#?s1?^?s2，返回既不在?s1、也不在?s2?當(dāng)中的元素
print({1,?2,?3}?^?{2,?3,?4})??#?{1,?4}

#?判斷兩個(gè)集合是否相等，也就是內(nèi)部的元素是否完全一致
#?順序無(wú)所謂，只比較元素是否全部相同
print({1,?2,?3}?==?{3,?2,?1})??#?True
print({1,?2,?3}?==?{1,?2,?4})??#?False

#?判斷一個(gè)集合是否包含另一個(gè)集合的所有元素
#?假設(shè)有兩個(gè)集合 s1 和 s2：
#????如果 s1 的元素都在 s2 中，那么 s2 >= s1；
#????如果 s2 的元素都在 s1 中，那么 s1 >= s2；
#????如果 s1 和元素和 s2 全部相同，那么 s1 == s2；
print({1,?2,?3}?>?{1,?2})??#?True
print({1,?2,?3}?>=?{1,?2,?3})??#?True

以上就是集合支持的一些 API，還是很簡(jiǎn)單的，下面來(lái)重點(diǎn)看一下集合的底層結(jié)構(gòu)。

集合的底層結(jié)構(gòu)

集合的數(shù)據(jù)結(jié)構(gòu)定義在 setobject.h 中，那么它長(zhǎng)什么樣子呢？

typedef?struct?{
????PyObject_HEAD
????Py_ssize_t?fill;
????Py_ssize_t?used;????????????
????Py_ssize_t?mask;
????setentry?*table;
????Py_hash_t?hash;???
????Py_ssize_t?finger;??????????
????setentry?smalltable[PySet_MINSIZE];
????PyObject?*weakreflist;????
}?PySetObject;

解釋一下這些字段的含義：

PyObject_HEAD：定長(zhǎng)對(duì)象的頭部信息，但集合顯然是一個(gè)變長(zhǎng)對(duì)象。所以和字典一樣，肯定有其它字段充當(dāng) ob_size；
fill：等于 active 態(tài)的 entry 數(shù)量加上 dummy 態(tài)的 entry 數(shù)量。和字典類似，一個(gè) entry 就是哈希表里面的一個(gè)元素，類型為 setentry，因此在集合里面一個(gè) entry 就是一個(gè) setentry 結(jié)構(gòu)體實(shí)例；
used：等于 active 態(tài)的 entry 數(shù)量，顯然這個(gè) used 充當(dāng)了 ob_size，也就是集合的元素個(gè)數(shù)；
mask：在看字典源碼的時(shí)候，我們也見(jiàn)到了 mask，它用于和哈希值進(jìn)行按位與、計(jì)算索引，并且這個(gè) mask 等于哈希表的容量減 1，為什么呢？假設(shè)哈希值等于 v，哈希表容量是 n，那么通過(guò) v 對(duì) n 取模即可得到一個(gè)位于 0 到 n-1 之間的數(shù)。但是取模運(yùn)算的效率不高，而 v&(n-1) 的作用等價(jià)于 v%n，并且速度更快，所以 mask 的值要等于哈希表的容量減 1。但是注意，只有在 n 為 2 的冪次方的時(shí)候， v&(n-1) 和 v%n 才是完全等價(jià)的，所以哈希表的容量要求是 2 的冪次方，就是為了將取模運(yùn)算優(yōu)化成按位與運(yùn)算。
table：指向 setentry 數(shù)組的指針，而這個(gè) setentry 數(shù)組可以是下面的 smalltable，也可以是單獨(dú)申請(qǐng)的一塊內(nèi)存；
hash：集合的哈希值，只適用于不可變集合；
finger：用于 pop 一個(gè)元素；
smalltable：一個(gè) setentry 類型的數(shù)組，集合的元素就存在里面。但我們知道，變長(zhǎng)對(duì)象的內(nèi)部不會(huì)存儲(chǔ)具體元素，而是會(huì)存儲(chǔ)一個(gè)指針，該指針指向的內(nèi)存區(qū)域才是用來(lái)存儲(chǔ)具體元素的。這樣當(dāng)擴(kuò)容的時(shí)候，只需要讓指針指向新的內(nèi)存區(qū)域即可，從而方便維護(hù)。沒(méi)錯(cuò)，對(duì)于集合而言，只有在容量不超過(guò) 8 的時(shí)候，元素才會(huì)存在里面；而一旦超過(guò)了8，那么會(huì)使用 malloc 單獨(dú)申請(qǐng)內(nèi)存；
weakreflist：弱引用列表，不做深入討論；

有了字典的經(jīng)驗(yàn)，再看集合會(huì)簡(jiǎn)單很多。然后是 setentry，用于承載集合內(nèi)的元素，那么它的結(jié)構(gòu)長(zhǎng)什么樣呢？相信你能夠猜到。

typedef?struct?{
????PyObject?*key;?
????Py_hash_t?hash;
}?setentry;

相比字典少了一個(gè) value，這是顯而易見(jiàn)的。因此集合的結(jié)構(gòu)很清晰了，假設(shè)有一個(gè)集合 {3.14, "abc", 666}，那么它的結(jié)構(gòu)如下：

由于集合里面只有三個(gè)元素，所以它們都會(huì)存在 smalltable 數(shù)組里面，我們通過(guò) ctypes 來(lái)證明這一點(diǎn)。

from?ctypes?import?*

class?PyObject(Structure):
????_fields_?=?[
????????("ob_refcnt",?c_ssize_t),
????????("ob_type",?c_void_p),
????]

class?SetEntry(Structure):
????_fields_?=?[
????????("key",?POINTER(PyObject)),
????????("hash",?c_longlong)
????]

class?PySetObject(PyObject):
????_fields_?=?[
????????("fill",?c_ssize_t),
????????("used",?c_ssize_t),
????????("mask",?c_ssize_t),
????????("table",?POINTER(SetEntry)),
????????("hash",?c_long),
????????("finger",?c_ssize_t),
????????("smalltable",?(SetEntry?*?8)),
????????("weakreflist",?POINTER(PyObject)),
????]


s?=?{3.14,?"abc",?666}
#?先來(lái)打印一下哈希值
print('hash(3.14)?=',?hash(3.14))
print('hash("abc")?=',?hash("abc"))
print('hash(666)?=',?hash(666))
"""
hash(3.14)?=?322818021289917443
hash("abc")?=?8036038346376407734
hash(666)?=?666
"""

#?獲取PySetObject結(jié)構(gòu)體實(shí)例
py_set_obj?=?PySetObject.from_address(id(s))
#?遍歷smalltable，打印索引、和哈希值
for?index,?entry?in?enumerate(py_set_obj.smalltable):
????print(index,?entry.hash)
"""
0?0
1?0
2?666
3?322818021289917443
4?0
5?0
6?8036038346376407734
7?0
"""

根據(jù)輸出的哈希值我們可以斷定，這三個(gè)元素確實(shí)存在了 smalltable 數(shù)組里面，并且 666 存在了數(shù)組索引為 2 的位置、3.14 存在了數(shù)組索引為 3 的位置、"abc" 存在了數(shù)組索引為 6 的位置。

當(dāng)然，由于哈希值是隨機(jī)的，所以每次執(zhí)行之后打印的結(jié)果都可能不一樣，但是整數(shù)除外，它的哈希值就是它本身。既然哈希值不一樣，那么每次映射出的索引也可能不同，但總之這三個(gè)元素是存在 smalltable 數(shù)組里面的。

然后我們?cè)倏疾煲幌缕渌淖侄危?/p>

s?=?{3.14,?"abc",?666}
py_set_obj?=?PySetObject.from_address(id(s))
# 集合里面有 3 個(gè)元素，所以 fill 和 used 都是 3
print(py_set_obj.fill)??#?3
print(py_set_obj.used)??#?3

# 將集合元素全部刪除
# 這里不能用 s.clear()，原因一會(huì)兒說(shuō)
for?_?in?range(len(s)):
????s.pop()
????
# 我們知道哈希表在刪除元素的時(shí)候是偽刪除
#?所以 fill 不變，但是 used 每次會(huì)減 1
print(py_set_obj.fill)??#?3
print(py_set_obj.used)??#?0

fill 成員維護(hù)的是 active 態(tài)的 entry 數(shù)量加上 dummy 態(tài)的 entry 數(shù)量，所以刪除元素時(shí)它的大小是不變的；但 used 成員的值每次會(huì)減 1，因?yàn)樗S護(hù)的是 active 態(tài)的 entry 的數(shù)量。所以只要不涉及元素的刪除，那么這兩者的大小是相等的。

然后我們上面說(shuō)不能用 s.clear()，因?yàn)樵摲椒ū硎厩蹇占?，此時(shí)會(huì)重置為初始狀態(tài)，然后 fill 和 used 都會(huì)是 0，我們就觀察不到想要的現(xiàn)象了。

刪除集合所有元素之后，我們?cè)偻锩嫣砑釉?，看看是什么效果?/p>

s?=?{3.14,?"abc",?666}
py_set_obj?=?PySetObject.from_address(id(s))
for?_?in?range(len(s)):
????s.pop()

#?添加一個(gè)元素
s.add(0)
print(py_set_obj.fill)??#?3
print(py_set_obj.used)??#?1

多次執(zhí)行的話，會(huì)發(fā)現(xiàn)打印的結(jié)果可能是 3、1，也有可能是 4、1。至于原因，有了字典的經(jīng)驗(yàn)，相信你肯定能猜到。

首先添加元素之后，used 肯定為 1。至于 fill，如果添加元素的時(shí)候，正好撞上了一個(gè) dummy 態(tài)的 entry，那么將其替換掉，此時(shí) fill 不變，仍然是 3；如果沒(méi)有撞上 dummy 態(tài)的 entry，而是添加在了新的位置，那么 fill 就是 4。

for?i?in?range(1,?10):
????s.add(i)
print(py_set_obj.fill)??#?10
print(py_set_obj.used)??#?10
s.pop()
print(py_set_obj.fill)??#?10
print(py_set_obj.used)??#?9

在之前代碼的基礎(chǔ)上，繼續(xù)添加 9 個(gè)元素，然后 used 變成了10，這很好理解，因?yàn)榇藭r(shí)集合有 10 個(gè)元素。但 fill 也是10，這是為什么？很簡(jiǎn)單，因?yàn)楣１頂U(kuò)容了，擴(kuò)容時(shí)會(huì)刪除 dummy 態(tài)的 entry，所以 fill 和 used 是相等的。同理，如果再繼續(xù) pop，那么 fill 和 used 就又變得不相等了。

集合的創(chuàng)建

集合的結(jié)構(gòu)我們已經(jīng)清楚了，再來(lái)看看它的初始化過(guò)程。我們調(diào)用類 set，傳入一個(gè)可迭代對(duì)象，便可創(chuàng)建一個(gè)集合，這個(gè)過(guò)程是怎樣的呢？

PyObject?*
PySet_New(PyObject?*iterable)
{??
????//底層調(diào)用了make_new_set
????return?make_new_set(&PySet_Type,?iterable);
}

底層提供了PySet_New函數(shù)用于創(chuàng)建一個(gè)集合，接收一個(gè)可迭代對(duì)象，然后調(diào)用 make_new_set 進(jìn)行創(chuàng)建。

static?PyObject?*
make_new_set(PyTypeObject?*type,?PyObject?*iterable)
{??
????// PySetObject?*指針
????PySetObject?*so;
??
????// 申請(qǐng)集合所需要的內(nèi)存
????so?=?(PySetObject?*)type->tp_alloc(type,?0);
????//申請(qǐng)失敗，返回 NULL
????if?(so?==?NULL)
????????return?NULL;
??
????// fill 和 used 初始都為 0
????so->fill?=?0;
????so->used?=?0;
????// PySet_MINSIZE 默認(rèn)為 8
????// 而 mask 等于哈希表容量減 1，所以初始值是 7
????so->mask?=?PySet_MINSIZE?-?1;
????// 初始化的時(shí)候，setentry 數(shù)組顯然是 smalltable
????// 所以讓 table 指向 smalltable 數(shù)組
????so->table?=?so->smalltable;
????// 初始 hash 值為 -1
????so->hash?=?-1;
????// finger為0
????so->finger?=?0;
????// 弱引用列表為NULL
????so->weakreflist?=?NULL;
????//以上只是初始化，如果可迭代對(duì)象不為 NULL
????//那么把元素依次設(shè)置到集合中
????if?(iterable?!=?NULL)?{
????//該過(guò)程是通過(guò) set_update_internal 函數(shù)實(shí)現(xiàn)的
????//該函數(shù)內(nèi)部會(huì)遍歷 iterable，將迭代出的元素依次添加到集合里面
????????if?(set_update_internal(so,?iterable))?{
????????????Py_DECREF(so);
????????????return?NULL;
????????}
????}
????//返回初始化完成的set
????return?(PyObject?*)so;
}

整個(gè)過(guò)程沒(méi)什么難度，非常好理解。