`объект в списке` ведет себя отличным от` объекта в dict`?

Question

У меня есть итератор с некоторыми объектами в нем, и я хотел создать коллекцию uniqueUsers, в которой я только список каждого пользователя один раз. Так играть вокруг немного, я попробовал это как список и Словарь:

>>> 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} 

Так я проверил это путем преобразования Dict в список при выполнении, если заявления, и это работает, как я бы ожидать, что это:

>>> 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, он просто создает список ключей dicts и тесты снова, но это явно не так.

Может ли кто-нибудь объяснить, как работает object in dict и почему он не ведет себя так же, как object in list (как я ожидал бы этого)?

Answer 1

Для того, чтобы понять, что происходит, вы должны понимать, как работает оператор in, membership test, для разных типов.

Для списков это довольно просто из-за того, что в основном состоит из списков: упорядоченные массивы, которые не заботятся о дубликатах. Единственный возможный способ определить критерий членства здесь - перебрать список и проверить каждый элемент на равенстве. Что-то вроде этого:

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

Словари немного отличаются: они хэш-таблицы были ключи предназначены быть уникальным. Для таблиц хэш требуется, чтобы ключи были hashable, что по существу означает, что должна быть явная функция, которая преобразует объект в целое число. Это хеш-значение затем используется, чтобы поместить отображение ключа/значения где-то в хеш-таблицу.

Поскольку значение хеш определяет, где в хеш-таблице помещается элемент, важно, чтобы объекты, которые должны быть одинаковыми, производят одно и то же значение хэш-функции. Таким образом, следующее значение должно быть правдой: 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 (классы, которые наследуют от object), эта «неудачная хэш-реализация» (которая основана на идентификаторе объекта) является значением по умолчанию. Поэтому, когда вы не реализуете свою собственную функцию __hash__, она по-прежнему использует ее.Это в конечном итоге означает, что если ваш __eq__ выполняет проверку подлинности (по умолчанию), хеш-функция будет не синхронизирована.

Таким образом, решение заключается в реализации __hash__ таким образом, чтобы оно соответствовало правилам, используемым в __eq__. Например, если вы сравниваете двух членов 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)) 

Обратите внимание, что вы не должны делать объект hashable, если он изменчив:

Если класс определяет изменяемые объекты и реализует метод __eq__(), он не должен реализовывать __hash__(), так как для реализации коллекций хеширования требуется, чтобы хэш-значение ключа было неизменным (если значение хэша объекта изменяется, оно будет в неправильном хэш-ведре).

Answer 2

TL; DR: in тестовые вызовы __eq__ для списков. Для dicts он сначала вызывает __hash__, и если хеш совпадает, то вызывает __eq__.

1. in только для звонков __eq__ для списков.
   • Без __eq__, сравнение в-Несс всегда False.

2. Для dicts, необходимо правильно реализовать __hash__и__eq__, чтобы иметь возможность сравнивать объекты в нем правильно:

   • Первый получает хэш объекта от __hash__

     • Без __hash__, для классов нового стиля, i t использует id(), который уникален для всех созданных объектов и, следовательно, никогда не соответствует существующему, если только это не тот же объект.
     • И как @poke отметил в комментарии:

       В Python 2, новые классы стилей (наследуемых от object) наследуют __hash__ реализацию объекта, который основан на id(), так что это, где это приходит.

   • Если хэш спичек, затем__eq__ вызывается для объекта с other.

     • Результат затем зависит от того, что возвращает __eq__.
   • Если хэш не матч, то __eq__ является не называется.

Так тест in называет __eq__ для списков и для dicts ... но dicts, только после того, как __hash__ возвращает соответствующий хэш. И не имея __hash__ не возвращает None, не выдает ошибку и не делает ее «немойной». ... в Python 2. Чтобы правильно использовать свой класс to_user в качестве ключей dict, вам необходимо иметь __hash__ method, который был выполнен правильно, синхронизирован с __eq__.

Детали:

Проверка на m.to_user not in uniqueUsers «объект в списке» работали правильно, потому что вы, вероятно, осуществил __eq__ метод, так как @poke указал. (И это кажется to_user возвращает объект, а не строка.)

Такая же проверка не работает для «объекта в Словаре» либо потому, что:
(а) __hash__ в этом классе плохо реализован, так как @poke также указал.
(b) Или Вы еще не внедрили __hash__. Это не вызывает ошибки в классах нового стиля Python2.

Использование the class in this answer в качестве отправной точки:

>>> 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