字典的自定義方法是怎么實現的？

作者：古明地覺 2024-08-26 11:13:26

由于 dk_nentries = 5，說明鍵值對數組用了 5 個 entry，而在之后，第 2 個和第 5 個 entry 被刪除了。一旦刪除，那么它的 me_key 和 me_value 會被重置為 NULL，和初始 entry 是等價的。

楔子

上一篇文章我們介紹了字典的創建過程，和一些基本操作，這些操作都對應一個魔法方法。但除了這些魔法方法之外，每個對象還可以單獨定義很多自己的方法，這些方法統一由類型對象的 tp_methods 字段維護，當然這些之前已經說過了。

圖片

里面有很多的自定義方法，比如 get、pop、setdefault 等等，我們來剖析一下。

字典的 get 方法

獲取指定 key 對應的 value，如果 key 不存在，那么返回默認值。

d = {"name": "陳詩萌"}
print(d.get("name"))
"""
陳詩萌
"""
# key 不存在，返回默認值 None
print(d.get("desc"))
"""
None
"""
# 當然也可以指定默認值
print(d.get("desc", "都柏林美少女"))
"""
都柏林美少女
"""

下面看一下源碼實現。

// Objects/clinc/dictobject.c.h
#define DICT_GET_METHODDEF    \
    {"get", _PyCFunction_CAST(dict_get), METH_FASTCALL, dict_get__doc__},

static PyObject *
dict_get(PyDictObject *self, PyObject *const *args, Py_ssize_t nargs)
{   
    // 返回值
    PyObject *return_value = NULL;
    // 指定的 key
    PyObject *key;
    // 默認值，默認為 None
    PyObject *default_value = Py_None;
    // get 方法接收 1 ~ 2 個參數
    if (!_PyArg_CheckPositional("get", nargs, 1, 2)) {
        goto exit;
    }
    // args[0] 便是指定的 key
    key = args[0];
    if (nargs < 2) {
        goto skip_optional;
    }
    // args[1] 便是傳入的默認值，如果有的話
    default_value = args[1];
skip_optional:
    return_value = dict_get_impl(self, key, default_value);

exit:
    return return_value;
}

// Objects/dictobject.c
static PyObject *
dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
{
    PyObject *val = NULL;
    Py_hash_t hash;  // 哈希值
    Py_ssize_t ix;   // 哈希槽存儲的鍵值對數組的索引
    // 計算哈希值
    if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return NULL;
    }
    // 獲取 key 對應的哈希槽存儲的鍵值對數組的索引
    ix = _Py_dict_lookup(self, key, hash, &val);
    if (ix == DKIX_ERROR)
        return NULL;
    // key 不存在，那么將默認值賦值給 val
    if (ix == DKIX_EMPTY || val == NULL) {
        val = default_value;
    }
    // 增加 val 的引用計數，然后返回
    return Py_NewRef(val);
}

以上就是字典的 get 方法，非常簡單。

字典的 setdefault 方法

這是一個非常強大的方法，但是用的人不是很多。它和 get 方法類似，都是傳入一個 key 和一個默認值，如果 key 存在，那么返回 key 對應的 value，否則返回默認值。

但它和 get 方法不同的是，setdefault 在 key 不存在時，會將 key 和默認值添加到字典中。

d = {"name": "陳詩萌"}
# 當 key 存在時，兩個方法的效果是一樣的，都等價于 d[key]
print(d.get("name"))
print(d.setdefault("name"))
"""
陳詩萌
陳詩萌
"""

# 但當 key 不存在時，就有差別了
# "desc" 這個 key 不存在，返回默認值
print(d.get("desc", "都柏林美少女"))
"""
都柏林美少女
"""
# 并且原始的字典不受影響
print(d)
"""
{'name': '陳詩萌'}
"""

# 但對于 setdefault 來說，key 不存在時
# 會將 key 和默認值添加進去，然后返回默認值
print(d.setdefault("desc", "都柏林美少女"))
"""
都柏林美少女
"""
# 原始的字典會發生改變
print(d)
"""
{'name': '陳詩萌', 'desc': '都柏林美少女'}
"""

所以當獲取的 key 不存在時，v = d.setdefault(key, value) 等價于如下。

d[key] = value
v = d[key]

那么 setdefault 一般用在什么地方呢？舉個例子。

