文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

字典是怎么扩容的?它会经历哪些过程?

2024-11-29 19:50

关注

而在早期,哈希表只使用一个键值对数组,这个键值对数组不仅要存储具体的 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 的幂次方,所以有两个条件:

基于以上两个限制条件,取到的最小值便是扩容之后的容量。为此 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 函数,传递的参数的含义如下:
    
    return dictresize(interp, mp, 
        calculate_log2_keysize(GROWTH_RATE(mp)), unicode);
}

所以核心在于 dictresize 函数,但这个函数比较长,在看它的内部实现之前,先来回顾一下基础知识。

图片

以上是字典的底层结构,假设变量 mp 指向了 PyDictObject 实例,那么可以得到如下信息。

因为分离表是 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,我们看一下分别使用结合表和分离表存储时,字典的结构是什么样子。

结合表:

图片

分离表:

图片

所以结合表是键和值存在一起,分离表是键和值分开存储,非常好理解。我们自己创建的字典,使用的都是结合表,分离表是为了减少对象属性字典的内存使用而专门引入的。

然后是字典(哈希表)的三种形式:

所以对于一个分离表而言,它的 key 一定都是字符串,否则不可能是分离表。而如果 key 都是字符串,那么既可以是分离表,也可以是结合表。

但如果不满足 key 都是字符串,或者说 key 没有类型限制,那么一定是结合表。所以 Generic combined table 里面的 combined 可以省略,因为当 key 的类型是 Generic 时,哈希表一定是 combined。

接着是转换关系:

好,最后我们看一下 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;
}

因为要对哈希表的种类分情况讨论,所以导致代码有点长,但逻辑不难理解:

以上就是哈希表的扩容,或者说字典的扩容,我们就介绍到这儿,下一篇文章来介绍字典的缓存池。

来源:古明地觉的编程教室内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