专栏首页Python七号为什么 Python3.6 之后字典是有序的

为什么 Python3.6 之后字典是有序的

字典的本质就是 hash 表,hash 表就是通过 key 找到其 value ,平均情况下你只需要花费 O(1) 的时间复杂度即可以完成对一个元素的查找,字典是否有序,并不是指字典能否按照键或者值进行排序,而是字典能否按照插入键值的顺序输出对应的键值。

比如,对于一个无序字典,插入顺序和遍历的顺序是不一致的:

>>> my_dict = dict()
>>> my_dict["name"] = "lowman"
>>> my_dict["age"] = 26
>>> my_dict["girl"] = "Tailand"
>>> my_dict["money"] = 80
>>> my_dict["hourse"] = None
>>> for key,value in my_dict.items():
...     print(key,value)
...
money 80
girl Tailand
age 26
hourse None
name lowman

而一个有序字典的输出是这样的:

name lowman
age 26
girl Tailand
money 80
hourse None

那为什么 Python3.6 之后,Python 的字典就有序了呢?

先从 Python3.6 之前说起。在 Python 3.6 之前,其数据结构如下图所示:

由于不同键的哈希值不一样,哈希表(entries)中的顺序是按照哈希值大小排序的,遍历时从前往后遍历并不能输出键值插入的顺序,其表现起来就是无序的。

此外,这种方式还有一个缺点,就是如果以稀疏的哈希表存储时,会浪费较多的内存空间,Python3.6 之后,对其进行了优化,哈希索引和真正的键值对分开存放,数据结构如下所示:

indices 指向了一列索引,entries 指向了原本的存储哈希表内容的结构。

你可以把 indices 理解成新的简化版的哈希表,entries 理解成一个数组,数组中的每个元素是原本应该存储的哈希结果:键和值。

查找或者插入一个元素的时候,根据键的哈希值结果取模 indices 的长度,就能得到对应的数组下标,再根据对应的数组下标到 entries 中获取到对应的结果,比如 hash("key2") % 8 的结果是 3,那么 indices[3] 的值是 1,这时候到 entries 中找到对应的 entries[1] 既为所求的结果:

这么做的好处是空间利用率得到了较大的提升,我们以 64 位操作系统为例,每个指针的长度为 8 字节,则原本需要 8 * 3 * 8 为 192

现在变成了 8 * 3 * 3 + 1 * 8 为 80,节省了 58% 左右的内存空间,如下图所示:

此外,由于 entries 是按照插入顺序进行插入的数组,对字典进行遍历时能按照插入顺序进行遍历,这也是为什么 Python3.6 以后的版本字典对象是有序的原因。

最后

如果你对 Python 解释器的实现感兴趣,可以阅读 CPython 的源码,源码之下无秘密,阅读源码也是提升自己最快的学习方式,这里推荐一个学习 CPython 的开源仓库 CPython-Internals[1],图文注释并茂,是非常有价值的学习资源。如果本文对你有帮助,还请点赞关注哈。

参考资料

[1]

CPython-Internals: https://github.com/zpoint/CPython-Internals/blob/master/README_CN.md

