44. 字典是怎么创建的，支持的操作又是如何实现的？

楔子

到目前为止，我们对字典应该已经有了非常细致的了解了，本篇文章来聊一聊字典的创建和相关操作，通过底层的源码实现，来进一步剖析字典。

字典的创建

字典在底层对应 PyDictObject 实例，它是怎么创建的呢？解释器提供了 PyDict_New 函数，会创建一个容量为 8 的字典。

// Objects/dictobject.c

// 对于结合表，键值对均由 PyDictKeysObject 维护
// 它一旦被创建，那么 dk_indices 的长度至少是 8
// 至于 dk_indices 里面的元素初始为 -1，表示哈希槽尚未被使用
static PyDictKeysObject empty_keys_struct = {
        1, /* dk_refcnt */
        1, /* dk_size */
        lookdict_split, /* dk_lookup */
        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
static PyObject *empty_values[1] = { NULL };

PyObject *
PyDict_New(void)
{
    dictkeys_incref(Py_EMPTY_KEYS);
    return new_dict(Py_EMPTY_KEYS, empty_values);
}

static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
    PyDictObject *mp;
    assert(keys != NULL);
    // 字典也有缓存池，关于缓存池我们之后再说，这里先不管
    if (numfree) {
        mp = free_list[--numfree];
        assert (mp != NULL);
        assert (Py_TYPE(mp) == &PyDict_Type);
        _Py_NewReference((PyObject *)mp);
    }
    else {
        // 为字典申请内存
        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
        if (mp == NULL) {
            // 由于是先为 PyDictKeysObject 申请内存
            // 所以当 PyDictObject 的内存申请失败时，还要处理 PyDictKeysObject
            dictkeys_decref(keys);
            if (values != empty_values) {
                free_values(values);
            }
            return NULL;
        }
    }
    // 字段初始化，而 keys 和 values 都是外界提前创建好，然后传过来的
    mp->ma_keys = keys;
    mp->ma_values = values;
    mp->ma_used = 0;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    ASSERT_CONSISTENT(mp);
    return (PyObject *)mp;
}

所以整个过程分为两步：

先创建 PyDictKeysObject 实例，底层默认提供了一个 Py_EMPTY_KEYS。
再创建 PyDictObject 实例，然后通过 ma_keys 字段使两者建立联系。

PyDictObject 实例的创建过程我们已经知道了，接下来是 PyDictKeysObject 实例的创建，只有它创建了，才能作为参数传递给 new_dict 函数。

// Objects/dictobject.c

static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
    PyDictKeysObject *dk;
    Py_ssize_t es, usable;

    assert(size >= PyDict_MINSIZE);
    assert(IS_POWER_OF_2(size));
    
    // USABLE_FRACTION(size) 表示键值对数组的长度
    // 它等于哈希索引数组长度的 2/3
    usable = USABLE_FRACTION(size);
    // 基于哈希索引数组的长度，计算每个元素的大小
    if (size <= 0xff) {
        es = 1;
    }
    else if (size <= 0xffff) {
        es = 2;
    }
#if SIZEOF_VOID_P > 4
    else if (size <= 0xffffffff) {
        es = 4;
    }
#endif
    else {
        es = sizeof(Py_ssize_t);
    }
    // 不仅是 PyDictObject，PyDictKeysObject 同样也有自己的缓存池
    // 关于它的缓存池，同样之后再聊，这里先不关心
    if (size == PyDict_MINSIZE && numfreekeys > 0) {
        dk = keys_free_list[--numfreekeys];
    }
    // 为 PyDictKeysObject 申请内存，当然还包括两个数组
    // 哈希索引数组的内存大小为 es * size
    // 键值对数组的大小为 sizeof(PyDictKeyEntry) * usable
    else {
        dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
                             + es * size
                             + sizeof(PyDictKeyEntry) * usable);
        if (dk == NULL) {
            PyErr_NoMemory();
            return NULL;
        }
    }
    _Py_INC_REFTOTAL;
    // 字段初始化
    dk->dk_refcnt = 1;
    dk->dk_size = size;
    dk->dk_usable = usable;
    dk->dk_lookup = lookdict_unicode_nodummy;
    dk->dk_nentries = 0;
    // memset 是一个 C 库函数：memset(p, val, size)
    // 作用是从指针 p 开始，将之后的 size 个字节的值全部初始化为 val
    // 显然这里是将哈希索引数组的元素都设置为 -1，注：(char)0xff == -1
    memset(&dk->dk_indices[0], 0xff, es * size);
    // 将键值对数组中每个 entry 的字段都设置为 0
    // entry 的内存已经申请了，但还没有保存任何的键值对
    // 所以将 me_hash、me_key、me_value 全部设置为 0
    // 注：对于指针类型来说，赋值为 0 和 NULL 是等价的，因为 NULL 保存的地址就是 0
    memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
    return dk;
}

