深入理解Python虚拟机中字典(dict)的实现原理及源码剖析

目录
  • 字典数据结构分析
  • 创建新字典对象
  • 哈希表扩容机制
  • 字典插入数据
  • 总结

字典数据结构分析

/* The ma_values pointer is NULL for a combined table
 * or points to an array of PyObject* for a split table
 */
typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;
    PyDictKeysObject *ma_keys;
    PyObject **ma_values;
} PyDictObject;

struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    Py_ssize_t dk_size;
    dict_lookup_func dk_lookup;
    Py_ssize_t dk_usable;
    PyDictKeyEntry dk_entries[1];
};

typedef struct {
    /* Cached hash code of me_key. */
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;

上面的各个字段的含义为:

  • ob_refcnt,对象的引用计数。
  • ob_type,对象的数据类型。
  • ma_used,当前哈希表当中的数据个数。
  • ma_keys,指向保存键值对的数组。
  • ma_values,这个指向值的数组,但是在 cpython 的具体实现当中不一定使用这个值,因为 _dictkeysobject 当中的 PyDictKeyEntry 数组当中的对象也是可以存储 value 的,这个值只有在键全部是字符串的时候才可能会使用,在本篇文章当中主要使用 PyDictKeyEntry 当中的 value 来讨论字典的实现,因此大家可以忽略这个变量。
  • dk_refcnt,这个也是用于表示引用计数,这个跟字典的视图有关系,原理和引用计数类似,这里暂时不管。
  • dk_size,这个表示哈希表的大小,必须是 2n,这样的话可以将模运算变成位与运算。
  • dk_lookup,这个表示哈希表的查找函数,他是一个函数指针。
  • dk_usable,表示当前数组当中还有多少个可以使用的键值对。
  • dk_entries,哈希表,真正存储键值对的地方。

整个哈希表的布局大致如下图所示:

创建新字典对象

这个函数还是比较简单,首先申请内存空间,然后进行一些初始化操作,申请哈希表用于保存键值对。

static PyObject *
dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
    PyObject *self;
    PyDictObject *d;

    assert(type != NULL && type->tp_alloc != NULL);
    // 申请内存空间
    self = type->tp_alloc(type, 0);
    if (self == NULL)
        return NULL;
    d = (PyDictObject *)self;

    /* The object has been implicitly tracked by tp_alloc */
    if (type == &PyDict_Type)
        _PyObject_GC_UNTRACK(d);
    // 因为还没有增加数据 因此哈希表当中 ma_used = 0
    d->ma_used = 0;
    // 申请保存键值对的数组  PyDict_MINSIZE_COMBINED 是一个宏定义 值为 8 表示哈希表数组的最小长度
    d->ma_keys = new_keys_object(PyDict_MINSIZE_COMBINED);
    // 如果申请失败返回 NULL
    if (d->ma_keys == NULL) {
        Py_DECREF(self);
        return NULL;
    }
    return self;
}

// new_keys_object 函数如下所示
static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
    PyDictKeysObject *dk;
    Py_ssize_t i;
    PyDictKeyEntry *ep0;

    assert(size >= PyDict_MINSIZE_SPLIT);
    assert(IS_POWER_OF_2(size));
    // 这里是申请内存的位置真正申请内存空间的大小为 PyDictKeysObject 的大小加上 size-1 个PyDictKeyEntry的大小
    // 这里你可能会有一位为啥不是 size 个 PyDictKeyEntry 的大小 因为在结构体 PyDictKeysObject 当中已经申请了一个 PyDictKeyEntry 对象了
    dk = PyMem_MALLOC(sizeof(PyDictKeysObject) +
                      sizeof(PyDictKeyEntry) * (size-1));
    if (dk == NULL) {
        PyErr_NoMemory();
        return NULL;
    }
    // 下面主要是一些初始化的操作 dk_refcnt 设置成 1 因为目前只有一个字典对象使用 这个 PyDictKeysObject 对象
    DK_DEBUG_INCREF dk->dk_refcnt = 1;
    dk->dk_size = size; // 哈希表的大小
    // 下面这行代码主要是表示哈希表当中目前还能存储多少个键值对 在 cpython 的实现当中允许有 2/3 的数组空间去存储数据 超过这个数则需要进行扩容
    dk->dk_usable = USABLE_FRACTION(size); // #define USABLE_FRACTION(n) ((((n) << 1)+1)/3)
    ep0 = &dk->dk_entries[0];
    /* Hash value of slot 0 is used by popitem, so it must be initialized */
    ep0->me_hash = 0;
    // 将所有的键值对初始化成 NULL
    for (i = 0; i < size; i++) {
        ep0[i].me_key = NULL;
        ep0[i].me_value = NULL;
    }
    dk->dk_lookup = lookdict_unicode_nodummy;
    return dk;
}

