集合支持的操作有哪些，它們是怎么實現的？
作者：古明地覺
假設有一個集合 s，那么 s.add("abc") 最終等價于?set_add_entry(so, "abc", hash("abc"))，所以核心邏輯位于 set_add_entry 里面，看一下它的實現，代碼比較長。
1.楔子
本篇文章來聊一聊集合支持的操作，比如元素的添加、刪除，以及集合的擴容等等。并且集合還支持交集、并集、差集等運算，它們又是如何實現的呢？那么就一起來看一看吧。
2.add 方法：添加元素
調用 add 方法可以向集合添加一個元素，在底層會執(zhí)行 set_add 函數。
// Objects/setobject.c
static PyObject *
set_add(PySetObject *so, PyObject *key)
{
// 調用了 set_add_key 函數
if (set_add_key(so, key))
return NULL;
// 返回 None
Py_RETURN_NONE;
}
static int
set_add_key(PySetObject *so, PyObject *key)
{
Py_hash_t hash;
// 計算哈希值，由于字符串內部會緩存自身的哈希值，因此需要判斷一下
// 如果 key 不是字符串，或者 key 是字符串、但哈希值為 -1（尚未計算過）
// 那么計算哈希值，但如果計算之后的結果是 -1，說明對象不支持哈希
if (!PyUnicode_CheckExact(key) ||
(hash = _PyASCIIObject_CAST(key)->hash) == -1) {
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
// 調用 set_add_entry
return set_add_entry(so, key, hash);
}假設有一個集合 s，那么 s.add("abc") 最終等價于 set_add_entry(so, "abc", hash("abc"))，所以核心邏輯位于 set_add_entry 里面，看一下它的實現，代碼比較長。
// Objects/setobject.c
static int
set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
{
setentry *table;
setentry *freeslot;
setentry *entry;
size_t perturb;
size_t mask;
size_t i;
int probes;
int cmp;
// 增加 key 的引用計數，當然這里的 key 指的就是集合的元素
Py_INCREF(key);
restart:
// mask 等于哈希表的容量減 1
mask = so->mask;
// 和字典一樣，讓 hash & mask 計算出一個索引
i = (size_t)hash & mask;
freeslot = NULL;
// perturb 初始等于哈希值
perturb = hash;
while (1) {
// 獲取指定的 entry，里面包含了元素 key 和哈希值
entry = &so->table[i];
// 關于這一步是做什么的，一會兒解釋
probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES: 0;
do {
// 如果哈希值為 0 并且 key 為 NULL，說明該位置還沒有存儲 entry
// 此時就找到了合適的位置，跳轉到 found_unused_or_dummy 標簽
if (entry->hash == 0 && entry->key == NULL)
goto found_unused_or_dummy;
// 否則說明該位置已經存儲了 entry，那么判斷哈希值是否相同
// 如果哈希值不同，那么 key 一定不相同
// 如果哈希值相同，那么 key 不一定相同
if (entry->hash == hash) {
// 所以當哈希值相等時
// 還要比較新添加的 key 和已存在的 key 是否相同
PyObject *startkey = entry->key;
assert(startkey != dummy);
// 這里的 startkey 和 key 都是 C 的變量，它們都是指針
// 如果兩者相等，說明指向的是同一個對象，那么直接判定為相等
// 于是跳轉到 found_active 標簽
if (startkey == key) // 相當于 Python 的 is
goto found_active;
// 如果 startkey 和 key 不等，說明指向的不是同一個對象
// 那么比較值是否相等，相當于 Python 的 ==
// 這里是針對字符串的一個快分支
if (PyUnicode_CheckExact(startkey)
&& PyUnicode_CheckExact(key)
&& _PyUnicode_EQ(startkey, key))
goto found_active;
table = so->table;
Py_INCREF(startkey);
// 如果 key 不是字符串，則執(zhí)行通用比較邏輯
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
// cmp > 0，說明結果為真，即兩個 key 的值相等
// 跳轉到 found_active 標簽
if (cmp > 0)
goto found_active;
// cmp < 0 表示執(zhí)行比較操作時出現錯誤，基本不會發(fā)生
if (cmp < 0)
goto comparison_error;
// 到這里說明兩個 key 雖然映射出的索引是一樣的，但它們的值不相等
// 那么要怎么辦呢？顯然要看下一個 entry 是否可用
// 然后下面這三行代碼估計讓人有些費解，如果在查詢的過程中
// 哈希表擴容了，或者 key 發(fā)生了改變，那么跳轉到 restart 標簽重新執(zhí)行
// 但因為 GIL 的存在，實際不會發(fā)生
if (table != so->table || entry->key != startkey)
goto restart;
mask = so->mask;
}
/* 如果是 Unused 態(tài)的 entry，那么
* entry->key == NULL
* entry->hash == 0
*
* 如果是 Dummy 態(tài)的 entry，那么
* entry->key == dummy
* entry->hash == -1
*
* 如果是 Active 態(tài)的 entry，那么
* entry->key == some key
* entry->hash == some hash
*/
// 說明 entry 處于 dummy 態(tài)，將它賦值給 freeslot
else if (entry->hash == -1) {
assert (entry->key == dummy);
freeslot = entry;
}
// 嘗試下一個 entry
entry++;
} while (probes--);
// 改變規(guī)則，重新映射，直到映射出一個可用的位置
perturb >>= PERTURB_SHIFT;
i = (i * 5 + 1 + perturb) & mask;
}
found_unused_or_dummy:
// 如果 freeslot == NULL，說明沒有撞上 Dummy 態(tài)的 entry
// 跳轉到 found_unused 標簽
if (freeslot == NULL)
goto found_unused;
// 否則說明撞上了 Dummy 態(tài)的 entry
// 集合的長度加 1，或者說 Active 態(tài)的 entry 個數加 1
so->used++;
// 更新 key 和 hash
freeslot->key = key;
freeslot->hash = hash;
return 0;
found_unused:
// 執(zhí)行到這里，說明找到了新的可用位置
// 那么不光 used 要加 1，fill 也要加 1
so->fill++;
so->used++;
// 更新 key 和 hash
entry->key = key;
entry->hash = hash;
// 如果哈希表的 entry 的個數（Active 態(tài) + Dummy 態(tài)）沒超過 mask * 3/5
// 那么目前的容量是合理的，直接返回
if ((size_t)so->fill*5 < mask*3)
return 0;
// 否則進行擴容，因為擴容的時候會丟棄 Dummy 的 entry
// 所以擴容之后的容量取決于 used，而不是 fill
// 如果 used 大于 50000，那么 2 倍擴容，否則 4 倍擴容
return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
found_active:
// 執(zhí)行到這里，說明添加的元素已經存在了
// 那么減少 key 的引用計數，然后返回
Py_DECREF(key);
return 0;
comparison_error:
// 執(zhí)行比較操作時出現錯誤，應該拋出異常，但這一步基本不會發(fā)生
Py_DECREF(key);
return -1;
}所以整個過程和字典是類似的，依舊是將哈希值和 mask 按位與，得到索引，通過索引找到對應的 entry。接下來對 entry 分情況討論。
說明一上來就找到了可用的 entry，那么直接跳轉到指定標簽，然后修改 entry 的 key 和 hash 字段，這樣新元素就添加成功了。
如果 entry->hash == hash。
說明找到的 entry 處于 Active 態(tài)，那么比較兩個 key 是否相等。如果相等，證明添加的元素已存在，則不插入，直接減少引用計數，因為不是字典，不存在更新一說。但如果兩個 key 不相等，說明出現索引沖突，那么要映射出一個新的索引，并且映射的方式和字典也是一樣的。
perturb >>= PERTURB_SHIFT;
i = (i * 5 + 1 + perturb) & mask;但字典和集合有一處不同，就是集合這里多了一個 do while 循環(huán)。
// Objects/setobject.c
#define LINEAR_PROBES 9
static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) {
// ...
while (1) {
// 當前映射出的索引為 i
entry = &so->table[i];
// 如果 i + 9 沒有超過 mask，那么 probes 等于 9，否則等于 0
probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES: 0;
// 因此這里 do while 內部的邏輯，要么執(zhí)行 1 次，要么執(zhí)行 10 次
do {
// ...
entry++;
} while (probes--);
perturb >>= PERTURB_SHIFT;
i = (i * 5 + 1 + perturb) & mask;
}
// ...
}當映射出的索引相同、但 key 不相同時，說明出現了索引沖突，對于字典來說，會立即重新映射，找到一個新的索引。
而集合由于只用一個數組存儲，可以有更好的做法。我們知道 CPU 是有緩存的，像 L1 Cache 加載數據會一次性加載 64 字節(jié)，稱為一個 cache line。所以通過索引遍歷包含 16 個 int32 的數組，每次 i++ 和每次 i += 4 的耗時是差不多的。
對于集合來說，因為映射出的索引是隨機的，使得對應的 entry 可能不在 cache 中，從而導致 CPU 下一次要重新讀取。所以 Python 引入了 LINEAR_PROBES，從當前的 entry 開始，向后查找 9 個 entry。如果還找不到可用位置，然后才重新計算，從而提高 cache 的穩(wěn)定性。
如果 entry->key == dummy，或者說 entry->hash == -1。
說明撞上了一個 Dummy 態(tài)的 entry，但估計有人又注意到了一個問題。
圖片
就是在發(fā)現 Dummy 態(tài)的 entry 之后，為啥沒有立即跳轉到 found_unused_or_dummy 標簽，而是要繼續(xù)循環(huán)呢？
很簡單，假設向集合添加了一個元素 x，又添加了一個元素 y，但 y 和 x 映射出的索引相同，于是嘗試下一個 entry。所以在添加 y 的時候，會形成一條探測鏈，對應的元素就是 x->y。然后再將 x 刪除，那么 x->y 就變成了 dummy->y。這時候如果再重新添加一個元素 y，那么肯定會撞上 Dummy 態(tài)的 entry，于是 dummy->y 就變成了 y->y。
所以當發(fā)現 Dummy 態(tài)的 entry 之后，如果立即跳轉，那么會無法消除集合的重復元素。因此正確的做法是先用變量保存起來，這里賦值給了 freeslot，然后繼續(xù)查找。如果找到了相同的元素，那么就不添加了，因為集合中的元素是唯一的。但如果最后找到的 entry 的 key 為空，說明元素不存在，此時才能跳轉到 found_unused_or_dummy 標簽，然后對 freeslot 進行判斷。如果不為空，說明撞上了 Dummy 態(tài)的 entry，那么直接復用該 entry 即可。
以上就是集合添加元素的過程，當然如果找到的是 Unused 態(tài)的 entry，則還要判斷容量的問題。如果 Active 態(tài) + Dummy 態(tài)的 entry 個數不小于 3/5*mask，那么擴容，擴容的規(guī)則是判斷 Active 態(tài)的 entry 個數是否大于 50000，是的話就 2 倍擴容，否則 4 倍擴容；
pop 方法：彈出元素
調用 pop 方法，可以從集合中彈出一個元素，在底層會執(zhí)行 set_pop 方法。
// Objects/setobject.c
static PyObject *
set_pop(PySetObject *so, PyObject *Py_UNUSED(ignored))
{
// so->table 是指向 entry 數組首元素的指針
// so->finger 是做什么的，稍后解釋，總之它是一個整數
// so->mask 等于 entry 數組的長度減 1，用于將取模運算優(yōu)化成按位與運算
// 因此 so->finger & so->mask 會得到一個 0 ~ mask 之間的整數，我們記為 n
// 顯然這里的變量 entry 會指向 entry 數組中索引 n 的元素
setentry *entry = so->table + (so->finger & so->mask);
// 變量 limit 則指向 entry 數組中最后一個元素（索引為 mask）
setentry *limit = so->table + so->mask;
PyObject *key;
// 如果集合長度為 0，那么 pop 方法會拋出 KeyError
if (so->used == 0) {
PyErr_SetString(PyExc_KeyError, "pop from an empty set");
return NULL;
}
// entry 有三種狀態(tài)，但顯然彈出的 entry 一定是 Active 態(tài)
// 所以如果 entry 處于 Unused 或 Dummy 態(tài)，直接下一輪循環(huán)
while (entry->key == NULL || entry->key==dummy) {
entry++;
// 我們記 so->finger & so->mask 的結果為 n
// 所以相當于從 entry 數組中索引為 n 的位置開始遍歷
// 如果遍歷到最后一個位置，也沒找到 Active 態(tài)的 entry，那么從頭開始遍歷
if (entry > limit)
entry = so->table; // 讓變量 entry 指向 entry 數組的首元素
// 所以不難發(fā)現，整個過程是先遍歷 entry 數組中 [n: limit] 的部分
// 如果沒有找到 Active 態(tài) entry，那么將 entry 重置為 so->table，從頭開始遍歷
// 因為執(zhí)行到這里，說明 so->used 大于 0，即集合的長度大于 0
// 那么當 entry > limit 時，在 entry 數組 [0: n] 的部分，一定存在 Active 態(tài)的 entry
}
// pop 方法會返回彈出的元素，所以獲取 entry->key
key = entry->key;
// 元素被彈出了，對應的 entry 要進行偽刪除，所謂的偽刪除就是設置一個特殊的墓碑值
// 所以將 entry->key 設置為 dummy，將 entry->hash 設置為 -1
entry->key = dummy;
entry->hash = -1;
// 集合的長度減 1
so->used--;
// 將 finger 更新為被刪除的 entry 在 entry 數組中的索引加 1
so->finger = entry - so->table + 1; /* next place to start */
return key;
}所以刪除的過程還是很簡單的，如果不考慮 finger 字段，你就可以簡單理解為遍歷整個 entry 數組，找到 Active 態(tài)的 entry，然后刪除即可。只是這么做會導致每次 pop 時，都要重頭開始遍歷數組。
而當引入了 finger 字段之后，由于該字段初始為 0，所以第一次 pop 時，會從數組的頭部開始遍歷。假設刪除的是數組中索引為 n 的 entry，那么刪除之后 finger 字段會被賦值為 n + 1，那么下一次 pop 就會從數組中索引為 n + 1 的 entry 開始遍歷。
我們通過 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 = {11, 22, 33, 44}
# 獲取 PySetObject 結構體實例
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 33
2 0
3 11
4 44
5 0
6 22
7 0
"""
# finger 初始為 0，因此在 pop 元素的時候會從頭開始遍歷數組
# 找到第一個 Active 態(tài)的 entry
print(py_set_obj.finger)
"""
0
"""
# 顯然第一次 pop 出的元素是 33
print(s.pop())
"""
33
"""
for index, entry in enumerate(py_set_obj.smalltable):
print(index, entry.hash)
"""
0 0
1 -1
2 0
3 11
4 44
5 0
6 22
7 0
"""
# 因為被偽刪除了
# 所以索引為 1 的 entry->key 會被設置為 NULL，entry->hash 被設置為 -1
# 至于 finger 則等于 1 + 1，下一次 pop 時，會從索引為 2 的位置開始遍歷
print(py_set_obj.finger)
"""
2
"""
# 那么同理，再次 pop 的時候，會彈出 11，然后 finger 變?yōu)?3 + 1 = 4
print(s.pop())
"""
11
"""
print(py_set_obj.finger)
"""
4
"""以上就是 finger 字段的作用，它避免了每次都要從頭遍歷 entry 數組。從這里也不難發(fā)現，當一個集合不斷執(zhí)行 pop 方法，將所有元素依次彈出時，這些元素的順序和直接遍歷 entry 數組拿到的元素的順序是一致的。
我們依舊舉例說明：
item1 = 22333
item2 = 177
item3 = 520
item4 = 10086
# 將它們映射成索引，由于是 4 個元素，因此哈希表容量為 8
index1 = item1 & 7
index2 = item2 & 7
index3 = item3 & 7
index4 = item4 & 7
print(index1, index2, index3, index4)
"""
5 1 0 6
"""
# 所以如果將 item1、item2、item3、item4 放到集合中
# 不管怎么排列，最終都是下面這個結果
# item3 會位于 entry 數組中索引為 0 的位置
# item2 會位于 entry 數組中索引為 1 的位置
# item1 會位于 entry 數組中索引為 5 的位置
# item4 會位于 entry 數組中索引為 6 的位置
# 所以不管是彈出元素，還是遍歷元素，亦或是直接打印集合
# 元素順序一定是 item3、item2、item1、item4
s1 = {item1, item2, item3, item4}
s2 = {item2, item1, item4, item3}
s3 = {item3, item1, item2, item4}
s4 = {item4, item3, item2, item1}
print(s1) # {520, 177, 22333, 10086}
print(s2) # {520, 177, 22333, 10086}
print(s3) # {520, 177, 22333, 10086}
print(s4) # {520, 177, 22333, 10086}
print(
item3, item2, item1, item4
) # 520 177 22333 10086怎么樣，是不是對集合又有了更深刻的認識了呢？
remove 方法：刪除指定元素
remove 方法可以接收參數，刪除集合中指定的元素。除了 remove，還有一個 discard 方法，這兩個方法的作用一模一樣，都是用來刪除指定元素。區(qū)別就是當刪除的元素不存在時，remove 方法會拋出 KeyError，而 discard 方法不會。
remove 方法在底層對應 set_remove 函數，discard 方法在底層對應 set_discard 函數，而 set_remove 函數只比 set_discard 函數多了一個 if 判斷，我們來看一下。
以上是 set_remove 函數，注意圖中綠色方框的部分，如果要刪除的元素不存在，那么 rv 會等于 DISCARD_NOTFOUND，于是拋出 KeyError。
如果將綠色方框里的 if 邏輯刪掉，得到的就是 set_discard 函數的源碼。所以這兩個函數做的事情是一樣的，區(qū)別就是 set_remove 會多做一層檢測，當刪除的元素不存在時，set_remove 會主動拋出一個 KeyError，而 set_discard 函數則什么也不做。
所以這里我們只看 set_remove 函數即可。
// Objects/setobject.c
#define DISCARD_NOTFOUND 0
#define DISCARD_FOUND 1
static PyObject *
set_remove(PySetObject *so, PyObject *key)
{
// 要刪除的 key，或者說元素
// 當然啦，從 C 的層面來看，刪除 key 其實就是刪除數組中該 key 對應的 entry
// 只不過這個刪除是偽刪除，即寫入一個特殊的墓碑值
PyObject *tmpkey;
int rv;
// rv 表示刪除結果，顯然刪除邏輯由 set_discard_key 函數實現
// 如果 rv < 0，表示刪除元素時出現錯誤，比如傳入了一個不可哈希的對象
// 如果 rv == 0，表示要刪除的元素在集合中不存在
// 如果 rv == 1，表示成功將元素從集合中刪除
rv = set_discard_key(so, key);
if (rv < 0) {
// 當傳入一個不可哈希對象時，會拋出 TypeError
// 我們知道集合也是不可哈希的，但如果要刪除的 key 是集合類型
// 那么解釋器會額外做一個兜底操作，我們一會兒通過 Python 代碼演示
if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
return NULL;
// 將回溯棧里的異常清空
PyErr_Clear();
// 基于集合里的元素創(chuàng)建不可變集合
tmpkey = make_new_set(&PyFrozenSet_Type, key);
if (tmpkey == NULL)
return NULL;
// 然后嘗試刪除這個不可變集合，如果還刪除失敗，則報錯
rv = set_discard_key(so, tmpkey);
Py_DECREF(tmpkey);
if (rv < 0)
return NULL;
}
// 如果 rv == DISCARD_NOTFOUND，表示要刪除的元素不存在
if (rv == DISCARD_NOTFOUND) {
_PyErr_SetKeyError(key); // 拋出 KeyError
return NULL;
}
Py_RETURN_NONE;
}我們看到當元素刪除失敗時，如果 key 是集合類型，那么解釋器會做一個兜底操作，這是什么意思呢？我們演示一遍。
try:
s = {[1, 2, 3]} # 列表不可哈希
except TypeError as e:
print(e)
"""
unhashable type: 'list'
"""
try:
s = {{1, 2, 3}} # 同樣，集合也不可哈希
except TypeError as e:
print(e)
"""
unhashable type: 'set'
"""
# 當我們嘗試 remove 列表時，依舊會拋出相同的錯誤
s = {1, 2, 3}
try:
s.remove([])
except TypeError as e:
print(e)
"""
unhashable type: 'list'
"""
# 但 remove 一個集合就不同了
s = {
frozenset({1, 2, 3}),
frozenset({4, 5, 6}),
}
# 不可變集合是可哈希對象，因此它可以放在集合中，也可以被刪除
s.remove(frozenset({1, 2, 3}))
# 但這里應該會拋出 TypeError: unhashable type: 'set'
# 而事實上異常也確實產生了，保存在回溯棧中，但是從源碼中我們看到，解釋器會多做一個檢測
# 如果刪除的 key 是集合類型，并且棧里的異常是 TypeError，那么將異常清空
# 然后基于集合創(chuàng)建不可變集合，并嘗試刪除這個不可變集合
s.remove({4, 5, 6})
# 所以這里 s.remove({4, 5, 6}) 等價于 s.remove(frozenset({4, 5, 6}))
print(s)
"""
set()
"""
# 我們看到 s 里面的兩個不可變集合被刪除了好，我們回到 set_remove 函數，它在刪除元素時會調用 set_discard_key 函數，顯然刪除指定元素的核心邏輯位于此函數中，我們看一下它做了什么。
// Objects/setobject.c
static int
set_discard_key(PySetObject *so, PyObject *key)
{
Py_hash_t hash;
// 檢測 key 是否為字符串，因為字符串內部已經保存了自身的哈希值
// 如果不是字符串，或者是字符串、但哈希值尚未計算（hash 字段等于 -1）
// 那么計算 key 的哈希值
if (!PyUnicode_CheckExact(key) ||
(hash = _PyASCIIObject_CAST(key)->hash) == -1) {
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
// 調用 set_discard_entry 函數
// 傳入三個參數：集合、要刪除的 key、以及 key 的哈希值
return set_discard_entry(so, key, hash);
}
static int
set_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
{
setentry *entry;
PyObject *old_key;
// 將 key 映射成索引，并獲取該索引對應的 entry 的指針
entry = set_lookkey(so, key, hash);
// 因為 entry 數組申請好之后，內部的每個元素都擁有一塊合法的內存
// 所以指針不可能為 NULL，如果為 NULL，證明內部出問題了
if (entry == NULL) // 基本不會發(fā)生
return -1;
// 如果 entry->key 為 NULL，證明要刪除的 key 不存在，返回 DISCARD_NOTFOUND
// 當 set_remove 函數發(fā)現返回的是 DISCARD_NOTFOUND，會拋出 KeyError
if (entry->key == NULL)
return DISCARD_NOTFOUND;
// 否則說明 key 存在
old_key = entry->key;
// 因為被刪除了，所以將 entry->key、entry->hash 設置為 dummy 和 -1
entry->key = dummy;
entry->hash = -1;
// 集合長度減 1
so->used--;
// 減少 key 指向對象的引用計數，因為集合不再持有對它的引用
Py_DECREF(old_key);
// 返回 DISCARD_FOUND
return DISCARD_FOUND;
}以上就是 set_remove 函數刪除指定元素的具體細節(jié)，邏輯并不復雜。但是里面出現了一個 set_lookkey 函數，它的作用是將哈希值映射成索引，返回指定的 entry。
顯然這些代碼在介紹 set_add 函數時已經見過了，邏輯是類似的。如果 entry->key 為空，說明找到了 Unused 態(tài)的 entry，即 key 不存在，那么直接將 entry 返回即可。
如果 entry->key 不為空，那么比較 entry->hash 和傳入的 hash 是否相等，如果哈希值不相等，那么 key 一定不相等，說明出現了索引沖突。當然啦，如果 entry 處于 Dummy 態(tài)，那么哈希值肯定也不相等，但不管哪一種，都要重新映射。
如果哈希值相等，那么比較 key 是否相等，如果 key 相等，說明查找的 key 存在于集合中，那么返回對應的 entry。如果 key 不相等，則重新映射。
copy 方法：拷貝一個集合
調用 copy 方法可以拷貝一個集合，在底層會執(zhí)行 set_copy 方法。
// Objects/setobject.c
static PyObject *
set_copy(PySetObject *so, PyObject *Py_UNUSED(ignored))
{
return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
}
static PyObject *
make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
{
if (type != &PySet_Type && type != &PyFrozenSet_Type) {
if (PyType_IsSubtype(type, &PySet_Type))
type = &PySet_Type;
else
type = &PyFrozenSet_Type;
}
return make_new_set(type, iterable);
}
static PyObject *
make_new_set(PyTypeObject *type, PyObject *iterable)
{
assert(PyType_Check(type));
PySetObject *so;
// 為集合申請內存
so = (PySetObject *)type->tp_alloc(type, 0);
if (so == NULL)
return NULL;
// 字段初始化，顯然剛創(chuàng)建的集合的容量為 8
so->fill = 0;
so->used = 0;
so->mask = PySet_MINSIZE - 1;
so->table = so->smalltable;
so->hash = -1;
so->finger = 0;
so->weakreflist = NULL;
// 調用 set_update_internal 函數，將可迭代對象的元素添加到集合中
if (iterable != NULL) {
if (set_update_internal(so, iterable)) {
Py_DECREF(so);
return NULL;
}
}
return (PyObject *)so;
}
static int
set_update_internal(PySetObject *so, PyObject *other)
{
// 參數 so 表示集合，other 表示可迭代對象
PyObject *key, *it;
// 如果 other 的類型也是集合（或者不可變集合）
// 那么調用 set_merge 函數
if (PyAnySet_Check(other))
return set_merge(so, other);
// 否則檢測 other 是否為字典
if (PyDict_CheckExact(other)) {
PyObject *value;
Py_ssize_t pos = 0;
Py_hash_t hash;
Py_ssize_t dictsize = PyDict_GET_SIZE(other);
if (dictsize < 0)
return -1;
// 判斷 so->fill + dictsize 是否達到了 so->mask 的 3/5
// 如果達到了，那么擴容
if ((so->fill + dictsize)*5 >= so->mask*3) {
if (set_table_resize(so, (so->used + dictsize)*2) != 0)
return -1;
}
// 遍歷字典，將字典的 key 和 hash 包裝成 entry，添加到數組中，value 丟棄
// 這里調用的是 set_add_entry 函數，我們介紹集合的 add 方法時說過
while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
if (set_add_entry(so, key, hash))
return -1;
}
return 0;
}
// 到這里說明 other 不是字典，那么迭代出來的整體就是 key
// 基于可迭代對象創(chuàng)建迭代器
it = PyObject_GetIter(other);
if (it == NULL)
return -1;
// 將元素迭代出來
while ((key = PyIter_Next(it)) != NULL) {
// 調用 set_add_key 函數，它內部會先計算 key 的哈希值
// 然后調用 set_add_entry 函數，添加元素
if (set_add_key(so, key)) {
Py_DECREF(it);
Py_DECREF(key);
return -1;
}
Py_DECREF(key);
}
Py_DECREF(it);
if (PyErr_Occurred())
return -1;
return 0;
}以上就是集合的 copy 方法的底層實現，非常簡單。說白了就是先創(chuàng)建一個新的集合，然后調用 set_update_internal 函數將老集合里面的元素拷貝過去。當然啦，該函數可以拷貝任意可迭代對象里的元素，不僅僅是集合。只是當可迭代對象是集合時，會單獨調用 set_merge 函數，如果不是集合，那么會直接遍歷。
update 方法：合并多個可迭代對象
調用 update 方法，可以合并多個可迭代對象，舉例說明。
s = {1, 2, 3}
s.update([4, 5, 6], (7, 8, 9))
print(s)
"""
{1, 2, 3, 4, 5, 6, 7, 8, 9}
"""相信你已經知道底層是怎么做的了，獲取每個可迭代對象，然后調用 set_update_internal 函數即可。那么底層是不是這么做的呢？我們來看一下，update 方法在底層對應 set_update 函數。
// Objects/setobject.c
static PyObject *
set_update(PySetObject *so, PyObject *args)
{
Py_ssize_t i;
// args 是一個元組
for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
// 遍歷拿到每個可迭代對象
PyObject *other = PyTuple_GET_ITEM(args, i);
// 調用 set_update_internal 函數
if (set_update_internal(so, other))
return NULL;
}
Py_RETURN_NONE;
}跟我們分析的一樣，非常簡單。
另外集合還有一個 union 方法，功能和 update 方法類似，但它會返回一個新的集合。
s1 = {1, 2, 3}
s1.update([4, 5, 6], (7, 8, 9))
print(s1)
"""
{1, 2, 3, 4, 5, 6, 7, 8, 9}
"""
s2 = {1, 2, 3}
s2_new = s2.union([4, 5, 6], (7, 8, 9))
print(s2)
print(s2_new)
"""
{1, 2, 3}
{1, 2, 3, 4, 5, 6, 7, 8, 9}
"""update 方法會原地修改，而 union 方法會返回新的集合，不會影響原有的集合。
其它的一些方法
集合還有一些常用的方法，只不過我們更傾向于使用操作符的形式。
- s1 & s2：對兩個集合做交集運算，返回新的集合，里面包含同時出現在 s1 和 s2 當中的元素；
- s1 | s2：對兩個集合做并集運算，返回新的集合，里面包含出現在 s1 或 s2 當中的元素；
- s1 - s2：對兩個集合做差集運算，返回新的集合，里面包含出現在 s1 當中、但沒有出現在 s2 當中的元素；
- s1 ^ s2：對兩個集合做對稱差集運算，返回新的集合，里面包含只出現在 s1 當中、或只出現在 s2 當中的元素；
- s1 == s2：判斷兩個集合的元素是否完全相同；
- s1 >= s2：判斷 s2 是否是 s1 的子集，如果是，那么 s2 - s1 == {}。
- s1 <= s2：判斷 s1 是否是 s2 的子集，如果是，那么 s1 - s2 == {}。
- s1 > s2：判斷 s2 是否是 s1 的真子集；
- s1 < s2：判斷 s1 是否是 s2 的真子集；
注意：在使用這些操作符時，兩側的 s1 和 s2 都要求是集合類型。但如果使用操作符對應的方法，那么則不要求 s2 是集合類型，只要是可迭代對象即可。
# 做交集運算
s = {"a", "b", "c"}
print(s.intersection("bcd"))
"""
{'b', 'c'}
"""
# print(s & "bcd") # TypeError這些方法都非常的有用，可以自己測試一下，加深一遍印象。至于這些方法的底層實現，感興趣也可以去 Objects/setobject.c 中探索一番，方法都定義在 set_methods 數組中。
這里我們就以集合的交集運算為例，看一下實現過程。
// Objects/setobject.c
static int
set_contains_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
{
// 判斷集合是否包含某個元素
setentry *entry;
// 調用 set_lookkey，返回 entry
// 如果 entry->key 不為空，證明元素存在，否則不存在
entry = set_lookkey(so, key, hash);
if (entry != NULL)
return entry->key != NULL;
return-1;
}
// 兩個集合做交集運算，返回新的集合
static PyObject *
set_intersection(PySetObject *so, PyObject *other)
{
PySetObject *result;
PyObject *key, *it, *tmp;
Py_hash_t hash;
int rv;
// 快分支：如果兩個集合相等，那么直接把其中一個拷貝一份
if ((PyObject *)so == other)
return set_copy(so, NULL);
// 否則創(chuàng)建一個新的空集合
result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
if (result == NULL)
returnNULL;
// 如果 other 是集合
if (PyAnySet_Check(other)) {
Py_ssize_t pos = 0;
setentry *entry;
// 如果 len(other) > len(so)，那么兩者交換位置
// 也就是遍歷元素較少的集合
if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
tmp = (PyObject *)so;
so = (PySetObject *)other;
other = tmp;
}
// 遍歷集合 other
while (set_next((PySetObject *)other, &pos, &entry)) {
key = entry->key;
hash = entry->hash;
Py_INCREF(key);
// 判斷 key 是否存在于集合 so 中
rv = set_contains_entry(so, key, hash);
if (rv < 0) {
Py_DECREF(result);
Py_DECREF(key);
returnNULL;
}
// 如果存在，那么添加到新集合 result 中
if (rv) {
if (set_add_entry(result, key, hash)) {
Py_DECREF(result);
Py_DECREF(key);
returnNULL;
}
}
Py_DECREF(key);
}
return (PyObject *)result;
}
// 如果 other 不是集合，那么獲取它的迭代器
it = PyObject_GetIter(other);
if (it == NULL) {
Py_DECREF(result);
returnNULL;
}
// 直接迭代內部的元素，以下邏輯和上面類似
while ((key = PyIter_Next(it)) != NULL) {
hash = PyObject_Hash(key);
if (hash == -1)
goto error;
// 如果 key 在 so 中存在，那么添加到 result 中
rv = set_contains_entry(so, key, hash);
if (rv < 0)
goto error;
if (rv) {
if (set_add_entry(result, key, hash))
goto error;
if (PySet_GET_SIZE(result) >= PySet_GET_SIZE(so)) {
Py_DECREF(key);
break;
}
}
Py_DECREF(key);
}
Py_DECREF(it);
if (PyErr_Occurred()) {
Py_DECREF(result);
returnNULL;
}
return (PyObject *)result;
error:
Py_DECREF(it);
Py_DECREF(result);
Py_DECREF(key);
returnNULL;
}以上就是集合的交集運算，至于其它的運算操作也是類似的，感興趣可以看一下。
小結
關于集合相關的內容我們就介紹完了，當然到目前為止，Python 的內置數據結構也基本介紹完了?；仡櫼幌挛覀兘榻B了哪些數據結構：
- 浮點數；
- 整數；
- 復數；
- 布爾值
- None；
- 切片；
- bytes 對象；
- bytearray 對象；
- 字符串；
- 列表；
- 元組；
- 字典；
- 集合；
以上這些結構都是內置的，當然還有一些數據結構是定義在標準庫里面的，我們后面再說。
責任編輯：武曉燕
來源：
古明地覺的編程教室
