45. 字典的自定义方法是怎么实现的？

楔子

上一篇文章我们介绍了字典的创建过程，和一些基本操作，这些操作都对应一个魔法方法。但除了这些魔法方法之外，每个对象还可以单独定义很多自己的方法，这些方法统一由类型对象的 tp_methods 字段维护，当然这些之前已经说过了。

里面有很多的自定义方法，比如 get、pop、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;
    PyDictKeyEntry *ep0, *ep;
    PyObject *res;
    // 返回值，一个二元组，负责存储 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 之后，要重构为结合表
    // 分离表要求 key 必须全部是字符串，并且不能删除键值对
    if (self->ma_keys->dk_lookup == lookdict_split) {
        if (dictresize(self, DK_SIZE(self->ma_keys))) {
            Py_DECREF(res);
            return NULL;
        }
    }
    ENSURE_ALLOWS_DELETIONS(self);

    // 获取键值对数组
    ep0 = DK_ENTRIES(self->ma_keys);
    // ma_keys->dk_nentries 表示键值对数组中已使用的 entry 个数
    // 那么 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);
    // 获取 entry
    ep = &ep0[i];
    // 基于哈希槽存储的索引，获取哈希槽的索引
    j = lookdict_index(self->ma_keys, ep->me_hash, i);
    assert(j >= 0);
    assert(dictkeys_get_index(self->ma_keys, j) == i);
    // 因为 entry 被删除了，所以对应的哈希槽存储的值要修改为 DKIX_DUMMY
    dictkeys_set_index(self->ma_keys, j, DKIX_DUMMY);
    // 将 key 和 value 保存在元组中
    PyTuple_SET_ITEM(res, 0, ep->me_key);
    PyTuple_SET_ITEM(res, 1, ep->me_value);
    // 因为被弹出了，所以 entry 的 me_key 和 me_value 要重置为 NULL
    ep->me_key = NULL;
    ep->me_value = NULL;
    // 这一步一会儿解释
    self->ma_keys->dk_nentries = i;
    // 键值对个数减 1
    self->ma_used--;
    self->ma_version_tag = DICT_NEXT_VERSION();
    ASSERT_CONSISTENT(self);
    return res;
}

以上就是 popitem 方法，但是里面有一行 self->ma_keys->dk_nentries = i 估计让人有些费解，我们解释一下。

首先当键值对数组的空间申请之后，entry 就已经存在了，初始状态下的 entry 的 me_key 和 me_value 均为 NULL。所以一个被伪删除的 entry 和初始的 entry 是等价的，下面假设有这么一个键值对数组。

对于一个容量为 16 的哈希表，它的键值对数组的长度为 10，由于 dk_nentries = 7，说明键值对数组使用了 7 个 entry。而在之后，第 2 个 entry 和第 7 个 entry 被删除了，一旦删除，那么它的 me_key 和 me_value 会被重置为 NULL，和初始 entry 是等价的。

这时候如果执行 popitem，那么会弹出最后一个 me_value 不为 NULL 的 entry，即没有被伪删除的 entry，对于当前来说就是第 6 个 entry。所以源码中的 i 初始等于 dk_nentries - 1，然后往前遍历，最终会找到索引为 5 的 entry，所以循环之后 i = 5。然后将索引为 5 的 entry 的 me_key 和 me_value 设置为 NULL，因为它被删除了。

注意：这里关键来了，既然变量 i 保存的是最后一个 me_value != NULL 的 entry 的索引，那么当它被删除之后，就意味着从索引 i 开始，后面所有的 entry 都相当于回归到了初始状态，那么直接将 dk_nentries 设置为 i。

由于 dk_nentries 被设置为 i，后续再添加键值对时，就会添加到索引为 i 的位置。对于当前来说，添加键值对时，修改的是 dk_entries[5] 的 me_key 和 me_value，而不是 dk_entries[7] 的 me_key 和 me_value。

所以通过 popitem 方法，被删除的 entry 是有可能实现复用的。

小结

以上我们就简单分析了字典的几个自定义方法，下一篇文章来聊一聊字典的扩容。

欢迎大家关注我的公众号：古明地觉的编程教室。

如果觉得文章对你有所帮助，也可以请作者吃个馒头，Thanks♪(･ω･)ﾉ。

CPython3.8 源码探秘

楔子

字典的 get 方法

字典的 setdefault 方法

字典的 popitem 方法

小结