生产良好哈希值的最简单方法是将您的值放入标准可哈希Python容器中,然后哈希{{它}}。这包括在子类中组合哈希。我会先解释为什么,然后再解释如何。
基本要求
首先:
如果两个对象测试相等,则它们必须具有相同的哈希值。
具有哈希值的对象必须随时间产生相同的哈希值。
只有遵循这两个规则,您的对象才能安全地用于字典和集合。哈希不变是保持字典和集合不会破裂的因素,因为它们使用哈希来选择存储位置,如果哈希值更改,则无法再次定位对象,即使给出另一个测试相等的对象。
请注意,即使两个对象是不同类型的,也无关紧要;True == 1 == 1.0因此都具有相同的哈希,并且在字典中都将计为相同的键。
好的哈希值的特点
您希望以尽可能多地产生不同哈希值的方式组合对象值的组件。这包括诸如排序和特定含义之类的内容,以便代表值的两个属性,但可以保存相同类型的Python对象的属性,仍然大多数情况下会产生不同的哈希值。
请注意,如果两个代表不同值的对象(不相等)具有相等的哈希值,则这是可以接受的。重用哈希值不会破坏集合或字典。然而,如果许多不同的对象值产生相等的哈希值,则会降低它们的效率,因为这增加了冲突的可能性。冲突需要
解决冲突,解决冲突需要更多的时间,以至于您可以
使用可预测哈希实现对服务器进行拒绝服务攻击)
(*)。
因此,您需要一个良好的哈希值分布范围。
要注意的陷阱
object.__hash__方法的文档包括一些有关如何组合值的建议:
“唯一必需的属性是比较相等的对象具有相同的哈希值;建议对对象的组成部分的哈希值进行某种混合(例如使用异或),这些组成部分也参与对象的比较。”
但是,仅使用XOR将不会产生良好的哈希值,特别是当您对其哈希值进行XOR的值可以是相同类型但根据它们被分配给的属性具有不同含义时。以下是一个示例:
>>> class Foo:
... def __init__(self, a, b):
... self.a = a
... self.b = b
... def __hash__(self):
... return hash(self.a) ^ hash(self.b)
...
>>> hash(Foo(42, 'spam')) == hash(Foo('spam', 42))
True
由于self.a和self.b的哈希值只是简单地进行了异或操作,我们得到了相同的哈希值,因此有效地减少了可用哈希数目。如果使用更多属性进行操作,则唯一哈希数将迅速减少。因此,如果组成哈希的元素中可以使用相同的值,则可能需要在哈希中包含有关每个属性的更多信息。
其次,请注意,虽然Python整数是无界的,但哈希值
不是。也就是说,哈希值具有有限范围。来自同一文档:
“注意:hash()将从对象的自定义__hash__()方法返回的值截断为Py_ssize_t的大小。这通常是64位版本上的8个字节和32位版本上的4个字节。”
这意味着,如果使用增加存储哈希值所需位数的加法、乘法或其他操作,则最终会丢失上位位,因此再次减少不同哈希值的数量。
接下来,如果将已经具有有限范围的多个哈希与XOR结合起来,很可能会得到更小的可能哈希数。尝试对0-10范围内1000个随机整数的哈希进行异或操作,以获得极端示例。
哈希,简单易行的方式
Python开发人员长期以来一直在解决上述问题,并为标准库类型解决了这个问题。利用它的优点。将您的值放入一个元组中,然后对该元组进行哈希处理。
Python元组使用简化版的
xxHash算法来捕获顺序信息并确保广泛的哈希值范围。因此,对于不同的属性,您可以通过在元组中给它们不同的位置来捕获不同的含义,然后对元组进行哈希:
def __hash__(self):
return hash((self.a, self.b))
这可以确保您对于唯一的排序获得唯一的哈希值。
如果您正在子类化某个东西,请将父实现的哈希放入元组位置之一:
def __hash__(self):
return hash((super().__hash__(), self.__more_data))
哈希一个哈希值会将其减少到60位或30位的值(在32位或64位平台上,分别),但与元组中的其他值结合使用时,这不是一个大问题。如果您真的很关心这个问题,在元组中放置
None
作为占位符,并异或父哈希(因此
super().__hash__() ^ hash((None, self.__more_data))
)。但这真的有点过头了。
如果您有多个值的相对顺序并不重要,并且不想逐个将它们全部异或在一起,请考虑使用
frozenset()
对象进行快速处理,再结合
collections.Counter()
对象(如果值不需要唯一)。
frozenset()
哈希操作通过首先重新排列哈希中的位来解决小哈希范围的问题。
from collections import Counter
hash(frozenset(Counter(...).items()))
一如既往,元组或frozenset()
中的所有值本身都必须是可哈希的。
考虑使用数据类
对于大多数你编写__hash__
函数的对象,实际上应该使用由生成的类:
from dataclasses import dataclass
from typing import Union
@dataclass(frozen=True)
class Foo:
a: Union[int, str]
b: Union[int, str]
当 frozen=True
或 unsafe_hash=True
时,Dataclasses 会给出一个合理的 __hash__
实现,使用包含所有字段值的 tuple()
。
Python通过使用进程级别的
随机哈希种子来对字符串、字节和
datetime
对象进行哈希处理,以保护您的代码免受哈希冲突攻击的影响。
(*)
return hash((self.a, tuple(self.b_list)))
- Bob Steinhash((self.a, *self.b_list))
将self.b_list
的所有值提取到为哈希创建的元组中,作为使用tuple()
的替代方法。 - Martijn Pieters