Springboot XShell Transformer cmd callback ant vue传值 jquery对象 matlab四舍五入 java遍历json数组 磁盘清理会误删东西吗 mysql将时间戳转换成日期 python内置库 python开发 python自学入门 python写入文件 java集合 java实现多线程 java文件重命名 java多线程编程 java比较字符串 java程序设计教程 java数据类型转换 千千静听绿色版 系统集成项目管理工程师教程 在线pr序列设置 vbs编程教学 反转颜色 用流量打电话的软件 思源字体 上传附件 语音分析软件 js字符转数字 s10截屏 虚拟声卡驱动 视频字幕制作软件 梦想世界科举答案 edquota 梦想世界答题器 正则表达式替换
当前位置: 首页 > 学习教程  > 编程语言

详解python-----字典

2020/10/8 20:32:42 文章标签:

前言 在python中字典是一种很重要的数据结构,我们工作中也会他的一些基本操作,今天我们就不讲操作,就简单讲一下他是怎么进行插入和获取的。有需要知道操作的可以去菜鸟教程观看。 字典的结构 python中dict的底层结构可以简单的理解成如下…

前言  

     在python中字典是一种很重要的数据结构,我们工作中也会他的一些基本操作,今天我们就不讲操作,就简单讲一下他是怎么进行插入和获取的。有需要知道操作的可以去菜鸟教程观看。

字典的结构

python中dict的底层结构可以简单的理解成如下代码所示

typedef struct {
    # me_key的散列值
    Py_hash_t me_hash;
    # 键
    PyObject *me_key;
    # 值
    PyObject *me_value;
} PyDictKeyEntry;

 在3.6之前python中dict的储存结构如下:

entries = [['--', '--', '--'],
           [-8522787127447073495, 'key1', 'val1'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
            ['--', '--', '--'],
           ['--', '--', '--'],
           [-6480567542315338377, 'key2', 'val2']]

但是在python3.6开始,借鉴 PyPy 字典设计,采用更紧凑的存储结构.内存效率更高, 

indices =  [None, 1, None, None, None, 0, None, None]
entries =  [[-9092791511155847987, 'key1', 'val1'],
            [-8522787127447073495, 'key1', 'val2']]

 indices就是哈希表,改变的只是布局, 哈希表算法将不变,更能节省空间, 新的布局迭代更快, keys() values() items(),直接在关联容器entries获取, 无需判断['--', '--', '--']空关联容器. 移动或者复制hash表,只需操作indices即可。

查询和插入过程

     我们都知道他查询的时间复杂度是O(1)是因为他是键值对的结构,那么我们知道他是怎么进行插入和查询的嘛?

      首先我们就说下字典是怎么进行插入的:

      插入数据的位置一般取决于数据的两个属性:1-键的哈希值(散列值);2-该值与其他的值的比较。在我们插入数据的时候首先会通过hash的方法得到哈希值,然后得到的哈希值会和掩码进行进行计算的到一个有效的数组索引,然后将哈希值,键的指针,值的指针放入数组中。

       举个例子来说假设初始分配了一个长度为8的数组(可以理解成8个块的内存),然后我们要放入一个键是name,value是kingname的数据。首先我们会通过hash得出key的哈希值是1278649844881305901,然后我们分配的长度为8数组,掩码就是0b111,通过计算1278649844881305901& 0b111得出索引是5,将数据放到相应的索引位置上,如图所示

    读取的时候python内部也是进行同样的步骤,先通过hash计算出哈希值,再去与掩码&位运算得出索引值,比较值相同则取出,否则使用高比特位在进行寻找新的索引。

插入时的键冲突

 看上面得例子有人肯定会问,那肯定会出现相同的索引值,那不就是数据覆盖了吗?

我们上面说过插入数据的位置取决于两个因素,一个是键的哈希值比较,另外一个是该值与其他值的比较。如果索引值相同那么会进行比较,如果是值是相同的那么就不需要插入,反之掩码会使用高比特位进行寻找新的索引,这一个过程被称为嗅探。在这个过程中仅使用了哈希值最后3个字节作为初计算索引但没有考虑其他字节,如果发生哈希值碰撞,在python中会使用哈希值中更多的比特位来解决这个问题。索引上面求索引值实际上是901& 0b111得出索引值的

字典的大小改变

   最后我们简单了解下字典是怎么改变大小的,一般在小于50000时每次改变大小都是原来的四倍,大于50000时则为原来的两倍,每次改变大小的时候都是发生在插入的时候,强调一点就是每次改变大小之后原来的数据要重新通过哈希放入,因为长度改变了他的掩码也在变,所以需要重新放入(其实有了解java  hashmap不用说就知道为什么,有空写一篇介绍hashmap)。还有一点:一般不超过大小的三分之二具有最佳空间节约的同时依然具有不错的哈希碰撞避免的概率。

 

扩展

最后的最后分享出来今天看python高性能看到一段代码,有点神似倒排索引:

 很少写博客,有不足之处可以指点出来,谢谢

知乎对python3.5前后字典解释,值得拜读


本文链接: http://www.dtmao.cc/news_show_250346.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?