“object in list”和“object in dict”的行为不同吗？

Question

“object in list”和“object in dict”的行为不同吗？

12

我有一个包含一些对象的迭代器，并想创建一个唯一用户集合，其中每个用户仅列出一次。所以我试着用列表和字典来实现：

>>> for m in ms: print m.to_user  # let's first look what's inside ms
...
Pete Kramer
Pete Kramer
Pete Kramer
>>> 
>>> uniqueUsers = []  # Create an empty list
>>> for m in ms:
...     if m.to_user not in uniqueUsers:
...         uniqueUsers.append(m.to_user)
...
>>> uniqueUsers
[Pete Kramer]  # This is what I would expect
>>> 
>>> uniqueUsers = {}  # Now let's create a dict
>>> for m in ms:
...     if m.to_user not in uniqueUsers:
...         uniqueUsers[m.to_user] = 1
...
>>> uniqueUsers
{Pete Kramer: 1, Pete Kramer: 1, Pete Kramer: 1}

那么我通过将字典转换为列表来测试它，在执行if语句时这样做是有效的，而且它工作得正常：

>>> uniqueUsers = {}
>>> for m in ms:
...     if m.to_user not in list(uniqueUsers):
...         uniqueUsers[m.to_user] = 1
...
>>> uniqueUsers
{Pete Kramer: 1}

我可以通过测试 uniqueUsers.keys() 来获得类似的结果。

问题是我不理解为什么会出现这种差异。我一直认为如果你执行if object in dict，它只是创建一个字典键的列表并对其进行测试，但显然情况并非如此。

有人能解释一下object in dict内部工作原理，并解释为什么它的行为与object in list不同（正如我所期望的那样）吗？

- kramer65

2

@vaultah 必须这样做（否则您将收到一个不可哈希的 TypeError），但实现可能与 __eq__ 的实现不一致。 - poke

你是如何实现 to_user 和主类的？Python 字典不会保留重复对象，因为它们具有相同的 __hash__ 值，但如果您从一个类创建多个实例，每次都会得到一个具有不同哈希值的新对象（由于它们具有相同的表示），但是在字典中的结果不会是表示，因为它们是相同的字符串，因此具有相同的哈希值。 - Mazdak

@aneroid OP的代码表明存在自定义的__eq__实现。这意味着如果没有实现，__hash__将返回None，使对象无法哈希化。 - poke

@poke 明白了，确实需要提醒一下。但这并不是一个错误，对吧？因此他看到了奇怪的行为。（我只是想指出从您的评论中可以得知，没有__hash__不会引发错误。）我假设你是在用Python2。 - aneroid

@aneroid 它不会抛出错误（因为有一个继承的实现），但是那个实现很可能与重写的 __eq__ 的实现不一致；所以这部分仍然是正确的。请注意，我的评论是回复另一个评论的，该评论说没有 __hash__ 实现。 - poke

显示剩余3条评论

2个回答

8

TL;DR：对于列表，in测试调用__eq__。对于字典，它首先调用__hash__，如果哈希匹配，则调用__eq__。

in测试仅为列表调用__eq__。
- 没有__eq__，比较结果始终为False。
对于字典，您需要正确实现__hash__和__eq__才能正确比较其中的对象：
- 首先从__hash__获取对象的哈希值
  - 如果没有__hash__，则对于新式类，它使用id()，它对于所有创建的对象都是唯一的，因此除非是相同的对象，否则永远不会匹配现有对象。
  - 正如@poke在评论中指出的那样：
    
    在Python 2中，新式类（继承自object）继承了object的__hash__实现，该实现基于id()，因此就是这里的原因。
- 如果哈希匹配，然后使用other调用该对象的__eq__。
  - 结果取决于__eq__返回的内容。
- 如果哈希值不匹配，则不会调用__eq__。

因此，in测试对于列表和字典都会调用__eq__...但是对于字典，只有在__hash__返回匹配的哈希值之后才会调用__eq__。 没有__hash__不会返回None，不会抛出错误，并且不会使其“不可哈希”。...在Python 2中。要正确使用您的to_user类作为字典键，您确实需要具有正确实现、与__eq__同步的__hash__方法。

详情：

“object in list” 检查 m.to_user not in uniqueUsers 工作正常，这是因为你可能实现了一个__eq__方法，正如@poke所指出的那样。（并且似乎to_user返回的是一个对象，而不是一个字符串。）

相同的检查对于“object in dict”也不起作用，因为：
（a）该类中的__hash__实现不良，如@poke所指出的。
（b）或者您根本没有实现__hash__。这在Python2新式类中不会引发错误。

