楔子

本篇文章來(lái)聊一聊 Python 的集合是怎么實(shí)現(xiàn)的？前面我們介紹了字典的實(shí)現(xiàn)原理，它底層是基于哈希表實(shí)現(xiàn)的，而集合也是如此。

事實(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)添加到集合中，然后處理消息。

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ù)。

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

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

# 刪除指定的元素，如果元素不存在，會(huì)拋出 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è)元素并返回，如果集合為空，會(huì)拋出 KeyError
# 時(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)單的。

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

集合和字典的內(nèi)部都使用了哈希表，但字典的哈希表采用兩個(gè)數(shù)組實(shí)現(xiàn)，而集合的哈希表采用一個(gè)數(shù)組實(shí)現(xiàn)。因此對(duì)于集合來(lái)說(shuō)，這個(gè)數(shù)組不僅要存儲(chǔ) entry，并且映射出的索引也是該數(shù)組的索引。

下面看一下集合的底層結(jié)構(gòu)長(zhǎng)什么樣子。

// Include/cpython/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

定長(zhǎng)對(duì)象的頭部信息，但集合顯然是一個(gè)變長(zhǎng)對(duì)象，所以和字典一樣，肯定有其它字段充當(dāng) ob_size。

Py_ssize_t fill

Active 態(tài)的 entry 數(shù)量加上 Dummy 態(tài)的 entry 數(shù)量。一個(gè) entry 就是哈希表里的一個(gè)元素，類型為 setentry，因此在集合里面，一個(gè) entry 就是一個(gè) setentry 結(jié)構(gòu)體實(shí)例。當(dāng)刪除集合的 entry 時(shí)，也必須是偽刪除，因?yàn)橐ＷC探測(cè)鏈不斷裂。如果 entry 被偽刪除了，那么它便處于 Dummy 態(tài)。

Py_ssize_t used

Active 態(tài)的 entry 數(shù)量，顯然這個(gè) used 充當(dāng)了 ob_size，也就是集合的元素個(gè)數(shù)；

Py_ssize_t 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)算。

setentry *table

指向 setentry 數(shù)組首元素的指針，這個(gè) setentry 數(shù)組可以是下面的 smalltable，也可以是單獨(dú)申請(qǐng)的一塊內(nèi)存；

Py_hash_t hash

集合的哈希值，只適用于不可變集合；

Py_ssize_t finger

用于 pop 方法；

setentry smalltable[8]

一個(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)什么樣呢？相信你能夠猜到。

// Include/cpython/setobject.h
#define PySet_MINSIZE 8

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，打印索引和 key 的哈希值
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ù)量。所以在不涉及元素的刪除時(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ò)程是怎樣的呢？

// Objects/setobject.c
PyObject *
PySet_New(PyObject *iterable)
{
    return make_new_set(&PySet_Type, iterable);
}

static PyObject *
make_new_set(PyTypeObject *type, PyObject *iterable)
{
    assert(PyType_Check(type));
    PySetObject *so;
    // 為 PySetObject 申請(qǐng)內(nèi)存，初始容量為 8
    so = (PySetObject *)type->tp_alloc(type, 0);
    if (so == NULL)
        return NULL;
    // 對(duì)字段做初始化
    so->fill = 0;
    so->used = 0;
    so->mask = PySet_MINSIZE - 1;
    // 哈希表容量為 8 時(shí)，元素會(huì)存在 smalltable 里面
    // 因此直接將 smalltable 賦值給 table
    so->table = so->smalltable;
    so->hash = -1;
    so->finger = 0;
    so->weakreflist = NULL;

    if (iterable != NULL) {
        // 遍歷 iterable，將迭代出的元素添加到集合中
        // 關(guān)于這個(gè)函數(shù)，我們之后再介紹
        if (set_update_internal(so, iterable)) {
            Py_DECREF(so);
            return NULL;
        }
    }

    return (PyObject *)so;
}

可以看到，集合的創(chuàng)建過(guò)程非常簡(jiǎn)單。

字典和集合的哈希表的差異

