python 字典最外层使用_python字典底层实现

python 字典最外层使用_python字典底层实现前言问题1:python中的字典到底是有序还是无序问题2:python中字典的效率如何python字典底层原理在Python3.5以前,字典是不能保证顺序的,键值对A先插入字典,键值对B后插

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

前言

  • 问题1:python中的字典到底是有序还是无序
  • 问题2:python中字典的效率如何
     

python字典底层原理

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

  但是从Python 3.6开始,字典是变成有顺序的了。你先插入键值对A,后插入键值对B,那么当你打印Keys列表的时候,你就会发现B一定在A的后面。

  不仅如此,从Python 3.6开始,下面的三种遍历操作,效率要高于Python 3.5之前:

for key in dict1
 
for value in dict1.values()
 
for key, value in dict1.items()

从Python 3.6开始,字典占用内存空间的大小,是字典里面键值对的个数,只有原来的30%~95%。
Python 3.6到底对字典做了什么优化呢?为了说明这个问题,我们需要先来说一说,在Python 3.5之前,字典的底层原理。
 

python3.5之前字典的底层原理

当我们初始化一个空字典的时候,CPython的底层会初始化一个二维数组,这个数组有8行,3列,如下面的示意图所示:

my_dict = {}
 
'''
此时的内存示意图
[
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---]
]
'''

现在,我们往字典里面添加一个数据:

my_dict['name'] = 'jkc'
 
'''
此时的内存示意图
[
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [1278649844881305901, 指向name的指针, 指向jkc的指针],
  [---, ---, ---],
  [---, ---, ---]
]
'''

这里解释一下,为什么添加了一个键值对以后,内存变成了这个样子:
首先我们调用Python 的hash函数,计算name这个字符串在当前运行时的hash值:

In [1]: hash('name')
Out[1]: 1278649844881305901

特别注意,我这里强调了『当前运行时』,这是因为,Python自带的这个hash函数,和我们传统上认为的Hash函数是不一样的。Python自带的这个hash函数计算出来的值,只能保证在每一个运行时的时候不变,但是当你关闭Python再重新打开,那么它的值就可能会改变,如下图所示:
python 字典最外层使用_python字典底层实现
假设在某一个运行时里面,hash(‘name’)的值为1278649844881305901。现在我们要把这个数对8取余数:

In [2]: 1278649844881305901 % 8
Out[2]: 5

余数为5,那么就把它放在刚刚初始化的二维数组中,下标为5的这一行。由于name和jkc是两个字符串,所以底层C语言会使用两个字符串变量存放这两个值,然后得到他们对应的指针。于是,我们这个二维数组下标为5的这一行,第一个值为name的hash值,第二个值为name这个字符串所在的内存的地址(指针就是内存地址),第三个值为jkc这个字符串所在的内存的地址。

现在,我们再来插入两个键值对:

my_dict['age'] = 26
my_dict['salary'] = 999999
 
'''
此时的内存示意图
[
  [-4234469173262486640, 指向salary的指针, 指向999999的指针],
  [1545085610920597121, 执行age的指针, 指向26的指针],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [1278649844881305901, 指向name的指针, 指向jkc的指针],
  [---, ---, ---],
  [---, ---, ---]
]
'''

那么字典怎么读取数据呢?首先假设我们要读取age对应的值。
此时,Python先计算在当前运行时下面,age对应的Hash值是多少:

In [2]: hash('age')
Out[2]: 1545085610920597121

现在这个hash值对8取余数:

In [2]: 1545085610920597121 % 8
Out[2]: 1

余数为1,那么二维数组里面,下标为1的这一行就是需要的键值对。直接返回这一行第三个指针对应的内存中的值,就是age对应的值26。
当你要循环遍历字典的Key的时候,Python底层会遍历这个二维数组,如果当前行有数据,那么就返回Key指针对应的内存里面的值。如果当前行没有数据,那么就跳过。所以总是会遍历整个二维数组的每一行。
每一行有三列,每一列占用8byte的内存空间,所以每一行会占用24byte的内存空间。
由于Hash值取余数以后,余数可大可小,所以字典的Key并不是按照插入的顺序存放的。
注意,这里我省略了与本文没有太大关系的两个点:

  • 1.开放寻址,当两个不同的Key,经过Hash以后,再对8取余数,可能余数会相同。此时Python为了不覆盖之前已有的值,就会使用开放寻址技术重新寻找一个新的位置存放这个新的键值对。
  • 2.当字典的键值对数量超过当前数组长度的2/3时,数组会进行扩容,8行变成16行,16行变成32行。长度变了以后,原来的余数位置也会发生变化,此时就需要移动原来位置的数据,导致插入效率变低。
     

python3.6之后字典的底层原理

在Python 3.6以后,字典的底层数据结构发生了变化,现在当你初始化一个空的字典以后,它在底层是这样的:

my_dict = {}
 
'''
此时的内存示意图
indices = [None, None, None, None, None, None, None, None]
 
entries = []
'''

当你初始化一个字典以后,Python单独生成了一个长度为8的一维数组。然后又生成了一个空的二维数组。

现在,我们往字典里面添加一个键值对:

my_dict['name'] = 'jkc'
 
'''
此时的内存示意图
indices = [None, 0, None, None, None, None, None, None]
 
entries = [[-5954193068542476671, 指向name的指针, 执行jkc的指针]]
'''

