通过研究字典的底层实现,我们找到了字典快速且高效的秘密,就是哈希表。而提到哈希表,必然绕不开哈希值,因为它决定了映射之后的索引。
如果想计算对象的哈希值,那么要保证对象必须是可哈希的。如果不可哈希,那么它就无法计算哈希值,自然也就无法作为字典的 key。那什么样的对象是可哈希的呢?
- 因为哈希值不能发生改变,所以对象必须是不可变对象;
- 当对象的哈希值相等时,要判断对象是否相等,所以对象必须实现 __eq__ 方法;
所以如果对象满足不可变、并且实现了 __eq__ 方法,那么它就是可哈希的,只有这样的对象才能作为字典的 key 或者集合的元素。
像整数、浮点数、字符串等内置的不可变对象都是可哈希的,可以作为字典的 key。而像列表、字典等可变对象则不是可哈希的,它们不可以作为字典的 key。然后关于元组需要单独说明,如果元组里面的元素都是可哈希的,那么该元组也是可哈希的,反之则不是。
# 键是可哈希的就行,值是否可哈希则没有要求 d = {1: 1, "xxx": [1, 2, 3], 3.14: 333} # 列表是可变对象,因此无法哈希 try: d = {[]: 123} except TypeError as e: print(e) """ unhashable type: 'list' """ # 元组也是可哈希的 d = {(1, 2, 3): 123} # 但如果元组里面包含了不可哈希的对象 # 那么整体也会变成不可哈希对象 try: d = {(1, 2, 3, []): 123} except TypeError as e: print(e) """ unhashable type: 'list' """
而我们自定义类的实例对象也是可哈希的,并且哈希值是通过对象的地址计算得到的。
class Some: pass s1 = Some() s2 = Some() print(hash(s1), hash(s2)) """ 8744065697364 8744065697355 """
当然 Python 也支持我们重写哈希函数,比如:
class Some: def __hash__(self): return 123 s1 = Some() s2 = Some() print(hash(s1), hash(s2)) """ 123 123 """ print({s1: 1, s2: 2}) """ {<__main__.Some object at 0x0000029C0ED045E0>: 1, <__main__.Some object at 0x0000029C5E116F20>: 2} """
因为哈希值一样,映射出来的索引自然也是相同的,所以在作为字典的 key 时,会发生冲突。由于类的实例对象之间默认不相等,因此会改变规则重新映射,找一个可以写入的位置。
如果两个对象相等,它们的哈希值一定也相等。
注意:我们自定义类的实例对象默认都是可哈希的,但如果类里面重写了 __eq__ 方法,且没有重写 __hash__ 方法的话,那么这个类的实例对象就不可哈希了。
class Some: def __eq__(self, other): return True try: hash(Some()) except TypeError as e: print(e) """ unhashable type: 'Some' """
为什么会有这种现象呢?首先上面说了,在没有重写 __hash__ 方法的时候,哈希值默认是根据对象的地址计算得到的。而且对象如果相等,那么哈希值一定是一样的,并且不可变。
但我们重写了 __eq__,相当于控制了 == 操作符的比较结果,两个对象是否相等就由我们来控制了,可哈希值却还是根据地址计算得到的。因为两个对象地址不同,所以哈希值不同,但是对象却可以相等、又可以不相等,这就导致了矛盾。所以在重写了__eq__、但是没有重写 __hash__ 的情况下,其实例对象便不可哈希了。
但如果重写了 __hash__,那么哈希值就不再通过地址计算了,因此此时是可以哈希的。
class Some: def __eq__(self, other): return True def __hash__(self): return 123 s1 = Some() s2 = Some() print({s1: 1, s2: 2}) """ {<__main__.Some object at 0x00000202D7D945E0>: 2} """
我们看到字典里面只有一个元素,因为重写了 __hash__ 方法之后,计算得到的哈希值都是一样的。如果没有重写 __eq__,实例对象之间默认是不相等的,因此哈希值一样,但是对象不相等,那么会重新映射。但我们重写了 __eq__,返回的结果是 True,所以 Python 认为对象是相等的,那么由于 key 的不重复性,只会保留一个键值对。
但需要注意的是,在比较相等时,会先比较地址是否一样,如果地址一样,那么哈希表会直接认为相等。
class Some: def __eq__(self, other): return False def __hash__(self): return 123 def __repr__(self): return "Some Instance" s1 = Some() # 我们看到 s1 == s1 为 False print(s1 == s1) """ False """ # 但是只保留了一个 key,咦,两个 key 不相等,难道不应该重新映射吗? # 原因就是刚才说的,在比较是否相等之前,会先判断地址是否一样 # 如果地址一样,那么认为是同一个 key,直接判定相等 print({s1: 1, s1: 2}) """ {Some Instance: 2} """ s2 = Some() # 此时会保留两个 key,因为 s1 和 s2 地址不同,s1 == s2 也为 False # 所以哈希表认为这是两个不同的 key # 但由于哈希值一样,那么映射出来的索引也一样 # 因此写入 s2: 2 时相当于发生了索引冲突,于是会重新映射 # 但总之这两个 key 都会被保留 print({s1: 1, s2: 2}) """ {Some Instance: 1, Some Instance: 2} """
同样的,我们再来看一个 Python 字典的例子。
d = {1: 123} d[1.0] = 234 print(d) # {1: 234} d[True] = 345 print(d) # {1: 345}
天哪噜,这是咋回事?首先整数在计算哈希值的时候,得到的结果就是其本身;而浮点数显然不是,但如果浮点数的小数点后面是 0,那么它和整数是等价的。
因此 3 和 3.0 的哈希值一样,并且两者也是相等的,因此它们被视为同一个 key,所以相当于是更新。同理 True 也一样,因为 bool 继承自 int,所以它等价于 1,比如:9 + True = 10。因此 True 和 1 相等,并且哈希值也相等,那么索引 d[True] = 345 同样相当于更新。
但是问题来了,值更新了我们可以理解,字典里面只有一个元素也可以理解,可为什么 key 一直是 1 呢?理论上最终结果应该是 True 才对啊。
其实这算是 Python 偷了个懒吧(开个玩笑),因为 key 的哈希值是一样的,并且也相等,所以只会更新 value,而不会修改 key。
从字典在设置元素的时候我们也知道,如果将 key 映射成索引之后,发现哈希索引数组的槽没有人用,那么就按照先来后到的顺序将键值对存储在键值对数组中,然后再把它在键值对数组中的索引存在哈希索引数组的指定槽中。
但如果发现槽有人用了,那么根据槽里面存的索引,去键值对数组中查找指定的 entry,然后比较两个 key 是否相等。如果对应的 key 不相等,则重新映射找一个新的槽;如果相等,则说明是同一个 key,那么把 value 换掉即可。
所以在替换元素的整个过程中,根本没有涉及到对键的修改,因此在上面那个例子中,value 会变、但 key 始终是 1,而不是 True。
为了加深理解,我们再举个例子:
d = {"高老师": 666} class A: def __hash__(self): return hash("高老师") def __eq__(self, other): return True # A() == "高老师" 为 True,两者哈希值也一样 # 所以相当于对 key 进行更新 d[A()] = 777 print(d) # {'高老师': 777} print(d["高老师"]) # 777 print(d[A()]) # 777
只要两个对象相等,并且哈希值相等,那么对于哈希表来说,它们就是同一个 key。
另外我们反复在提哈希值,而哈希值是通过哈希函数运算得到的,一个理想的哈希函数要保证哈希值尽量均匀地分布于整个哈希空间中,越是相近的值,其哈希值差别应该越大。还是那句话,哈希函数对哈希表的好坏起着至关重要的作用。
以上我们就详细地聊了聊对象的哈希值,如果对象可以计算哈希值,那么它一定实现了 __hash__ 方法,而内置的不可变对象都实现了。
事实上内置的哈希函数 hash,本质上也是调用了 __hash__。
print(hash("hello")) print("hello".__hash__()) """ -7465190714692855315 -7465190714692855315 """
下一篇文章来聊一聊索引冲突是怎么解决的?