字典和集合都是采用哈希表實(shí)現(xiàn)的，但字典的哈希表使用了兩個(gè)數(shù)組，而集合的哈希表使用了一個(gè)數(shù)組，我們對(duì)比一下兩者的差異。

假設(shè)有一個(gè)字典和一個(gè)集合，字典包含三個(gè)鍵值對(duì)，分別是 "a": 1、"b": 2、"c": 3，集合包含三個(gè)元素，分別是 "a"、"b"、"c"，然后映射出的索引分別是 2、5、3。

圖片

注：為了方便，這里的圖畫(huà)得沒(méi)有那么嚴(yán)謹(jǐn)。比如集合的哈希表，里面的元素直接用字符串代替了，但其實(shí)它存儲(chǔ)的是 setentry entry，而 entry 的 key 字段指向的才是字符串。當(dāng)然這里我們心里清楚就好。

在介紹字典的時(shí)候我們說(shuō)過(guò)，早期的字典內(nèi)部的哈希表也是使用一個(gè)數(shù)組實(shí)現(xiàn)，除了 entry 會(huì)多存儲(chǔ)一個(gè) value 之外，其它和當(dāng)前的集合是類似的。

但如果只使用一個(gè)數(shù)組實(shí)現(xiàn)，會(huì)導(dǎo)致內(nèi)存浪費(fèi)嚴(yán)重，因?yàn)楣１肀仨氁ＷC一定的稀疏性。所以后續(xù)字典內(nèi)部的哈希表采用兩個(gè)數(shù)組實(shí)現(xiàn)，將存儲(chǔ)鍵值對(duì)的數(shù)組的長(zhǎng)度壓縮到原來(lái)的 2/3，至于映射出的索引則由另一個(gè)數(shù)組（哈希索引數(shù)組）來(lái)承載。

雖然引入新的數(shù)組會(huì)帶來(lái)額外的內(nèi)存開(kāi)銷（假設(shè)大小為 m 字節(jié)），但存儲(chǔ)鍵值對(duì)的數(shù)組不用再浪費(fèi) 1/3 的空間（假設(shè)大小為 n 字節(jié)），只要 m 小于 n，那么使用兩個(gè)數(shù)組就會(huì)更加節(jié)省內(nèi)存。而在介紹字典的時(shí)候我們也看到了，m 是遠(yuǎn)小于 n 的。

那么問(wèn)題來(lái)了，為什么集合不使用兩個(gè)數(shù)組呢？很簡(jiǎn)單，因?yàn)槭褂靡粋€(gè)數(shù)組實(shí)現(xiàn)哈希表會(huì)更簡(jiǎn)單，雖然也更加浪費(fèi)內(nèi)存。而集合和字典在哈希表的實(shí)現(xiàn)上之所以區(qū)別對(duì)待，還是使用頻率的問(wèn)題，解釋器內(nèi)部極度依賴字典，比如全局變量就是使用字典存儲(chǔ)的。

可以說(shuō)字典的效率高度影響著整個(gè)解釋器的效率，字典的內(nèi)存大小高度影響著解釋器的內(nèi)存占用。因此 Python 除了優(yōu)化字典的搜索性能之外，還要盡可能地減少字典的內(nèi)存大小。所以字典搞出了分離表、結(jié)合表，以及根據(jù) key 是否全部是字符串來(lái)選擇使用不同的結(jié)構(gòu)體表示 entry，這一切操作都是為了將字典的內(nèi)存占用降到最低。

至于集合，解釋器對(duì)它的依賴就很小了，所以內(nèi)部的哈希表，只采用了一個(gè)數(shù)組實(shí)現(xiàn)。雖然會(huì)有內(nèi)存浪費(fèi)，但無(wú)傷大雅。

好，回到上面的例子，如果將字典的鍵值對(duì) "b": 2 和集合的元素 "b" 刪掉，那么它們的結(jié)構(gòu)會(huì)發(fā)生什么變化呢？

圖片

