Python字典的核心底层原理讲解
作者:Devin01213 发布时间:2022-03-26 08:31:09
字典对象的核心是散列表。散列表是一个稀疏数组(总是有空白元素的数组),数组的每个单元叫做 bucket。每个 bucket 有两部分:一个是键对象的引用,一个是值对象的引用。所有 bucket 结构和大小一致,我们可以通过偏移量来读取指定 bucket。下面通过存储与获取数据的过程介绍字典的底层原理。
存储数据的过程
例如,我们将‘name' = ‘张三' 这个键值对存储到字典map中,假设数组长度为8,可以用3位二进制表示。
>>> map = {}
>>> map
{}
>>> map['name'] = '张三'
1、计算name的散列值。
>>> bin(hash('name'))
'0b101011100000110111101000101010100010011010110010100101001000110'
2、用散列值的最右边 3 位数字作为偏移量,即“110”,十进制是数字 6。我们查看偏移量 6,对应的 bucket 是否为空。如果为空,则将键值对放进去。如果不为空,则依次取右移 3 位作为偏移量,即“000”,十进制是数字0,循环此过程,直到找到为空的 bucket 将键值对放进去。python 会根据散列表的拥挤程度扩容。“扩容”指的是:创造更大的数组,将原有内容拷贝到新数组中。接近 2/3 时,数组就会扩容。扩容后,偏移量的数字个数增加,如数组长度扩容到16时,可以用最右边4位数字作为偏移量。
获取数据的过程
>>> map.get('name')
'张三'
1、计算name的散列值
2、用最右边 3 位数字作为偏移量,即“110”,十进制是数字6。查看偏移量 6,对应的 bucket 是否为空。如果为空,则返回 None。如果不为空,则将这个 bucket 的键对象计算对应散列值,和我们的散列值进行比较,如果相等,则将对应“值对象”返回;如果不相等,则再依次取其他几位数字,重新计算偏移量。循环此过程。
小结:
1.键必须可散列,如数字、元组、字符串;自定义对象需要满足支持hash、支持通过__eq__()方法检测相等性、若 a==b 为真,则 hash(a)==hash(b)也为真。
>>> b = [1,2] //List不可散列
>>> bin(hash(b))
Traceback (most recent call last):
File "<pyshell#90>", line 1, in <module>
bin(hash(b))
TypeError: unhashable type: 'list'
2. 字典在内存中开销巨大,典型的空间换时间;
3. 键查询速度很快;
4. 往字典里面添加新建可能导致扩容,导致散列表中键的次序变化。因此,不要在遍历字典的同时进行字典的修改。
来源:https://blog.csdn.net/ym01213/article/details/86616749
猜你喜欢
- getattr()函数是Python自省的核心函数,具体使用大体如下:获取对象引用getattrGetattr用于返回一个对象属性,或者方法
- 因为工作(懒惰),几年了,断断续续学习又半途而废了一个又一个技能。试着开始用博客记录学习过程中的问题和解决方式,以便激励自己和顺便万一帮助了
- 方法组成模式方法里的所有语句都必须处在同一个归纳层次上无用的注释让代码自我表白标注为什么这样,而不是如何这样对方法表现进行描述等于重复表现这
- asp之家注:对于ACCESS数据库中的NULL,经常我们直接判断该字段是否为空用的是:name="",但是这个还不够,
- 本文以实例形式展示了Python获取电脑硬件信息及状态的实现方法,是Python程序设计中很有实用价值的技巧。分享给大家供大家参考之用。具体
- 协程的定义协程(Coroutine),又称微线程,纤程。(协程是一种用户态的轻量级线程)作用:在执行 A 函数的时候,可以随时中断,去执行
- 这篇文章主要介绍了python自动化unittest yaml使用过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参
- 通过phpmyadmin连接mysql数据库时提示:“2003 无法登录 MySQL服务器”。。。很明显这是没有启动mysql服务,右击我的
- 讲解1、库:os,shutil.copy2、代码效果:对指定文件夹内文件等量分配到新的文件夹3、代码原理:用os.listdir()遍历文件
- 本文实例为大家分享了python实现人民币转大写人民币的具体代码,供大家参考,具体内容如下直接上代码:# -*- coding: utf-8
- 130 :文件格式不正确。(还不是很清楚错误的状况) 145 :文件无法打开。 1005:创建表
- $n=round(1.95583, 2); 这是四舍五入法保留2位小数
- 一、什么是进程进程是执行中的程序,是资源分配的最小单位:操作系统以进程为单位分配存储空间,进程拥有独立地址空间、内存、数据栈等操作系统管理所
- 追本溯源,从使用开始首先看一下我们通常是如何使用微软自带的认证,一般在Startup里面配置我们所需的依赖认证服务,这里通过JWT的认证方式
- 本文实例为大家分享了Python实现图形用户界面计算器的具体代码,供大家参考,具体内容如下简易用户图形界面计算器设计思路:简易图形用户界面计
- 由于惯性思维,导致使用for循环修改列表中的值出现问题首次尝试:def make_great(original): for magician
- xlsxwriter可能用过的人并不是很多,不过使用后就会感觉,他的功能让你叹服,除了可以按要求生成你所需要的excel外还可以加上很形象的
- JetBrains网址:https://www.jetbrains.com/shop/eform/students注册成功后,在校期间都可以
- 今天网页调试的时候在线订单出现错误:Server 对象 错误 'ASP 0178
- 前言:以往看到我博客的小伙伴可能都知道,我的前言一般都是吐槽和讲废话环节,哈哈哈哈。今天难得休息,最近可真是太忙了,博主已经连续一年都在99