对于比较相同的类是否真的有必要散列相同的值？

Question

阅读this answer 看来，如果在自定义class 中定义了__eq__，那么也需要定义__hash__。这是可以理解的。
然而，目前尚不清楚，为什么 - 实际上 - __eq__ 应该与 self.__hash__()==other.__hash__

相同

想象这样一个 class：

class Foo:
    ...
    self.Name
    self.Value
    ...
    def __eq__(self,other):
        return self.Value==other.Value
    ...
    def __hash__(self):
        return id(self.Name)

这样 class 实例可以按值进行比较，这可能是唯一合理的用途，但按名称认为相同。
这样 set 就不能包含同名的多个实例，但比较仍然有效。

这样的定义可能有什么问题？

用Value定义__eq__、__lt__等的原因是为了能够按Value对实例进行排序，并能够使用像max这样的函数.例如，he class 应该表示设备（比如加热元件）的物理输出。这些输出中的每一个都有唯一的名称。该值是输出设备的功率。要找到要打开的加热元件的最佳组合，能够按功率（值）比较它们是很有用的。然而，在一个集合或字典中，不应该有多个具有相同名称的输出。当然，不同名称的不同输出可能很容易具有相同的功率。

Answer 1

问题是它没有意义，散列用于对象的高效分桶。因此，当你有一个集合，它被实现为一个散列table，每个散列指向一个桶，通常是一个元素列表。为了检查某个元素是否在集合（或其他基于散列的容器）中，您转到散列指向的存储桶，然后遍历列表中的所有元素，将它们一一比较。

换句话说 - 散列不应该是一个比较器（它可以，并且有时应该给你一个误报）。特别是，在您的示例中，您的集合将不起作用 - 它不会识别重复项，因为它们不会相互比较。

class Foo:

    def __eq__(self,other):
        return self.Value==other.Value

    def __hash__(self):
        return id(self.Name)


a = set()
el = Foo()
el.Name = 'x'
el.Value = 1

el2 = Foo()
el2.Name = 'x'
el2.Value = 2

a.add(el)
a.add(el2)
print len(a) # should be 1, right? Well it is 2

实际上更糟糕的是，如果您有 2 个具有相同值但名称不同的对象，它们也不会被识别为相同

class Foo:

    def __eq__(self,other):
        return self.Value==other.Value

    def __hash__(self):
        return id(self.Name)


a = set()
el = Foo()
el.Name = 'x'
el.Value = 2

el2 = Foo()
el2.Name = 'a'
el2.Value = 2

a.add(el)
a.add(el2)
print len(a) # should be 1, right? Well it is 2 again

正确执行（因此，"if a == b, then hash(a) == hash(b)"）给出：

class Foo:

    def __eq__(self,other):
        return self.Name==other.Name

    def __hash__(self):
        return id(self.Name)


a = set()
el = Foo()
el.Name = 'x'
el.Value = 1

el2 = Foo()
el2.Name = 'x'
el2.Value = 2

a.add(el)
a.add(el2)
print len(a) # is really 1

更新

还有一个非确定性的部分，很难轻易复现，但本质上hash并没有唯一定义一个bucket。通常是这样

bucket_id = hash(object) % size_of_allocated_memory

因此，具有不同哈希值的事物仍然可以在同一个桶中结束。因此，即使名称不同，由于值相等，您可以获得两个相等的元素（集合内部），反之亦然，这取决于实际的内部实现、内存限制等。

一般来说，还有很多可能出错的例子，因为散列被定义作为函数 h : X -> Z 使得 x == y => h(x) == h(y)，因此人们实施他们的容器、授权协议和其他工具可以免费假设这个属性。如果你破坏它——每一个使用散列的工具都可能破坏。此外，它可能会及时中断，这意味着您更新了一些库并且您的代码将停止工作，因为对基础库的有效更新（使用上述假设）可能会导致利用您的违反这个假设。

更新 2

最后，为了解决您的问题 - 您根本不应该定义 eq、lt 运算符来处理排序。它是关于元素的实际比较，这应该与其余行为兼容。您所要做的就是定义一个单独的 comparator 并在您的排序例程中使用它（python 中的排序接受任何比较器，您不需要依赖 <, > 等.).另一种方法是在值上定义有效的 <、>、=，但为了保持名称的唯一性——保持一个集合……嗯……名称，而不是对象本身。无论您选择哪条路径 - 这里的关键要素是： 相等性和散列必须兼容，仅此而已。

Answer 2

可以像这样实现您的class，不会有任何问题。但是，您必须 100% 确定不会有两个不同的对象产生相同的哈希值。考虑以下示例：

class Foo:
    def __init__(self, name, value):
        self.name= name
        self.value= value

    def __eq__(self, other):
        return self.value == other.value

    def __hash__(self):
        return hash(self.name[0])

s= set()
s.add(Foo('a', 1))
s.add(Foo('b', 1))
print(len(s)) # output: 2

但是如果发生哈希冲突，你就会遇到问题：

s.add(Foo('abc', 1))
print(len(s)) # output: 2

为了防止这种情况，您必须确切地知道散列是如何生成的（如果您依赖 id 或 hash，可能因实现而异！）以及用于生成散列的属性值（本例中为 name）。这就是为什么排除哈希冲突的可能性非常困难，如果不是不可能的话。这基本上就像乞求意想不到的事情发生。

对于比较相同的类是否真的有必要散列相同的值？

Is it really necessary to hash the same for classes that compare the same?

python

class

hash

equivalence

更新

更新 2

对于比较相同的 类 是否真的有必要散列相同的值？

Is it really necessary to hash the same for classes that compare the same?

python

class

hash

equivalence

更新

更新 2

对于比较相同的类是否真的有必要散列相同的值？