深入認識Python內(nèi)建類型——dict

注：本篇是根據(jù)教程學(xué)習(xí)記錄的筆記，部分內(nèi)容與教程是相同的，因為轉(zhuǎn)載需要填鏈接，但是沒有，所以填的原創(chuàng)，如果侵權(quán)會直接刪除。

“深入認識Python內(nèi)建類型”這部分的內(nèi)容會從源碼角度為大家介紹Python中各種常用的內(nèi)建類型。

dict是日常開發(fā)中最常用的內(nèi)建類型之一，并且Python虛擬機的運行也十分依賴dict對象。掌握好dict的底層知識，無論是對數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識的理解，還是對開發(fā)效率的提升，應(yīng)該都是有一定幫助的。

1 執(zhí)行效率

無論是Java中的Hashmap，還是Python中的dict，都是效率很高的數(shù)據(jù)結(jié)構(gòu)。Hashmap也是Java面試中的基本考點：數(shù)組+鏈表+紅黑樹的哈希表，有著很高的時間效率。同樣地，Python中的dict也由于它底層的哈希表結(jié)構(gòu)，在插入、刪除、查找等操作上都有著O(1)的平均復(fù)雜度（最壞情況下是O(n)）。這里我們將list和dict對比一下，看看二者的搜索效率差別有多大：（數(shù)據(jù)來源于原文章，大家可以自行測試下）

思考：這里原文章是比較的將需要搜索的數(shù)據(jù)分別作為list的元素和dict的key，個人認為這樣的比較并沒有意義。因為本質(zhì)上list也是哈希表，其中key是0到n-1，值就是我們要查找的元素；而這里的dict是將要查找的元素作為key，而值是True（原文章中代碼是這樣設(shè)置的）。如果真要比較可以比較下查詢list的0~n-1和查詢dict的對應(yīng)key，這樣才是控制變量法，hh。當(dāng)然這里我個人覺得不妥的本質(zhì)原因是：list它有存儲意義的地方是它的value部分，而dict的key和value都有一定的存儲意義，個人認為沒必要過分糾結(jié)這兩者的搜索效率，弄清楚二者的底層原理，在實際工程中選擇運用才是最重要的。

2 內(nèi)部結(jié)構(gòu)

2.1 PyDictObject

• 由于關(guān)聯(lián)式容器使用的場景非常廣泛，幾乎所有現(xiàn)代編程語言都提供某種關(guān)聯(lián)式容器，而且特別關(guān)注鍵的搜索效率。例如C++標(biāo)準(zhǔn)庫中的map就是一種關(guān)聯(lián)式容器，其內(nèi)部基于紅黑樹實現(xiàn)，此外還有剛剛提到的Java中的Hashmap。紅黑樹是一種平衡二叉樹，能夠提供良好的操作效率，插入、刪除、搜索等關(guān)鍵操作的時間復(fù)雜度都是O(logn)。

• Python虛擬機的運行重度依賴dict對象，像名字空間、對象屬性空間等概念的底層都是由dict對象來管理數(shù)據(jù)的。因此，Python對dict對象的效率要求更為苛刻。于是，Python中的dict使用了效率優(yōu)于O(logn)的哈希表。

dict對象在Python內(nèi)部由結(jié)構(gòu)體PyDictObject表示，源碼如下：

typedef struct {
    PyObject_HEAD
    /* Number of items in the dictionary */
    Py_ssize_t ma_used;
    /* Dictionary version: globally unique, value change each time
       the dictionary is modified */
    uint64_t ma_version_tag;
    PyDictKeysObject *ma_keys;
    /* If ma_values is NULL, the table is "combined": keys and values
       are stored in ma_keys.
       If ma_values is not NULL, the table is splitted:
       keys are stored in ma_keys and values are stored in ma_values */
    PyObject **ma_values;
} PyDictObject;

源碼分析：

• ma_used：對象當(dāng)前所保存的鍵值對個數(shù)
• ma_version_tag：對象當(dāng)前版本號，每次修改時更新（版本號感覺在業(yè)務(wù)開發(fā)中也挺常見的）
• ma_keys：指向由鍵對象映射的哈希表結(jié)構(gòu)，類型為PyDictKeysObject
• ma_values：splitted模式下指向所有值對象組成的數(shù)組（如果是combined模式，值會存儲在ma_keys中，此時ma_values為空）

2.2 PyDictKeysObject

從PyDictObject的源碼中可以看到，相關(guān)的哈希表是通過PyDictKeysObject來實現(xiàn)的，源碼如下：

struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    /* Size of the hash table (dk_indices). It must be a power of 2. */
    Py_ssize_t dk_size;
    /* Function to lookup in the hash table (dk_indices):
       - lookdict(): general-purpose, and may return DKIX_ERROR if (and
         only if) a comparison raises an exception.
       - lookdict_unicode(): specialized to Unicode string keys, comparison of
         which can never raise an exception; that function can never return
         DKIX_ERROR.
       - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further
         specialized for Unicode string keys that cannot be the <dummy> value.
       - lookdict_split(): Version of lookdict() for split tables. */
    dict_lookup_func dk_lookup;
    /* Number of usable entries in dk_entries. */
    Py_ssize_t dk_usable;
    /* Number of used entries in dk_entries. */
    Py_ssize_t dk_nentries;
    /* Actual hash table of dk_size entries. It holds indices in dk_entries,
       or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
       Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
       The size in bytes of an indice depends on dk_size:
       - 1 byte if dk_size <= 0xff (char*)
       - 2 bytes if dk_size <= 0xffff (int16_t*)
       - 4 bytes if dk_size <= 0xffffffff (int32_t*)
       - 8 bytes otherwise (int64_t*)
       Dynamically sized, SIZEOF_VOID_P is minimum. */
    char dk_indices[];  /* char is required to avoid strict aliasing. */
    /* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
       see the DK_ENTRIES() macro */
};

源碼分析：

• dk_refcnt：引用計數(shù)，和映射視圖的實現(xiàn)有關(guān)，類似對象引用計數(shù)
• dk_size：哈希表大小，必須是2的整數(shù)次冪，這樣可以將模運算優(yōu)化成位運算（可以學(xué)習(xí)一下，結(jié)合實際業(yè)務(wù)運用）
• dk_lookup：哈希查找函數(shù)指針，可以根據(jù)dict當(dāng)前狀態(tài)選用最優(yōu)函數(shù)
• dk_usable：鍵值對數(shù)組可用個數(shù)
• dk_nentries：鍵值對數(shù)組已用個數(shù)
• dk_indices：哈希表起始地址，哈希表后緊接著鍵值對數(shù)組dk_entries，dk_entries的類型為PyDictKeyEntry

2.3 PyDictKeyEntry

從PyDictKeysObject中可以看到，鍵值對結(jié)構(gòu)體是由PyDictKeyEntry實現(xiàn)的，源碼如下：

