Điều gì xảy ra khi bạn gọi 'nếu khóa trong dict`

Question

Tôi có một lớp (hãy gọi nó là myClass) thực hiện cả hai __hash__ và __eq__. Tôi cũng có một số dict ánh xạ đối tượng myClass đối với một số giá trị, tính toán mất một thời gian.

Trong quá trình chương trình của tôi, nhiều (theo thứ tự triệu) myClass đối tượng được khởi tạo. Đây là lý do tại sao tôi sử dụng dict để theo dõi các giá trị đó.

Tuy nhiên, đôi khi đối tượng myClass mới có thể tương đương với đối tượng cũ hơn (như được xác định theo phương pháp __eq__). Vì vậy, thay vì tính toán giá trị cho đối tượng đó một lần nữa, tôi chỉ muốn tra cứu giá trị của đối tượng cũ hơn myClass trong dict. Để thực hiện điều này, tôi làm if myNewMyClassObj in dict.

Dưới đây là câu hỏi của tôi:

Khi tôi sử dụng mà in khoản, những gì được gọi là, __hash__ hoặc __eq__? Điểm sử dụng dict là thời gian tra cứu O (1). Vì vậy, sau đó __hash__ phải được gọi. Nhưng nếu __hash__ và __eq__ không phải là phương pháp tương đương thì sao? Trong trường hợp đó, tôi có dương tính giả cho if myNewMyClassObj in dict không?

Theo dõi câu hỏi:

Tôi muốn giảm thiểu số lượng các mục trong dict của tôi, vì vậy tôi tưởng muốn giữ chỉ là một trong một bộ tương đương myClass đối tượng trong dict. Vì vậy, một lần nữa, có vẻ như __eq__ cần phải được gọi khi máy tính if myNewClassObj in dict, trong đó sẽ làm ô uế một O dict 's (1) tra cứu thời gian để một O (n) tra cứu thời gian

Answer 1

Đầu tiên, __hash__(myNewMyClassObj) được gọi. Nếu không tìm thấy đối tượng nào có cùng giá trị băm trong từ điển, Python giả định myNewMyClassObj không có trong từ điển. (Lưu ý rằng Python đòi hỏi bất cứ khi nào __eq__ đánh giá là bình đẳng cho hai đối tượng, __hash__ họ phải giống hệt nhau.)

Nếu một số đối tượng với cùng __hash__ được tìm thấy trong từ điển, __eq__ được kêu gọi mỗi người trong số họ. Nếu __eq__ đánh giá bằng nhau cho bất kỳ trường hợp nào, số myNewMyClassObj in dict_ trả về Đúng.

Do đó, bạn chỉ cần đảm bảo cả hai số điện thoại __eq__ và __hash__ đều nhanh.

Để câu hỏi tiếp theo của bạn: có, dict_ chỉ lưu trữ một trong số các đối tượng tương đương MyClass (như được xác định bởi __eq__). (Như được đặt.)

Lưu ý rằng __eq__ chỉ được gọi trên các đối tượng có cùng giá trị băm và được phân bổ cho cùng một nhóm. Số lượng các đối tượng như vậy thường là một số rất nhỏ (thực hiện dict đảm bảo rằng). Vì vậy, bạn vẫn có (khoảng) O(1) hiệu suất tra cứu.

Answer 2

__hash__ sẽ luôn luôn được gọi là; __eq__ sẽ được gọi nếu đối tượng thực sự nằm trong từ điển, hoặc nếu một đối tượng khác có cùng giá trị băm trong từ điển. Giá trị băm được sử dụng để thu hẹp lựa chọn các phím có thể. Các khóa được nhóm thành "nhóm" theo giá trị băm, nhưng để tra cứu Python vẫn phải kiểm tra từng khóa trong nhóm để lấy sự bình đẳng bằng khóa tra cứu. Xem http://wiki.python.org/moin/DictionaryKeys. Xem các ví dụ sau:

>>> class Foo(object): 
...  def __init__(self, x): 
...   self.x = x 
...  
...  def __hash__(self): 
...   print "Hash" 
...   return hash(self.x) 
... 
...  def __eq__(self, other): 
...   print "Eq" 
...   return self.x == other.x 
>>> Foo(1) in d 
Hash 
Eq 
10: True 
>>> Foo(2) in d 
Hash 
Eq 
11: True 
>>> Foo(3) in d 
Hash 
Eq 
12: True 
>>> Foo(4) in d 
Hash 
13: False 

Trong ví dụ này, bạn có thể thấy __hash__ luôn được gọi. __eq__ được gọi một lần cho mỗi lần tra cứu khi đối tượng nằm trong dict, bởi vì tất cả chúng đều có giá trị băm riêng biệt, vì vậy một kiểm tra bình đẳng là đủ để xác minh rằng đối tượng có giá trị băm đó thực sự là truy vấn. __eq__ không được gọi trong trường hợp cuối cùng, vì không có đối tượng nào trong dict có cùng giá trị băm như Foo(4), vì vậy, Python không cần phải tiếp tục với __eq__.

>>> class Foo(object): 
...  def __init__(self, x): 
...   self.x = x 
...  
...  def __hash__(self): 
...   print "Hash" 
...   return 1 
... 
...  def __eq__(self, other): 
...   print "Eq" 
...   return self.x == other.x 
>>> d = {Foo(1): 2, Foo(2): 3, Foo(3): 4} 
Hash 
Hash 
Eq 
Hash 
Eq 
Eq 
>>> Foo(1) in d 
Hash 
Eq 
18: True 
>>> Foo(2) in d 
Hash 
Eq 
Eq 
19: True 
>>> Foo(3) in d 
Hash 
Eq 
Eq 
Eq 
20: True 
>>> Foo(4) in d 
Hash 
Eq 
Eq 
Eq 
21: False 

Trong phiên bản này, tất cả các đối tượng đều có cùng giá trị băm. Trong trường hợp này, __eq__ luôn được gọi, đôi khi nhiều lần, vì hàm băm không phân biệt giữa các giá trị, vì vậy Python cần kiểm tra mức độ bình đẳng đối với tất cả các giá trị trong dict cho đến khi tìm thấy giá trị bằng nhau cái mà nó đang tìm kiếm). Đôi khi nó tìm thấy nó trên lần thử đầu tiên (Foo(1) in dict ở trên), đôi khi nó phải kiểm tra tất cả các giá trị.

Answer 3

__hash__ xác định nhóm đối tượng được đưa vào, __eq__ chỉ được gọi khi đối tượng nằm trong cùng một nhóm.