哈希表扩容机制

首先我们先了解一下字典实现当中哈希表的扩容机制,当我们不断的往字典当中加入新的数据的时候,很快字典当中的数据就会达到数组长度的 23 ,这个时候就需要扩容,扩容之后的数组大小计算方式如下:

#define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))

新的数组的大小等于原来键值对的个数乘以 2 加上原来数组长度的一半。

总的来说扩容主要有三个步骤:

  • 计算新的数组的大小。
  • 创建新的数组。
  • 将原来的哈希表当中的数据加入到新的数组当中(也就是再哈希的过程)。

具体的实现代码如下所示:

static int
insertion_resize(PyDictObject *mp)
{
    return dictresize(mp, GROWTH_RATE(mp));
}

static int
dictresize(PyDictObject *mp, Py_ssize_t minused)
{
    Py_ssize_t newsize;
    PyDictKeysObject *oldkeys;
    PyObject **oldvalues;
    Py_ssize_t i, oldsize;
    // 下面的代码的主要作用就是计算得到能够大于等于 minused 最小的 2 的整数次幂
/* Find the smallest table size > minused. */
    for (newsize = PyDict_MINSIZE_COMBINED;
         newsize <= minused && newsize > 0;
         newsize <<= 1)
        ;
    if (newsize <= 0) {
        PyErr_NoMemory();
        return -1;
    }
    oldkeys = mp->ma_keys;
    oldvalues = mp->ma_values;
    /* Allocate a new table. */
   // 创建新的数组
    mp->ma_keys = new_keys_object(newsize);
    if (mp->ma_keys == NULL) {
        mp->ma_keys = oldkeys;
        return -1;
    }
    if (oldkeys->dk_lookup == lookdict)
        mp->ma_keys->dk_lookup = lookdict;
    oldsize = DK_SIZE(oldkeys);
    mp->ma_values = NULL;
    /* If empty then nothing to copy so just return */
    if (oldsize == 1) {
        assert(oldkeys == Py_EMPTY_KEYS);
        DK_DECREF(oldkeys);
        return 0;
    }
    /* Main loop below assumes we can transfer refcount to new keys
     * and that value is stored in me_value.
     * Increment ref-counts and copy values here to compensate
     * This (resizing a split table) should be relatively rare */
    if (oldvalues != NULL) {
        for (i = 0; i < oldsize; i++) {
            if (oldvalues[i] != NULL) {
                Py_INCREF(oldkeys->dk_entries[i].me_key);
                oldkeys->dk_entries[i].me_value = oldvalues[i];
            }
        }
    }
    /* Main loop */
    // 将原来数组当中的元素加入到新的数组当中
    for (i = 0; i < oldsize; i++) {
        PyDictKeyEntry *ep = &oldkeys->dk_entries[i];
        if (ep->me_value != NULL) {
            assert(ep->me_key != dummy);
            insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);
        }
    }
    // 更新一下当前哈希表当中能够插入多少数据
    mp->ma_keys->dk_usable -= mp->ma_used;
    if (oldvalues != NULL) {
        /* NULL out me_value slot in oldkeys, in case it was shared */
        for (i = 0; i < oldsize; i++)
            oldkeys->dk_entries[i].me_value = NULL;
        assert(oldvalues != empty_values);
        free_values(oldvalues);
        DK_DECREF(oldkeys);
    }
    else {
        assert(oldkeys->dk_lookup != lookdict_split);
        if (oldkeys->dk_lookup != lookdict_unicode_nodummy) {
            PyDictKeyEntry *ep0 = &oldkeys->dk_entries[0];
            for (i = 0; i < oldsize; i++) {
                if (ep0[i].me_key == dummy)
                    Py_DECREF(dummy);
            }
        }
        assert(oldkeys->dk_refcnt == 1);
        DK_DEBUG_DECREF PyMem_FREE(oldkeys);
    }
    return 0;
}

字典插入数据