为什么内存会变成这个样子呢?我们来一步一步地看:

在当前运行时,name这个字符串的hash值为-5954193068542476671,这个值对8取余数是1:

>>> hash('name')
-5954193068542476671
>>> hash('name') % 8
1

所以,我们把indices这个一维数组里面,下标为1的位置修改为0。

这里的0是什么意思呢?0是二位数组entries的索引。现在entries里面只有一行,就是我们刚刚添加的这个键值对的三个数据:name的hash值、指向name的指针和指向jkc的指针。所以indices里面填写的数字0,就是刚刚我们插入的这个键值对的数据在二位数组里面的行索引。

好,现在我们再来插入两条数据:

my_dict['address'] = 'xxx'
my_dict['salary'] = 999999
 
'''
此时的内存示意图
indices = [1, 0, None, None, None, None, 2, None]
 
entries = [
  [-5954193068542476671, 指向name的指针, 执行jkc的指针],
  [9043074951938101872, 指向address的指针,指向xxx的指针],
  [7324055671294268046, 指向salary的指针, 指向999999的指针]
]
'''

现在如果我要读取数据怎么办呢?假如我要读取salary的值,那么首先计算salary的hash值,以及这个值对8的余数:

>>> hash('salary')
7324055671294268046
>>> hash('salary') % 8
6

那么我就去读indices下标为6的这个值。这个值为2.

然后再去读entries里面,下标为2的这一行的数据,也就是salary对应的数据了。

新的这种方式,当我要插入新的数据的时候,始终只是往entries的后面添加数据,这样就能保证插入的顺序。当我们要遍历字典的Keys和Values的时候,直接遍历entries即可,里面每一行都是有用的数据,不存在跳过的情况,减少了遍历的个数。

老的方式,当二维数组有8行的时候,即使有效数据只有3行,但它占用的内存空间还是 8 * 24 = 192 byte。但使用新的方式,如果只有三行有效数据,那么entries也就只有3行,占用的空间为3 * 24 =72 byte,而indices由于只是一个一维的数组,只占用8 byte,所以一共占用 80 byte。内存占用只有原来的41%。
 

字典的用法总结

  • 1.键必须可散列
    • (1) 数字、字符串、元组,都是可散列的。
    • (2) 自定义对象需要支持下面三点:
      • ①支持 hash()函数
      • ②支持通过__eq__()方法检测相等性。
      • ③若 a==b 为真,则 hash(a)==hash(b)也为真。
  • 2.字典在内存中开销巨大,典型的空间换时间。
  • 3.键查询速度很快
  • 4.往字典里面添加新建可能导致扩容,导致散列表中键的次序变化。因此,不要在遍历字 典的同时进行字典的修改。

参考:https://www.cnblogs.com/songyifan427/p/11198719.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164808.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • spel表达式的用法_el表达式判断是否为空

    spel表达式的用法_el表达式判断是否为空spel表达式运算使用翻看公司代码,这一块不是很懂,查资料,记一下,还是太菜1.常用的对象Expression:表达式对象SpelExpressionParser:表达式解析器EvaluationContext:上下文2.使用本文参考了下面的几篇文章https://www.cnblogs.com/shihuc/p/9338173.htmlhttps://blog.csdn.net/f641385712/article/details/90812967下面的例子主要是来源于第一

  • CLion linux激活码【中文破解版】

    (CLion linux激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlS32PGH0SQB-eyJsaWNlbnNlSWQi…

  • linux route输出分析,Traceroute原理分析[通俗易懂]

    linux route输出分析,Traceroute原理分析[通俗易懂]traceroute,现代Linux系统上的tracepath,还有Windows系统上的tracert,均是用于同一目的的网络调试工具。它们用于显示数据包在IP网络中经过的路由器的IP地址。原理这些程序是利用IP数据包的存活时间(TTL)值来实现其功能的。当一台计算机发送IP数据包时,会为数据包设置存活时间(TTL)值。每当数据包经过一个路由器,其存活时间值就会减1。当存活时间减到…

  • pycharm如何调试代码_pycharm调试debug入门

    pycharm如何调试代码_pycharm调试debug入门1.首先在怀疑出错的代码处的前面设置断点2.点击pycharmdebug按钮3.stepover也就是F8进行单击调试,只有光标在哪一行就是即将运行的代码只有光标跳到下一行,这一行才会执行4.运行到某一个自定义函数def的时候如果想知道里面如何运行单击stepinto(F7)然后继续stepover最后可能返回一个result回到main函数继续stepover。5.如果是嵌套函数,函数里面还有别的自定义函数可以运行到那一行时继续stepinto6.如.

  • 2021 goland激活码[在线序列号]

    2021 goland激活码[在线序列号],https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • JMM内存模型

    JMM内存模型Java内存模型即JavaMemoryModel,简称JMM。JMM定义了Java虚拟机(JVM)在计算机内存(RAM)中的工作方式。JVM是整个计算机虚拟模型,所以JMM是隶属于JVM的。如果我们要想深入了解Java并发编程,就要先理解好Java内存模型。Java内存模型定义了多线程之间共享变量的可见性以及如何在需要的时候对共享变量进行同步。原始的Java内存模型效率并不是很理想,

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号