Python3.6 之后字典是有序的?
作者:somenzz 发布时间:2021-02-14 08:27:53
字典的本质就是 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
,图文注释并茂,是非常有价值的学习资源
来源:https://mp.weixin.qq.com/s?__biz=MzU0OTg3NzU2NA==&mid=2247488769&idx=1&sn=7980639b565208eab5d7d643e03faa89&scene
猜你喜欢
- 前言pytest.mark.skip可以标记无法在某些平台上运行的测试功能,或者您希望失败的测试功能希望满足某些条件才执行某些测试用例,否则
- 为音视频自动生成字幕的 python 工具autosub 是一个能自动为音视频生成字幕的 python 包,以下为其简介和使用说明。auto
- 由于最近测试需要录制系统界面的操作过程,因为都是全屏的操作,所以用python做一个简单的录屏小工具。实现过程也是比较简单,就是通过对屏幕操
- Module Tabs(也称选项卡,后文中简称Tab,以便更符合中国设计师的日常叫法) 是一个常见的交互元素——将不同的内容重叠放置在某一布
- 一个装饰器已经作用在一个函数上,你想撤销它,直接访问原始的未包装的那个函数。假设装饰器是通过 @wraps 来实现的,那么你可以通过访问 w
- 以前用Ubuntu的时候感觉很简单的事到ContOS上却变得很头痛,在执行以下命令安装python-pip居然什么也没执行。yum inst
- 本文实例讲述了Python实现获取前100组勾股数的方法。分享给大家供大家参考,具体如下:本来想采用穷举试探的方式来做这个算法,后来发现还是
- 最近看了下go发送smtp邮件,于是总结一下简单示例 先上一个最简单的代码 (网上搂的代码改了改)package mainimport (
- 这篇文章主要介绍了IOS苹果AppStore内购付款的服务器端php验证方法(使用thinkphp)。AppStore内购在app中支付的过
- 快速+简单搭建环境。如果有问题,欢迎进群讨论留言。第一步:安装python解释器官网地址:https://www.python.org/自动
- 前言:str转换为json格式,前提一定需要保证这个str的格式和json是一致的,即左边最外层是大括号,右边的最外层是大括号。如果不一致,
- 在python的时间使用时,我们无非就是输出字符串的形式,又或者是其他的形式跟字符串之间的来回转换。时间数组对于我们获取具体的年或是天数,都
- 设计师常常使用一些独特的字体效果和页面效果,阴影是其中一个,它可以让页面中的文字和元素具有立体的效果,从而被突出出来。比如对于文字阴影,传统
- 使用Northwind 数据库首先查询Employees表查询结果:city列里面只有5个城市使用ROW_NUMBER() OVER(PAR
- 这段后门代码可以隐藏在asp文件中,大家可以搜索一些特点的关键字,查看文件的修改日期,看看是不是有如下的代码。<%if re
- 分区视图联接来自一组成员的水平分区数据,使数据看起来象来自同一张表。SQL Server 2000 区分本地分区视图和分布式分区视图。在本地
- 本文实例讲述了python自动化测试之从命令行运行测试用例with verbosity,分享给大家供大家参考。具体如下:实例文件recipe
- WTForms 是用于web开发的灵活的表单验证和呈现库,它可以与您选择的任何web框架和模板引擎一起工作,并支持数据验证、CSRF保护、国
- /** 2 * 检索数组元素(原型扩展或重载) 3 * @param {o} 被检索的元素值 4 * @type int 5 * @retu
- 在asp中利用excel的一个方法是将excel文件作为一个数据库进行链接,然后的操作和对access数据库操作类似.但是这个方法不是总能有