-
Python里的dict和set的效率有多高?
-
为什么它们是无序的?
-
为什么并不是所有的Python对象都可以当作dict的键或set里的元素?
-
为什么dict的键和set的元素的顺序是根据它们被添加的次序而定的,以及为什么在映射对象的生命周期中,这个顺序并不是一成不变的?
-
为什么不应该在迭代循环dict或是set的同时往里添加元素?
Python里的dict和set的效率有多高?
由实验得知,不管查询有多少个元素的字典或集合,所耗费的时间都能忽略不计(前提是字典或者集合不超过内存大小).
字典中的散列表
散列表其实是一个稀疏数组(总是有空白元素的数组被称为稀疏数组).在一般的数据结构教材中,散列表里的单元通常叫作表元(bucket).
在dict的散列表当中,每个键值对都占用一个表元,每个表元都有两个部分,一个是对键的引用,另一个是对值的引用.
因为所有表元素的大小都相同，所以表元素可以按偏移量读取。
[En]
Because all table elements are of the same size, a table element can be read by offset.
Python会设法保证大概还有三分之一的表元是空的,所以在快要达到这个阈值的时候,原有散列表会被复制到一个更大的空间里面.
如果要把一个对象放入散列表,那么首先要计算这个元素键的散列值.Python中可以用hash()方法来做这件事情.
1.散列值和相等性
内置的hash()方法可以用于所有的内置类型对象.如果是自定义对象调用hash()的话,实际上运行的是自定义的 __hash__.
如果两个对象在比较时相等，则它们的哈希值必须相等，否则哈希表将无法正常工作。
[En]
If the two objects are equal when comparing, then their hash values must be equal, otherwise the hash table will not work properly.
例如,如果11.0为真,那么hash(1)hash(1.0)也必须为真,但其实这两个数字(整型和浮点)的内部结构是完全不一样的.
既然提到了整型,CPython的实现细节里有一条是:如果有一个整型对象,而且它能被存进一个机器字中,那么它的散列值就是它本身的值.
为了使哈希值适合哈希表索引的角色，它们必须尽可能地分散在索引空间中。这意味着在理想情况下，相似但不相等的对象越多，其散列值的差异就越大。
[En]
In order for hash values to be suitable for the role of hash table index, they must be dispersed as much as possible in the index space. This means that in an ideal situation, the more similar but unequal objects, the greater the difference in their hash values.
"""
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 返回表元里的值 |
|--------------------------------------------------------------------------|
添加新元素和更新现有键值的操作几乎与上面相同。只是对于前者，当找到一个空的表元素时，会放置一个新元素。
[En]
The operation of adding new elements and updating existing key values is almost the same as above. It’s just that for the former, a new element is placed when an empty table element is found.
对于后者,在找到对应的表元后,原表里值对象会被替换成新值.
另外在插入新值时,Python可能会按照散列表的拥挤程度来决定是否要重新分配内存来为它扩容.如果增加了散列表的大小,那散列值所占的位数和用作索引的位数就会随之增加,这样做的目的是为了减少发生散列冲突的概率.
表面上看,这个算法似乎很费事,而实际上就是dict里有数百万个元素,多数的搜索过程中并不会有冲突发生,平均下来每次搜索可能会有一到两次冲突.
在正常情况下,就算是最不走运的键所遇到的冲突的次数用一只手也能数过来.
1.键必须死可散列的
可哈希对象必须满足以下要求：
[En]
A hashable object must meet the following requirements:
1)支持hash()函数,并且通过 __hash__()方法所得到的散列值是不变的.
2)支持通过 __eq__()方法来检测相等性.
3)若 a == b为真,则 hash(a) == hash(b)也为真
所有由用户定义的对象默认都是可散列的,因为它们散列值由id()来获取,而且它们都是不相等的.
如果你实现了一个类的 __eq__()方法,并且希望它是可散列的,那么它一点要有个恰当的 __hash__方法,保证a==b为真的情况下 hash(a)==hash(b)也必定为真.
否则，常量哈希表算法将被破坏，由这些对象组成的词典和集合将完全不可靠，这是一个可怕的后果。
[En]
Otherwise, the constant hash table algorithm will be destroyed and the dictionaries and collections made up of these objects will be completely unreliable, which is a terrible consequence.
另一方面,如果一个含有自定义 __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的风格,用由字典组成的列表来存放这些记录,用元组取代字典能节省空间的原因有两个:
其一是避免哈希表占用的空间。第二，不需要将记录中的字段名称存储在每个元素中。
[En]
One is to avoid the space consumed by hash tables. The second is that there is no need to store the names of the fields in the record in each element.
在用户自定义的类型中, __slots__属性可以改变实例属性的存储方式,由dict变成tuple.
3.键查询很快
dict的实现是典型的空间换时间:字典类型有着巨大的内存开销,但它们提供了无视数据量的快速访问–只要字典能被装在内存里.
4.键的次序取决于添加顺序
当往dict里添加新键而又发生散列冲突的时候,新键可能会被安排存放到另一个位置.于是下面的这种情况就会发生:
由 dict([(key1, value1), (key2, value2)])和 dict([(key2, value2), (key1, value1)])得到的两个字典,在进行比较的时候,它们是相等的.
但是如果在key1和key2被添加到字典里的过程中有冲突发生的话,这两个键出现在字典里的顺序是不一样的.
下面的示例显示了当前的橡树。此示例使用相同的数据创建三个词典。唯一的区别是数据以不同的顺序出现。如您所见，尽管键的顺序打乱了，但这三本词典仍然被认为是相等的。
[En]
The following example shows this current oak. This example creates three dictionaries with the same data. The only difference is that the data appear in a different order. As you can see, although the order of the keys is out of order, the three dictionaries are still considered equal.
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解释器都可能做出为字典扩容的决定.扩容导致的结果就是要新建一个更大的散列表,并把字典里已有的元素添加到新表里.
该过程可能会导致新的散列冲突，从而导致新散列表中密钥的顺序改变。
[En]
This process may cause new hash conflicts, resulting in a change in the order of keys in the new hash table.
要注意的是,上面提到的这些变化是否会发生以及如何发生,都依赖于字典背后的实现,因此你不能很自信的说自己知道背后发生了什么.
如果在迭代字典中的所有键的同时修改字典，循环很可能会跳过一些键，甚至跳过字典中已有的键。
[En]
If you modify the dictionary at the same time while iterating over all the keys in a dictionary, the loop is likely to skip some keys-or even those already in the dictionary.
由此可知,不要对字典同时进行迭代和修改.如果想扫描并修改一个字典,最好分成两步来进行:
首先对字典迭代,以得出需要添加的内容,把这些内容放在一个新字典里;迭代结束之后再对原字典进行更新.
在Python3中,.keys() .items() .values()方法返回的都是字典视图.也就是说,这些方法返回的值更像集合.
1.集合里的元素必须是可散列的.
2.集合很消耗内存.
3.可以很高效的判断元素是否存在于某个集合.
4.元素的次序取决于被添加到集合里的次序.
5.往集合里添加元素,可能会改变集合里已有元素的次序.
结尾给大家推荐一个非常好的学习教程，希望对你学习Python有帮助！
Original: https://www.cnblogs.com/djdjdj123/p/15483539.html
Author: Python探索牛
Title: Python里的dict和set的背后小秘密
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/510918/
转载文章受原作者版权保护。转载请注明原作者出处！