"b" 映射出的索引為 5，因此對(duì)于字典來(lái)說(shuō)，會(huì)將索引為 5 的哈希槽的值設(shè)置為 dummy。然后是鍵值對(duì)數(shù)組，會(huì)將指定的 entry 的 me_key 和 me_value 字段全部設(shè)置為 NULL，相當(dāng)于回歸到了初始狀態(tài)。

需要注意的是，數(shù)組一旦申請(qǐng)，那么 entry 的空間就已經(jīng)有了，只是 me_key 和 me_value 字段均為 NULL。而所謂添加鍵值對(duì)，本質(zhì)上也是修改指定 entry 的 me_key 和 me_value 字段。

對(duì)于集合來(lái)說(shuō)，它只有一個(gè)數(shù)組，這個(gè)數(shù)組不僅要存儲(chǔ)鍵值對(duì)，它的索引還表示 key 映射出的索引，當(dāng)然這里的 key 指的就是集合的元素。"b" 映射出的索引為 5，所以將數(shù)組中索引為 5 的 entry->key 設(shè)置為 dummy。

但要注意的是，字典的 dummy 是一個(gè)整數(shù)，值為 -2（DKIX_DUMMY），因?yàn)楣Ｋ饕龜?shù)組存儲(chǔ)的是整數(shù)。key 映射出的索引是哈希索引數(shù)組的索引，如果對(duì)應(yīng)的哈希槽存儲(chǔ)的值是 -2，說(shuō)明當(dāng)前搜索的 key 對(duì)應(yīng)的 entry 被刪除了，應(yīng)該繼續(xù)向后搜索。

而集合的 dummy 是一個(gè)結(jié)構(gòu)體指針，定義如下：

// Objects/setobject.c
static PyObject _dummy_struct;
#define dummy (&_dummy_struct)

因?yàn)榧蟽?nèi)部的哈希表只使用了一個(gè)數(shù)組，該數(shù)組存儲(chǔ)的是 setentry。如果在查找的時(shí)候，發(fā)現(xiàn)對(duì)應(yīng)的 entry 的 key 等于 dummy，就知道該 entry 被刪除了，應(yīng)該繼續(xù)向后搜索。

好，繼續(xù)回到上面的例子，假設(shè)這時(shí)候再給字典添加一個(gè)鍵值對(duì) "d": 4，給集合添加一個(gè)元素 "d"，而字符串 "d" 映射出的索引也是 5，那么結(jié)構(gòu)是怎樣的呢？

圖片

對(duì)于字典來(lái)說(shuō)，鍵值對(duì)始終按照先來(lái)后到的順序添加在鍵值對(duì)數(shù)組中，然后將它在鍵值對(duì)數(shù)組中的索引保存在指定的哈希槽中。由于索引為 5 的哈希槽保存的是 -2，處于 Dummy 態(tài)，因此直接將它設(shè)置為 3。

同理對(duì)于集合來(lái)說(shuō)也是類似的。數(shù)組索引為 5 的位置保存的值等于 dummy，處于 Dummy 態(tài)，說(shuō)明該元素被刪除了，那么直接替換掉。因此整個(gè)過(guò)程的邏輯很簡(jiǎn)單：由于索引會(huì)存在沖突，所以元素刪除之后，需要寫入一個(gè)特殊的墓碑值，也就是這里的 dummy，因?yàn)橐ＷC探測(cè)鏈不斷裂。但如果集合后續(xù)添加元素時(shí)，正好撞上了一個(gè) Dummy 態(tài)的 entry，那么會(huì)直接替換掉。

所以不論是字典還是集合，只要處于 Dummy 態(tài)，都可以替換掉。因?yàn)?Dummy 態(tài)存在的目的就是為了保證探測(cè)鏈不斷裂，而替換之后探測(cè)鏈依舊是完整的。

小結(jié)

以上我們就剖析了集合的底層結(jié)構(gòu)以及它的創(chuàng)建過(guò)程，不難發(fā)現(xiàn)集合的實(shí)現(xiàn)比字典要簡(jiǎn)單很多，并且集合沒(méi)有自己的緩存池。