typedef struct {
    /* Cached hash code of me_key. */
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;

源碼分析：

• me_hash：鍵對象的哈希值，避免重復(fù)計算
• me_key：鍵對象指針
• me_value：值對象指針

2.4 圖示及實例

dict內(nèi)部的hash表圖示如下：

dict對象真正的核心在于PyDictKeysObject中，它包含兩個關(guān)鍵數(shù)組：一個是哈希索引數(shù)組dk_indices，另一個是鍵值對數(shù)組dk_entries。dict所維護的鍵值對，會按照先來后到的順序保存于鍵值對數(shù)組中；而哈希索引數(shù)組對應(yīng)槽位則保存著鍵值對在數(shù)組中的位置。

以向空dict對象d中插入{'jim': 70}為例，步驟如下：

i. 將鍵值對保存在dk_entries數(shù)組末尾（這里數(shù)組初始為空，末尾即數(shù)組下標(biāo)為”0“的位置）；

ii. 計算鍵對象'jim'的哈希值并取右3位（即對8取模，dk_indices數(shù)組長度為8，這里前面提到了保持數(shù)組長度為2的整數(shù)次冪，可以將模運算轉(zhuǎn)化為位運算，這里直接取右3位即可），假設(shè)最后獲取到的值為5，即對應(yīng)dk_indices數(shù)組中下標(biāo)為5的位置；

iii. 將被插入的鍵值對在dk_entries數(shù)組中對應(yīng)的下標(biāo)”0“，保存于哈希索引數(shù)組dk_indices中下標(biāo)為5的位置。

進行查找操作，步驟如下：

i. 計算鍵對象'jim'的哈希值，并取右3位，得到該鍵在哈希索引數(shù)組dk_indices中的下標(biāo)5；

ii. 找到哈希索引數(shù)組dk_indices下標(biāo)為5的位置，取出其中保存的值——0，即鍵值對在dk_entries數(shù)組中的位置；

iii. 找到dk_entries數(shù)組下標(biāo)為0的位置，取出值對象me_value。（這里我不確定在查找時會不會再次驗證me_key是否為'jim'，感興趣的讀者可以自行去查看一下相應(yīng)的源碼）

這里涉及到的結(jié)構(gòu)比較多，直接看圖示可能也不是很清晰，但是通過上面的插入和查找兩個過程，應(yīng)該可以幫助大家理清楚這里的關(guān)系。我個人覺得這里的設(shè)計還是很巧妙的，可能暫時還看不出來為什么這么做，后續(xù)我會繼續(xù)為大家介紹。

3 容量策略

示例：

>>> import sys
>>> d1 = {}
>>> sys.getsizeof(d1)
240
>>> d2 = {'a': 1}
>>> sys.getsizeof(d1)
240

可以看到，dict和list在容量策略上有所不同，Python會為空dict對象也分配一定的容量，而對空list對象并不會預(yù)先分配底層數(shù)組。下面簡單介紹下dict的容量策略。

哈希表越密集，哈希沖突則越頻繁，性能也就越差。因此，哈希表必須是一種稀疏的表結(jié)構(gòu)，越稀疏則性能越好。但是由于內(nèi)存開銷的制約，哈希表不可能無限度稀疏，需要在時間和空間上進行權(quán)衡。實踐經(jīng)驗表明，一個1/3到2/3滿的哈希表，性能是較為理想的——以相對合理的內(nèi)存換取相對高效的執(zhí)行性能。

為保證哈希表的稀疏程度，進而控制哈希沖突頻率，Python底層通過USABLE_FRACTION宏將哈希表內(nèi)元素控制在2/3以內(nèi)。USABLE_FRACTION根據(jù)哈希表的規(guī)模n，計算哈希表可存儲元素個數(shù)，也就是鍵值對數(shù)組dk_entries的長度。以長度為8的哈希表為例，最多可以保持5個鍵值對，超出則需要擴容。USABLE_FRACTION是一個非常重要的宏定義：

# define USABLE_FRACTION(n) (((n) << 1)/3)

此外，哈希表的規(guī)模一定是2的整數(shù)次冪，即Python對dict采用翻倍擴容策略。

4 內(nèi)存優(yōu)化

在Python3.6之前，dict的哈希表并沒有分成兩個數(shù)組實現(xiàn)，而是由一個鍵值對數(shù)組（結(jié)構(gòu)和PyDictKeyEntry一樣，但是會有很多“空位”）實現(xiàn)，這個數(shù)組也承擔(dān)哈希索引的角色：

entries = [    ['--', '--', '--'],
    [hash, key, value],
    ['--', '--', '--'],
    [hash, key, value],
    ['--', '--', '--'],
]

哈希值直接在數(shù)組中定位到對應(yīng)的下標(biāo)，找到對應(yīng)的鍵值對，這樣一步就能完成。Python3.6之后通過兩個數(shù)組來實現(xiàn)則是出于對內(nèi)存的考量。

• 由于哈希表必須保持稀疏，最多只有2/3滿（太滿會導(dǎo)致哈希沖突頻發(fā)，性能下降），這意味著至少要浪費1/3的內(nèi)存空間，而一個鍵值對條目PyDictKeyEntry的大小達到了24字節(jié)。試想一個規(guī)模為65536的哈希表，將浪費：

  65536 * 1/3 * 24 = 524288 B 大小的空間（512KB）

  為了盡量節(jié)省內(nèi)存，Python將鍵值對數(shù)組壓縮到原來的2/3（原來只能2/3滿，現(xiàn)在可以全滿），只負責(zé)存儲，索引由另一個數(shù)組負責(zé)。由于索引數(shù)組indices只需要保存鍵值對數(shù)組的下標(biāo)，即保存整數(shù)，而整數(shù)占用的空間很?。ɡ鏸nt為4字節(jié)），因此可以節(jié)省大量內(nèi)存。

• 此外，索引數(shù)組還可以根據(jù)哈希表的規(guī)模，選擇不同大小的整數(shù)類型。對于規(guī)模不超過256的哈希表，選擇8位整數(shù)即可；對于規(guī)模不超過65536的哈希表，16位整數(shù)足以；其他以此類推。

對比一下兩種方式在內(nèi)存上的開銷：

5 dict中哈希表

這一節(jié)主要介紹哈希函數(shù)、哈希沖突、哈希攻擊以及刪除操作相關(guān)的知識點。

5.1 哈希函數(shù)

根據(jù)哈希表性質(zhì)，鍵對象必須滿足以下兩個條件，否則哈希表便不能正常工作：

i. 哈希值在對象的整個生命周期內(nèi)不能改變

ii. 可比較，并且比較結(jié)果相等的兩個對象的哈希值必須相同

滿足這兩個條件的對象便是可哈希（hashable）對象，只有可哈希對象才可作為哈希表的鍵。因此，像dict、set等底層由哈希表實現(xiàn)的容器對象，其鍵對象必須是可哈希對象。在Python的內(nèi)建類型中，不可變對象都是可哈希對象，而可變對象則不是：

>>> hash([])
Traceback (most recent call last):
  File "<pyshell#0>", line 1, in <module>
    hash([])
TypeError: unhashable type: 'list'

dict、list等不可哈希對象不能作為哈希表的鍵：

>>> {[]: 'list is not hashable'}
Traceback (most recent call last):
  File "<pyshell#1>", line 1, in <module>
    {[]: 'list is not hashable'}
TypeError: unhashable type: 'list'
>>> {{}: 'list is not hashable'}
Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    {{}: 'list is not hashable'}
TypeError: unhashable type: 'dict'

而用戶自定義的對象默認便是可哈希對象，對象哈希值由對象地址計算而來，且任意兩個不同對象均不相等：

>>> class A:
    pass
>>> a = A()
>>> b = A()
>>> hash(a), hash(b)
(160513133217, 160513132857)
>>>a == b
False
>>> a is b
False

那么，哈希值是如何計算的呢？答案是——哈希函數(shù)。哈希值計算作為對象行為的一種，會由各個類型對象的tp_hash指針指向的哈希函數(shù)來計算。對于用戶自定義的對象，可以實現(xiàn)__hash__()魔法方法，重寫哈希值計算方法。

5.2 哈希沖突

理想的哈希函數(shù)必須保證哈希值盡量均勻地分布于整個哈?？臻g，越是接近的值，其哈希值差別應(yīng)該越大。而一方面，不同的對象哈希值有可能相同；另一方面，與哈希值空間相比，哈希表的槽位是非常有限的。因此，存在多個鍵被映射到哈希索引同一槽位的可能性，這就是哈希沖突。

• 解決哈希沖突的常用方法有兩種：

  i. 鏈地址法（seperate chaining）

  ii. 開放定址法（open addressing）

  • 為每個哈希槽維護一個鏈表，所有哈希到同一槽位的鍵保存到對應(yīng)的鏈表中

這是Python采用的方法。將數(shù)據(jù)直接保存于哈希槽位中，如果槽位已被占用，則嘗試另一個。一般而言，第i次嘗試會在首槽位基礎(chǔ)上加上一定的偏移量di。因此，探測方法因函數(shù)di而異。常見的方法有線性探測（linear probing）以及平方探測（quadratic probing）

• 線性探測：di是一個線性函數(shù)，如：di = 2 * i
• 平方探測：di是一個二次函數(shù)，如：di = i ^ 2

線性探測和平方探測很簡單，但同時也存在一定的問題：固定的探測序列會加大沖突的概率。Python對此進行了優(yōu)化，探測函數(shù)參考對象哈希值，生成不同的探測序列，進一步降低哈希沖突的可能性。Python探測方法在lookdict()函數(shù)中實現(xiàn)，關(guān)鍵代碼如下：

static Py_ssize_t _Py_HOT_FUNCTION
lookdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr)
{
    size_t i, mask, perturb;
    PyDictKeysObject *dk;
    PyDictKeyEntry *ep0;
top:
    dk = mp->ma_keys;
    ep0 = DK_ENTRIES(dk);
    mask = DK_MASK(dk);
    perturb = hash;
    i = (size_t)hash & mask;
    for (;;) {
        Py_ssize_t ix = dk_get_index(dk, i);
        // 省略鍵比較部分代碼
        // 計算下個槽位
        // 由于參考了對象哈希值，探測序列因哈希值而異
        perturb >>= PERTURB_SHIFT;
        i = (i*5 + perturb + 1) & mask;
    }
    Py_UNREACHABLE();
}

