字典是怎么創建的，支持的操作又是如何實現的？

作者：古明地覺 2024-08-22 10:11:00

關于字典是怎么創建的，以及它添加鍵值對、基于鍵獲取值的源碼細節，我們就分析完了。當然還沒有結束，字典還有很多的自定義方法，我們下一篇文章來剖析這些自定義方法的實現細節。?

楔子

到目前為止，我們對字典應該已經有了細致的了解了，本篇文章來聊一聊字典的創建和相關操作，通過底層的源碼實現，來進一步剖析字典。

字典的創建

字典在底層對應 PyDictObject 實例，它是怎么創建的呢？解釋器提供了 PyDict_New 函數，會創建一個容量為 8 的字典。

// Objects/dictobject.c

// 對于結合表，鍵值對均由 PyDictKeysObject 維護
// 它一旦被創建，那么 dk_indices 的長度至少是 8
// 至于 dk_indices 里面的元素初始為 -1，表示哈希槽尚未被使用
static PyDictKeysObject empty_keys_struct = {
    _Py_IMMORTAL_REFCNT, /* dk_refcnt */
    0,                   /* dk_log2_size */
    0,                   /* dk_log2_index_bytes */
    DICT_KEYS_UNICODE,   /* dk_kind */
    1,                   /* dk_version */
    0,                   /* dk_usable (immutable) */
    0,                   /* dk_nentries */
    {DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
     DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
};

#define Py_EMPTY_KEYS &empty_keys_struct


PyObject *
PyDict_New(void)
{
    PyInterpreterState *interp = _PyInterpreterState_GET();
    return new_dict(interp, Py_EMPTY_KEYS, NULL, 0, 0);
}

static PyObject *
new_dict(PyInterpreterState *interp,
         PyDictKeysObject *keys, PyDictValues *values,
         Py_ssize_t used, int free_values_on_failure)
{
   // 解釋一下相關參數
   /* interp: 進程狀態對象
    * keys: PyDictKeysObject 實例
    * values: 維護字典的值，如果是結合表，那么為 NULL
    *         所以 PyDict_New 創建的是結合表
    * used: 鍵值對的個數，初始為 0
    */
    // 指向創建的字典
    PyDictObject *mp;
    assert(keys != NULL);
    // 字典也有緩存池，關于緩存池我們之后再說，這里先不管
#if PyDict_MAXFREELIST > 0
    struct _Py_dict_state *state = get_dict_state(interp);
    if (state->numfree) {
        mp = state->free_list[--state->numfree];
        assert (mp != NULL);
        assert (Py_IS_TYPE(mp, &PyDict_Type));
        OBJECT_STAT_INC(from_freelist);
        _Py_NewReference((PyObject *)mp);
    }
    else
#endif
    {
        // 為 PyDictObject 對象申請內存
        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
        // 由于是先為 PyDictKeysObject 申請內存
        // 所以當 PyDictObject 的內存申請失敗時，還要處理 PyDictKeysObject
        if (mp == NULL) {
            dictkeys_decref(interp, keys);
            if (free_values_on_failure) {
                free_values(values);
            }
            return NULL;
        }
    }
    // 字段初始化，而 keys 和 values 都是外界提前創建好，然后傳過來的
    mp->ma_keys = keys;
    mp->ma_values = values;
    mp->ma_used = used;
    mp->ma_version_tag = DICT_NEXT_VERSION(interp);
    ASSERT_CONSISTENT(mp);
    // 返回字典
    return (PyObject *)mp;
}

所以整個過程分為兩步：

先創建 PyDictKeysObject 實例（如果是分離表，那么還要創建 PyDictValues 實例），底層默認提供了一個 Py_EMPTY_KEYS。
再創建 PyDictObject 實例，然后通過 ma_keys 字段使兩者建立聯系。

PyDictObject 實例的創建過程我們已經知道了，接下來是 PyDictKeysObject 實例的創建，只有它創建了，才能作為參數傳遞給 new_dict 函數。

// Objects/dictobject.c

static PyDictKeysObject*
new_keys_object(PyInterpreterState *interp, uint8_t log2_size, bool unicode)
{   
    PyDictKeysObject *dk;
    Py_ssize_t usable;
    int log2_bytes;
    // entry 的大小
    // 如果 key 全部是字符串，那么大小為 16 字節，否則是 24 字節
    size_t entry_size = unicode ? sizeof(PyDictUnicodeEntry) \
                        : sizeof(PyDictKeyEntry);

    assert(log2_size >= PyDict_LOG_MINSIZE);
    // USABLE_FRACTION((size_t)1<<log2_size) 表示鍵值對數組的長度
    // 它等于哈希索引數組長度的 2/3
    usable = USABLE_FRACTION((size_t)1<<log2_size);
    // 1 << log2_size 表示哈希索引數組的長度
    // 1 << log2_bytes 表示哈希索引數組的內存大小
    // 如果 log2_size < 8，即 (1 << log2_size) < 256
    // 那么哈希索引數組中，每個元素占 1 字節
    // 此時 (1 << log2_bytes) == (1 << log2_size)
    // 所以將 log2_size 賦值給 log2_bytes
    if (log2_size < 8) {
        log2_bytes = log2_size;
    }
    // 如果 256 <= (1 << log2_size) < 65536
    // 那么哈希索引數組中，每個元素占 2 字節
    // 此時 (1 << log2_bytes) == (1 << log2_size) * 2
    // 而 (1 << log2_size) * 2 等價于 (1 << (log2_size + 1))
    // 所以 log2_bytes = log2_size + 1
    else if (log2_size < 16) {
        log2_bytes = log2_size + 1;
    }
    // 此時哈希索引數組每個元素占 8 字節
    // (1 <= log2_bytes) == (1 << log2_size) * 2 * 2 * 2
    // 所以 log2_bytes = log2_size + 3
    else if (log2_size >= 32) {
        log2_bytes = log2_size + 3;
    }
    // 否則說明哈希索引數組每個元素占 4 字節
    // (1 <= log2_bytes) == (1 << log2_size) * 2 * 2
    // 所以 log2_bytes = log2_size + 2
    else {
        log2_bytes = log2_size + 2;
    }
    
    // 不僅是 PyDictObject，PyDictKeysObject 同樣也有自己的緩存池
    // 關于它的緩存池，同樣之后再聊，這里先不關心
#if PyDict_MAXFREELIST > 0
    struct _Py_dict_state *state = get_dict_state(interp);
    if (log2_size == PyDict_LOG_MINSIZE && unicode 
     && state->keys_numfree > 0) {
        dk = state->keys_free_list[--state->keys_numfree];
        OBJECT_STAT_INC(from_freelist);
    }
    else
#endif
    {
        // 為 PyDictKeysObject 申請內存，當然還包括兩個數組
        // 哈希索引數組的內存大小為 1 << log2_bytes
        // 鍵值對數組的大小為 entry_size * usable
        dk = PyObject_Malloc(sizeof(PyDictKeysObject)
                             + ((size_t)1 << log2_bytes)
                             + entry_size * usable);
        if (dk == NULL) {
            PyErr_NoMemory();
            return NULL;
        }
    }
    // 字段初始化
    dk->dk_refcnt = 1;
    dk->dk_log2_size = log2_size;
    dk->dk_log2_index_bytes = log2_bytes;
    dk->dk_kind = unicode ? DICT_KEYS_UNICODE : DICT_KEYS_GENERAL;
    dk->dk_nentries = 0;
    dk->dk_usable = usable;
    dk->dk_version = 0;
    // memset 是一個 C 庫函數：memset(p, val, size)
    // 作用是從指針 p 開始，將之后的 size 個字節的值全部初始化為 val
    // 顯然這里是將哈希索引數組的元素都設置為 -1，注：(char)0xff == -1
    memset(&dk->dk_indices[0], 0xff, ((size_t)1 << log2_bytes));
    // 將鍵值對數組中每個 entry 的字段都設置為 0
    // entry 的內存已經申請了，但還沒有保存任何的鍵值對
    // 所以將 me_hash、me_key、me_value 全部設置為 0
    // 注：對于指針類型來說，賦值為 0 和 NULL 是等價的，因為 NULL 保存的地址就是 0
    memset(&dk->dk_indices[(size_t)1 << log2_bytes], 0, entry_size * usable);
    return dk;
}

以上就是 PyDictKeysObject 實例的創建，當它創建完畢后，再作為參數傳遞給 new_dict 函數創建 PyDictObject 實例，整個過程還是比較簡單的。

字典都有哪些方法？

首先類型對象定義了三個方法簇：

tp_as_number：實例對象作為數值型對象擁有的方法；
tp_as_sequence：實例對象作為序列型對象擁有的方法；
tp_as_mapping：實例對象作為映射型對象擁有的方法；

當然啦，這三個方法簇對實例對象的類型要求并不嚴格，比如字符串作為序列型對象，也可以實現 tp_as_number，比如字符串實現了里面的取模運算符，用于格式化。

那么字典呢，它的這幾個方法簇都定義了哪些方法呢？

// object/dictobject.c
static PyNumberMethods dict_as_number = {
    .nb_or = dict_or,
    .nb_inplace_or = dict_ior,
};

static PySequenceMethods dict_as_sequence = {
    0,                          /* sq_length */
    0,                          /* sq_concat */
    0,                          /* sq_repeat */
    0,                          /* sq_item */
    0,                          /* sq_slice */
    0,                          /* sq_ass_item */
    0,                          /* sq_ass_slice */
    PyDict_Contains,            /* sq_contains */
    0,                          /* sq_inplace_concat */
    0,                          /* sq_inplace_repeat */
};

static PyMappingMethods dict_as_mapping = {
    (lenfunc)dict_length, /*mp_length*/
    (binaryfunc)dict_subscript, /*mp_subscript*/
    (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
};

以上就是字典的幾個方法簇，我們從 Python 的角度來演示一下。

# dict_as_number.nb_or：用于合并兩個字典
d1 = {"a": 1, "b": 2}
d2 = {"c": 3, "d": 4}
print(d1 | d2)
"""
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
"""
# 等價于如下
print({**d1, **d2})
"""
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
"""

# dict_as_number.nb_inplace_or：更新字典
d1 |= d2  # 等價于 d1.update(d2)
print(d1)
"""
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
"""

# dict_as_sequence.sq_contains：判斷 key 是否存在
print("a" in d1)
"""
True
"""

# dict_as_mapping.dict_length：返回字典長度
print(len(d1))
"""
4
"""

# dict_as_mapping.dict_subscript：基于 key 獲取 value
print(d1["a"])
"""
1
"""

# dict_as_mapping.dict_ass_sub：設置 key、value
d1["高老師"] = "美男子"
print(d1["高老師"])
"""
美男子
"""

以上三個方法簇是很多對象共有的，里面的每一個 C 函數都對應 Python 的一個魔法方法，比如：

dict_as_number.nb_or 對應 Python 的 __or__。
dict_as_mapping.mp_subscript 對應 Python 的 __getitem__。
dict_as_mapping.mp_ass_subscript 對應 Python 的 __setitem__。

接下來我們就從源碼的角度，來看看這些方法是怎么實現的。

設置鍵值對

設置鍵值對，比如 d["a"] = 1，那么會調用 dict_as_mapping.mp_ass_subscript，看一下它的具體邏輯。

// Objects/dictobject.c
static int
dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
{   
    // 參數 mp 指向字典，參數 v 指向 key，參數 w 指向 value
    // 雖然是設置鍵值對，但如果 w == NULL，那么也可以實現刪除的效果
    if (w == NULL)
        return PyDict_DelItem((PyObject *)mp, v);
    else
        return PyDict_SetItem((PyObject *)mp, v, w);
}


int
PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
    // op 必須指向字典
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    assert(key);
    assert(value);
    // Py_NewRef(obj) 會增加 obj 指向對象的引用計數，并返回 obj
    // 所以這里將 key、value 的引用計數加 1 之后，又調用了 _PyDict_SetItem_Take2
    return _PyDict_SetItem_Take2((PyDictObject *)op,
                                 Py_NewRef(key), Py_NewRef(value));
}

int
_PyDict_SetItem_Take2(PyDictObject *mp, PyObject *key, PyObject *value)
{
    assert(key);
    assert(value);
    assert(PyDict_Check(mp));
    Py_hash_t hash;
    // 如果 key 不是字符串，或者 key 是字符串、但哈希值等于 -1（尚未計算）
    // 那么計算哈希值
    if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
        hash = PyObject_Hash(key);
        if (hash == -1) {
            Py_DECREF(key);
            Py_DECREF(value);
            return -1;
        }
    }
    PyInterpreterState *interp = _PyInterpreterState_GET();
    // 如果是一個空字典，那么調用 insert_to_emptydict
    if (mp->ma_keys == Py_EMPTY_KEYS) {
        return insert_to_emptydict(interp, mp, key, hash, value);
    }
    // 不是空字典，那么調用 insertdict
    return insertdict(interp, mp, key, hash, value);
}