data = [
    ("陳詩萌", "2020", 5), ("陳詩萌", "2020", 2),
    ("陳詩萌", "2021", 1), ("陳詩萌", "2021", 4), ("陳詩萌", "2021", 3),

    ("高老師", "2022", 7), ("高老師", "2022", 3), ("高老師", "2022", 3),
    ("高老師", "2023", 4), ("高老師", "2023", 1)
]
# 對于上面這種數據，我們需要變成下面這個樣子
"""
{
    '陳詩萌': {
        '2020': [5, 2], 
        '2021': [1, 4, 3]
    }, 
    '高老師': {
        '2022': [7, 3, 3], 
        '2023': [4, 1]
    }
}
"""
# 如果使用 setdefault 方法，就非常好解決了
d = {}
for name, year, cnt in data:
    d.setdefault(name, {}).setdefault(year, []).append(cnt)
print(d)

下面來看一下源碼實現。

// Objects/clinc/dictobject.c.h
#define DICT_SETDEFAULT_METHODDEF    \
    {"setdefault", _PyCFunction_CAST(dict_setdefault), \
     METH_FASTCALL, dict_setdefault__doc__},

static PyObject *
dict_setdefault(PyDictObject *self, PyObject *const *args, Py_ssize_t nargs)
{
    // 這部分和 get 方法是類似的
    PyObject *return_value = NULL;
    PyObject *key;
    PyObject *default_value = Py_None;

    if (!_PyArg_CheckPositional("setdefault", nargs, 1, 2)) {
        goto exit;
    }
    key = args[0];
    if (nargs < 2) {
        goto skip_optional;
    }
    default_value = args[1];
skip_optional:
    return_value = dict_setdefault_impl(self, key, default_value);

exit:
    return return_value;
}

// Objects/dictobject.c
static PyObject *
dict_setdefault_impl(PyDictObject *self, PyObject *key,
                     PyObject *default_value)
{
    PyObject *val;
    val = PyDict_SetDefault((PyObject *)self, key, default_value);
    return Py_XNewRef(val);
}

所以核心在于 PyDict_SetDefault 函數，這個函數比較長，但邏輯不難理解。

// Objects/dictobject.c
PyObject *
PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
{
    PyDictObject *mp = (PyDictObject *)d;
    PyObject *value;
    Py_hash_t hash;
    PyInterpreterState *interp = _PyInterpreterState_GET();

    if (!PyDict_Check(d)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    // 獲取哈希值
    if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return NULL;
    }
    // 如果 mp->ma_keys 等于 Py_EMPTY_KEYS，證明字典是空的，那么 key 肯定不存在
    // 將 key 和 defaultobj 添加進字典中，并返回 defaultobj
    if (mp->ma_keys == Py_EMPTY_KEYS) {
        if (insert_to_emptydict(interp, mp, Py_NewRef(key), hash,
                                Py_NewRef(defaultobj)) < 0) {
            return NULL;
        }
        return defaultobj;
    }
    // 如果 key 不是字符串，但當前字典是 Unicode table
    // 意味著字典的結構要發生改變，調用 insertion_resize，該方法后續會聊
    if (!PyUnicode_CheckExact(key) && DK_IS_UNICODE(mp->ma_keys)) {
        if (insertion_resize(interp, mp, 0) < 0) {
            return NULL;
        }
    }
    // 獲取哈希槽存儲的鍵值對數組的索引
    Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &value);
    if (ix == DKIX_ERROR)
        return NULL;
    // 如果 ix == -1，說明 key 不存在，那么要先添加鍵值對
    if (ix == DKIX_EMPTY) {
        uint64_t new_version = _PyDict_NotifyEvent(
                interp, PyDict_EVENT_ADDED, mp, key, defaultobj);
        // 當字典的 key 集合發生改變時，dk_version 要重置為 0
        mp->ma_keys->dk_version = 0;
        // value 等于默認值
        value = defaultobj;
        // 是否還有可用空間，如果沒有，調用 insertion_resize
        if (mp->ma_keys->dk_usable <= 0) {
            if (insertion_resize(interp, mp, 1) < 0) {
                return NULL;
            }
        }
        // 返回 key 映射之后的哈希槽的索引
        Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
        // 新添加的 entry 在鍵值對數組中的索引為 mp->ma_keys->dk_nentries
        // 將該索引賦值給 dk_indices[hashpose]
        dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
        // 如果字典的 key 全部是字符串
        if (DK_IS_UNICODE(mp->ma_keys)) {
            assert(PyUnicode_CheckExact(key));
            // 那么 entry 由 PyDictUnicodeEntry 結構體表示
            PyDictUnicodeEntry *ep = \
                    &DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
            ep->me_key = Py_NewRef(key);  // 增加 key 的引用計數
            // 如果字典是分離表
            if (_PyDict_HasSplitTable(mp)) {
                Py_ssize_t index = (int)mp->ma_keys->dk_nentries;
                assert(index < SHARED_KEYS_MAX_SIZE);
                assert(mp->ma_values->values[index] == NULL);
                // 值由 mp->ma_values 存儲
                mp->ma_values->values[index] = Py_NewRef(value);
                _PyDictValues_AddToInsertionOrder(mp->ma_values, index);
            }
            // 如果字典是結合表，那么鍵和值均保存在 entry 中
            else {
                ep->me_value = Py_NewRef(value);
            }
        }
        // 說明字典的 key 不全是字符串，此時 entry 由 PyDictKeyEntry 結構體表示
        // 并且此時字典一定是結合表
        else {
            // 設置 me_key、me_value、me_hash
            PyDictKeyEntry *ep = \
                    &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
            ep->me_key = Py_NewRef(key);
            ep->me_hash = hash;
            ep->me_value = Py_NewRef(value);
        }
        MAINTAIN_TRACKING(mp, key, value);
        mp->ma_used++;  // 字典的長度加 1
        mp->ma_version_tag = new_version;  // 版本號改變
        mp->ma_keys->dk_usable--;  // 鍵值對數組中可用元素的個數減 1
        mp->ma_keys->dk_nentries++;  // 鍵值對數組中已存儲的元素的個數加 1
        assert(mp->ma_keys->dk_usable >= 0);
    }
    // ...
    ASSERT_CONSISTENT(mp);
    // 返回 value
    return value;
}

