Python里的dict和set的背后小秘密
作者:Python探索牛 发布时间:2023-11-20 01:01:11
目录
Python里的dict和set的效率有多高?
字典中的散列表
1.散列值和相等性
散列表算法
dict的实现及其导致的结果
1.键必须死可散列的
2.字典在内存上的开销巨大
3.键查询很快
4.键的次序取决于添加顺序
5.往字典里添加新键可能会改变已有键的顺序
set的实现及其导致的结果
总结
Python里的dict和set的效率有多高?
为什么它们是无序的?
为什么并不是所有的Python对象都可以当作dict的键或set里的元素?
为什么dict的键和set的元素的顺序是根据它们被添加的次序而定的,以及为什么在映射对象的生命周期中,这个顺序并不是一成不变的?
为什么不应该在迭代循环dict或是set的同时往里添加元素?
Python里的dict和set的效率有多高?
由实验得知,不管查询有多少个元素的字典或集合,所耗费的时间都能忽略不计(前提是字典或者集合不超过内存大小).
字典中的散列表
散列表其实是一个稀疏数组(总是有空白元素的数组被称为稀疏数组).在一般的数据结构教材中,散列表里的单元通常叫作表元(bucket).
在dict的散列表当中,每个键值对都占用一个表元,每个表元都有两个部分,一个是对键的引用,另一个是对值的引用.
因为所有的表元的大小一致,所以可以通过偏移量来读取某个表元.
Python会设法保证大概还有三分之一的表元是空的,所以在快要达到这个阈值的时候,原有散列表会被复制到一个更大的空间里面.
如果要把一个对象放入散列表,那么首先要计算这个元素键的散列值.Python中可以用hash()方法来做这件事情.
1.散列值和相等性
内置的hash()方法可以用于所有的内置类型对象.如果是自定义对象调用hash()的话,实际上运行的是自定义的__hash__.
如果这两个对象在比较的时候是相等的,那么它们的散列值必须相等,否则散列表就不能正常运行了.
例如,如果11.0为真,那么hash(1)hash(1.0)也必须为真,但其实这两个数字(整型和浮点)的内部结构是完全不一样的.
既然提到了整型,CPython的实现细节里有一条是:如果有一个整型对象,而且它能被存进一个机器字中,那么它的散列值就是它本身的值.
为了让散列值能够胜任散列表索引这一角色,它们必须在索引空间中尽量分散开来.这意味着在最理想的状况下,越是相似但不相等的对象,它们散列值的差别应该越大.
"""
import sys
# 通过sys.maxsize获取操作系统的整数最大值,转换成二进制,计算位数,加上一个符号位
MAX_BITS = len(format(sys.maxsize, 'b'))
print('%s-bit Python build' % (MAX_BITS + 1))
def hash_diff(o1, o2):
h1 = '{:>0{}b}'.format(hash(o1), MAX_BITS) # 计算o1的散列值,并用0补满空位
h2 = '{:>0{}b}'.format(hash(o2), MAX_BITS) # 计算o2的散列值,并用0补满空位
# 比较h1和h2的每一位,用!标识出来,否则用' '表示
diff = ''.join('!' if b1 != b2 else ' ' for b1, b2 in zip(h1, h2))
count = '!={}'.format(diff.count('!')) # 显示不同的总数
width = max(len(repr(o1)), len(repr(o2)), 8) # 行头的宽度
sep = '_' * (width * 2 + MAX_BITS) # 分割线
return '{!r:{width}} {}\n{:{width}} {} {}\n{!r:{width}} {}\n{}'.format(
o1, h1, ' ' * width, diff, count, o2, h2, sep, width=width
)
print(hash_diff(1, 1.0))
print(hash_diff(1.0, 1.0001))
print(hash_diff(1.0001, 1.0002))
print(hash_diff(1.0002, 1.0003))
从Python3.3开始,str,bytes和datetime对象的散列值计算过程中多了随机的'加盐'这一步.
所加盐值是Python进程内的一个常量,但是每次启动Python解释器都会生成一个不同的盐值.
随机盐值的加入是为了防止DOS攻击而采取的一种安全措施.
散列表算法
为了获取my_dict[search_key]背后的值,Python首先会调用hash(search_key)来计算search_key的散列值,把这个值最低的几位数字当作偏移量,在散列表里查找表元(具体取几位,得看当前散列表的大小).若找到的表元是空的,则抛出KeyError异常.
若不是空的,则表元里会有一对found_key:found_value.这时候Python会检验search_key == found_key是否为真,如果是,就会返回found_value.
如果search_key和found_key不匹配的话,这种情况称为[散列冲突].发生这种情况是因为,散列表所做的其实是把随机的元素映射到只有几位的数字上,而散列表本身的索引又只能依赖于这个数字的一部分.为了解决散列冲突,算法会在散列值中另外再取几位,然后用特殊的方法处理一下,把新得到的数字再当作索引来寻找表元.
若这次找到的表元是空的,则同样抛出KeyError;若非空,或者键匹配,则返回这个值;或者又发现了散列冲突,则重复以上的步骤.
从字典中取值的算法流程如下:给定一个键,这个算法要么返回一个值,要么抛出KeyError异常
|-------------------------------------------------------------------------|
|计算键的散列值 ________使用散列值的另一部分来定位散列表中的零一行 |
| | | ↑ |
| | | | 否 (散列冲突) |
| | ↓ | |
|使用散列值的一部分 表元 | |
|来定位散列表中的一 ------→ 为空? ---------否-------→ 键相等? |
|个表元 | | |
| |是 |是 |
| ↓ ↓ |
| 抛出KeyError 返回表元里的值 |
|--------------------------------------------------------------------------|
添加新元素和更新现有键值的操作几乎跟上面一样.只不过对于前者,在发现空表元的时候会放入一个新元素;
对于后者,在找到对应的表元后,原表里值对象会被替换成新值.
另外在插入新值时,Python可能会按照散列表的拥挤程度来决定是否要重新分配内存来为它扩容.如果增加了散列表的大小,那散列值所占的位数和用作索引的位数就会随之增加,这样做的目的是为了减少发生散列冲突的概率.
表面上看,这个算法似乎很费事,而实际上就是dict里有数百万个元素,多数的搜索过程中并不会有冲突发生,平均下来每次搜索可能会有一到两次冲突.
在正常情况下,就算是最不走运的键所遇到的冲突的次数用一只手也能数过来.
dict的实现及其导致的结果
1.键必须死可散列的
一个可散列的对象必须满足以下要求:
1)支持hash()函数,并且通过__hash__()方法所得到的散列值是不变的.
2)支持通过__eq__()方法来检测相等性.
3)若a == b为真,则hash(a) == hash(b)也为真
所有由用户定义的对象默认都是可散列的,因为它们散列值由id()来获取,而且它们都是不相等的.
如果你实现了一个类的__eq__()方法,并且希望它是可散列的,那么它一点要有个恰当的__hash__方法,保证a==b为真的情况下hash(a)==hash(b)也必定为真.
否则就会破坏恒定的散列表算法,导致由这些对象所组成的字典和集合完全失去可靠性,这个后果是非常可怕的.
另一方面,如果一个含有自定义__eq__依赖的类处于可变的状态,那就不要在这个类中实现__hash__方法,因为它的实例时不可散列的.
'''
学习中遇到问题没人解答?小编创建了一个Python学习交流群:725638078
寻找有志同道合的小伙伴,互帮互助,群里还有不错的视频学习教程和PDF电子书!
'''
class A:
def __init__(self, a):
self.a = a
def __hash__(self):
return 1
def __eq__(self, other):
return hash_diff(self, other)
def __repr__(self):
return str(self.a)
a = A(1)
b = A(2)
d1 = {a: 1, b: 2, 1: 3}
print(d1) # {1: 3} 会发现里面只有一个键值对
2.字典在内存上的开销巨大
由于字典使用了散列表,而散列表又必须时稀疏的,这导致它在空间上的效率低下.举例而言.如果你需要存放数量巨大的记录,那么放在由元组或是具名元组构成的列表中会是比较好的选择;
最好不要根据JSON的风格,用由字典组成的列表来存放这些记录,用元组取代字典能节省空间的原因有两个:
其一是避免了散列表所消耗的空间. 其二是无需把记录中字段的名字在每个元素里都存一遍.
在用户自定义的类型中,__slots__属性可以改变实例属性的存储方式,由dict变成tuple.
3.键查询很快
dict的实现是典型的空间换时间:字典类型有着巨大的内存开销,但它们提供了无视数据量的快速访问--只要字典能被装在内存里.
4.键的次序取决于添加顺序
当往dict里添加新键而又发生散列冲突的时候,新键可能会被安排存放到另一个位置.于是下面的这种情况就会发生:
由dict([(key1, value1), (key2, value2)])和dict([(key2, value2), (key1, value1)])得到的两个字典,在进行比较的时候,它们是相等的.
但是如果在key1和key2被添加到字典里的过程中有冲突发生的话,这两个键出现在字典里的顺序是不一样的.
下面的示例展示了这个现橡.这个示例用同样的数据创建了3个字典,唯一的区别就是数据出现的顺序不一样.可以看到,虽然键的次序是乱的,这3个字典仍然被视作相等的.
STUDENTS = [
(89, '孙悟空'),
(79, '猪八戒'),
(69, '沙和尚'),
(59, '小白龙'),
(49, '唐僧')
]
d1 = dict(STUDENTS)
print('d1:', d1.keys())
d2 = dict(sorted(STUDENTS))
print('d2:', d2.keys())
d3 = dict(sorted(STUDENTS, key=lambda x: x[1]))
print('d3', d3.keys())
assert d1 == d2 and d2 == d3
5.往字典里添加新键可能会改变已有键的顺序
无论何时往字典里添加新的键,Python解释器都可能做出为字典扩容的决定.扩容导致的结果就是要新建一个更大的散列表,并把字典里已有的元素添加到新表里.
这个过程可能会发生新的散列冲突,导致新散列表中键的次序变化.
要注意的是,上面提到的这些变化是否会发生以及如何发生,都依赖于字典背后的实现,因此你不能很自信的说自己知道背后发生了什么.
如果你在迭代一个字典的所有键的过程中同时对字典进行修改,那么这个循环很可能会跳过一些键----甚至是跳过那些字典中已经有的键.
由此可知,不要对字典同时进行迭代和修改.如果想扫描并修改一个字典,最好分成两步来进行:
首先对字典迭代,以得出需要添加的内容,把这些内容放在一个新字典里;迭代结束之后再对原字典进行更新.
在Python3中,.keys() .items() .values()方法返回的都是字典视图.也就是说,这些方法返回的值更像集合.
set的实现及其导致的结果
set和frozenset的实现也依赖散列表,但在它们的散列表里存放的只有元素的引用.在set加入到Python之前,我们都是把字典加上无意义的值当作集合来用.
1.集合里的元素必须是可散列的.
2.集合很消耗内存.
3.可以很高效的判断元素是否存在于某个集合.
4.元素的次序取决于被添加到集合里的次序.
5.往集合里添加元素,可能会改变集合里已有元素的次序.
来源:https://www.cnblogs.com/djdjdj123/p/15483539.html
猜你喜欢
- Redis 除了做缓存,还能干很多很多事情:分布式锁、限流、处理请求接口幂等性。。。太多太多了配置首先我们创建一个 Spring Boot
- upload.htm <html><head><title>网站维护 -
- 首先将ORACLE 10g的安装光盘放入光驱,如果自动运行,一般会出现如图1安装界面: 图1 单击“开始安装”,就可以安装ORACLE 10
- 有别于JS跨域、IFRAME跨域等的常用处理办法,还可以利用P3P来实现跨域。P3P是什么P3P(Platform for Privacy
- 本文实例讲述了php生成随机数/生成随机字符串的方法。分享给大家供大家参考,具体如下:有时候我们的项目需要生成随机数,但是又不想那么麻烦,那
- 这学期在学习编译原理,最近的上机作业就是做一个简单的词法分析器,在做的过程中,突然有个需求就是判断一个字符串是否为合法的标示符,因为我是用p
- 非原创:英文版混乱的标记语言XHTML2/HTML5源文地址:漫画英文版源文地址感谢我的同事Kevin Jaw的翻译。他的博客地址是:Kev
- <?php session_start(); $_SESSION['username']="zhuzhao&
- 在广大网友心目中,他们就是中国互联网搜索领域的三驾马车。无论这三家搜索巨头承不承认,在网友眼中总会来将他们进行对比比较。当然,更多时候的比较
- 用SQL语句添加删除修改字段 1.增加字段 alter table docdsp add dspcode char(200) 2.删除字段
- 面是我下载页面down.php 的php代码 现在我发现,用迅雷,谷歌浏览器直接打开,就能输出下载文件,一点不起防盗链作用。&nb
- 主要代码如下: total = application("All
- MySQL语句优化的基本原则:◆1、使用索引来更快地遍历表。缺省情况下建立的索引是非群集索引,但有时它并不是最佳的。在非群集索引下,数据在物
- 在添加新记录时,有时候我们需要将部分动态内容自动添加到指定的文本域,例如上传一个文件后,将文件名自动添加到一个独立的记录框内,以
- 您是否常常在做网页的过程中发现一个问题呢?当图片上传的时候,如果图片太大 ,就会把网页撑破,唯一做的就要先把它用软件缩小,再上传上
- 要想更好的理解 css, 尤其是 IE 下对 css 的渲染,haslayout 是一个非常有必要彻底弄清除的概念。大多IE下的显示错误,就
- 1,FCKeditor 编辑器最新版本: 2.3.1站点:http://www.fckeditor.net 演示:http://w
- 一、功能简述正是微博如火如荼的时节,其中各个微博的分享功能是网站推广产品的好东东啊,此时如何方便快捷的使用微博的分享功能就显得比较重要了。我
- 字体设计是人类商业活动的需求,它随着时代和科学技术的进步而不断地变化着。被广泛应用于网络生活的各个方面。现代字体设计在电脑技术的应用中已经深
- 本文实例讲述了让thinkphp支持大小写url地址访问的方法。分享给大家供大家参考。具体实现方法如下:通常ThinkPHP默认是区别大小写