所以最終會調用 insert_to_emptydict 或 insertdict，這里我們直接看 insertdict 函數的具體實現。

// Objects/dictobject.c
static int
insertdict(PyInterpreterState *interp, PyDictObject *mp,
           PyObject *key, Py_hash_t hash, PyObject *value)
{
    PyObject *old_value;
    // 如果 dk_kind 不等于 DICT_KEYS_GENERAL，即所有的 key 都是字符串
    // 但是新插入的 key 不是字符串，那么字典的結構要發生改變
    // 此時會調用 insertion_resize 函數，該函數內部會調用 dictresize 函數
    // 關于 dictresize 后續介紹，這里暫時先不關注
    if (DK_IS_UNICODE(mp->ma_keys) && !PyUnicode_CheckExact(key)) {
        if (insertion_resize(interp, mp, 0) < 0)
            goto Fail;
        assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL);
    }
    // 探測函數，將 key 的哈希值映射成索引，該索引是哈希槽的索引
    // 然后返回該哈希槽存儲的鍵值對數組的索引，同時修改 old_value
    Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &old_value);
    if (ix == DKIX_ERROR)
        goto Fail;
    // GC 跟蹤
    MAINTAIN_TRACKING(mp, key, value);
    // 如果 ix == -1，說明 key 在字典中不存在
    if (ix == DKIX_EMPTY) {
        // 字典的版本號，無需關注
        uint64_t new_version = _PyDict_NotifyEvent(
                interp, PyDict_EVENT_ADDED, mp, key, value);
        // 對字典修改時，dk_version 會重置為 0，無需關注
        mp->ma_keys->dk_version = 0;
        assert(old_value == NULL);
        // 如果鍵值對數組的長度小于等于 0，說明還沒有為鍵值對數組分配內存
        // 那么依舊調用 insertion_resize，該函數后續解釋
        if (mp->ma_keys->dk_usable <= 0) {
            /* Need to resize. */
            if (insertion_resize(interp, mp, 1) < 0)
                goto Fail;
        }
        // 按照相同的規則對 key 的哈希值進行映射，并返回哈希槽的索引
        // 如果沒有撞上 Dummy 態的哈希槽，那么 dk_indices[hashpos] 會等于 ix
        // 如果在映射的過程中，撞上了 Dummy 態的哈希槽，那么直接將該槽的索引返回
        // 但不管是哪一種情況，我們都找到了一個合法的槽
        Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
        // 新的 entry 會添加在鍵值對數組中索引為 mp->ma_keys->dk_nentries 的位置
        // 因為鍵值對始終是按照先來后到的順序追加的，然后調用 dictkeys_set_index
        // 將 entry 在鍵值對數組中的索引，賦值給 mp->ma_keys->dk_indices[hashpos]
        dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
        // 添加鍵值對，如果所有的 key 都是字符串
        if (DK_IS_UNICODE(mp->ma_keys)) {
            // 鍵值對的類型為 PyDictUnicodeEntry
            PyDictUnicodeEntry *ep;
            // dk_entries[dk_nentries] 便對應新的 entry，由于內存一開始便分配好了
            // 因此所謂添加，其實就是修改它的 me_key 和 me_value 字段
            // 將這兩個字段的值，修改為參數 key 和參數 value
            ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
            // 將 me_key 字段的值設置為參數 key
            ep->me_key = key;
            // 如果 mp->ma_values 不為空，證明字典使用的是分離表
            if (mp->ma_values) {
                Py_ssize_t index = mp->ma_keys->dk_nentries;
                _PyDictValues_AddToInsertionOrder(mp->ma_values, index);
                assert (mp->ma_values->values[index] == NULL);
                // 分離表的話，value 統一由 mp->ma_values 維護
                // 至于 entry 里面的 me_value 字段則始終為 NULL
                mp->ma_values->values[index] = value;
            }
            // 否則說明字典使用的是結合表，將 entry->me_value 的值設置為 value
            else {
                ep->me_value = value;
            }
        }
        // 如果不滿足所有字段的值都是字符串，此時一定是結合表
        // 并且 entry 的類型是 PyDictKeyEntry
        else {
            PyDictKeyEntry *ep;
            // 獲取 entry，更新 me_key、me_value、me_hash
            ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
            ep->me_key = key;
            ep->me_hash = hash;
            ep->me_value = value;
        }
        // 字典長度加 1
        mp->ma_used++;
        // 更新字典的版本號
        mp->ma_version_tag = new_version;
        // 鍵值對數組還可以容納的 entry 個數減 1
        mp->ma_keys->dk_usable--;
        // 鍵值對已存儲的 entry 個數加 1
        mp->ma_keys->dk_nentries++;
        assert(mp->ma_keys->dk_usable >= 0);
        ASSERT_CONSISTENT(mp);
        return 0;
    }
    // 如果程序走到這里，說明 ix >= 0，即 key 已存在
    // 那么當 old_value != value 時，要對值進行更新
    if (old_value != value) {
        uint64_t new_version = _PyDict_NotifyEvent(
                interp, PyDict_EVENT_MODIFIED, mp, key, value);
        // 分離表，更新 mp->ma_values->values[ix]
        if (_PyDict_HasSplitTable(mp)) {
            mp->ma_values->values[ix] = value;
            if (old_value == NULL) {
                _PyDictValues_AddToInsertionOrder(mp->ma_values, ix);
                mp->ma_used++;
            }
        }
        else {
            // 結合表，獲取 entry，更新它的 me_value 字段
            assert(old_value != NULL);
            if (DK_IS_UNICODE(mp->ma_keys)) {
                DK_UNICODE_ENTRIES(mp->ma_keys)[ix].me_value = value;
            }
            else {
                DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
            }
        }
        mp->ma_version_tag = new_version;
    }
    Py_XDECREF(old_value); 
    ASSERT_CONSISTENT(mp);
    Py_DECREF(key);
    return 0;