以上便是 setdefault 方法。

字典的 popitem 方法

字典的 pop 方法之前已經說過了，這里來看一下 popitem 方法。

d = {"x": 1, "y": 2, "z": 3}
# pop 方法可以彈出指定的 key，并返回對應的 value
# 如果 key 不存在，并且沒有指定默認值，會拋出 KeyError，否則返回默認值
print(d.pop("x"))  # 1

# 而 popitem 方法則是彈出字典的最后一個鍵值對
d = {"x": 1, "y": 2, "z": 3}
print(d.popitem())  # ('z', 3)
print(d)  # {'x': 1, 'y': 2}

下面看一下源碼實現。

// Objects/clinc/dictobject.c.h
#define DICT_POPITEM_METHODDEF    \
    {"popitem", (PyCFunction)dict_popitem, METH_NOARGS, dict_popitem__doc__},

static PyObject *
dict_popitem(PyDictObject *self, PyObject *Py_UNUSED(ignored))
{
    return dict_popitem_impl(self);
}

// Objects/dictobject.c
static PyObject *
dict_popitem_impl(PyDictObject *self)
{
    Py_ssize_t i, j;
    PyObject *res;
    uint64_t new_version;
    PyInterpreterState *interp = _PyInterpreterState_GET();
    // 返回值，一個二元組，負責存儲 key 和 value
    res = PyTuple_New(2);
    if (res == NULL)
        return NULL;
    // 如果字典的長度為 0，那么拋出 KeyError
    if (self->ma_used == 0) {
        Py_DECREF(res);
        PyErr_SetString(PyExc_KeyError, "popitem(): dictionary is empty");
        return NULL;
    }
    // 如果字典使用分離表，那么當 popitem 之后，要重構為結合表
    if (self->ma_keys->dk_kind == DICT_KEYS_SPLIT) {
        if (dictresize(interp, self, DK_LOG_SIZE(self->ma_keys), 1)) {
            Py_DECREF(res);
            return NULL;
        }
    }
    // 字典的 key 集合發生改變時，dk_version 要重置為 0
    self->ma_keys->dk_version = 0;

    PyObject *key, *value;
    Py_hash_t hash;
    // 字典所有的 key 都是字符串
    if (DK_IS_UNICODE(self->ma_keys)) {
        PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(self->ma_keys);
        // ma_keys->dk_nentries 表示鍵值對數組中已使用的元素個數
        // 那么 entry 的最大索引就是 ma_keys->dk_nentries - 1
        i = self->ma_keys->dk_nentries - 1;
        // 從 i 開始往前遍歷，找到第一個 me_value != NULL 的 entry
        // 因為被刪除的 entry 依舊會駐留在鍵值對數組中，但 me_key、me_value 被設置為 NULL
        while (i >= 0 && ep0[i].me_value == NULL) {
            i--;
        }
        assert(i >= 0);
        // 獲取 key
        key = ep0[i].me_key;
        new_version = _PyDict_NotifyEvent(
                interp, PyDict_EVENT_DELETED, self, key, NULL);
        hash = unicode_get_hash(key);
        // 獲取 value
        value = ep0[i].me_value;
        // 因為被彈出了，所以 entry 的 me_key 和 me_value 要重置為 NULL
        ep0[i].me_key = NULL;
        ep0[i].me_value = NULL;
    }
    // 字典的 key 不全是字符串，代碼和上面是類似的
    else {
        PyDictKeyEntry *ep0 = DK_ENTRIES(self->ma_keys);
        i = self->ma_keys->dk_nentries - 1;
        while (i >= 0 && ep0[i].me_value == NULL) {
            i--;
        }
        assert(i >= 0);

        key = ep0[i].me_key;
        new_version = _PyDict_NotifyEvent(
                interp, PyDict_EVENT_DELETED, self, key, NULL);
        hash = ep0[i].me_hash;
        value = ep0[i].me_value;
        ep0[i].me_key = NULL;
        ep0[i].me_hash = -1;
        ep0[i].me_value = NULL;
    }
    // 基于哈希值和哈希槽存儲的索引，獲取哈希槽的索引
    j = lookdict_index(self->ma_keys, hash, i);
    assert(j >= 0);
    assert(dictkeys_get_index(self->ma_keys, j) == i);
    // 將索引為 j 的哈希槽存儲的值設置為 DKIX_DUMMY
    dictkeys_set_index(self->ma_keys, j, DKIX_DUMMY);
    // res = (key, value)
    PyTuple_SET_ITEM(res, 0, key);
    PyTuple_SET_ITEM(res, 1, value);
    // 這一步一會兒解釋
    self->ma_keys->dk_nentries = i;
    // 鍵值對個數減 1
    self->ma_used--;
    self->ma_version_tag = new_version;
    ASSERT_CONSISTENT(self);
    return res;
}

