Python里的dict和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.往集合里添加元素,可能会改变集合里已有元素的次序.

频道导航