在介绍字典的底层结构时我们看到，当已使用的 entry 数量达到总容量的 2/3 时，会发生扩容。
而在早期，哈希表只使用一个键值对数组，这个键值对数组不仅要存储具体的 entry，还要承载哈希索引数组的功能。本来这个方式很简单，但是内存浪费严重，于是后面 Python 官方就将一个数组拆成两个数组来实现。
不是说只能用 2/3 吗？那就只给键值对数组申请 2/3 容量的空间，并且只负责存储键值对。至于索引，则由哈希索引数组来体现。通过将 key 映射成索引，找到指定的哈希槽，再根据槽里面存储的索引，找到键值对数组中存储的 entry。
因此减少内存开销的核心就在于，避免键值对数组的浪费。
所以哈希索引数组的长度就可以看成是哈希表的容量，而键值对数组的长度本身就是哈希索引数组的 2/3、或者说容量的 2/3。那么很明显，当键值对数组满了，就说明当前的哈希表要扩容了。
// Objects/dictobject.c #define GROWTH_RATE(d) ((d)->ma_used*3)
扩容之后的新哈希表的容量要大于等于 ma_used * 3，注意：是大于等于 ma_used * 3，不是 dk_nentries * 3。因为 dk_nentries 还包含了被删除的 entry，但哈希表在扩容的时候会将其丢弃，所以扩容之后新哈希表的容量取决于 ma_used。
当然啦，哈希表的容量还要等于 2 的幂次方，所以有两个条件：
- 大于等于 ma_used * 3；
- 等于 2 的幂次方；
基于以上两个限制条件，取到的最小值便是扩容之后的容量。为此 Python 底层专门提供了一个 calculate_log2_keysize 函数，看一下它的逻辑。
// Objects/dictobject.c static inline uint8_t calculate_log2_keysize(Py_ssize_t minsize) { // 参数 minsize 表示字典的 ma_used * 3，即长度 * 3 // 1 << log2_size 便是扩容之后的字典的容量 uint8_t log2_size; // PyDict_LOG_MINSIZE 是一个宏，值为 3，所以字典的最小容量是 8 // 如果 (1 << log2_size) < minsize，那么不断循环 // 直到条件不满足时，便找到了大于等于 minsize 的最小 2 的幂次方数 for (log2_size = PyDict_LOG_MINSIZE; (((Py_ssize_t)1) << log2_size) < minsize; log2_size++) ; return log2_size; }
只不过返回的不是扩容之后的字典的容量，而是以 2 为底、容量的对数。
然后我们来看看扩容对应的具体逻辑。
// Objects/dictobject.c static int insertion_resize(PyInterpreterState *interp, PyDictObject *mp, int unicode) { // 当字典添加 entry 却发现容量不够时，会调用 insertion_resize 函数 // 该函数内部会调用 dictresize 函数，传递的参数的含义如下： /* * 参数一：进程状态对象 * 参数二：字典 * 参数三：扩容之后的字典的容量的对数 * 参数四：是否是 unicode table，即字典的 key 是否都是字符串 */ return dictresize(interp, mp, calculate_log2_keysize(GROWTH_RATE(mp)), unicode); }
所以核心在于 dictresize 函数，但这个函数比较长，在看它的内部实现之前，先来回顾一下基础知识。
以上是字典的底层结构，假设变量 mp 指向了 PyDictObject 实例，那么可以得到如下信息。
- mp->ma_keys->dk_indices 便是哈希索引数组，它的长度便是哈希表的容量。
- mp->ma_keys->dk_entries 便是键值对数组，里面的一个 entry 就是一个键值对。
- 如果字典使用的是结合表，那么 entry 的 me_key、me_value 字段负责存储键和值，此时 mp->ma_values 为 NULL。
- 如果字典使用的是分离表，那么 entry 的 me_key 字段负责存储键，me_value 字段则始终为 NULL，此时由 mp->ma_values 负责存储值，这种做法可以让多个字典共享一组 key，从而节省内存。
因为分离表是 Python 针对实例对象的属性字典单独设计的，我们平时创建的都是结合表，所以一开始并没有讨论分离表。但分离表其实非常简单，这里来补充一下吧，我们看一下 ma_values 是怎么定义的。
// Include/dictobject.h typedef struct _dictvalues PyDictValues; // Include/internal/pycore_dict.h struct _dictvalues { PyObject *values[1]; };
结构非常简单，就是维护了一个数组，保存所有的 value。另外我们发现字段 values 是一个数组，而不是指向数组首元素的二级指针，这就说明使用分离表的字典的容量是固定的，如果要扩容，那么结构会发生改变，分离表会重构为结合表。
现在假设有一个字典，里面有三个键值对 "a": 1, "b": 2, "c": 3，我们看一下分别使用结合表和分离表存储时，字典的结构是什么样子。
结合表：
分离表：
所以结合表是键和值存在一起，分离表是键和值分开存储，非常好理解。我们自己创建的字典，使用的都是结合表，分离表是为了减少对象属性字典的内存使用而专门引入的。
然后是字典（哈希表）的三种形式：
- Unicode split table：分离表，key 全部是字符串。
- Unicode combined table：结合表，key 全部是字符串。
- Generic combined table：结合表，key 的类型没有限制。
所以对于一个分离表而言，它的 key 一定都是字符串，否则不可能是分离表。而如果 key 都是字符串，那么既可以是分离表，也可以是结合表。
但如果不满足 key 都是字符串，或者说 key 没有类型限制，那么一定是结合表。所以 Generic combined table 里面的 combined 可以省略，因为当 key 的类型是 Generic 时，哈希表一定是 combined。
接着是转换关系：
- split 可以转成 combined，但反过来不行。
- unicode 可以转成 generic，但反过来不行。
好，最后我们看一下 dictresize 函数。
// Objects/dictobject.c static int dictresize(PyInterpreterState *interp, PyDictObject *mp, uint8_t log2_newsize, int unicode) { // mp->ma_keys PyDictKeysObject *oldkeys; // mp->ma_values PyDictValues *oldvalues; // log2_newsize 是扩容之后的字典的容量的对数 // 它是由 insertion_resize 函数传过来的 // SIZEOF_SIZE_T 是一个宏，在 64 位机器上等于 8 // 所以 log2_newsize 不能超过 64，即字典的容量不能达到 2 ** 64 if (log2_newsize >= SIZEOF_SIZE_T*8) { PyErr_NoMemory(); // 否则抛出 MemoryError return -1; } assert(log2_newsize >= PyDict_LOG_MINSIZE); oldkeys = mp->ma_keys; oldvalues = mp->ma_values; // 如果 !(dk->dk_kind != DICT_KEYS_GENERAL)，说明字典之前是 Generic table // 而一个 Generic table 不可能变成 Unicode table，所以将 unicode 设置为 0 if (!DK_IS_UNICODE(oldkeys)) { unicode = 0; } // 在介绍字典的创建时，我们说过这个函数，它负责为 PyDictKeysObject 实例申请内存 mp->ma_keys = new_keys_object(interp, log2_newsize, unicode); if (mp->ma_keys == NULL) { mp->ma_keys = oldkeys; return -1; } assert(mp->ma_keys->dk_usable >= mp->ma_used); // 字典的长度 Py_ssize_t numentries = mp->ma_used; // 如果 oldvalues 不为 NULL，说明字典使用的是分离表 // 那么当字典发生扩容时，要转成结合表 if (oldvalues != NULL) { // oldentries，一个 entry 16 字节 PyDictUnicodeEntry *oldentries = DK_UNICODE_ENTRIES(oldkeys); // split -> Generic combined if (mp->ma_keys->dk_kind == DICT_KEYS_GENERAL) { // newentries，一个 entry 24 字节 PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys); for (Py_ssize_t i = 0; i < numentries; i++) { int index = get_index_from_order(mp, i); PyDictUnicodeEntry *ep = &oldentries[index]; assert(oldvalues->values[index] != NULL); // key 始终存储在 entry 中 newentries[i].me_key = Py_NewRef(ep->me_key); // 设置哈希值 newentries[i].me_hash = unicode_get_hash(ep->me_key); // 将 mp->ma_values 里面的值，赋值给 entry->me_value newentries[i].me_value = oldvalues->values[index]; } // 因为扩容了，所以遍历键值对数组，依次对里面的 key 进行索引映射 // 找到指定的哈希槽，让其保存 key 对应的 entry 在键值对数组中的索引 // 因此这一步就是在重新构建哈希索引数组 build_indices_generic(mp->ma_keys, newentries, numentries); } // split -> Unicode combined else { // 代码和上面是一样的，唯一的区别就是这里 entry 的类型和之前是一样的 // 因为重构前后都是 Unicode table，所以 entry 的类型不变 PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(mp->ma_keys); for (Py_ssize_t i = 0; i < numentries; i++) { int index = get_index_from_order(mp, i); PyDictUnicodeEntry *ep = &oldentries[index]; assert(oldvalues->values[index] != NULL); newentries[i].me_key = Py_NewRef(ep->me_key); newentries[i].me_value = oldvalues->values[index]; } build_indices_unicode(mp->ma_keys, newentries, numentries); } dictkeys_decref(interp, oldkeys); // 释放 ma_values mp->ma_values = NULL; free_values(oldvalues); } // 说明字典使用的是结合表，重构的结果依旧是结合表 else { // Generic -> Generic if (oldkeys->dk_kind == DICT_KEYS_GENERAL) { assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL); PyDictKeyEntry *oldentries = DK_ENTRIES(oldkeys); PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys); // 如果 entry 的数量等于字典的长度，说明没有被删除的 entry // 那么直接 memcpy 过去即可 if (oldkeys->dk_nentries == numentries) { memcpy(newentries, oldentries, numentries * sizeof(PyDictKeyEntry)); } // 否则要遍历 oldentries，将 me_value != NULL 的 entry 拷贝过去 else { PyDictKeyEntry *ep = oldentries; for (Py_ssize_t i = 0; i < numentries; i++) { while (ep->me_value == NULL) ep++; newentries[i] = *ep++; } } // 重构哈希索引数组 build_indices_generic(mp->ma_keys, newentries, numentries); } else { PyDictUnicodeEntry *oldentries = DK_UNICODE_ENTRIES(oldkeys); // Unicode combined -> Unicode combined if (unicode) { // 逻辑和上面类似，如果不存在被删除的 entry，那么直接拷贝 // 否则的话，依次遍历，获取 me_value 不为 NULL 的 entry PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(mp->ma_keys); if (oldkeys->dk_nentries == numentries && mp->ma_keys->dk_kind == DICT_KEYS_UNICODE) { memcpy(newentries, oldentries, numentries * sizeof(PyDictUnicodeEntry)); } else { PyDictUnicodeEntry *ep = oldentries; for (Py_ssize_t i = 0; i < numentries; i++) { while (ep->me_value == NULL) ep++; newentries[i] = *ep++; } } build_indices_unicode(mp->ma_keys, newentries, numentries); } // Unicode combined -> Generic combined else { // 因为前后 entry 的大小不一样，一个 16 字节，一个 24 字节 // 所以只能遍历，然后重新给字段赋值 PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys); PyDictUnicodeEntry *ep = oldentries; for (Py_ssize_t i = 0; i < numentries; i++) { while (ep->me_value == NULL) ep++; newentries[i].me_key = ep->me_key; newentries[i].me_hash = unicode_get_hash(ep->me_key); newentries[i].me_value = ep->me_value; ep++; } build_indices_generic(mp->ma_keys, newentries, numentries); } } // Py_EMPTY_KEYS 是静态定义好的，永远存在 // 如果 oldkeys != Py_EMPTY_KEYS，那么要释放掉 if (oldkeys != Py_EMPTY_KEYS) { assert(oldkeys->dk_kind != DICT_KEYS_SPLIT); assert(oldkeys->dk_refcnt == 1); // 以下是缓存池操作，我们下一篇文章细说 #if PyDict_MAXFREELIST > 0 struct _Py_dict_state *state = get_dict_state(interp); if (DK_LOG_SIZE(oldkeys) == PyDict_LOG_MINSIZE && DK_IS_UNICODE(oldkeys) && state->keys_numfree < PyDict_MAXFREELIST) { state->keys_free_list[state->keys_numfree++] = oldkeys; OBJECT_STAT_INC(to_freelist); } else #endif { PyObject_Free(oldkeys); } } } // dk_usable 表示还可以容纳多少个键值对 // dk_nentries 表示已经容纳了多少个键值对 // 而 numentries 表示字典的长度，所以重构之后 // dk_usable 的大小要减去 numentries，dk_nentries 直接等于 numentries mp->ma_keys->dk_usable -= numentries; mp->ma_keys->dk_nentries = numentries; ASSERT_CONSISTENT(mp); return 0; }
因为要对哈希表的种类分情况讨论，所以导致代码有点长，但逻辑不难理解：
- 首先确定哈希表的容量，它要满足 2 的幂次方，并且大于等于 ma_used * 3。
- 为 ma_keys 重新申请内存。
- 根据哈希表的种类分情况讨论，但核心都是将老的没有被删除的 entry 搬过去。
- 释放 ma_keys，如果字典之前是分离表，还要释放 ma_values。
以上就是哈希表的扩容，或者说字典的扩容，我们就介绍到这儿，下一篇文章来介绍字典的缓存池。