以上就是 popitem 方法，但是里面有一行 self->ma_keys->dk_nentries = i; 估計讓人有些費解，我們解釋一下。

首先當鍵值對數組的空間申請之后，entry 就已經存在了，初始狀態下的 entry 的 me_key 和 me_value 均為 NULL。所以一個被偽刪除的 entry 和初始的 entry 是等價的，下面假設有這么一個鍵值對數組。

圖片

這時候如果執行 popitem，那么會彈出最后一個 me_value 不為 NULL 的 entry，即沒有被偽刪除的 entry，對于當前來說就是第 4 個 entry。

所以源碼中的 i 初始等于 dk_nentries - 1，然后往前遍歷，最終會找到索引為 3 的 entry，所以循環之后 i = 3。然后將索引為 3 的 entry 的 me_key 和 me_value 設置為 NULL，因為它被刪除了。

注意：這里關鍵來了，既然變量 i 保存的是最后一個 me_value != NULL 的 entry 的索引，那么當它被刪除之后，就意味著從索引 i 開始，后面所有的 entry 都相當于回歸到了初始狀態。

圖片

由于 dk_nentries 會被設置為 i，后續再添加鍵值對時，會添加到索引為 i 的位置。對于當前來說，添加鍵值對時，修改的是 dk_entries[3] 的 me_key 和 me_value，而不是 dk_entries[5] 的 me_key 和 me_value。

所以通過 popitem 方法，被刪除的 entry 是有可能實現復用的。

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

字典 entry 自定義

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

字典的自定義方法是怎么實現的？

楔子

字典的 get 方法

字典的 setdefault 方法

字典的 popitem 方法