1

__hash__ 和 __eq__ 如何用于集合中的标识？例如一些应该有助于解决一些多米诺骨牌难题的代码：

class foo(object):
    def __init__(self, one, two):
        self.one = one
        self.two = two
    def __eq__(self,other):
        if (self.one == other.one) and (self.two == other.two): return True
        if (self.two == other.one) and (self.one == other.two): return True
        return False
    def __hash__(self):
        return hash(self.one + self.two)

s = set()

for i in range(7):
    for j in range(7):
        s.add(foo(i,j))
len(s) // returns 28 Why?

如果我只使用 __eq__() len(s) 等于 49。没关系，因为据我了解对象（例如 1-2 和 2-1）不一样，但代表相同的多米诺骨牌。所以我添加了哈希函数。
现在它按我想要的方式工作，但我不明白一件事：1-3 和 2-2 的哈希值应该相同，因此它们应该算作相同的对象并且不应该添加到集合中。但他们做到了！我卡住了。

4

5 回答 5

4

用于 dict/set 目的的平等取决于__eq__. 但是，要求比较相等的对象具有相同的哈希值，这就是您需要__hash__. 请参阅此问题以进行一些类似的讨论。

哈希本身并不能确定两个对象在字典中是否相同。散列就像一条“捷径”，只能以一种方式起作用：如果两个对象具有不同的散列，则它们肯定不相等；但如果它们具有相同的哈希值，它们仍然可能不相等。

在您的示例中，您定义__hash__并__eq__做不同的事情。哈希仅取决于多米诺骨牌上数字的总和，但相等性取决于两个单独的数字（按顺序）。这是合法的，因为相同的多米诺骨牌仍然具有相同的哈希值。然而，就像我上面所说的，这并不意味着等和多米诺骨牌会被认为是平等的。一些不相​​等的多米诺骨牌仍然具有相等的哈希值。但是相等仍然由 决定__eq__，并且__eq__仍然按顺序查看这两个数字，这就是决定它们是否相等的原因。

在我看来，在您的情况下，适当的做法是定义两者__hash__并__eq__依赖于有序对——也就是说，首先比较两个数字中较大的一个，然后比较较小的一个。这意味着 2-1 和 1-2 将被视为相同。

于 2013-01-16T06:35:29.337 回答
2

哈希只是帮助 Python 排列对象的提示。当foo在集合中查找某个对象时，它仍然需要检查集合中的每个对象，其哈希值与foo.

这就像为字母表中的每个字母准备一个书架。假设您想将一本新书添加到您的收藏中，前提是您还没有它的副本；你会先去书架上找合适的信。但是你必须查看书架上的每一本书，并将其与你手中的那本书进行比较，看看它是否相同。你不会因为书架上已经有东西就丢弃这本新书。

如果您想使用其他值来过滤掉“重复项”，请使用 dict 将多米诺骨牌的总值映射到您看到的第一张多米诺骨牌。不要颠覆 Python 内置的行为来表示完全不同的东西。（正如您所发现的，无论如何，它在这种情况下不起作用。）

于 2013-01-16T06:34:36.853 回答
1

哈希函数的要求是，如果x == y对于两个值，则hash(x) == hash(y). 反过来不一定是真的。

通过考虑字符串的散列，您可以很容易地了解为什么会出现这种情况。假设它hash(str)返回一个 32 位数字，并且我们正在散列长度超过 4 个字符的字符串（即包含超过 32 位）。可能的字符串比可能的哈希值多，所以一些不相等的字符串必须共享相同的哈希（这是鸽子原理的一个应用）。

Python 集被实现为哈希表。当检查一个对象是否是集合的成员时，它会调用它的哈希函数并使用结果来挑选一个桶，然后使用相等运算符来查看它是否匹配桶中的任何项目。

在您的实施中，2-2 和 1-3 多米诺骨牌将最终出现在哈希桶中，但它们的比较并不相等。因此，两者都可以添加到集合中。

