Python 的集合是怎麼實現的？

楔子

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

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

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

集合的使用場景

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

1）去重

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

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

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

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

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

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

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

# 現在要判斷 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 對象
# 該對象具備集合的性質，可以直接和集合進行運算

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

集合的 API

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

# 如果要創建一個空集合，那麼要使用 set()
# 寫成 {} 的話，解釋器會認爲這是一個空字典
s = {1, 2, 3}

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

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

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

# 隨機彈出一個元素並返回
# 時間複雜度爲 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 當中的元素
print({1, 2, 3} - {2, 3, 4})  # {1}

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

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

# 判斷一個集合是否包含另一個集合的所有元素
# 假設有兩個集合 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，還是很簡單的，下面來重點看一下集合的底層結構。

集合的底層結構

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

有了字典的經驗，再看集合會簡單很多。然後是 setentry，用於承載集合內的元素，那麼它的結構長什麼樣呢？相信你能夠猜到。

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

相比字典少了一個 value，這是顯而易見的。因此集合的結構很清晰了，假設有一個集合 {3.14, "abc", 666}，那麼它的結構如下：

由於集合裏面只有三個元素，所以它們都會存在 smalltable 數組裏面，我們通過 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結構體實例
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
"""

根據輸出的哈希值我們可以斷定，這三個元素確實存在了 smalltable 數組裏面，並且 666 存在了數組索引爲 2 的位置、3.14 存在了數組索引爲 3 的位置、"abc" 存在了數組索引爲 6 的位置。

當然，由於哈希值是隨機的，所以每次執行之後打印的結果都可能不一樣，但是整數除外，它的哈希值就是它本身。既然哈希值不一樣，那麼每次映射出來的索引也可能不同，但總之這三個元素是存在 smalltable 數組裏面的。

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

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 成員維護的是 active 態的 entry 數量加上 dummy 態的 entry 數量，所以刪除元素時它的大小是不變的；但 used 成員的值每次會減 1，因爲它維護的是 active 態的 entry 的數量。所以只要不涉及元素的刪除，那麼這兩者的大小是相等的。

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

刪除集合所有元素之後，我們再往裏面添加元素，看看是什麼效果：

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

多次執行的話，會發現打印的結果可能是 3、1，也有可能是 4、1。至於原因，有了字典的經驗，相信你肯定能猜到。

首先添加元素之後，used 肯定爲 1。至於 fill，如果添加元素的時候，正好撞上了一個 dummy 態的 entry，那麼將其替換掉，此時 fill 不變，仍然是 3；如果沒有撞上 dummy 態的 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

在之前代碼的基礎上，繼續添加 9 個元素，然後 used 變成了 10，這很好理解，因爲此時集合有 10 個元素。但 fill 也是 10，這是爲什麼？很簡單，因爲哈希表擴容了，擴容時會刪除 dummy 態的 entry，所以 fill 和 used 是相等的。同理，如果再繼續 pop，那麼 fill 和 used 就又變得不相等了。

集合的創建

集合的結構我們已經清楚了，再來看看它的初始化過程。我們調用類 set，傳入一個可迭代對象，便可創建一個集合，這個過程是怎樣的呢？

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

底層提供了 PySet_New 函數用於創建一個集合，接收一個可迭代對象，然後調用 make_new_set 進行創建。

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;
  
    // fill 和 used 初始都爲 0
    so->fill = 0;
    so->used = 0;
    // PySet_MINSIZE 默認爲 8
    // 而 mask 等於哈希表容量減 1，所以初始值是 7
    so->mask = PySet_MINSIZE - 1;
    // 初始化的時候，setentry 數組顯然是 smalltable
    // 所以讓 table 指向 smalltable 數組
    so->table = so->smalltable;
    // 初始 hash 值爲 -1
    so->hash = -1;
    // finger爲0
    so->finger = 0;
    // 弱引用列表爲NULL
    so->weakreflist = NULL;
    //以上只是初始化，如果可迭代對象不爲 NULL
    //那麼把元素依次設置到集合中
    if (iterable != NULL) {
    //該過程是通過 set_update_internal 函數實現的
    //該函數內部會遍歷 iterable，將迭代出的元素依次添加到集合裏面
        if (set_update_internal(so, iterable)) {
            Py_DECREF(so);
            return NULL;
        }
    }
    //返回初始化完成的set
    return (PyObject *)so;
}

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

小結

以上就是集合相關的內容，它的效率也是非常高的，能夠以 O(1) 的複雜度去查找某個元素。最關鍵的是，它用起來也特別的方便。

此外 Python 裏面還有一個 frozenset，也就是不可變的集合。但 frozenset 對象和 set 對象都是同一個結構體，只有 PySetObject，沒有 PyFrozenSetObject。

我們在看 PySetObject 的時候，發現該對象裏面也有個 hash 成員，如果是不可變集合，那麼 hash 值是不爲 -1 的，因爲它不可以添加、刪除元素，是不可變對象。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ASAMuBLBbVEazyPDsdCb2A

猜你喜歡