以上就是 PyDictKeysObject 实例的创建，当它创建完毕后，再作为参数传递给 new_dict 函数创建 PyDictObject 实例，整个过程还是比较简单的。

字典都有哪些方法？

首先类型对象定义了三个方法簇：

tp_as_number：实例对象作为数值型对象拥有的方法；
tp_as_sequence：实例对象作为序列型对象拥有的方法；
tp_as_mapping：实例对象作为映射型对象拥有的方法；

当然啦，这三个方法簇对实例对象的类型要求并不严格，比如字符串作为序列型对象，也可以实现 tp_as_number，像字符串实现了里面的取模运算符，用于格式化。

那么字典呢，它的这几个方法簇都定义了哪些方法呢？

// Objects/dictobject.c

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 的角度来演示一下。

d = {"a": 1, "b": 2, "c": 3, "d": 4}

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

# dict_as_mapping.dict_length：返回字典长度
print(len(d))  # 4

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

# dict_as_mapping.dict_ass_sub：设置 key、value
d["高老师"] = "美男子"
print(d["高老师"])  # 美男子

接下来我们就从源码的角度，来看看这些方法是怎么实现的。

设置键值对

设置键值对，比如 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)
{
    PyDictObject *mp;
    Py_hash_t hash;
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    assert(key);
    assert(value);
    mp = (PyDictObject *)op;
    // 如果 key 不是字符串，或者 key 是字符串、但哈希值等于 -1（尚未计算）
    // 那么计算哈希值
    if (!PyUnicode_CheckExact(key) ||
        (hash = ((PyASCIIObject *) key)->hash) == -1)
    {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return -1;
    }
    // 如果是一个空字典，那么调用 insert_to_emptydict
    if (mp->ma_keys == Py_EMPTY_KEYS) {
        return insert_to_emptydict(mp, key, hash, value);
    }
    // 不是空字典，那么调用 insertdict
    return insertdict(mp, key, hash, value);
}

所以最终会调用 insert_to_emptydict 或 insertdict，这里我们直接看 insertdict 函数的具体实现。

// Objects/dictobject.c

