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

更新時間：2022年12月02日 11:16:26 作者：古明地覺

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

楔子

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

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

事實上，集合就類似于沒有value的字典。

集合的使用場景

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

1）去重

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

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

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

顯然集合此時就派上用場了，我們可以創(chuàng)建一個集合，每來一條消息，就檢測它的編號是否在集合中。如果存在，則說明消息已經(jīng)被處理過了，忽略掉；如果不存在，說明消息還沒有被處理，那么就將它的編號添加到集合中，然后處理消息。

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

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

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

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

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

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

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

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

集合的 API

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

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

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

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

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

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

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

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

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

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

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

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

#?判斷一個集合是否包含另一個集合的所有元素
#?假設(shè)有兩個集合 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é)構(gòu)。

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

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

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

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

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

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

由于集合里面只有三個元素，所以它們都會存在 smalltable 數(shù)組里面，我們通過 ctypes 來證明這一點。

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}
#?先來打印一下哈希值
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)體實例
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ù)輸出的哈希值我們可以斷定，這三個元素確實存在了 smalltable 數(shù)組里面，并且 666 存在了數(shù)組索引為 2 的位置、3.14 存在了數(shù)組索引為 3 的位置、"abc" 存在了數(shù)組索引為 6 的位置。

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

然后我們再考察一下其它的字段：

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

# 將集合元素全部刪除
# 這里不能用 s.clear()，原因一會兒說
for?_?in?range(len(s)):
????s.pop()
????
# 我們知道哈希表在刪除元素的時候是偽刪除
#?所以 fill 不變，但是 used 每次會減 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ù)量，所以刪除元素時它的大小是不變的；但 used 成員的值每次會減 1，因為它維護(hù)的是 active 態(tài)的 entry 的數(shù)量。所以只要不涉及元素的刪除，那么這兩者的大小是相等的。

然后我們上面說不能用 s.clear()，因為該方法表示清空集合，此時會重置為初始狀態(tài)，然后 fill 和 used 都會是 0，我們就觀察不到想要的現(xiàn)象了。

刪除集合所有元素之后，我們再往里面添加元素，看看是什么效果：

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

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

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

首先添加元素之后，used 肯定為 1。至于 fill，如果添加元素的時候，正好撞上了一個 dummy 態(tài)的 entry，那么將其替換掉，此時 fill 不變，仍然是 3；如果沒有撞上 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 個元素，然后 used 變成了10，這很好理解，因為此時集合有 10 個元素。但 fill 也是10，這是為什么？很簡單，因為哈希表擴(kuò)容了，擴(kuò)容時會刪除 dummy 態(tài)的 entry，所以 fill 和 used 是相等的。同理，如果再繼續(xù) pop，那么 fill 和 used 就又變得不相等了。

集合的創(chuàng)建

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

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

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

static?PyObject?*
make_new_set(PyTypeObject?*type,?PyObject?*iterable)
{??
????// PySetObject?*指針
????PySetObject?*so;
??
????// 申請集合所需要的內(nèi)存
????so?=?(PySetObject?*)type->tp_alloc(type,?0);
????//申請失敗，返回 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;
????// 初始化的時候，setentry 數(shù)組顯然是 smalltable
????// 所以讓 table 指向 smalltable 數(shù)組
????so->table?=?so->smalltable;
????// 初始 hash 值為 -1
????so->hash?=?-1;
????// finger為0
????so->finger?=?0;
????// 弱引用列表為NULL
????so->weakreflist?=?NULL;
????//以上只是初始化，如果可迭代對象不為 NULL
????//那么把元素依次設(shè)置到集合中
????if?(iterable?!=?NULL)?{
????//該過程是通過 set_update_internal 函數(shù)實現(xiàn)的
????//該函數(shù)內(nèi)部會遍歷 iterable，將迭代出的元素依次添加到集合里面
????????if?(set_update_internal(so,?iterable))?{
????????????Py_DECREF(so);
????????????return?NULL;
????????}
????}
????//返回初始化完成的set
????return?(PyObject?*)so;
}

整個過程沒什么難度，非常好理解。