Python中的默认 __hash__ 是什么?

80

我经常使用奇特的东西作为字典的键,所以我想知道正确的做法——这需要为我的对象实现良好的哈希方法。我知道这里已经有其他提问,例如good way to implement hash,但我想了解默认的__hash__如何适用于自定义对象,并且是否可以依赖它。

我注意到可变对象明确是不可哈希的,因为hash({})会引发错误...但奇怪的是,自定义类是可哈希的:

>>> class Object(object): pass
>>> o = Object()
>>> hash(o)

那么,有人知道这个默认哈希函数是如何工作的吗?通过了解这一点,我想知道:

如果我将同一类型的对象作为字典键放入其中,我能否依赖于这个默认哈希函数?例如:

key1 = MyObject()
key2 = MyObject()
key3 = MyObject()
{key1: 1, key2: 'blabla', key3: 456}

如果我在字典中使用不同类型的对象作为键,那么我可以依赖它吗?例如:

{int: 123, MyObject(10): 'bla', 'plo': 890}

在最后一种情况中,如何确保我的自定义哈希与内置哈希不冲突?例如:

{int: 123, MyObject(10): 'bla', MyObjectWithCustomHash(123): 890}

2
https://dev59.com/snE85IYBdhLWcg3wLAQV#2909119 - John La Rooy
3
明白了,已经看到问题中的链接了。 - sebpiq
2
虽然无关紧要,但是需要注意的一点是,“如果你要重写 __hash__,也要重写 __eq__”。 - John Strood
1
用户定义的类默认具有__eq__()和__hash__()方法;使用它们,所有对象都不相等(除了它们自己),并且x.hash()返回一个适当的值,使得x == y意味着x is y和hash(x) == hash(y)。 - Dobob
6个回答

43
您可以依赖的是:自定义对象具有默认的hash(),其基于对象的标识。即使用默认哈希的任何对象在其生命周期内都将具有该哈希的恒定值,不同的对象可能具有不同的哈希值。
您不能依赖id()返回值与hash()返回值之间的任何特定关系。在Python 2.6及更早版本的标准C实现中,它们是相同的,在Python 2.7-3.2中,hash(x)==id(x)/16编辑:最初我写道,在发布3.2.3及更高版本或2.7.3及更高版本中,哈希值可能会被随机化,并且在Python 3.3中,关系将始终被随机化。实际上,目前该随机化仅适用于散列字符串,因此除以16的关系现在可能仍然成立,但请勿过于依赖它。
哈希碰撞通常并不重要:在字典查找中,为了找到一个对象,它必须具有相同的哈希值并且还必须相等。只有当您得到非常高比例的碰撞时,例如在导致Python的最新版本能够随机化哈希计算的拒绝服务攻击中,碰撞才会有影响。

顺便说一句:从3.3版本开始,低位比特被滚动而不是截断 - 至少到3.12版本为止 - Karl Knechtel

20
在 Python 3 中,以下函数用于 object 的子类,针对对象的 id()(来自 pyhash.c)进行操作。
Py_hash_t
_Py_HashPointer(void *p)
{
    Py_hash_t x;
    size_t y = (size_t)p;
    /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
       excessive hash collisions for dicts and sets */
    y = (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4));
    x = (Py_hash_t)y;
    if (x == -1)
        x = -2;
    return x;
}

SIZEOF_VOID_P 在 64 位 Python 中为 8,在 32 位 Python 中为 4。

>>> class test: pass
...
>>> a = test()
>>> id(a)
4325845928
>>> hash(a)
-9223372036584410438

你可以看到哈希是使用公式(id(a) >> 4) | (id(a) << (8 * SIZEOF_VOID_P - 4))id(a)计算的,其中按位运算在C有符号整数上执行。例如,对于上面定义的a:

>>> import numpy
>>> y = numpy.array([4325845928], dtype='int64')
>>> SIZEOF_VOID_P = 8
>>> (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4))
array([-9223372036584410438])
请注意,我正在使用 numpy.array(dtype='int64'),以便按照C语言的方式执行位运算(如果您在Python整数上执行相同的操作,则会获得不同的行为,因为它们不会溢出)。详情请参见https://dev59.com/MVfUa4cB1Zd3GeqPFSs0#5994397

根据达uncan所说 - 在Python 3.3中,id()hash()之间甚至没有固定的关系。 - Piotr Dobrogost
@PiotrDobrogost 这里有一个固定的关系式,它是(id(x) >> 4) | (id(x) << (8 * SIZEOF_VOID_P - 4))。我贴在这里的代码是从Python 3源码中取出的。d(输入到_Py_HashPointer函数中的变量)是对象的内存地址,即它的id()。运行SIZEOF_VOID_P = 8; y = numpy.array([4325845928], dtype='int64'); print((y >> 4) | (y << (8 * SIZEOF_VOID_P - 4)))。结果是-9223372036584410438,这与我上面展示的例子相符。 - asmeurer
我认为Duncan指的是Python 3.3中引入的哈希随机化。然而,目前它仅对字符串起作用,你展示的代码可能是针对一般情况的。 - Piotr Dobrogost
size_t在C语言中是无符号的(不带符号),因此正如注释所述,这是一个滚动操作。 - David Munro
2
截至3.12版本,尽管已经进行了重构,但它仍然以这种方式工作。这是在基本的object类型中找到的默认实现;任何其他类型(如str)都可以自由地覆盖它。 - Karl Knechtel

13

文档指出自定义对象依赖于id()作为它们的hash()实现:

CPython实现细节:这是内存中对象的地址。

如果您将自定义对象与像int这样的内置类型混合使用,则可能会发生哈希冲突,但如果它们平均分布,则没有任何问题。除非您真正遇到性能问题,否则不要过多调查。


