這篇文章主要講解了“Python 實現(xiàn)字典特性的原理”,文中的講解內(nèi)容簡單清晰,易于學(xué)習(xí)與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“Python 實現(xiàn)字典特性的原理”吧!
創(chuàng)新互聯(lián)專注于網(wǎng)站建設(shè)|成都網(wǎng)站維護公司|優(yōu)化|托管以及網(wǎng)絡(luò)推廣,積累了大量的網(wǎng)站設(shè)計與制作經(jīng)驗,為許多企業(yè)提供了網(wǎng)站定制設(shè)計服務(wù),案例作品覆蓋成都攪拌罐車等行業(yè)。能根據(jù)企業(yè)所處的行業(yè)與銷售的產(chǎn)品,結(jié)合品牌形象的塑造,量身策劃品質(zhì)網(wǎng)站。
在前面的文章中我們介紹了 dict 的特性:
dict 是存儲鍵值對的關(guān)聯(lián)容器
dict 中的 key 是唯一的
可使用 dict[key] 語法來快速訪問 dict 中的元素
Python 3.6 之后的版本會保持元素添加到 dict 中的順序
那么,Python 底層是如何支撐這些特性的呢?其運行效率如何?
我們今天就來簡單探索一下 dict 在 Python 中的底層實現(xiàn),并嘗試結(jié)合 CPython 源碼來回答上邊的問題。
【基本原理】
首先我們來思考一下如何從一批數(shù)據(jù)中快速查找一個元素。
在計算機中,對數(shù)據(jù)的訪問是基于數(shù)據(jù)的存儲方式的,不同的存儲方式訪問效率差別很大。
我們熟知的 list,底層是基于數(shù)組實現(xiàn)的。數(shù)組的優(yōu)點在于能通過索引實現(xiàn)隨機訪問,非??欤瑫r間復(fù)雜度為O(1)。但前提是,你需要知道被訪問的元素的位置。而對于 key-value 這種關(guān)聯(lián)數(shù)據(jù),我們在應(yīng)用中并不關(guān)注其存放位置。
如果單純使用數(shù)組來存放 key-value,我們需要按順序比對數(shù)組中的每個元素,找到目的 key。當(dāng)數(shù)據(jù)量很大時,這種查找效率很低。
有沒有能實現(xiàn)高效比對的數(shù)據(jù)結(jié)構(gòu)呢?有!
學(xué)過 C++ 的同學(xué)應(yīng)該知道,C++ 標(biāo)準(zhǔn)庫提供了一個關(guān)聯(lián)容器:map。它可以高效地存取鍵值對,其底層是基于紅黑樹來實現(xiàn)的。紅黑樹是一個自平衡的二叉搜索樹,查找效率很高。
那么,Python 中的 dict 是基于紅黑樹實現(xiàn)的嗎?答案是否定的。
Python 為了實現(xiàn)更快的訪問速率,采用了另一種存儲結(jié)構(gòu):哈希表。
哈希表基于數(shù)組隨機訪問的特性,使用哈希算法來快速計算 key 的哈希值,從而定位元素在底層數(shù)組中的位置,實現(xiàn)元素的快速訪問。
這種結(jié)構(gòu)的訪問效率和數(shù)組相同,但是存在一定的缺點:哈希算法無法保證對每個 key 求值結(jié)果的唯一性,因而不同的 key 可能會得到相同的存放位置。這就導(dǎo)致了沖突。
哈希表需要采取一定的策略來避免鍵沖突。當(dāng)然,存在沖突的鍵的訪問效率也會有所降低。
下面我們就來看一下 CPython 是如何通過哈希表來實現(xiàn) dict 的。
【字典相關(guān)數(shù)據(jù)結(jié)構(gòu)】
1,字典對象 PyDictObject
typedef struct { PyObject_HEAD /*字典用元素的個數(shù)*/ Py_ssize_t ma_used; /*全局唯一的版本號,會在 dict 被修改時發(fā)生變化*/ uint64_t ma_version_tag; /*存放元素或元素 key,承擔(dān)哈希表的具體實現(xiàn)*/ PyDictKeysObject *ma_keys; /* 當(dāng)哈希表為組合(combined)模式時,value 存儲在 ma_keys 的每個 PyDictKeyEntry 對象中,此值為 NULL。 當(dāng)哈希表為分離(splitted)模式時用于存儲元素的 value。 */ PyObject **ma_values; } PyDictObject;
每個 dict 都是一個 PyDictObject 對象。
此結(jié)構(gòu)中,最重要的是 ma_keys 這個成員變量,它是實現(xiàn)哈希表的關(guān)鍵所在。
2,哈希表 PyDictKeysObject
struct _dictkeysobject { Py_ssize_t dk_refcnt; /* 哈希表(dk_indices)的大小,其值為 2 的乘冪. */ Py_ssize_t dk_size; /* 用于在哈希表(dk_indices)中執(zhí)行查找的函數(shù)*/ dict_lookup_func dk_lookup; /* dk_entries 中可用 entries 的個數(shù) */ Py_ssize_t dk_usable; /* dk_entries 中已用 entries 的個數(shù) */ Py_ssize_t dk_nentries; /* 哈希表. 可動態(tài) resize。64位系統(tǒng)上其最小尺寸為8,32位系統(tǒng)上最小尺寸為4. */ char dk_indices[]; /* "PyDictKeyEntry dk_entries[dk_usable];" */ }; typedef struct _dictkeysobject PyDictKeysObject;
從名稱來看,PyDictKeysObject 是用來存儲字典元素的 key 的。而實際上,在組合模式下,它存儲的是 key-value 對。那么,無論哪種模式,至少 key 是存儲在這個對象中的。
這個對象是我們研究的重點。
PyDictKeysObject 的內(nèi)存布局如下所示:
我們在上邊代碼中簡單標(biāo)注了 PyDictObject 各成員變量的含義。現(xiàn)在重點關(guān)注dk_indices。
dk_indices 是一個 char 類型的數(shù)組,從定義來看,這是一塊裸內(nèi)存。它正是哈希表真正使用的存儲空間。
dk_indices 數(shù)組的前部分存放的是字典元素(鍵值對)在 dk_entries 中的索引值。我們可把這部分叫做:哈希表索引內(nèi)存塊。
根據(jù)數(shù)組大小的不同,每個索引值的類型具有不同的解釋方法。
索引類型 | 數(shù)組大小 dk_size |
---|---|
int8 | dk_size <= 128 |
int16 | 256 <= dk_size <= 2**15 |
int32 | 2**16 <= dk_size <= 2**31 |
int64 | dk_size >= 2**32 |
由此可見,數(shù)組越大,每個值表示的索引范圍也越大。
每個索引值的取值區(qū)間為[0, dk_size*2/3],或者為:-1(內(nèi)存未被使用過),-2(內(nèi)存已使用過)。
dk_indices 數(shù)組的后半部分用于存儲 dict 中的元素。這段空間被解釋為:PyDictKeyEntry dk_entries[dk_usable]。我們可把這部分叫做:哈希表鍵值對內(nèi)存塊。
dk_entries 中元素的個數(shù)為 dk_size 的 2/3。這個值既能有效減少 key 的沖突,也可提升內(nèi)存空間的利用率。
3,字典元素
typedef struct { Py_hash_t me_hash; /* 對 me_key 哈希值的緩存 */ PyObject *me_key; PyObject *me_value; /* 僅當(dāng)哈希表為組合模式時有意義 */ } PyDictKeyEntry;
哈希表為組合模式時,這里邊存放的就是我們的鍵值對。
哈希表為分離模式時,僅通過 me_key 存儲元素是 key。
【hash 表】
從上邊數(shù)據(jù)結(jié)構(gòu)的定義中,我們已經(jīng)知道,dict 會將鍵值對存放在一塊連續(xù)的內(nèi)存空間 dk_indices 中。dk_indices 正是 dict 使用的哈希表。
那么, 如何理解 dk_indices 這個哈希表呢?
通常,哈希表有兩種實現(xiàn)方式:沖突鏈和開放尋址。這兩種方式對應(yīng)的是兩種解決鍵沖突的方法。
沖突鏈:將哈希值相同的 key 組織為一個鏈表。
哈希表只存放指向元素鏈表的指針,哈希值相同的元素依次追加到每個鏈表的尾部。
開放尋址:從哈希表中的沖突位置查找下一個可用的位置。
元素存放在哈希表中,若發(fā)現(xiàn)沖突,從沖突位置(如 kv1 所在位置)開始通過某種策略查找下一個可用的位置(如 kv3)。
CPython 采用的是開放尋址方式,并且使用了一種優(yōu)化的存儲結(jié)構(gòu)。
dk_indices 數(shù)組的前部分用來存儲鍵值對的位置索引,后部分用來存儲鍵值對。這是一種高效緊湊的存儲結(jié)構(gòu)。
我們從 dictobject.c 的 insert_dict() 函數(shù)中截取一段代碼,來驗證這個結(jié)構(gòu)。
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value) 函數(shù)用于向字典 mp 中插入一個哈希值為 hash 的 key-value 鍵值對。
這個片段開頭的 if (ix == DKIX_EMPTY) 表明可以將這個鍵值對插入哈希表的一個未曾使用過的位置(稱為 slot)中。
代碼接下來檢查哈希表剩余空間是否可用,不足則 resize。
接下來調(diào)用 find_empty_slot() 獲取 slot 在哈希表索引內(nèi)存塊中的位置索引 hashpos,這個函數(shù)實現(xiàn)了沖突算法。
通過 DK_ENTRIES 宏獲取 ma_keys 中下一塊可用的內(nèi)存 ep,由于哈希表鍵值對內(nèi)存塊是連續(xù)的,下一塊可用的內(nèi)存可通過當(dāng)前已存儲的鍵值對個數(shù) dk_nentries 加上 dk_indices 前部分的偏移計算而來。
#define DK_ENTRIES(dk) \ ((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))
我們通過 DK_ENTRIES 的宏定義能清楚地看到它是在訪問 dk_indices 的鍵值對內(nèi)存塊。
現(xiàn)在,我們知道了元素在哈希表索引內(nèi)存塊中的位置 hashpos 和在鍵值對內(nèi)存塊中的“相對位置” dk_nentries,調(diào)用 dictkeys_set_index() 即可在哈希表中設(shè)置這兩者的關(guān)系:indices[hashpos] = dk_nentries.
接下來的代碼對 ep 指向的內(nèi)存數(shù)據(jù)進行了更新,并累加 dk_nentries。
大家可仔細體會一下這個過程。
這種存儲結(jié)構(gòu),也保證了使用 key 訪問元素的效率。
由 key 的哈希值能快速映射到元素在哈希表索引內(nèi)存塊的位置 hashpos,再由 hashpos 中保存的鍵值對內(nèi)存塊的位置偏移“索引”就可以直接訪問對應(yīng)的鍵值對。
【hash 算法和沖突算法】
實現(xiàn)哈希表有三個重要的元素:數(shù)據(jù)結(jié)構(gòu)、hash 算法和沖突算法。
我們已經(jīng)了解了數(shù)據(jù)結(jié)構(gòu)。那么,CPython 使用什么 hash 算法呢?
如果你沒有手動實現(xiàn) __hash__ 方法,它就使用內(nèi)置的 hash() 函數(shù)來計算 key 的哈希值。
CPython 采用開放尋址的方法來解決沖突。
其沖突算法如下:
首先初始化哈希表的位置索引 i,然后獲取 i 處存放的鍵值對內(nèi)存塊的索引 ix。在循環(huán)中不斷更新 i 并檢測 ix 的值,直到 ix < 0,即此時哈希表索引內(nèi)存塊的 i 處代表著一個從未使用的 slot。
更新 i 的算法不太容易理解,可不用深究。
【如何保持元素插入順序】
dict 一個有趣的特性就是會保持元素插入時的位置順序:
>>> d={} >>> d[3]="Three" >>> d[1]="One" >>> d[2]="Two" >>> d[0]="Zero" >>> d {3: 'Three', 1: 'One', 2: 'Two', 0: 'Zero'} >>> >>> list(d.keys()) [3, 1, 2, 0]
從上邊對哈希表的分析中,我們很容易就能明白其中的原因:元素被逐個追加到鍵值對內(nèi)存塊的尾部。
當(dāng)我們打印 dict,或調(diào)用其 keys() 方法時,dict 直接訪問鍵值對內(nèi)存塊。因而可按照元素插入時的順序?qū)⑺鼈兎祷亍?/p>
【resize】
既然 dict 使用了連續(xù)的內(nèi)存塊來實現(xiàn)哈希表,那么當(dāng)插入較多元素時,其內(nèi)存空間有可能不足,這時就需要擴大內(nèi)存。另一方面,如果之前已分配了較大內(nèi)存空間,而后執(zhí)行了大量刪除元素的操作,這時候也有必要減小內(nèi)存,避免浪費。
static int insertion_resize(PyDictObject *mp) { return dictresize(mp, GROWTH_RATE(mp)); }
insertion_resize() 調(diào)用 dictresize() 來調(diào)整 dict 的大小。dictresize() 的第二個參數(shù)就是調(diào)整后的大小,這里是一個宏。在 CPython 3.9.2 中,其定義為:
#define GROWTH_RATE(d) ((d)->ma_used*3)
可以看到,dict 的大小會被調(diào)整為原來已使用(包含有效鍵值對)內(nèi)存的 3 倍。
這個調(diào)整幅度還是蠻大的,其好處是可以避免頻繁 resize。
【結(jié)語】
本文簡單介紹了 Python 字典的底層數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)算法,通過使用內(nèi)存優(yōu)化的哈希表,dict 很好地支持了快速查找和插入有序等特性。這種數(shù)據(jù)結(jié)構(gòu)設(shè)計方法非常很值得我們在開發(fā)中借鑒使用。
感謝各位的閱讀,以上就是“Python 實現(xiàn)字典特性的原理”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對Python 實現(xiàn)字典特性的原理這一問題有了更深刻的體會,具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián),小編將為大家推送更多相關(guān)知識點的文章,歡迎關(guān)注!