鴻蒙OS 4.0公測機型公布：甚至連nova6都支持
華為全新的HarmonyOS 4.0操作系統將于今天下午正式登場，官方在發布會之前也已經正式給出了可升級的機型產品，這意味著這些機型會率先支持升級享用。這次的HarmonyOS 4.0支持
本篇文章來聊一聊 Python 的集合是怎么實現的？前面我們介紹了字典的實現原理，它底層是基于哈希表實現的，而集合也是如此。
事實上，集合就類似于沒有 value 的字典。
那么集合都有哪些用處呢？
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同理，基于此方式，我們也可以檢測一個字典是否包含指定的多個 key。
data = { "name": "satori", "age": 17, "gender": "female"}# 判斷字典是否包含 name、age、gender 三個 keyprint( data.keys() >= {"name", "age", "gender"}) # True# 字典的 keys 方法會返回一個 dict_keys 對象# 該對象具備集合的性質，可以直接和集合進行運算顯然對于這種需求，有了集合就方便多了。
然后我們來羅列一下集合支持的 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}# 隨機彈出一個元素并返回，如果集合為空，會拋出 KeyError# 時間復雜度為 O(1)print(s.pop()) # 1print(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}) # Trueprint({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}) # Trueprint({1, 2, 3} >= {1, 2, 3}) # True以上就是集合支持的一些 API，還是很簡單的。
集合和字典的內部都使用了哈希表，但字典的哈希表采用兩個數組實現，而集合的哈希表采用一個數組實現。因此對于集合來說，這個數組不僅要存儲 entry，并且映射出的索引也是該數組的索引。
下面看一下集合的底層結構長什么樣子。
// Include/cpython/setobject.htypedef 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;解釋一下這些字段的含義：
定長對象的頭部信息，但集合顯然是一個變長對象，所以和字典一樣，肯定有其它字段充當 ob_size。
Active 態的 entry 數量加上 Dummy 態的 entry 數量。一個 entry 就是哈希表里的一個元素，類型為 setentry，因此在集合里面，一個 entry 就是一個 setentry 結構體實例。當刪除集合的 entry 時，也必須是偽刪除，因為要保證探測鏈不斷裂。如果 entry 被偽刪除了，那么它便處于 Dummy 態。
Active 態的 entry 數量，顯然這個 used 充當了 ob_size，也就是集合的元素個數；
在看字典源碼的時候，我們也見到了 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 的冪次方，就是為了將取模運算優化成按位與運算。
指向 setentry 數組首元素的指針，這個 setentry 數組可以是下面的 smalltable，也可以是單獨申請的一塊內存；
集合的哈希值，只適用于不可變集合；
用于 pop 方法；
一個 setentry 類型的數組，集合的元素就存在里面。但我們知道，變長對象的內部不會存儲具體的元素，而是會存儲一個指針，該指針指向的內存區域才是用來存儲具體元素的。這樣當擴容的時候，只需要讓指針指向新的內存區域即可，從而方便維護。沒錯，對于集合而言，只有在容量不超過 8 的時候，元素才會存在里面；而一旦超過了 8，那么會使用 malloc 單獨申請內存；
弱引用列表，不做深入討論；
有了字典的經驗，再看集合會簡單很多。然后是 setentry，用于承載集合內的元素，那么它的結構長什么樣呢？相信你能夠猜到。
// Include/cpython/setobject.h#define PySet_MINSIZE 8typedef 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) = 322818021289917443hash("abc") = 8036038346376407734hash(666) = 666"""# 獲取 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 01 02 6663 3228180212899174434 05 06 80360383463764077347 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 都是 3print(py_set_obj.fill) # 3print(py_set_obj.used) # 3# 將集合元素全部刪除# 這里不能用 s.clear()，原因一會兒說for _ in range(len(s)): s.pop() # 我們知道哈希表在刪除元素的時候是偽刪除# 所以 fill 不變，但是 used 每次會減 1print(py_set_obj.fill) # 3print(py_set_obj.used) # 0fill 字段維護的是 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) # 3print(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) # 10print(py_set_obj.used) # 10s.pop()print(py_set_obj.fill) # 10print(py_set_obj.used) # 9在之前代碼的基礎上，繼續添加 9 個元素，然后 used 變成了 10，這很好理解，因為此時集合有 10 個元素。但 fill 也是 10，這是為什么？很簡單，因為哈希表擴容了，擴容時會刪除 Dummy 態的 entry，所以 fill 和 used 是相等的。同理，如果再繼續 pop，那么 fill 和 used 就又變得不相等了。
集合的結構我們已經清楚了，再來看看它的初始化過程。我們調用類 set，傳入一個可迭代對象，便可創建一個集合，這個過程是怎樣的呢？
// Objects/setobject.cPyObject *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 申請內存，初始容量為 8 so = (PySetObject *)type->tp_alloc(type, 0); if (so == NULL) return NULL; // 對字段做初始化 so->fill = 0; so->used = 0; so->mask = PySet_MINSIZE - 1; // 哈希表容量為 8 時，元素會存在 smalltable 里面 // 因此直接將 smalltable 賦值給 table so->table = so->smalltable; so->hash = -1; so->finger = 0; so->weakreflist = NULL; if (iterable != NULL) { // 遍歷 iterable，將迭代出的元素添加到集合中 // 關于這個函數，我們之后再介紹 if (set_update_internal(so, iterable)) { Py_DECREF(so); return NULL; } } return (PyObject *)so;}可以看到，集合的創建過程非常簡單。
字典和集合都是采用哈希表實現的，但字典的哈希表使用了兩個數組，而集合的哈希表使用了一個數組，我們對比一下兩者的差異。
假設有一個字典和一個集合，字典包含三個鍵值對，分別是 "a": 1、"b": 2、"c": 3，集合包含三個元素，分別是 "a"、"b"、"c"，然后映射出的索引分別是 2、5、3。
圖片
注：為了方便，這里的圖畫得沒有那么嚴謹。比如集合的哈希表，里面的元素直接用字符串代替了，但其實它存儲的是 setentry entry，而 entry 的 key 字段指向的才是字符串。當然這里我們心里清楚就好。
在介紹字典的時候我們說過，早期的字典內部的哈希表也是使用一個數組實現，除了 entry 會多存儲一個 value 之外，其它和當前的集合是類似的。
但如果只使用一個數組實現，會導致內存浪費嚴重，因為哈希表必須要保證一定的稀疏性。所以后續字典內部的哈希表采用兩個數組實現，將存儲鍵值對的數組的長度壓縮到原來的 2/3，至于映射出的索引則由另一個數組（哈希索引數組）來承載。
雖然引入新的數組會帶來額外的內存開銷（假設大小為 m 字節），但存儲鍵值對的數組不用再浪費 1/3 的空間（假設大小為 n 字節），只要 m 小于 n，那么使用兩個數組就會更加節省內存。而在介紹字典的時候我們也看到了，m 是遠小于 n 的。
那么問題來了，為什么集合不使用兩個數組呢？很簡單，因為使用一個數組實現哈希表會更簡單，雖然也更加浪費內存。而集合和字典在哈希表的實現上之所以區別對待，還是使用頻率的問題，解釋器內部極度依賴字典，比如全局變量就是使用字典存儲的。
可以說字典的效率高度影響著整個解釋器的效率，字典的內存大小高度影響著解釋器的內存占用。因此 Python 除了優化字典的搜索性能之外，還要盡可能地減少字典的內存大小。所以字典搞出了分離表、結合表，以及根據 key 是否全部是字符串來選擇使用不同的結構體表示 entry，這一切操作都是為了將字典的內存占用降到最低。
至于集合，解釋器對它的依賴就很小了，所以內部的哈希表，只采用了一個數組實現。雖然會有內存浪費，但無傷大雅。
好，回到上面的例子，如果將字典的鍵值對 "b": 2 和集合的元素 "b" 刪掉，那么它們的結構會發生什么變化呢？
圖片
"b" 映射出的索引為 5，因此對于字典來說，會將索引為 5 的哈希槽的值設置為 dummy。然后是鍵值對數組，會將指定的 entry 的 me_key 和 me_value 字段全部設置為 NULL，相當于回歸到了初始狀態。
需要注意的是，數組一旦申請，那么 entry 的空間就已經有了，只是 me_key 和 me_value 字段均為 NULL。而所謂添加鍵值對，本質上也是修改指定 entry 的 me_key 和 me_value 字段。
對于集合來說，它只有一個數組，這個數組不僅要存儲鍵值對，它的索引還表示 key 映射出的索引，當然這里的 key 指的就是集合的元素。"b" 映射出的索引為 5，所以將數組中索引為 5 的 entry->key 設置為 dummy。
但要注意的是，字典的 dummy 是一個整數，值為 -2（DKIX_DUMMY），因為哈希索引數組存儲的是整數。key 映射出的索引是哈希索引數組的索引，如果對應的哈希槽存儲的值是 -2，說明當前搜索的 key 對應的 entry 被刪除了，應該繼續向后搜索。
而集合的 dummy 是一個結構體指針，定義如下：
// Objects/setobject.cstatic PyObject _dummy_struct;#define dummy (&_dummy_struct)因為集合內部的哈希表只使用了一個數組，該數組存儲的是 setentry。如果在查找的時候，發現對應的 entry 的 key 等于 dummy，就知道該 entry 被刪除了，應該繼續向后搜索。
好，繼續回到上面的例子，假設這時候再給字典添加一個鍵值對 "d": 4，給集合添加一個元素 "d"，而字符串 "d" 映射出的索引也是 5，那么結構是怎樣的呢？
圖片
對于字典來說，鍵值對始終按照先來后到的順序添加在鍵值對數組中，然后將它在鍵值對數組中的索引保存在指定的哈希槽中。由于索引為 5 的哈希槽保存的是 -2，處于 Dummy 態，因此直接將它設置為 3。
同理對于集合來說也是類似的。數組索引為 5 的位置保存的值等于 dummy，處于 Dummy 態，說明該元素被刪除了，那么直接替換掉。因此整個過程的邏輯很簡單：由于索引會存在沖突，所以元素刪除之后，需要寫入一個特殊的墓碑值，也就是這里的 dummy，因為要保證探測鏈不斷裂。但如果集合后續添加元素時，正好撞上了一個 Dummy 態的 entry，那么會直接替換掉。
所以不論是字典還是集合，只要處于 Dummy 態，都可以替換掉。因為 Dummy 態存在的目的就是為了保證探測鏈不斷裂，而替換之后探測鏈依舊是完整的。
以上我們就剖析了集合的底層結構以及它的創建過程，不難發現集合的實現比字典要簡單很多，并且集合沒有自己的緩存池。
本文鏈接：http://www.tebozhan.com/showinfo-26-112773-0.html解密 Python 集合的實現原理
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號