楔子
到目前为止，我们对字典应该已经有了细致的了解了，本篇文章来聊一聊字典的创建和相关操作，通过底层的源码实现，来进一步剖析字典。
字典的创建
字典在底层对应 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：高老师
以上就是获取键值对。
小结
关于字典是怎么创建的，以及它添加键值对、基于键获取值的源码细节，我们就分析完了。当然还没有结束，字典还有很多的自定义方法，我们下一篇文章来剖析这些自定义方法的实现细节。
