存储 dict 的元素前是计算 key 的 hash 值?

news/2024/7/17 22:06:29

dict 的高性能与其存储方式是分不开的,我们知道 dict 的存储是基于哈希表(又称散列表),需要计算 hash 值,那么是计算谁的 hash 值呢?是像别人说的:存储 dict 元素前计算 key 的 hash 值?

验证

这里先创建个字典

>>> my_dict = {'a': 'apple', 'b': 'banana'}

由于哈希表是一块连续的内存空间(数组),在不考虑 hash 值冲突的情况下,如果计算的是 key 的 hash 值,那么:'a' 的 hash 值与 'b' 的 hash 值之间的差值'a' 的内存地址与 'b' 的内存地址之间的差值(可理解为内存地址里的距离) 相等才对,也就是说以下的等式成立才对

hash('a') - hash('b') == id('a') - id('b')

但事实上面等式返回的是 False

>>> hash('a') - hash('b') == id('a') - id('b')
False

先看看其中各项的具体值是多少

>>> hash('a')
-7336862871683211644
>>> hash('b')
3607308758832868774
>>> id('a')
1290454097736
>>> id('b')
1290454096056
>>> id('a') - id('b')
1680
>>> hash('a') - hash('b')
-10944171630516080418

可以很明显得看到差距还是挺大的
这说明计算的不是 key 的 hash 值(这种说法不够严谨),那计算的是什么呢?

计算的是 key 所在内存地址的 hash 值

在不考虑 hash 冲突的情况下, 'a' 所在内存地址的 hash 值与 'b' 所在内存地址的 hash 值之间的差值'a' 的内存地址与 'b' 的内存地址之间的差值 相等,也就是说以下的等式成立才对

hash(id('a')) - hash(id('b')) == id('a') - id('b')
>>> hash(id('a')) - hash(id('b')) == id('a') - id('b')
True
>>> id('a') - id('b')
1680
>>> hash(id('a')) - hash(id('b'))
1680

下面再多验证几个

>>> my_dict['c'] = 'cherry'
>>> hash(id('b')) - hash(id('c')) == id('b') - id('c')
True
>>> id('b') - id('c')
791760
>>> hash(id('b')) - hash(id('c'))
791760
>>> a['d'] = 'date'
>>> hash(id('d')) - hash(id('c')) == id('d') - id('c')
True
>>> id('d') - id('c')
1400
>>> hash(id('d')) - hash(id('c'))
1400

到这里就可以证明上面的结论

为何计算的是 key 所在的内存地址的 hash 值?

比如上面的'a'(1 个字符) 明显比其所在的内存地址 1290454097736(13 个字符)要短。短的计算不是更快吗?
记住一句话:Python 中一切皆对象,'a'是个 str 对象,1290454097736 是个 int 对象

>>> type('a')
<class 'str'>
>>> type(id('a'))
<class 'int'>

一个对象里不是仅仅存储对应值,它还有很多属性(含方法),来看看谁的属性多

>>> len(dir('a'))
77
>>> len(dir(id('a')))
70

str 对象比 int 对象多 7 个属性

它们都有个叫 __sizeof__() 的魔法方法,用于获取当前对象所占用的内存空间大小(字节)

>>> id('a').__sizeof__()
32
>>> 'a'.__sizeof__()
50

从上面可以发现:虽然 'a' 看起来只有 1 个字符,但其占用的内存空间要大于其内存地址 id('a') 所占用的空间

当然这不是主要原因,Python 解释器会将其转换为适当的数据类型再进行 hash 计算

不过,dict 的 key 不仅仅可以是 str 对象,也可以是 int、bytes、fromzenset 等这些可哈希(hashable)对象,可哈希对象都是不可变(immutable)对象(注意:反之不一定成立,如 tuple),不可变对象内存地址不变。大多数情况下,相比计算这些不同对象类型的 hash 值,直接计算对象所在内存地址(整数)的 hash 值性能更高,这也就是为什么不是计算 key 的 hash 值,而是计算 key 所在内存地址的 hash 值

  • 手动汉化 PyCharm 的过程
  • 模拟登陆Github
  • 字符图像识别——数字字母混合
  • 爬取猫眼实时票房数据

http://lihuaxi.xjx100.cn/news/271062.html

相关文章

小白的Unity5之路(一)

Player移动: 1 public float speed 6f;2 Vector3 movement;3 Rigidbody playerRididbody;4 5 void FixedUpdate () {6 float h Input.GetAxisRaw("Horizontal");7 float v Input.GetAxisRaw("Vertical");8 Move(h, v); 9…

html css发展前景,网页设计的发展趋势

原标题&#xff1a;网页设计的发展趋势1.传感器访问赋予页面对用户环境的感知能力很多年以来&#xff0c;web 页面掌握的用户情况十分有限&#xff0c;通常只有用户的屏幕尺寸以及浏览器类型等。但现在各种 W3C 标准把环境光、麦克风、摄像头等各种传感器数据都提供出来了。这使…

推荐一款免费的数据库管理工具,比Navicat还要好用,功能还很强大

点击上方蓝色“方志朋”&#xff0c;选择“设为星标”回复“666”获取独家整理的学习资料&#xff01;作者&#xff1a;不剪发的Tony老师blog.csdn.net/horses/article/details/89683422DBeaver 是一个基于 Java 开发&#xff0c;免费开源的通用数据库管理和开发工具&#xff0…

从Ops到NoOps,阿里文娱智能运维的关键:自动化应用容量管理

作者| 阿里文娱高级开发工程师 金呈编辑 | 夕颜来源 | CSDN&#xff08;ID&#xff1a;CSDNnews&#xff09;概述1. 背景随着业务形态发展&#xff0c;更多的生产力集中到业务创新&#xff0c;这背后要求研发能力的不断升级。阿里文娱持续倾向用更加高效、稳定、低成本的方式支…

Android 系统启动过程

文章来源于网络&#xff0c;心得来源于整理。请尊重作者&#xff1a;http://hi.baidu.com/guoxiaoming/blog/item/24e9e9f8c9628f1fd9f9fd89.html/cmtid/7525d63fb437a6cd7c1e713bAndroid 系统启动过程Android 从系统启动有4个步骤: 1, init进程启动 2. Native服务启动 3.Syste…

深入浅出Yolov3和Yolov4

点击上方“小白学视觉”&#xff0c;选择加"星标"或“置顶”重磅干货&#xff0c;第一时间送达因为工作原因&#xff0c;项目中经常遇到目标检测的任务&#xff0c;因此对目标检测算法会经常使用和关注&#xff0c;比如Yolov3、Yolov4算法。当然&#xff0c;实际项目…

python创建虚拟环境sublime_如何设置python 虚拟环境 sublime text

一、首先下载安装Sublime Text3下载.注册码下载可用&#xff1a;—– BEGIN LICENSE —–Ryan ClarkSingle User LicenseEA7E-8124792158A7DE B690A7A3 8EC04710 006A5EEB34E77CA3 9C82C81F 0DB6371B 79704E6F93F36655 B031503A 03257CCC 01B20F60D304FA8D B1B4F0AF 8A76C7BA 0…

Papers Without Code网站,张贴复现不了的论文

点击上方“视学算法”&#xff0c;选择加"星标"或“置顶”重磅干货&#xff0c;第一时间送达来源丨机器之心编辑丨极市平台「无法复现的论文都是耍流氓。」二十几天前&#xff0c;Reddit 用户「ContributionSecure14」在机器学习社区疯狂吐槽&#xff1a;「我花了一个…