3

我有两个对象代表同一个对象。我什至保证他们有相同的哈希值。我仍然从字典中得到一个错误：

>>> hash(one)
1098414562
>>> hash(one+zero)
1098414562
>>> a={one:1}
>>> a[one+zero]

Traceback (most recent call last):
  File "<pyshell#25>", line 1, in <module>
    a[one+zero]
KeyError: {{|}|}

我还需要做什么来确保字典将其重新识别为相同的键？

4

3 回答 3

3

要成为正确可散列的字典键，对象还必须定义__eq__()or __cmp__()。它们必须比较相等才能被识别为相同的键。

如果对象具有相同的哈希，但比较不相等，则假定哈希冲突，并且它们在同一个哈希桶中分开。

当通过哈希查找对象时，匹配哈希桶中的所有对象都与它进行比较，如果没有相等，则为KeyError。

于 2013-07-01T00:27:27.547 回答
2

如果一个类没有定义一个__cmp__()或__eq__()方法，它也不应该定义一个__hash__()操作；如果它定义了__cmp__()or__eq__()但不是__hash__()，它的实例将不能在散列集合中使用。如果一个类定义了可变对象并实现了__cmp__()or__eq__()方法，则不应实现__hash__()，因为可散列集合实现要求对象的散列值是不可变的（如果对象的散列值发生更改，它将位于错误的散列桶中）。

来源

于 2013-07-01T00:27:05.660 回答
0

这称为哈希冲突。散列只是在字典中分配键的一种相对有效的方式。它不保证唯一性。当你查找一个键时，需要考虑所有具有匹配哈希的键，并使用该__eq__方法来确定它们是否真的匹配。

旁白：可能有一个类总是为它的任何实例返回相同的哈希值。然而，这破坏了通常的O(1)查找复杂性

n您可以通过尝试此处的不同值轻松查看线性时间查找

class MyInt(int):
    def __hash__(self):
        return hash(1)

d = {MyInt(i): i for i in xrange(n)}

d[MyInt(1)]  # This will take O(n) time since all values have the same hash
于 2013-07-01T01:16:15.110 回答