3.2.1　字典對象解析

Python字典采用了散列表或者哈希表。因為理論上，在最優情況下，散列表能提供O(1)復雜度的搜索效率。Python的實現本身使用了大量字典。比如在正常情況下，每個對象都有一個__dict__屬性，再如函數的關鍵字參數**kwargs等都依賴于Python的字典，所以搜索效率是Python字典的首要目標。

Python3.6以后，字典變化較大，最大的變化就是dict變得有序了，并且效率提高了20%～30%，特別是內存利用率更高了。

下面看看C層面的關于字典實現的3個結構體。

第一個核心結構體為PyDictKeyEntry，也稱entry或slot。

entry定義的源碼位置為Objects/dict-common.h。

---

// Objects/dict-common.h
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;

---

由源碼可見，dict存儲了每一對key-value的結構體。dict中的每一對key-value對應一個PyDictKeyEntry類型的對象。

PyDictKeyEntry對象的解讀如下。

1）me_hash：存儲了key的哈希值，專門用一個成員記錄key的散列值，以避免每次查詢都要去重新計算。

2）me_value：在PyDictKeyEntry中value是一個PyObject*，這也是Python中的dict容量大的原因。在Python中，所有對象歸根結底都是PyObject對象。

3）me_key：在一個PyDictObject對象變化的過程中，entry會在不同的狀態間轉換。PyDictObject對象中的entry可以在4種狀態間轉換，分別為Unused態、Active態、Dummy態和Pending態。

·Unused：當一個entry處于Unused態時，entry的me_key和me_value都為NULL，這表示這個entry并沒有存儲（key，value）對，并且之前也沒有存儲過。每一個entry在初始化的時候都會處于這種狀態。而且只有在Unused態下，一個entry的me_key才會為NULL。

·Active：當一個entry存儲了（key，value）對時，entry便轉換到了Active態。在Active態下，me_key和me_value都不能為NULL。更進一步地說，me_key不能為dummy對象。

·Dummy：當entry中存儲的（key，value）對被刪除后，entry的狀態不能直接從Active態轉為Unused態，否則會導致沖突探測鏈的中斷。相反，entry中的me_key將指向dummy對象，entry進入Dummy態，這就是偽刪除技術。當Python沿著某條沖突鏈搜索時，如果發現entry處于Dummy態，說明目前該entry雖然是無效的，但是其后的entry可能是有效的，是應該被搜索的。這樣，就保證了沖突探測鏈的連續性。

·Pending態：索引≥0，鍵！=空，值=空（僅拆分），尚未插入拆分表中。

第二個核心結構體為PyDictKeysObject。

PyDictKeysObject源碼位置為Objects/dict-common.h。

---

// Objects/dict-common.h
typedef struct _dictkeysobject PyDictKeysObject;
/* See dictobject.c for actual layout of DictKeysObject */
struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    。。。。
};

---

對于該對象，需要關注對象中的對象映射數，即df_refcnt對象。

第三個核心結構體為PyDictObject。

PyDictObjec源碼位置為Include/cpython/dictobject.h。

---

// Objects/cpython/dictobject.h 
typedef struct _dictkeysobject PyDictKeysObject;

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;

---

PyDictObjec對象的解讀如下。

·PyObject_HEAD：是所有Python對象共有的，包含兩個成員：一個是引用計數，另一個是指向對象所屬類型的指針。

·ma_used：當使用內置函數len()去獲取字典的長度時，底層直接返回ma_used這個成員的值。

·ma_version_tag：字典版本號，全局唯一，每次字典更改，版本號也要改變。

·ma_keys：是一個指針，指向另一個核心結構體PyDictKeysObject，是實現字典的關鍵所在。

·ma_values：是一個指向指針的指針，當它為NULL時，散列表是組合的，key和value存儲在ma_keys里；當它不為NULL時，散列表是分離的，key存儲在ma_keys里，而value存儲在ma_values里。