本文分享自微信公众号 - Python七号(PythonSeven),作者:somenzz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-10-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python3.6之后字典变成有序

    在记忆里python的字典是无序的,但是这个结果是有序的,查了一下发现在python 3.6 版本之前都是无序的,但是之后都变成有序的了。

    生信编程日常
  • 为什么Python 3.7以后字典有序并且效率更高?

    在Python 3.5(含)以前,字典是不能保证顺序的,键值对A先插入字典,键值对B后插入字典,但是当你打印字典的Keys列表时,你会发现B可能在A的前面。

    青南
  • 什么是大端序和小端序,为什么要有字节序

    字节序,又称端序或尾序(英语中用单词:Endianness 表示),在计算机领域中,指电脑内存中或在数字通信链路中,占用多个字节的数据的字节排列顺序。

    KevinYan
  • Python之有序字典(OrderedDict)与 普通字典(dict)

    之前我认为python中的字典是无序的,因为它是按照hash来存储的,最近开发过程中对数据序列化之后,返回了OrderedDict类型数据,返回数据格式如下

    SEian.G
  • Python中的字典到底是有序的吗

    之前写了文章介绍python中的列表和字典,在文章中描述到了python中的列表是有序的,字典是无序的,后来有粉丝在群里提醒我,说python3.6的版...

    小博测试成长之路
  • 不是有效的win32应用程序 为什么需要有效的

    随着互联网技术的发展,在成年人的日常生活中需要电脑来工作,即使是学生,在上学期间也会需要电脑。例如学校用电脑授课,这都是需要电脑来完成的,而对于电脑的使用,有一...

    用户8794017
  • 了解Python及python的安装及启

    为什么python使用这么多? python语法简单,上手容易,精通难。现在使用爬虫比较多,还可以作前端。 ##########################...

    py3study
  • 3 个 Python 编程小技巧

    我们知道,字典的本质是哈希表,本身是无法排序的,但 Python 3.6 之后,字典是可以按照插入的顺序进行遍历的,这就是有序字典,其中的原理,可以阅读为什么 ...

    somenzz
  • Python 3.7:数据类的介绍

    Python3.7预计在今年夏天发布,让我们一起偷瞄一眼它带来的新功能吧!如果你经常一个人在家用Pycharm撸代码,请确保将你的Pycharm...

    IT派
  • 究竟!为什么处理排序后的数组比没有排序的快?想过没有?

    今天周日,没什么重要的事情要做,于是我早早的就醒来了。看了一会渡边淳一的书,内心逐渐感到平静——心情不佳的时候,书好像是最好的药物。心情平静了,就需要做一些更有...

    沉默王二
  • 获取cdn配置的步骤是什么?获得配置之后有什么好处?

    关于cdn配置,大家还是比较熟悉的,长时间工作后积攒了大量的经验,但是在业绩方面上需要始终难以实现突破,主要是因为网速太慢,彼此之间的沟通和交流受到了一定的限制...

    用户8715145
  • Python3.6的新特性f-string和新字典

    应该大多数的写Python的都知道这个特性,所以这篇文章是给不知道的同学写的,知道的就跳过吧。

    andrew_a
  • Python学习,字符串格式化方法不止%和farmat,还有f-string

    一说起字符串格式化,我们脑海里最先出现的必然是%和format,但是在python3.6之后,又更新了一种更快更便捷的方法,那就是f-string!它是由PEP...

    云飞
  • python实现的摩斯电码解码\编码器

    代码地址如下:http://www.demodashi.com/demo/14743.html

    用户7886150
  • 你应该知道的Python3.6、3.7、3.8新特性小结

    很多人在学习了基本的Python语言知识后,就转入应用阶段了,后期很少对语言本身的新变化、新内容进行跟踪学习和知识更新,甚至连已经发布了好几年的Python3....

    砸漏
  • Python——云里雾里的生成器、迭代器

    关于生成器generator,从字面上理解,就是能生成***的机器,的确它是一个很牛逼的机器,他可以生成很多我们需要的数据,比如全体自然数,好好想一下,能用哪个...

    Ed_Frey
  • Python3中的f-Strings增强版字符串格式化方法

    在Python3.6提供f-Strings新的字符串格式化语法。不仅更加可读、简洁,相比其他方式也不易造成错误,而且还更快。 看完本文你将学习到如何以及为什么...

    砸漏
  • 关于python中set与dict的无序问题

    每个熟悉python的人都知道,python提供给了我们各种各样原生的数据结构,如list、tuple、set、dict等等。这些形形色色的数据结构为我们程序猿...

    kirin
  • Python字典实现--源码解读

    python dict的基本介绍Hash Table 概念dict实现的三个核心结构体解读dict的底层几个C API源码

    用户7886150

扫码关注云+社区

领取腾讯云代金券