使用此答案中的类作为起点：

>>> class Test2(object):
...     def __init__(self, name):
...         self.name = name
...
...     def __eq__(self, other):
...         return self.name == other.name
...
>>> test_Dict = {}
>>> test_List = []
>>>
>>> obj1 = Test2('a')
>>> obj2 = Test2('a')
>>>
>>> test_Dict[obj1] = 'x'
>>> test_Dict[obj2] = 'y'
>>>
>>> test_List.append(obj1)
>>> test_List.append(obj2)
>>>
>>> test_Dict
{<__main__.Test2 object at 0x0000000002EFC518>: 'x', <__main__.Test2 object at 0x0000000002EFC940>: 'y'}
>>> test_List
[<__main__.Test2 object at 0x0000000002EFC518>, <__main__.Test2 object at 0x0000000002EFC940>]
>>>
>>> Test2('a') in test_Dict
False
>>> Test2('a') in test_List
True

- aneroid

2

你的 tl;dr 有一个小错误：确实会调用 __eq__ 来查找字典中的元素，但只有在计算对象的哈希值并找到哈希匹配后才会这样做。 - poke

有疑问。而且，如果未定义__eq__但已定义__hash__，则字典的in测试仍会失败。它需要两者都有。当然，列表只使用__eq__，因此如果没有它，它总是为假。 - aneroid

是的，在字典中哈希值仅用作第一步，以查找元素在哈希表中的位置。字典仍将对所有找到的元素使用相等性检查来确保它们是否相等。如果没有被覆盖，__eq__ 将退回到一个身份检查。 - poke

编写了一些测试类来展示不同的组合。我将发布一个pastebin链接，而不是非常长的代码。 - aneroid

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- poke · Accepted Answer

为了理解正在发生的事情，您需要了解in操作符和成员测试在不同类型中的行为。

对于列表来说，这相当简单，因为列表的本质是有序数组，不关心重复项。在这里执行成员测试的唯一可能方式是迭代列表并检查每个项目的相等性。像这样：

# x in lst
for item in lst:
    if x == item:
        return True
return False

字典有些不同：它们是哈希表，其中键（keys）应该是唯一的。哈希表要求键（keys）是可哈希的，这基本上意味着需要有一个明确的函数将对象转换为整数。然后使用此哈希值将键/值映射放置在哈希表中的某个地方。

由于哈希值确定了项在哈希表中的位置，因此具有相同意义的对象必须产生相同的哈希值。因此以下含义必须为真：x == y => hash(x) == hash(y)。反之则不需要成立；不同的对象产生相同的哈希值是完全有效的。

当对字典进行成员资格测试时，字典会首先查找哈希值。如果找到它，那么它将对找到的所有项执行相等性检查；如果没有找到哈希值，则假定它是一个不同的对象：

# x in dct
h = hash(x)
items = getItemsForHash(dct, h)
for item in items:
    if x == item:
        return True
# items is empty, or no match inside the loop
return False

由于在使用成员测试时，针对列表可以得到所需的结果，这意味着您的对象正确实现了等式比较（__eq__）。但是，由于在使用字典时未获得正确结果，这表明 __hash__ 实现与等式比较实现不同步：

>>> class SomeType:
        def __init__ (self, x):
            self.x = x
        def __eq__ (self, other):
            return self.x == other.x
        def __hash__ (self):
            # bad hash implementation
            return hash(id(self))

>>> l = [SomeType(1)]
>>> d = { SomeType(1): 'x' }
>>> x = SomeType(1)
>>> x in l
True
>>> x in d
False

请注意，对于Python 2中的新式类（继承自的类），这个“糟糕的哈希实现”（基于对象的id）是默认的。因此，当您没有实现自己的__hash__函数时，它仍然会使用那个默认的实现。这最终意味着，除非您的__eq__只执行标识检查（默认情况下），否则哈希函数将不同步。

因此，解决方案是以与__eq__使用的规则相一致的方式实现__hash__。例如，如果要比较两个成员self.x和self.y，则应该在这两个成员上使用复合哈希。最简单的方法是返回这些值的元组的哈希值:

class SomeType (object):
    def __init__ (self, x, y):
        self.x = x
        self.y = y

    def __eq__ (self, other):
        return self.x == other.x and self.y == other.y

    def __hash__ (self):
        return hash((self.x, self.y))

请注意，如果一个对象是可变的，则不应将其变成可哈希对象：

如果一个类定义了可变对象并实现了__eq__()方法，则不应该实现__hash__()，因为哈希集合的实现要求键的哈希值是不可变的（如果对象的哈希值发生变化，则会在错误的哈希桶中）。