python - 如何在 Python3 中组合哈希码？

Question

我更熟悉从子类中的父类(super class)构建复杂/组合哈希码的“Java 方式”。 Python 3 中是否有更好/不同/首选的方式？ (我无法通过 Google 在这件事上找到任何特定于 Python3 的内容。)

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.__data和 self.__more_data是简单的、可散列的数据，例如 str或 int .

Answer 1

产生良好散列的最简单方法是将您的值放入标准的可散列 Python 容器中，然后对其进行散列。这包括在子类中组合哈希。我将解释原因，然后解释如何。

基本要求

第一件事:

如果两个对象测试结果相等，则它们 必须具有相同的哈希值

具有哈希值的对象，必须随着时间的推移产生相同的哈希值。

只有当你遵循这两条规则时，你的对象才能安全地用于字典和集合中。散列不变是防止字典和集合被破坏的原因，因为它们使用散列来选择存储位置，并且如果散列更改，则在给定另一个测试相等的对象的情况下将无法再次定位该对象。

请注意，即使两个对象的类型不同也无关紧要； True == 1 == 1.0所以都具有相同的哈希值，并且都将被视为字典中的相同键。

什么是好的哈希值

您希望以尽可能为不同值生成不同散列的方式组合对象值的组件。这包括诸如排序和特定含义之类的事情，因此代表值的不同方面但可以保存相同类型的 Python 对象的两个属性在大多数情况下仍会产生不同的哈希值。

请注意，如果代表不同值(不会测试相等)的两个对象具有相同的散列值，那很好。重用哈希值不会破坏集合或字典。但是，如果许多不同的对象值产生相同的散列值，则会降低它们的效率，因为会增加冲突的可能性。碰撞要求 collision resolution并且冲突解决需要更多时间，以至于您可以 use denial of service attacks on servers with predictable hashing implementations ) (*)。

所以你想要一个很好的散列值的广泛传播。

需要注意的陷阱

documentation for the object.__hash__ method包括一些关于如何组合值的建议:

The only required property is that objects which compare equal have the same hash value; it is advised to somehow mix together (e.g. using exclusive or) the hash values for the components of the object that also play a part in comparison of objects.

但仅使用 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只是 XOR 在一起，我们得到了相同的散列值，因此有效地将可用散列的数量减半。使用更多属性这样做，您可以迅速减少唯一散列的数量。因此，如果可以在组成散列的不同元素中使用相同的值，您可能希望在散列中包含更多关于每个属性的信息。

接下来，要知道虽然 Python 整数是无界的，但哈希值不是。也就是说，哈希值的范围是有限的。来自同一文档:

Note: hash() truncates the value returned from an object’s custom __hash__() method to the size of a Py_ssize_t. This is typically 8 bytes on 64-bit builds and 4 bytes on 32-bit builds.

这意味着，如果您使用加法或乘法或其他增加存储散列值所需位数的操作，您最终将丢失高位，因此再次减少不同散列值的数量。

接下来，如果您将多个散列与已经具有有限范围的 XOR 组合在一起，那么您最终可能会得到更少数量的可能散列。对于一个极端的例子，尝试对 0-10 范围内的 1000 个随机整数的哈希进行异或运算。

散列，最简单的方法

Python 开发人员长期以来一直在努力解决上述陷阱，并针对标准库类型解决了这个问题。充分利用这一点。将您的值放在一个元组中，然后对该元组进行哈希处理。

Python 元组使用 xxHash algorithm 的简化版本捕获订单信息并确保广泛的散列值。所以对于不同的属性，你可以通过在元组中给它们不同的位置来捕捉不同的含义，然后对元组进行散列:

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()))

考虑使用数据类

对于您编写的大多数对象 __hash__函数，您实际上想要使用 dataclass generated class :

from dataclasses import dataclass
from typing import Union

@dataclass(frozen=True)
class Foo:
    a: Union[int, str]
    b: Union[int, str]

数据类被赋予了理智 __hash__实现时间 frozen=True或 unsafe_hash=True ，使用 tuple()所有字段值。

(*) Python 通过使用进程范围的 random hash seed 来保护您的代码免受此类哈希冲突攻击。散列字符串、字节和 datetime对象。