如何在Python3中合并哈希码?

20

我更熟悉使用Java方式在子类中从超类构建复杂/组合哈希码的方法。Python 3 中是否有更好/不同/首选的方法?(我在Google上找不到任何关于这个问题的特定内容。)

class Superclass:
    def __init__(self, data):
        self.__data = data

    def __hash__(self):
        return hash(self.__data)

class Subclass(Superclass):
    def __init__(self, data, more_data):
        super().__init__(data)
        self.__more_data = more_data

    def __hash__(self):
        # Just a guess...
        return hash(super()) + 31 * hash(self.__more_data)
为了简化这个问题,请假设self.__dataself.__more_data是简单的可哈希数据,例如strint
4个回答

34
生产良好哈希值的最简单方法是将您的值放入标准可哈希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()哈希操作通过首先重新排列哈希中的位来解决小哈希范围的问题。
# unordered collection hashing
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=Trueunsafe_hash=True 时,Dataclasses 会给出一个合理的 __hash__ 实现,使用包含所有字段值的 tuple()


Python通过使用进程级别的随机哈希种子来对字符串、字节和datetime对象进行哈希处理,以保护您的代码免受哈希冲突攻击的影响。(*)

提示:将任何列表属性转换为元组:return hash((self.a, tuple(self.b_list))) - Bob Stein
1
@BobStein:这适用于任何可变(不可哈希)数据结构,而不仅仅是列表,并且您可能需要递归地转换值。您可以在此处使用hash((self.a, *self.b_list))self.b_list的所有值提取到为哈希创建的元组中,作为使用tuple()的替代方法。 - Martijn Pieters

6

Python文档建议使用异或运算符来组合哈希值:

唯一必需的属性是比较相等的对象具有相同的哈希值;建议以某种方式混合(例如使用异或)对象的组件的哈希值,这些组件在对象比较中也起作用。

我还建议使用异或运算符而不是加法和乘法,因为:

注意

hash() 截断从对象的自定义 __hash__() 方法返回的值到一个 Py_ssize_t 的大小。在 64 位构建上通常为 8 个字节,在 32 位构建上为 4 个字节。如果对象的 __hash__() 必须在不同位大小的构建上进行交互操作,请确保在所有支持的构建上检查宽度。可以使用 python -c "import sys; print(sys.hash_info.width)" 轻松实现此目的。

顺便说一下,这份文档适用于 Python 2.7 和 Python 3.4。

关于对称性和将项与自身进行异或的说明。

正如评论中指出的那样,异或是对称的,因此操作顺序消失了。两个相同元素的异或也等于零。因此,如果不希望出现这种情况,请混合一些旋转或移位,或者更好的方法是使用this solution's suggestion,即对识别元素的元组取哈希值。如果您不想保留顺序,请考虑使用frozenset


很好的回答。感谢提供参考资料。 关于“截断”,这是由于Python中整数没有限制的精度吗?整数具有无限精度。(大多数人对此感到惊讶!) - kevinarpe
1
我知道整数具有无限精度。然而,hash()函数并没有无限精度。它被实现为返回一个Py_ssize_t类型的值,这个值很可能是8字节,因此它将返回__hash__的结果模2^64-1的余数。 - Thom Wiggers
这是一个合理的实现吗:return super().__hash__() ^ hash(self.__more_data) - kevinarpe
这是正确的,但对于加法也适用…你可以尝试将其与旋转结合起来。 - Thom Wiggers
1
@ThomWiggers:这就是SO的前辈推荐的:https://dev59.com/enI-5IYBdhLWcg3w18V3#1646913 (c#)“_没有人真正知道为什么它运行得很好……_” - 3dGrabber
显示剩余6条评论

3

不要将多个字符串组合在一起,使用元组,因为它们在Python中是可哈希的。

t: Tuple[str, str, int] = ('Field1', 'Field2', 33)
print(t.__hash__())

这将使代码更易读。

1
我很欣赏这个答案的简洁明了,其他答案提供了很好的细节,但是这个答案对于快速得到答案非常有价值,需要更多的赞。 - David Parks
然而,我认为print(t.__hash__())最好改为print(hash(t))呈现。 - David Parks

-2

对于任何阅读此内容的人,XOR哈希是一个不好的想法,因为可能会出现一系列重复哈希值的特定序列进行XOR运算并有效地从哈希集中删除元素。

例如:

(hash('asd') ^ hash('asd') ^ hash('derp')) == hash('derp')

甚至还有:

(hash('asd') ^ hash('derp') ^ hash('asd')) == hash('derp')

因此,如果您使用此技术来确定某个值集合是否在组合哈希中,其中可能已将重复值添加到哈希中,则使用XOR可能会导致该值从集合中删除。相反,您应该考虑使用OR,它具有避免无限整数增长的先前帖子提到的相同属性,但确保不会删除重复项。

(hash('asd') | hash('asd') | hash('derp')) != hash('derp')

如果你想更深入地探索这方面的内容,你应该查阅布隆过滤器。


&掩码,所以在有多个值的情况下,您将继续删除位。您正在显着降低熵,因此现在情况更糟。我不确定您为什么提到布隆过滤器,因为它们本质上只是异或散列... - Martijn Pieters
布隆过滤器中的元素不进行异或运算,这是我之前描述的原因。在你所提出的技术(对哈希值进行异或运算)中,如何确保元素一定存在于集合中? - Hashes are probabilistic sets
对不起,我确实错了。Bloom过滤器在哈希结果上使用OR运算(设置位而非重置)。 - Martijn Pieters

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接