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

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

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

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

1 執(zhí)行效率

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

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

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

2.1 PyDictObject

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

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

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

2.2 PyDictKeysObject

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

2.3 PyDictKeyEntry

從PyDictKeysObject中可以看到，鍵值對(duì)結(jié)構(gòu)體是由PyDictKeyEntry實(shí)現(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：鍵對(duì)象的哈希值，避免重復(fù)計(jì)算
• me_key：鍵對(duì)象指針
• me_value：值對(duì)象指針

2.4 圖示及實(shí)例

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

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

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

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

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

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

進(jìn)行查找操作，步驟如下：

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

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

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

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

3 容量策略

示例：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 dict中哈希表

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

5.1 哈希函數(shù)

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

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

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

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

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

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

>>> {[]: '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'

而用戶自定義的對(duì)象默認(rèn)便是可哈希對(duì)象，對(duì)象哈希值由對(duì)象地址計(jì)算而來(lái)，且任意兩個(gè)不同對(duì)象均不相等：

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

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

5.2 哈希沖突

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

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

  i. 鏈地址法（seperate chaining）

  ii. 開放定址法（open addressing）

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

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

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

線性探測(cè)和平方探測(cè)很簡(jiǎn)單，但同時(shí)也存在一定的問題：固定的探測(cè)序列會(huì)加大沖突的概率。Python對(duì)此進(jìn)行了優(yōu)化，探測(cè)函數(shù)參考對(duì)象哈希值，生成不同的探測(cè)序列，進(jìn)一步降低哈希沖突的可能性。Python探測(cè)方法在lookdict()函數(shù)中實(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);
        // 省略鍵比較部分代碼
        // 計(jì)算下個(gè)槽位
        // 由于參考了對(duì)象哈希值，探測(cè)序列因哈希值而異
        perturb >>= PERTURB_SHIFT;
        i = (i*5 + perturb + 1) & mask;
    }
    Py_UNREACHABLE();
}

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

5.3 哈希攻擊

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

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

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

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

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

  i. Python解釋器進(jìn)程啟動(dòng)后，產(chǎn)生一個(gè)隨機(jī)數(shù)作為鹽

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

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

5.4 刪除操作

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

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

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

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

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

5.5 問題

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

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ā)生了大量刪除（沒記錯(cuò)的話是可用個(gè)數(shù)為0時(shí)才會(huì)縮容，這里大家可以自行看下源碼），剩余元素個(gè)數(shù)減少很多，PyDictKeysObject尺寸就會(huì)變小，此時(shí)就會(huì)完成縮容（大家還記得前面提到過的dk_usable，dk_nentries等字段嗎，沒記錯(cuò)的話它們?cè)谶@里就發(fā)揮作用了，大家可以自行看下源碼）?？傊?，縮容不會(huì)在刪除的時(shí)候立刻觸發(fā)，而是在當(dāng)插入并且dk_entries耗盡時(shí)才會(huì)觸發(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)就是不斷對(duì)newsize進(jìn)行翻倍變化，找到大于minsize的最小值

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

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