如何在 Python3 中组合哈希码?
How to combine hash codes in in Python3?
我更熟悉 "Java way" 从子类中的超类构建复杂/组合的哈希码。 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
。
The python documentation建议你使用异或来组合哈希:
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 而不是加法和乘法,因为:
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. If an object’s __hash__()
must interoperate on builds of different bit sizes, be sure to check the width on all supported builds. An easy way to do this is with python -c "import sys; print(sys.hash_info.width)
"
顺便说一下,此文档对于 python 2.7 和 python 3.4 是相同的。
关于对称性和项目自身异或的说明。
正如评论中所指出的,xor 是对称的,因此操作顺序消失了。两个相同元素的异或也为零。因此,如果不需要混合一些旋转或移位,或者更好,使用 来获取标识元素的元组的哈希值。如果您不想保留顺序,请考虑使用 frozenset
.
对于阅读本文的任何人来说,对哈希进行异或运算不是一个好主意,因为重复哈希值的特定序列可能会一起异或并有效地从哈希集中删除一个元素。
例如:
(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')
如果您想对此进行更多探索,您应该查看 Bloom 过滤器。
生成良好散列的最简单方法是将您的值放入标准的可散列 Python 容器中,然后散列 that。这包括在子类中组合哈希。我会解释为什么,然后如何。
基本要求
要事第一:
- 如果两个对象测试相等,则它们必须具有相同的散列值
- 具有散列的对象,必须随时间产生相同的散列。
只有遵循这两条规则,您的对象才能安全地用于字典和集合中。哈希值不变是防止字典和集合被破坏的原因,因为它们使用哈希值来选择存储位置,并且如果哈希值发生变化,则如果另一个对象测试相等,则将无法再次定位该对象。
请注意,即使两个对象的类型不同也没关系; True == 1 == 1.0
所以它们都具有相同的哈希值,并且在字典中都算作相同的键。
什么是好的哈希值
您希望以尽可能为不同值生成不同散列的方式组合对象值的组成部分。这包括 ordering 和 specific meaning 之类的东西,所以这两个属性代表您的价值的不同方面,但可以包含相同类型的 Python 个对象,仍然会产生不同的哈希值,大部分时间。
请注意,如果代表不同值(不会测试相等)的两个对象具有相同的哈希值,则很好。重用哈希值不会破坏集合或字典。但是,如果许多不同的对象值产生相同的哈希值,那么会降低它们的 效率 ,因为您会增加冲突的可能性。碰撞需要 collision resolution and collision resolution takes more time, so much so that you can 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 不会产生好的哈希值,当您将其哈希值异或在一起的值可能属于同一类型但具有不同的含义时,则不会产生良好的哈希值,具体取决于属性他们被分配到。举例说明:
>>> 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-ed 在一起,我们得到了两个顺序相同的哈希值,因此有效地将可用哈希的数量减半。使用更多属性这样做,您可以快速减少唯一哈希值的数量。因此,如果可以在构成哈希的不同元素中使用相同的值,则您可能希望在哈希中包含更多关于每个属性的信息。
接下来,知道虽然 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 组合,您最终得到的可能哈希值可能会更少。尝试 XOR-ing 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
作为占位符放在元组中并对父散列进行 XOR(所以 super().__hash__() ^ hash((None, self.__more_data))
)。但这确实有点矫枉过正。
如果您有多个值,其相对顺序 不重要 ,并且不想将这些值一一异或,请考虑使用 frozenset()
用于快速处理的对象,如果值不是唯一的,则与 collections.Counter()
对象结合使用。 frozenset()
哈希操作通过首先重新排列哈希中的位来说明小哈希范围:
# unordered collection hashing
from collections import Counter
hash(frozenset(Counter(...).items()))
一如既往,元组或 frozenset()
中的所有值都必须是 hashabe 他们自己。
考虑使用数据类
对于您为其编写 __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]
当 frozen=True
或 unsafe_hash=True
时,使用所有字段值的 tuple()
为数据类提供合理的 __hash__
实现。
(*) Python 通过使用 process-wide random hash seed 来散列字符串、字节和datetime
个对象。
不要将多个字符串组合在一起,而是使用元组,因为它们在 python 中是可散列的。
t: Tuple[str, str, int] = ('Field1', 'Field2', 33)
print(t.__hash__())
这将使代码更易于阅读。
我更熟悉 "Java way" 从子类中的超类构建复杂/组合的哈希码。 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
。
The python documentation建议你使用异或来组合哈希:
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 而不是加法和乘法,因为:
Note
hash()
truncates the value returned from an object’s custom__hash__()
method to the size of aPy_ssize_t
. This is typically 8 bytes on 64-bit builds and 4 bytes on 32-bit builds. If an object’s__hash__()
must interoperate on builds of different bit sizes, be sure to check the width on all supported builds. An easy way to do this is withpython -c "import sys; print(sys.hash_info.width)
"
顺便说一下,此文档对于 python 2.7 和 python 3.4 是相同的。
关于对称性和项目自身异或的说明。
正如评论中所指出的,xor 是对称的,因此操作顺序消失了。两个相同元素的异或也为零。因此,如果不需要混合一些旋转或移位,或者更好,使用 frozenset
.
对于阅读本文的任何人来说,对哈希进行异或运算不是一个好主意,因为重复哈希值的特定序列可能会一起异或并有效地从哈希集中删除一个元素。
例如:
(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')
如果您想对此进行更多探索,您应该查看 Bloom 过滤器。
生成良好散列的最简单方法是将您的值放入标准的可散列 Python 容器中,然后散列 that。这包括在子类中组合哈希。我会解释为什么,然后如何。
基本要求
要事第一:
- 如果两个对象测试相等,则它们必须具有相同的散列值
- 具有散列的对象,必须随时间产生相同的散列。
只有遵循这两条规则,您的对象才能安全地用于字典和集合中。哈希值不变是防止字典和集合被破坏的原因,因为它们使用哈希值来选择存储位置,并且如果哈希值发生变化,则如果另一个对象测试相等,则将无法再次定位该对象。
请注意,即使两个对象的类型不同也没关系; True == 1 == 1.0
所以它们都具有相同的哈希值,并且在字典中都算作相同的键。
什么是好的哈希值
您希望以尽可能为不同值生成不同散列的方式组合对象值的组成部分。这包括 ordering 和 specific meaning 之类的东西,所以这两个属性代表您的价值的不同方面,但可以包含相同类型的 Python 个对象,仍然会产生不同的哈希值,大部分时间。
请注意,如果代表不同值(不会测试相等)的两个对象具有相同的哈希值,则很好。重用哈希值不会破坏集合或字典。但是,如果许多不同的对象值产生相同的哈希值,那么会降低它们的 效率 ,因为您会增加冲突的可能性。碰撞需要 collision resolution and collision resolution takes more time, so much so that you can 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 不会产生好的哈希值,当您将其哈希值异或在一起的值可能属于同一类型但具有不同的含义时,则不会产生良好的哈希值,具体取决于属性他们被分配到。举例说明:
>>> 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-ed 在一起,我们得到了两个顺序相同的哈希值,因此有效地将可用哈希的数量减半。使用更多属性这样做,您可以快速减少唯一哈希值的数量。因此,如果可以在构成哈希的不同元素中使用相同的值,则您可能希望在哈希中包含更多关于每个属性的信息。
接下来,知道虽然 Python 整数是无界的,但散列值 不是 。也就是说,哈希值有一个有限的范围。来自同一文档:
Note:
hash()
truncates the value returned from an object’s custom__hash__()
method to the size of aPy_ssize_t
. This is typically 8 bytes on 64-bit builds and 4 bytes on 32-bit builds.
这意味着如果您使用加法或乘法或其他增加存储哈希值所需位数的运算,您最终将丢失高位,从而再次减少不同哈希值的数量。
接下来,如果您将多个哈希值与已经具有有限范围的 XOR 组合,您最终得到的可能哈希值可能会更少。尝试 XOR-ing 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
作为占位符放在元组中并对父散列进行 XOR(所以 super().__hash__() ^ hash((None, self.__more_data))
)。但这确实有点矫枉过正。
如果您有多个值,其相对顺序 不重要 ,并且不想将这些值一一异或,请考虑使用 frozenset()
用于快速处理的对象,如果值不是唯一的,则与 collections.Counter()
对象结合使用。 frozenset()
哈希操作通过首先重新排列哈希中的位来说明小哈希范围:
# unordered collection hashing
from collections import Counter
hash(frozenset(Counter(...).items()))
一如既往,元组或 frozenset()
中的所有值都必须是 hashabe 他们自己。
考虑使用数据类
对于您为其编写 __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]
当 frozen=True
或 unsafe_hash=True
时,使用所有字段值的 tuple()
为数据类提供合理的 __hash__
实现。
(*) Python 通过使用 process-wide random hash seed 来散列字符串、字节和datetime
个对象。
不要将多个字符串组合在一起,而是使用元组,因为它们在 python 中是可散列的。
t: Tuple[str, str, int] = ('Field1', 'Field2', 33)
print(t.__hash__())
这将使代码更易于阅读。