Python字典的核心底层原理讲解

2024-09-28 17:06:59

字典对象的核心是散列表。散列表是一个稀疏数组（总是有空白元素的数组），数组的每个单元叫做 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. 往字典里面添加新建可能导致扩容，导致散列表中键的次序变化。因此，不要在遍历字典的同时进行字典的修改。

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

使用Python批量修改文件名的代码实例

这两天在整理一些文章,但是文件夹中每个文章没有序号会看起来很乱,所以想着能不能用Python写一个小脚本. 于是乎,参考了多方资料,简单写了下面几行代码 import osdef tekan(): i=1 #为序号赋初值 for old_file in os.listdir('.'): #os.listfir('.')用于获取当前文件夹所有文件名,'.'表示当前文件夹,也可改为目标文件路径 if 'py' not in old_file: #由于脚本文件不需要修改文件名,所以这里做个判断 #ne
Python使用post及get方式提交数据的实例

最近在使用Python的过程中,发现网上很少提到在使用post方式时,怎么传一个数组作为参数的示例,此处根据自己的实践经验,给出相关示例: 单纯的post请求: def http_post(): url = "http://152.1.12.11:8080/web" postdata = dict(d=2, p=10) post = [] post.append(postdata) req = urllib2.Request(url, json.dumps(post)) #需要是jso
Python制作动态字符图的实例

这次我们拿小龙猫来做演示这里就不必多说了,也就导入几个用到的包: SOURCE_PATH:这个是GIF的路径OUTPUT_PATH:这个是每一帧的存放路径FRAMES_PATH:这个也是每一帧的存放路径,不过是已转为字符画的图片 create_dir() 方法只是用来创建文件夹的,若是存在那便会删掉里面的内容,所以不要放东西进去哦 processImage() 方法是把GIF的每一帧提取出来的,这里面的 img.seek(index) 是对GIF每一帧的索引,由于我也还不知道如何判断GIF总共
Python微医挂号网医生数据抓取

1. 写在前面今天要抓取的一个网站叫做微医网站,地址为 https://www.guahao.com ,我们将通过python3爬虫抓取这个网址,然后数据存储到CSV里面,为后面的一些分析类的教程做准备.本篇文章主要使用的库为pyppeteer 和 pyquery 首先找到医生列表页 https://www.guahao.com/expert/all/全国/all/不限/p5 这个页面显示有 75952 条数据 ,实际测试中,翻页到第38页,数据就加载不出来了,目测后台程序猿没有把数据返回,
Python爬虫实战之12306抢票开源

今天就和大家一起来讨论一下python实现12306余票查询(pycharm+python3.7),一起来感受一下python爬虫的简单实践我们说先在浏览器中打开开发者工具(F12),尝试一次余票的查询,通过开发者工具查看发出请求的包余票查询界面可以看到红框框中的URL就是我们向12306服务器发出的请求,那么具体是什么呢?我们来看看 https://kyfw.12306.cn/otn/leftTicket/queryZ?leftTicketDTO.train_date=2019-01-2
几行Python代码爬取3000+上市公司的信息

前言入门爬虫很容易,几行代码就可以,可以说是学习 Python 最简单的途径. 刚开始动手写爬虫,你只需要关注最核心的部分,也就是先成功抓到数据,其他的诸如:下载速度.存储方式.代码条理性等先不管,这样的代码简短易懂.容易上手,能够增强信心. 基本环境配置版本:Python3 系统:Windows 相关模块:pandas.csv 爬取目标网站实现代码 import pandas as pdimport csvfor i in range(1,178): # 爬取全部页 tb = pd.re
Python中extend和append的区别讲解

append() 方法向列表的尾部添加一个新的元素.只接受一个参数. >>> num = [1,2] >>> num.append(3) >>> num [1, 2, 3] >>> num.append('a') >>> num [1, 2, 3, 'a'] >>> num.append(6,7) Traceback (most recent call last): File "<p
正确理解Python中if __name__ == '__main__'

在Python,我们经常会编写 if __name__ == '__main__' 这么一段代码,这段代码该怎么来理解? 这段代码的功能理解如下: 一个python的文件有两种使用的方法: 作用一,直接作为脚本执行. 作用二,import到其他的python脚本中被调用(模块重用)执行. if __name__ == '__main__': 的作用就是控制这两种情况执行代码的过程,在if __name__ == '__main__': 下的代码只有在第一种情况下(即文件作为脚本直接执行)才会被执
Python对象与引用的介绍

对象 Python 中,一切皆对象.每个对象由:标识(identity).类型(type).value(值)组成. 1. 标识用于唯一标识对象,通常对应于对象在计算机内存地址.使用内置函数 id(obj)可返回对象 obj 的标识. 2. 类型用于表示对象存储的"数据"的类型.类型可以限制对象的取值范围以及可执行的操作.可以使用 type(obj)获得对象的所属类型. 3. 值表示对象所存储的数据的信息.使用 print(obj)可以直接打印出值. 对象的本质:一个内存块,拥有特定的值
Python并发:多线程与多进程的详解

本篇概要 1.线程与多线程 2.进程与多进程 3.多线程并发下载图片 4.多进程并发提高数字运算关于并发在计算机编程领域,并发编程是一个很常见的名词和功能了,其实并发这个理念,最初是源于铁路和电报的早期工作.比如在同一个铁路系统上如何安排多列火车,保证每列火车的运行都不会发生冲突. 后来在20世纪60年代,学术界对计算机的并行计算开始进行研究,再后来,操作系统能够进行并发的处理任务,编程语言能够为程序实现并发的功能. 线程与多线程什么是线程一个线程可以看成是一个有序的指令流(完成特定任务

Python字典的核心底层原理讲解

相关推荐

随机推荐