于 2013-01-16T08:00:34.783 回答
0

您可以在 Python数据模型文档中了解这一点，但简短的回答是您可以将哈希函数重写为：

def __hash__(self):
    return hash(tuple(sorted((self.one, self.two))))
于 2013-01-16T06:34:07.990 回答
0

我喜欢 Eevee 提供的答案的声音，但我很难想象一个实现。这是我对Eevee提供的答案的解释、解释和实现。

  • 使用两个多米诺骨牌值的总和作为字典键。
  • 将任一 domino 值存储为字典值。

例如，给定多米诺骨牌“12”，总和为 3，因此字典键将为 3。然后我们可以选择任一值（1 或 2）存储在该位置（我们将选择第一个值 1 ）。

domino_pairs = {}
pair = '12'
pair_key = sum(map(int, pair))
domino_pairs[pair_key] = int(pair[0]) # Store the first pair's first value.
print domino_pairs

输出：

{3: '1'}

虽然我们只存储了多米诺骨牌对中的一个值，但另一个值可以很容易地从字典键和值中计算出来：

pair = '12'
pair_key = sum(map(int, pair))
domino_pairs[pair_key] = int(pair[0]) # Store the first pair's first value.
# Retrieve pair from dictionary.
print pair_key - domino_pairs[pair_key] # 3-1 = 2

输出：

2

但是，由于两个不同的对可能具有相同的总数，我们需要针对单个键存储多个值。因此，我们针对单个键存储值列表（即两对的总和）。把它放到一个函数中：

def add_pair(dct, pair):
  pair_key = sum(map(int, pair))
  if pair_key not in dct:
    dct[pair_key] = []
  dct[pair_key].append(int(pair[0]))

domino_pairs = {}
add_pair(domino_pairs, '22')
add_pair(domino_pairs, '04')
print domino_pairs

输出：

{4: [2, 0]}

这是有道理的。两对总和为 4，但每对中的第一个值不同，因此我们存储两者。到目前为止的实现将允许重复：

domino_pairs = {}
add_pair(domino_pairs, '40')
add_pair(domino_pairs, '04')
print domino_pairs

输出

   {4: [4, 0]}

'40' 和 '04' 在 Dominos 中是相同的，所以我们不需要同时存储两者。我们需要一种检查重复项的方法。为此，我们将定义一个新函数has_pair：

 def has_pair(dct, pair):
  pair_key = sum(map(int, pair))
  if pair_key not in dct:
    return False
  return (int(pair[0]) in dct[pair_key] or 
    int(pair[1]) in dct[pair_key])

像往常一样，我们得到总和（我们的字典键）。如果它不在字典中，则该对不存在。如果它在字典中，我们必须检查我们对中的任何一个值是否存在于字典“bucket”中。让我们将此检查插入add_pair，因此我们不会添加重复的多米诺骨牌对：

def add_pair(dct, pair):
  pair_key = sum(map(int, pair))
  if has_pair(dct, pair):
    return
  if pair_key not in dct:
    dct[pair_key] = []
  dct[pair_key].append(int(pair[0]))

现在添加重复的多米诺骨牌对可以正常工作：

domino_pairs = {}
add_pair(domino_pairs, '40')
add_pair(domino_pairs, '04')
print domino_pairs

输出：

{4: [4]}

最后，一个 print 函数展示了如何仅存储多米诺骨牌对的总和以及同一对中的单个值与存储对本身相同：

def print_pairs(dct):
  for total in dct:
    for a in dct[total]:
      a = int(a)
      b = int(total) - int(a)
      print '(%d, %d)'%(a,b)

测试：

domino_pairs = {}
add_pair(domino_pairs, '40')
add_pair(domino_pairs, '04')
add_pair(domino_pairs, '23')
add_pair(domino_pairs, '50')
print_pairs(domino_pairs)

输出：

(4, 0)
(2, 3)
(5, 0)
于 2016-03-12T14:00:35.267 回答