`đối tượng trong danh sách` hoạt động khác với` đối tượng trong dict`?

Question

Tôi đã có một trình lặp với một số đối tượng trong đó và tôi muốn tạo một bộ sưu tập những người dùng duy nhất mà tôi chỉ liệt kê mọi người dùng một lần. Vì vậy, chơi xung quanh một chút tôi đã thử nó với cả một danh sách và một dict:

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

Vì vậy, tôi đã kiểm tra nó bằng cách chuyển đổi các dict vào một danh sách khi thực hiện câu lệnh if, và làm việc như tôi mong chờ nó:

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

và tôi có thể có được một kết quả tương tự bằng cách kiểm tra chống uniqueUsers.keys().

Điều này là tôi không hiểu tại sao sự khác biệt này xảy ra. Tôi luôn luôn nghĩ rằng nếu bạn làm if object in dict, nó chỉ đơn giản là tạo ra một danh sách các phím dicts và kiểm tra một lần nữa đó, nhưng đó rõ ràng không phải là trường hợp.

Ai có thể giải thích cách object in dict nội bộ hoạt động và tại sao nó không hoạt động tương tự như object in list (như tôi mong đợi)?

Answer 1

Để hiểu điều gì đang diễn ra, bạn phải hiểu cách nhà điều hành in, membership test hoạt động với các loại khác nhau.

Đối với danh sách, điều này khá đơn giản do danh sách cơ bản là: Các mảng được sắp xếp không quan tâm đến các bản sao. Cách duy nhất có thể để tạo thành một thử nghiệm thành viên ở đây là để lặp qua danh sách và kiểm tra mọi mục trên bình đẳng. Một cái gì đó như thế này:

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

Từ điển có một chút khác biệt: Chúng là các bảng băm là khóa có nghĩa là duy nhất. Bảng băm yêu cầu các khóa phải là hashable, về cơ bản có nghĩa là cần phải có một hàm rõ ràng để chuyển đổi đối tượng thành một số nguyên. Giá trị băm này sau đó được sử dụng để đặt ánh xạ khóa/giá trị vào đâu đó trong bảng băm.

Vì giá trị băm xác định vị trí trong bảng băm mà một mục được đặt, điều quan trọng là các đối tượng được tạo giống hệt nhau sẽ tạo ra giá trị băm giống nhau. Vì vậy, hàm ý sau đây phải đúng: x == y => hash(x) == hash(y). Ngược lại không cần phải đúng; hoàn toàn hợp lệ để có các đối tượng khác nhau tạo ra cùng một giá trị băm.

Khi kiểm tra thành viên trên từ điển được thực hiện, từ điển trước tiên sẽ tìm giá trị băm. Nếu nó có thể tìm thấy nó, sau đó nó sẽ thực hiện một kiểm tra bình đẳng trên tất cả các mục nó tìm thấy; nếu nó không tìm thấy giá trị băm, sau đó nó giả định rằng đó là một đối tượng khác nhau:

# 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 

Kể từ khi bạn nhận được kết quả mong muốn khi sử dụng một thử nghiệm thành viên chống lại một danh sách, đó có nghĩa là đối tượng của bạn thực hiện việc so sánh bình đẳng (__eq__) chính xác. Nhưng kể từ khi bạn không nhận được kết quả chính xác khi sử dụng một từ điển, có vẻ là một việc thực hiện __hash__ đó là không đồng bộ với việc thực hiện so sánh bình đẳng:

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

Lưu ý rằng đối với các lớp học kiểu mới bằng Python 2 (các lớp kế thừa từ object), "triển khai băm xấu" (dựa trên id đối tượng) là mặc định. Vì vậy, khi bạn không thực hiện chức năng của riêng bạn __hash__, nó vẫn sử dụng chức năng đó.Điều này cuối cùng có nghĩa là trừ khi __eq__ của bạn chỉ thực hiện kiểm tra nhận dạng (mặc định), hàm băm sẽ không đồng bộ.

Vì vậy, giải pháp là triển khai __hash__ theo cách nó phù hợp với các quy tắc được sử dụng trong __eq__. Ví dụ: nếu bạn so sánh hai thành viên self.x và self.y, thì bạn nên sử dụng hàm băm phức hợp trên hai thành viên đó. Cách dễ nhất để làm điều đó là để trả về giá trị hash của một tuple của những giá trị:

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

Lưu ý rằng bạn không nên thực hiện một hashable đối tượng nếu nó là có thể thay đổi:

Nếu một định nghĩa lớp đối tượng có thể thay đổi và triển khai phương thức __eq__(), không nên triển khai __hash__() do việc triển khai bộ sưu tập có thể băm yêu cầu giá trị băm của khóa không thay đổi (nếu giá trị băm của đối tượng thay đổi, nó sẽ nằm trong nhóm băm sai).

Answer 2

TL; DR: in cuộc gọi kiểm tra __eq__ cho danh sách. Đối với dicts, trước tiên nó gọi __hash__ và nếu băm phù hợp, sau đó gọi __eq__.

1. in chỉ kiểm tra cuộc gọi __eq__ cho danh sách.
   • Nếu không có một __eq__, so sánh in-Ness luôn là False.

2. Đối dicts, bạn cần có một thực hiện một cách chính xác __hash__và__eq__ để có thể so sánh các đối tượng trong nó đúng:

   • đầu tiên được băm của đối tượng từ __hash__

     • Nếu không có __hash__, đối với các lớp học theo phong cách mới, tôi t sử dụng id() là duy nhất cho tất cả các đối tượng được tạo và do đó không bao giờ khớp với một đối tượng hiện có trừ khi nó là cùng một đối tượng.
     • Và như @poke chỉ ra trong một chú thích:

       Trong Python 2, các lớp học kiểu mới (kế thừa từ object) thừa kế thực hiện __hash__ đối tượng mà là dựa trên id(), vì vậy đó là nơi mà đến từ đâu.

   • Nếu các trận đấu băm, sau đó __eq__ được gọi là cho rằng đối tượng với other.

     • Kết quả sau đó phụ thuộc vào số tiền trả về __eq__.
   • Nếu băm không trận đấu, sau đó __eq__ là không gọi.

Vì vậy, các thử nghiệm in gọi __eq__ cho các danh sách và cho dicts ... nhưng đối với dicts, chỉ sau khi __hash__ trả về một băm phù hợp. Và không có số __hash__ không trả lại None, không ném lỗi và không làm cho nó "không thể sửa chữa". ... trong Python 2. Để sử dụng lớp to_user chính xác của bạn làm khóa chính tả, bạn cần phải có một __hash__ method được triển khai chính xác, đồng bộ với __eq__.

chi tiết:

Vui lòng cung cho m.to_user not in uniqueUsers "đối tượng trong danh sách" làm việc một cách chính xác bởi vì bạn đã có thể thực hiện một phương pháp __eq__, như @poke chỉ ra. (Và nó xuất hiện to_user lợi nhuận một đối tượng, không phải là một chuỗi.)

Vui lòng cung cùng không làm việc cho "đối tượng trong dict" hoặc vì:
(a) __hash__ trong lớp đó được thực hiện tồi tệ, như @poke cũng chỉ ra.
(b) Hoặc bạn chưa triển khai __hash__. Điều này không gây ra lỗi trong Python2 các lớp kiểu mới.

Sử dụng the class in this answer như là một điểm khởi đầu:

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