我们在不断的往字典当中插入数据的时候很可能会遇到哈希冲突,字典处理哈希冲突的方法基本和集合遇到哈希冲突的处理方法是差不多的,都是使用开发地址法,但是这个开放地址法实现的相对比较复杂,具体程序如下所示:

static void
insertdict_clean(PyDictObject *mp, PyObject *key, Py_hash_t hash,
                 PyObject *value)
{
    size_t i;
    size_t perturb;
    PyDictKeysObject *k = mp->ma_keys;
    // 首先得到 mask 的值
    size_t mask = (size_t)DK_SIZE(k)-1;
    PyDictKeyEntry *ep0 = &k->dk_entries[0];
    PyDictKeyEntry *ep;

    i = hash & mask;
    ep = &ep0[i];
    for (perturb = hash; ep->me_key != NULL; perturb >>= PERTURB_SHIFT) {
        // 下面便是遇到哈希冲突时的处理办法
        i = (i << 2) + i + perturb + 1;
        ep = &ep0[i & mask];
    }
    assert(ep->me_value == NULL);
    ep->me_key = key;
    ep->me_hash = hash;
    ep->me_value = value;
}

总结

在本篇文章当中主要给大家简单介绍了一下在 cpython 内部字典的实现机制,总的来说整个字典的实现机制还是相当复杂的,本篇文章只是谈到了整个字典实现的一小部分,主要设计字典的内存布局以及相关的数据结构,最重要的字典的创建扩容和插入,这对我们理解哈希表的结构还是非常有帮助的!!!

以上就是深入理解Python虚拟机中字典(dict)的实现原理及源码剖析的详细内容,更多关于Python虚拟机字典的资料请关注我们其它相关文章!

(0)

