Python內建類型dict的源碼是什么

這篇文章主要介紹“Python內建類型dict的源碼是什么”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“Python內建類型dict的源碼是什么”文章能幫助大家解決問題。

1 執行效率

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

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

2 內部結構

2.1 PyDictObject

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

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

dict對象在Python內部由結構體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：對象當前所保存的鍵值對個數

• ma_version_tag：對象當前版本號，每次修改時更新（版本號感覺在業務開發中也挺常見的）

• ma_keys：指向由鍵對象映射的哈希表結構，類型為PyDictKeysObject

• ma_values：splitted模式下指向所有值對象組成的數組（如果是combined模式，值會存儲在ma_keys中，此時ma_values為空）

2.2 PyDictKeysObject

從PyDictObject的源碼中可以看到，相關的哈希表是通過PyDictKeysObject來實現的，源碼如下：

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：引用計數，和映射視圖的實現有關，類似對象引用計數

• dk_size：哈希表大小，必須是2的整數次冪，這樣可以將模運算優化成位運算（可以學習一下，結合實際業務運用）

• dk_lookup：哈希查找函數指針，可以根據dict當前狀態選用最優函數

• dk_usable：鍵值對數組可用個數

• dk_nentries：鍵值對數組已用個數

• dk_indices：哈希表起始地址，哈希表后緊接著鍵值對數組dk_entries，dk_entries的類型為PyDictKeyEntry

2.3 PyDictKeyEntry

從PyDictKeysObject中可以看到，鍵值對結構體是由PyDictKeyEntry實現的，源碼如下：

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：鍵對象的哈希值，避免重復計算

• me_key：鍵對象指針

• me_value：值對象指針

2.4 圖示及實例

dict內部的hash表圖示如下：

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

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

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

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

iii. 將被插入的鍵值對在dk_entries數組中對應的下標”0“，保存于哈希索引數組dk_indices中下標為5的位置。

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

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

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

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

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

3 容量策略

示例：

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

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

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

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

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

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

4 內存優化

在Python3.6之前，dict的哈希表并沒有分成兩個數組實現，而是由一個鍵值對數組（結構和PyDictKeyEntry一樣，但是會有很多“空位”）實現，這個數組也承擔哈希索引的角色：

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

哈希值直接在數組中定位到對應的下標，找到對應的鍵值對，這樣一步就能完成。Python3.6之后通過兩個數組來實現則是出于對內存的考量。

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

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

  為了盡量節省內存，Python將鍵值對數組壓縮到原來的2/3（原來只能2/3滿，現在可以全滿），只負責存儲，索引由另一個數組負責。由于索引數組indices只需要保存鍵值對數組的下標，即保存整數，而整數占用的空間很小（例如int為4字節），因此可以節省大量內存。

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

對比一下兩種方式在內存上的開銷：

5 dict中哈希表

這一節主要介紹哈希函數、哈希沖突、哈希攻擊以及刪除操作相關的知識點。

5.1 哈希函數

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

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

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

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

>>> 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

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

5.2 哈希沖突

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

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

  i. 鏈地址法（seperate chaining）

  ii. 開放定址法（open addressing）

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

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

• 線性探測：di是一個線性函數，如：di = 2 * i

• 平方探測：di是一個二次函數，如：di = i ^ 2

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

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行，探測序列涉及到的參數是與對象的哈希值相關的，具體計算方式大家可以看下源碼，這里我就不贅述了。

5.3 哈希攻擊

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

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

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

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

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

  i. Python解釋器進程啟動后，產生一個隨機數作為鹽

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

  這樣一來，攻擊者無法獲知解釋器內部的隨機數，也就無法構造出哈希值相同的對象了。

5.4 刪除操作

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

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

哈希槽位狀態常量如下：

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

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

5.5 問題

刪除操作不會將dk_entries中的條目回收重用，隨著插入地進行，dk_entries最終會耗盡，Python將創建一個新的PyDictKeysObject，并將數據拷貝過去。新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)
        ;
    // ... 
}

源碼分析：

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

函數dictresize()的參數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循環就是不斷對newsize進行翻倍變化，找到大于minsize的最小值

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

關于“Python內建類型dict的源碼是什么”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。