我经常使用时髦的东西作为字典的键,因此,我想知道什么是正确的方法 - 这通过为我的对象实现良好的哈希方法.我知道这里提出的其他问题是实现哈希的好方法,但我想了解默认如何__hash__适用于自定义对象,以及是否可以依赖它.
我注意到mutables显然是不可删除的,因为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}
Dun*_*can 29
您可以信赖的内容:自定义对象具有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能够随机化哈希计算.
在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)使用公式计算哈希值(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上执行相同的操作,则会因为不溢出而获得不同的行为).请参阅/sf/answers/419607821/.
用户定义类的默认哈希就是返回它们的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>
请注意,即使f和g对它们的属性相同的价值观,他们是不相等的仰起脸g在d没有找到下存储的值f.此外,即使我们改变的值f.foo,查找f中d还发现价值:
>>> f.foo = 11
>>> d[f]
10
假设一些任意新类的实例应该被视为非等价的,除非程序员明确声明两个实例的条件通过定义__eq__和来被视为等价__hash__.
这非常有效; 如果我定义一个Car类,我可能会认为两辆具有相同属性的汽车代表两种不同的汽车.如果我有一个字典映射车到注册车主,我不想找到爱丽丝当我查看鲍勃的车,即使爱丽丝和鲍勃碰巧拥有相同的车!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的基于散列的容器相对容忍次优散列函数,只要它们不是完全退化的.
>>> class C(object):
... pass
...
>>> c = C()
>>> hash(c) == id(c)
True
查看函数ID