相关推荐

  • 深入理解Python虚拟机中元组(tuple)的实现原理及源码

    目录 元组的结构 元组操作函数源码剖析 创建元组 查看元组的长度 元组当中是否包含数据 获取和设置元组中的数据 释放元组内存空间 总结 元组的结构 在这一小节当中主要介绍在 python 当中元组的数据结构: typedef struct { PyObject_VAR_HEAD PyObject *ob_item[1]; /* ob_item contains space for 'ob_size' elements. * Items must normally not be NULL, exc

  • 深入理解Python虚拟机中复数(complex)的实现原理及源码剖析

    目录 复数数据结构 复数的操作 复数加法 复数取反 Repr 函数 总结 复数数据结构 在 cpython 当中对于复数的数据结构实现如下所示: typedef struct { double real; double imag; } Py_complex; #define PyObject_HEAD PyObject ob_base; typedef struct { PyObject_HEAD Py_complex cval; } PyComplexObject; typedef struc

  • 深入理解Python虚拟机中整型(int)的实现原理及源码剖析

    目录 数据结构 深入分析 PyLongObject 字段的语意 小整数池 整数的加法实现 总结 数据结构 在 cpython 内部的 int 类型的实现数据结构如下所示: typedef struct _longobject PyLongObject; struct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; }; #define PyObject_VAR_HEAD PyVarObject ob_base; typedef struct

  • Python虚拟机栈帧对象及获取源码学习

    目录 Python虚拟机 1. 栈帧对象 1.1 PyFrameObject 1.2 栈帧对象链 1.3 栈帧获取 2. 字节码执行 Python虚拟机 注:本篇是根据教程学习记录的笔记,部分内容与教程是相同的,因为转载需要填链接,但是没有,所以填的原创,如果侵权会直接删除.此外,本篇内容大部分都咨询了ChatGPT,为笔者解决了很多问题. 问题: 在Python 程序执行过程与字节码中,我们研究了Python程序的编译过程:通过Python解释器中的编译器对 Python 源码进行编译,最终获

  • Python 虚拟机集合set实现原理及源码解析

    目录 深入理解 Python 虚拟机:集合(set)的实现原理及源码剖析 数据结构介绍 创建集合对象 往集合当中加入数据 哈希表数组扩容 从集合当中删除元素 pop 总结 深入理解 Python 虚拟机:集合(set)的实现原理及源码剖析 在本篇文章当中主要给大家介绍在 cpython 虚拟机当中的集合 set 的实现原理(哈希表)以及对应的源代码分析. 数据结构介绍 typedef struct { PyObject_HEAD Py_ssize_t fill; /* Number active

  • python中字典dict常用操作方法实例总结

    本文实例总结了python中字典dict常用操作方法.分享给大家供大家参考.具体如下: 下面的python代码展示python中字典的常用操作,字典在python开发中有着举足轻重的地位,掌握字典操作相当重要 #创建一空字典 x = {} #创建包含三个项目的字典 x = {"one":1, "two":2, "three":3} #访问其中的一个元素 x['two'] #返回字典中的所有键列表 x.keys() #返回字典中的所有值列表 x.v

  • python 实现将字典dict、列表list中的中文正常显示方法

    在代码文件中定义中文时,经常会遇到问题,要么编码错误,要么是无法正常打印显示. 例如,dict_chinese.py: #!/usr/bin/python a={'name': 'fengshou'} b={'name': "丰收"} print "a=", a print "b=", b 问题1 执行,查看结果 $ python dict_chinese.py File "dict_chinese.py", line 5 S

  • Python中getpass模块无回显输入源码解析

    本文主要讨论了python中getpass模块的相关内容,具体如下. getpass模块 昨天跟学弟吹牛b安利Python标准库官方文档的时候偶然发现了这个模块.仔细一看内容挺少的,只有两个主要api,就花了点时间阅读了一下源码,感觉挺实用的,在这安利给大家. getpass.getpass(prompt='Password: ', stream=None) 调用该函数可以在命令行窗口里面无回显输入密码.参数prompt代表提示字符串,默认是'Password: '.在Unix系统中,strea

  • python基于tkinter制作无损音乐下载工具(附源码)

    继续写GUI,本次依然使用Tkinter设计一款图形界面,使用Tkinter做一款音乐下载软件,听起来听平常的,但是我这款软件能够下载 无损音乐下载软件,听起来不错吧,Let`s go! 一.准备工作 python Tkinter 二.预览 1.搜索 2.下载 3.结果 无损音乐就这样下载完了. 三.详细设计 这里仅展示我设计的整体思路. 四.源代码 4.1 Music_Search-v1.0.py from tkinter import * from tkinter import ttk fr

  • python源码剖析之PyObject详解

    一.Python中的对象 Python中一切皆是对象. ----Guido van Rossum(1989) 这句话只要你学过python,你就很有可能在你的Python学习之旅的前30分钟就已经见过了,但是这句话具体是什么意思呢? 一句话来说,就是面向对象中的"类"和"对象"在Python中都是对象.类似于int对象的类型对象,实现了"类的概念",对类型对象"实例化"得到的实例对象实现了"对象"这个概念.

  • Python爬虫实战之虎牙视频爬取附源码

    目录 知识点 开发环境 分析目标url 开始代码 最开始还是线导入所需模块 数据请求 获取视频标题以及url地址 获取视频id 保存数据 调用函数 运行代码,得到数据 知识点 爬虫基本流程 re正则表达式简单使用 requests json数据解析方法 视频数据保存 开发环境 Python 3.8 Pycharm 爬虫基本思路流程: (重点) [无论任何网站 任何数据内容 都是按照这个流程去分析] 1.确定需求 (爬取的内容是什么东西?) 都通过开发者工具进行抓包分析 分析视频播放url地址 是

  • Python写一个简单上课点名系统(附源码)

    目录 一.准备工作 1.Tkinter 2.PIL 二.预览 1.启动 2.开始点名-顺序点名 3.开始点名-随机点名 4.手动加载人名单 5.开始点名-顺序点名-Pyqt5版本 三.思路 1.整体实现思路 2.点名实现思路 四.源代码 五.总结 一.准备工作 1.Tkinter Tkinter 是 python 内置的 TK GUI 工具集.TK 是 Tcl 语言的原生 GUI 库.作为 python 的图形设计工具,它所使用的 Tcl 语言环境已经完全嵌入到了 python 解释器中. 我们

  • 深入理解框架背后的原理及源码分析

    目录 问题1 问题2 总结 近期团队中同学遇到几个问题,想在这儿跟大家分享一波,虽说不是很有难度,但是背后也折射出一些问题,值得思考. 开始之前先简单介绍一下我所在团队的技术栈,基于这个背景再展开后面将提到的几个问题,将会有更深刻的体会. 控制层基于SpringMvc,数据持久层基于JdbcTemplate自己封装了一套类MyBatis的Dao框架,视图层基于Velocity模板技术,其余组件基于SpringCloud全家桶. 问题1 某应用发布以后开始报数据库连接池不够用异常,日志如下: co

随机推荐