那么,您的意思是如果我只使用自定义类型,就不应该出现冲突吗? - sebpiq
2
对,id 是唯一的。其他类型的问题在于它们不一定使用 id(),而是经常使用更合理的哈希值;例如,整数只使用其值作为哈希值。 - poke
所以:{int: 123, MyObject(): 465, MyType: 890} 应该是安全的,对吧? - sebpiq
另外...让我再次强调,尽管文档上说,在Python 2.7中id(custom_obj) != hash(custom_obj) - sebpiq
尽管可能会发生哈希冲突,但它们是“安全的”。这只是一个性能问题。回答你的问题,如果你的键不仅仅是自定义对象实例,那么可能会发生哈希冲突。 - user816328
显示剩余2条评论

10

用户定义类的默认哈希是返回它们的 id。这提供了通常很有用的行为;使用用户定义类的实例作为字典键将允许在再次提供完全相同对象以查找值时检索关联值。例如:

>>> class Foo(object):
    def __init__(self, foo):
        self.foo = foo


>>> f = Foo(10)
>>> d = {f: 10}
>>> d[f]
10

这与用户定义类的默认相等性匹配:

>>> g = Foo(10)
>>> f == g
False
>>> d[g]

Traceback (most recent call last):
  File "<pyshell#9>", line 1, in <module>
    d[g]
KeyError: <__main__.Foo object at 0x0000000002D69390>
注意,尽管 fg 的属性具有相同的值,它们并不相等,查找 d 中的 g 并不能找到存储在 f 下的值。此外,即使我们更改了 f.foo 的值,在 d 中查找 f 仍然可以找到该值。
>>> f.foo = 11
>>> d[f]
10

假设某个新类的实例在没有程序员特别声明其等效条件的情况下应被视为不等效,这可以通过定义__eq____hash__来实现。

这种方法非常有效;如果我定义一个Car类,那么具有相同属性的两辆汽车可能代表着两辆不同的汽车。如果我有一个映射汽车到注册所有者的字典,我不希望在查找Bob的汽车时找到Alice,即使Alice和Bob恰好拥有相同的汽车!另一方面,如果我定义了一个表示邮政编码的类,则可能确实希望将具有相同代码的两个不同对象视为可互换的"同一"事物的表示。在这种情况下,如果我有一个将邮政编码映射到州的字典,我显然希望能够使用表示相同邮政编码的两个不同对象找到相同的州。

我将其称为“值类型”和“对象类型”之间的区别。值类型表示某个值,我关心的是该,而不是每个单独对象的标识。用两种不同的方式得到相同值都是同样好的,并且围绕值类型传递代码的"契约"通常只承诺提供一个具有某些值的对象,而不指定哪个特定对象。对于对象类型,则每个单独实例都有自己的标识符,即使它包含与另一个实例完全相同的数据。围绕对象类型传递代码的"契约"通常承诺跟踪确切的单个对象。

那么为什么内置的可变类不使用其id作为其哈希值?因为它们都是容器,我们通常认为容器在大多数情况下类似于值类型,其值由所包含的元素确定:

>>> [1, 2, 3] == [1, 2, 3]
True
>>> {f: 10} == {f: 10}
True

但是,可变容器具有短暂的值。某个给定列表当前具有值[1, 2, 3],但它可以被改变为具有值[4, 5, 6]。如果您可以将列表用作字典键,则我们必须对查找是否应使用列表的(当前)值或其标识进行裁决。无论哪种方式,当正在用作字典键的对象的值通过突变而发生变化时,我们都可能会感到(非常)惊讶。仅当对象的值其标识或对象的标识与其价值无关时,将对象用作字典键才能很好地工作。因此,Python选择声明不可哈希的可变容器。


现在,针对您直接提出的问题的更具体细节:

1)由于在CPython中,默认哈希映射到对象的内存地址(尽管根据其他答案/评论,似乎只有<2.6),因此在同时存在的两个使用默认散列的对象上,无论涉及哪些类,它们的哈希值都不可能产生冲突(如果它作为字典键存储,它就是活动的)。我还期望其他不使用内存地址作为哈希的Python实现在使用默认哈希时应该仍然具有良好的哈希分布。所以是的,你可以依靠它。

2)只要您不返回作为自定义哈希的结果恰好是某个现有对象的哈希值,您就应该相对安全。我的理解是,Python基于哈希的容器对次优哈希函数相对宽容,只要它们不完全退化。


5
>>> class C(object):
...     pass
... 
>>> c = C()
>>> hash(c) == id(c)
True

请查看函数id

2
我在Python 2.7和3.2上得到了“False”,但在Python 2.6上得到了“True”。 - huon
5
早期版本的CPython直接使用id()的值作为默认的hash(),而新版本则使用id()/16,因为在CPython中,所有的id都是16的倍数,并且你希望低位设置。这纯粹是一种实现细节:默认的hash()是从id()生成的,但在不同的版本中确切的生成方式会有所改变。在Python 3.3中,甚至不会有一个固定的id()hash()之间的关系。 - Duncan
@Duncan 为什么要除以16?为什么所有的ID都是16的倍数,并且希望低位设置? - onepiece
Python对象对齐于内存字大小,因此对于64位解释器,每个对象都对齐于16的倍数。id仅仅是内存地址,所以所有的id都是16的倍数。这很重要,因为当你遇到哈希冲突时,新的哈希值会从旧的哈希值中使用最低的5位重新计算,如果其中4位始终为0,则有很高的可能性会再次发生冲突。 - Duncan

-2
>>> class C(object):
...     pass
... 
>>> c = C()
>>> hash(c) == id(c)
False
>>> hash(c) == id(c)/16
True

除以16的结果为True


2
抄袭三年前发布的答案几乎没有任何用处。 - Alex Huszagh

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