static int
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
    PyObject *old_value;
    PyDictKeyEntry *ep;

    Py_INCREF(key);
    Py_INCREF(value);
    // 字典有两种结构，分别是分离表和结合表
    // 如果是分离表，那么 key 必须全部是字符串，因为它是为对象的属性字典引入的，而属性肯定是字符串
    // 所以当字典使用的是分离表，并且插入的 key 不是字符串时，那么要重构为结合表
    if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
        if (insertion_resize(mp) < 0)
            goto Fail;
    }
    // 探测函数，将 key 的哈希值映射成索引，该索引是哈希槽的索引
    // 然后返回该哈希槽存储的键值对数组的索引，同时修改 old_value
    Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);
    if (ix == DKIX_ERROR)
        goto Fail;

    assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);
    MAINTAIN_TRACKING(mp, key, value);

    // 分离表不仅要求 key 全部是字符串，并且不能删除，否则要重构为结合表
    if (_PyDict_HasSplitTable(mp) &&
        ((ix >= 0 && old_value == NULL && mp->ma_used != ix) ||
         (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
        if (insertion_resize(mp) < 0)
            goto Fail;
        ix = DKIX_EMPTY;
    }
    
    // 如果 ix == -1，说明 key 在字典中不存在
    if (ix == DKIX_EMPTY) {
        assert(old_value == NULL);
        // 如果键值对数组的长度小于等于 0，说明还没有为键值对数组分配内存
        // 那么依旧调用 insertion_resize，该函数后续解释
        if (mp->ma_keys->dk_usable <= 0) {
            if (insertion_resize(mp) < 0)
                goto Fail;
        }
        // 按照相同的规则对 key 的哈希值进行映射，并返回哈希槽的索引
        // 如果没有撞上 Dummy 态的哈希槽，那么 dk_indices[hashpos] 会等于 ix
        // 如果在映射的过程中，撞上了 Dummy 态的哈希槽，那么直接将该槽的索引返回
        // 但不管是哪一种情况，我们都找到了一个合法的槽
        Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
        // dk_entries[dk_nentries] 便对应新的 entry，由于内存一开始便分配好了
        // 因此所谓添加，其实就是修改它的 me_key 和 me_value 字段
        // 将这两个字段的值，修改为参数 key 和参数 value
        ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
        // 新的 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);
        // 更新 me_key 和 me_value
        ep->me_key = key;
        ep->me_hash = hash;
        // 如果 mp->ma_values 不为空，证明字典使用的是分离表
        if (mp->ma_values) {
            // 分离表的话，value 统一由 mp->ma_values 维护
            // 至于 entry 里面的 me_value 字段则始终为 NULL
            assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
            mp->ma_values[mp->ma_keys->dk_nentries] = value;
        }
        // 否则说明字典使用的是结合表，将 entry->me_value 的值设置为 value
        else {
            ep->me_value = value;
        }
        mp->ma_used++;  // 字典长度加 1
        mp->ma_version_tag = DICT_NEXT_VERSION();  // 更新字典的版本号
        mp->ma_keys->dk_usable--;  // 键值对数组还可以容纳的 entry 个数减 1
        mp->ma_keys->dk_nentries++;  // 键值对已存储的 entry 个数加 1
        assert(mp->ma_keys->dk_usable >= 0);
        ASSERT_CONSISTENT(mp);
        return 0;
    }
    // 如果程序走到这里，说明 ix >= 0，即 key 已存在
    // 那么当 old_value != value 时，要对值进行更新
    if (old_value != value) {
        // 分离表，更新 mp->ma_values->values[ix]
        if (_PyDict_HasSplitTable(mp)) {
            mp->ma_values[ix] = value;
            if (old_value == NULL) {
                /* pending state */
                assert(ix == mp->ma_used);
                mp->ma_used++;
            }
        }
        else {
            // 结合表，获取 entry，更新它的 me_value 字段
            assert(old_value != NULL);
            DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
        }
        mp->ma_version_tag = DICT_NEXT_VERSION();
    }
    Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
    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 = ((PyASCIIObject *) key)->hash) == -1) {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return NULL;
    }
    // 探测函数，将 key 映射成索引，并返回对应的哈希槽存储的键值对数组的索引
    // 并且在函数内部，还会对参数 value 进行修改，所以这里要传递二级指针
    // 如果键值对存在，那么参数 value 就是对应的值，否则 value 会等于 NULL
    ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
    if (ix == DKIX_ERROR)
        return NULL;
    // 当 ix == -1 或 value == NULL 时，说明 key 对应的键值对不存在
    if (ix == DKIX_EMPTY || value == NULL) {
        if (!PyDict_CheckExact(mp)) {
            // 但如果 mp 不是字典，即 type(mp) is not dict
            // 那么说明 mp 的类型一定继承了 dict
            PyObject *missing, *res;
            _Py_IDENTIFIER(__missing__);
            // 检测 mp 是否定义了 __missing__ 方法，如果定义了则调用
            // 所以该方法要定义在继承了 dict 的子类中
            missing = _PyObject_LookupSpecial((PyObject *)mp, &PyId___missing__);
            if (missing != NULL) {
                res = PyObject_CallFunctionObjArgs(missing,
                                                   key, NULL);
                Py_DECREF(missing);
                return res;
            }
            else if (PyErr_Occurred())
                return NULL;
        }
        // 到这里说明 key 不存在，并且也没有定义 __missing__，那么 KeyError
        _PyErr_SetKeyError(key);
        return NULL;
    }
    // 否则说明键值对存在，那么增加引用计数，返回 value
    Py_INCREF(value);
    return 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：高老师

以上就是获取键值对。

小结

关于字典是怎么创建的，以及它添加键值对、基于键获取值的源码细节，我们就分析完了。当然还没有结束，字典还有很多的自定义方法，我们下一篇文章来剖析这些自定义方法的实现细节。

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

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

CPython3.8 源码探秘

楔子

字典的创建

字典都有哪些方法？

设置键值对

基于 key 获取 value

小结