源碼分析：第20~21行，探測序列涉及到的參數(shù)是與對象的哈希值相關(guān)的，具體計算方式大家可以看下源碼，這里我就不贅述了。

5.3 哈希攻擊

Python在3.3之前，哈希算法只根據(jù)對象本身計算哈希值。因此，只要Python解釋器相同，對象哈希值也肯定相同。執(zhí)行Python2解釋器的兩個交互式終端，示例如下：（來自原文章）

>>> import os
>>> os.getpid()
2878
>>> hash('fashion')
3629822619130952182

>>> import os
>>> os.getpid()
2915
>>> hash('fashion')
3629822619130952182

如果我們構(gòu)造出大量哈希值相同的key，并提交給服務(wù)器：例如向一臺Python2Web服務(wù)器post一個json數(shù)據(jù)，數(shù)據(jù)包含大量的key，這些key的哈希值均相同。這意味哈希表將頻繁發(fā)生哈希沖突，性能由O(1)直接下降到了O(n)，這就是哈希攻擊。

• 產(chǎn)生上述問題的原因是：Python3.3之前的哈希算法只根據(jù)對象本身來計算哈希值，這樣會導(dǎo)致攻擊者很容易構(gòu)建哈希值相同的key。于是，Python之后在計算對象哈希值時，會加鹽。具體做法如下：

  i. Python解釋器進程啟動后，產(chǎn)生一個隨機數(shù)作為鹽

  ii. 哈希函數(shù)同時參考對象本身以及鹽計算哈希值

  這樣一來，攻擊者無法獲知解釋器內(nèi)部的隨機數(shù)，也就無法構(gòu)造出哈希值相同的對象了。

