淺析Python是如何實現集合的

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

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

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

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

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

# 字典的 keys 方法會返回一個 dict_keys 物件
# 該物件具備集合的性質，可以直接和集合進行運算

# 如果要建立一個空集合，那麼要使用 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

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;

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

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
"""

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

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

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

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;
  
    // 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;
}