69

我经常使用时髦的东西作为字典的键,因此,我想知道正确的方法是什么——这通过为我的对象实现良好的哈希方法。我知道这里提出的其他问题,例如实现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}
4

6 回答 6

39

您可以依赖什么:自定义对象有一个默认值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 能够随机化哈希计算。

于 2012-07-04T07:57:11.817 回答
13

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

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

如果您将自定义对象与内置类型(如int它们)混合使用,则可能是哈希冲突,但如果它们均匀分布,那根本没有问题。除非您真的遇到性能问题,否则不要进行太多调查。

于 2012-07-04T07:33:56.183 回答
13

在 Python 3 中,以下函数用于对象的子类objectid()来自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_P64 位 Python 为 8,32 位 Python 为 4。

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

您可以看到哈希是id(a)使用公式计算得出的,其中对有符号整数(id(a) >> 4) | (id(a) << (8 * SIZEOF_VOID_P - 4))执行按位运算。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 int 执行相同的操作,则会得到不同的行为,因为它们不会溢出)。请参阅https://stackoverflow.com/a/5994397/161801

于 2015-11-06T17:31:19.613 回答
9

用户定义的类的默认哈希是只返回它们的 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具有相同的属性值,它们也不相等,并且在查找gd找不到存储在 下的值f。此外,即使我们更改 的值,f.foo查找仍然会找到该值:fd

>>> f.foo = 11
>>> d[f]
10

__eq__假设是一些任意新类的实例应该被视为非等价的,除非程序员通过定义和明确声明两个实例被视为等价的条件__hash__

这非常有效;如果我定义一个Car类,我可能会认为两辆具有相同属性的汽车代表两辆不同的汽车。如果我有一本将汽车映射到注册车主的字典,我不想在查找 Bob 的汽车时找到 Alice,即使 Alice 和 Bob 碰巧拥有相同的汽车!OTOH,如果我定义一个类来表示邮政编码,我可能确实想考虑两个具有相同代码的不同对象是“相同”事物的可互换表示,在这种情况下,如果我有一个将邮政编码映射到州的字典,我显然希望能够找到具有表示相同邮政编码的两个不同对象的相同状态。

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

那么为什么内置的可变类不使用它们的 id 作为它们的哈希呢?这是因为它们都是容器,我们通常认为容器大多类似于值类型,它们的值由包含的元素决定:

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

但是可变容器的值是瞬态的。一些给定的列表当前具有该值[1, 2, 3],但它可以被变异为具有该值[4, 5, 6]。如果您可以使用列表作为字典键,那么我们必须就查找是否应该使用列表的(当前)值或其标识做出裁决。无论哪种方式,当当前用作字典键的对象的值通过变异来更改时,我们都会(非常)惊讶。仅当对象的值是它的标识,或者对象的标识与其值无关时,将对象用作字典键才有效。所以 Python 选择的答案是声明可变容器不可散列。


现在,回答您的直接问题的更具体细节:

1)由于CPython中的这个默认散列(虽然显然只有<2.6,根据其他答案/评论)映射到对象的内存地址,所以在CPython中,没有两个同时使用默认散列的对象可能会发生冲突它们的哈希值,不管涉及的类是什么(如果它被存储为字典键,它就是实时的)。我还希望其他不使用内存地址作为散列的 Python 实现仍然应该在使用默认散列的对象之间具有良好的散列分布。所以是的,你可以依靠它。

2)只要您不返回与某个现有对象的哈希值完全相同的结果作为您的自定义哈希值,您就应该相对没问题。我的理解是,Python 的基于散列的容器相对可以容忍次优散列函数,只要它们没有完全退化。

于 2012-07-04T08:05:53.483 回答
4
>>> class C(object):
...     pass
... 
>>> c = C()
>>> hash(c) == id(c)
True

见函数ID

于 2012-07-04T07:30:18.263 回答
-3
>>> class C(object):
...     pass
... 
>>> c = C()
>>> hash(c) == id(c)
False
>>> hash(c) == id(c)/16
True

除以 16 为真

于 2015-08-27T09:17:30.433 回答