Fail:
    Py_DECREF(value);
    Py_DECREF(key);
    return -1;
}

以上就是獲取鍵值對，源碼細節和我們之前分析哈希表時說的是一樣的。

基于 key 獲取 value

如果是獲取 value，比如 v = d["a"]，那么會調用 dict_as_mapping.mp_subscript，看一下它的具體邏輯。

// Objects/dictobject.c
static PyObject *
dict_subscript(PyDictObject *mp, PyObject *key)
{
    Py_ssize_t ix;
    Py_hash_t hash;
    PyObject *value;
    // 如果 key 不是字符串，或者 key 是字符串、但哈希值為 -1，那么計算哈希值
    if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return NULL;
    }
    // 探測函數，將 key 映射成索引，并返回對應的哈希槽存儲的鍵值對數組的索引
    // 并且在函數內部，還會對參數 value 進行修改，所以這里要傳遞指針
    // 如果鍵值對存在，那么參數 value 就是對應的值，否則 value 會等于 NULL
    ix = _Py_dict_lookup(mp, key, hash, &value);
    if (ix == DKIX_ERROR)
        return NULL;
    // 當 ix == -1 或 value == NULL 時，說明 key 對應的鍵值對不存在
    if (ix == DKIX_EMPTY || value == NULL) {
        // 但如果 mp 不是字典，即 type(mp) is not dict
        // 那么說明 mp 的類型一定繼承了 dict
        if (!PyDict_CheckExact(mp)) {
            // 檢測 mp 是否定義了 __missing__ 方法，如果定義了則調用
            // 所以該方法要定義在繼承了 dict 的子類中
            PyObject *missing, *res;
            missing = _PyObject_LookupSpecial(
                    (PyObject *)mp, &_Py_ID(__missing__));
            if (missing != NULL) {
                res = PyObject_CallOneArg(missing, key);
                Py_DECREF(missing);
                return res;
            }
            else if (PyErr_Occurred())
                return NULL;
        }
        // 到這里說明 key 不存在，并且也沒有定義 __missing__，那么 KeyError
        _PyErr_SetKeyError(key);
        return NULL;
    }
    // 否則說明鍵值對存在，那么增加引用計數，返回 value
    return Py_NewRef(value);
}

所以獲取 value 的話，也比較簡單，關鍵在于里面有一個 __missing__ 方法，我們來解釋一下。

class Dict(dict):

    def __getitem__(self, item):
        return super().__getitem__(item)

    def __missing__(self, key):
        return f"不存在的 key：{key}"


d = Dict({"a": 1, "b": 2})
# 會執行 Dict.__getitem__(d, "a")
# 在內部會調用字典的 __getitem__
print(d["a"])  # 1
print(d["b"])  # 2

# 而在調用字典的 __getitem__ 時，如果發現 key 不存在
# 那么會嘗試尋找 __missing__ 方法
print(d["c"])  # 不存在的 key：c
print(d["高老師"])  # 不存在的 key：高老師

以上就是獲取鍵值對。

小結

關于字典是怎么創建的，以及它添加鍵值對、基于鍵獲取值的源碼細節，我們就分析完了。當然還沒有結束，字典還有很多的自定義方法，我們下一篇文章來剖析這些自定義方法的實現細節。

責任編輯：武曉燕來源：古明地覺的編程教室

字典取值源碼

成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

字典是怎么創建的，支持的操作又是如何實現的？

楔子

字典的創建

字典都有哪些方法？

設置鍵值對

基于 key 獲取 value

小結