5.4 刪除操作

示例：向dict依次插入三組鍵值對，鍵對象依次為key1、key2、key3，其中key2和key3發(fā)生了哈希沖突，經(jīng)過處理后重新定位到dk_indices[6]的位置。圖示如下：

如果要刪除key2，假設(shè)我們將key2對應(yīng)的dk_indices[1]設(shè)置為-1，那么此時我們查詢key3時就會出錯——因為key3初始對應(yīng)的操作就是dk_indices[1]，只是發(fā)生了哈希沖突蔡最終分配到了dk_indices[6]，而此時dk_indices[1]的值為-1，就會導(dǎo)致查詢的結(jié)果是key3不存在。因此，在刪除元素時，會將對應(yīng)的dk_indices設(shè)置為一個特殊的值DUMMY，避免中斷哈希探索鏈（也就是通過標(biāo)志位來解決，很常見的做法）。

哈希槽位狀態(tài)常量如下：

#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2)  /* Used internally */
#define DKIX_ERROR (-3)

• 對于被刪除元素在dk_entries中對應(yīng)的存儲單元，Python是不做處理的。假設(shè)此時再插入key4，Python會直接使用dk_entries[3]，而不會使用被刪除的key2所占用的dk_entries[1]。這里會存在一定的浪費。

5.5 問題

刪除操作不會將dk_entries中的條目回收重用，隨著插入地進行，dk_entries最終會耗盡，Python將創(chuàng)建一個新的PyDictKeysObject，并將數(shù)據(jù)拷貝過去。新PyDictKeysObject尺寸由GROWTH_RATE宏計算。這里給大家簡單列下源碼：

static int
dictresize(PyDictObject *mp, Py_ssize_t minsize)
{
    /* Find the smallest table size > minused. */
    for (newsize = PyDict_MINSIZE;
         newsize < minsize && newsize > 0;
         newsize <<= 1)
        ;
    // ... 
}

源碼分析：

如果此前發(fā)生了大量刪除（沒記錯的話是可用個數(shù)為0時才會縮容，這里大家可以自行看下源碼），剩余元素個數(shù)減少很多，PyDictKeysObject尺寸就會變小，此時就會完成縮容（大家還記得前面提到過的dk_usable，dk_nentries等字段嗎，沒記錯的話它們在這里就發(fā)揮作用了，大家可以自行看下源碼）。總之，縮容不會在刪除的時候立刻觸發(fā)，而是在當(dāng)插入并且dk_entries耗盡時才會觸發(fā)。

函數(shù)dictresize()的參數(shù)Py_ssize_t minsize由GROWTH_RATE宏傳入：

#define GROWTH_RATE(d) ((d)->ma_used*3)
static int
insertion_resize(PyDictObject *mp)
{
    return dictresize(mp, GROWTH_RATE(mp));
}

• 這里的for循環(huán)就是不斷對newsize進行翻倍變化，找到大于minsize的最小值

• 擴容時，Python分配新的哈希索引數(shù)組和鍵值對數(shù)組，然后將舊數(shù)組中的鍵值對逐一拷貝到新數(shù)組，再調(diào)整數(shù)組指針指向新數(shù)組，最后回收舊數(shù)組。這里的拷貝并不是直接拷貝過去，而是逐個插入新表的過程，這是因為哈希表的規(guī)模改變了，相應(yīng)的哈希函數(shù)值對哈希表長度取模后的結(jié)果也會變化，所以不能直接拷貝。

以上就是Python內(nèi)建類型dict深入理解源碼學(xué)習(xí)的詳細內(nèi)容，更多關(guān)于Python內(nèi)建類型dict的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論