Cosa succede quando si chiama `if digit in dict`

Question

Ho una classe (chiamiamola myClass) che implementa sia __hash__ e __eq__. Ho anche un dict che mappa gli oggetti myClass con un certo valore, calcolo che richiede del tempo.

Nel corso del mio programma, molti (nell'ordine di milioni) myClass oggetti sono istanziati. Questo è il motivo per cui utilizzo lo dict per tenere traccia di questi valori.

Tuttavia, a volte un nuovo oggetto myClass potrebbe essere equivalente a uno più vecchio (come definito dal metodo __eq__). Quindi, piuttosto che calcolare nuovamente il valore per quell'oggetto, preferirei semplicemente cercare il valore dell'oggetto myClass precedente nello dict. Per fare questo, lo faccio if myNewMyClassObj in dict.

ecco la mia domanda:

Quando uso che in clausola, ciò che viene chiamato, __hash__ o __eq__? Il punto di utilizzo di un dict è che è O (1) tempo di ricerca. Quindi è necessario chiamare __hash__. Ma cosa succede se __hash__ e __eq__ non sono metodi equivalenti? In tal caso, riceverò un falso positivo per if myNewMyClassObj in dict?

Follow up domanda:

voglio ridurre al minimo il numero di voci nella mia dict, quindi vorrei idealmente come mantenere solo uno di una serie di equivalenti myClass oggetti nel dict. Così ancora una volta, sembra che __eq__ deve essere chiamato nel calcolo if myNewClassObj in dict, che contaminano l'O dict s'(1) Occhiata tempo per un O (n) Occhiata tempo

Answer 1

Prima viene chiamato __hash__(myNewMyClassObj). Se nel dizionario non si trova nessun oggetto con lo stesso hash, Python assume che myNewMyClassObj non sia nel dizionario. (Si noti che Python richiede che ogni volta __eq__ valutata come uguale per due oggetti, la loro __hash__ devono essere identici.)

Se alcuni oggetti con lo stesso __hash__ si trovano nel dizionario, __eq__ viene chiamato su ciascuno di essi. Se __eq__ viene valutato come uguale per nessuno di essi, myNewMyClassObj in dict_ restituisce True.

Pertanto, è sufficiente assicurarsi che sia __eq__ sia __hash__ siano veloci.

Alla domanda di follow-up: sì, dict_ memorizza solo uno di un set di oggetti equivalenti MyClass (come definito da __eq__). (Come impostato.)

Si noti che __eq__ viene richiamato solo sugli oggetti con lo stesso hash e assegnati allo stesso bucket. Il numero di tali oggetti è in genere un numero molto piccolo (l'implementazione di dict ne garantisce l'integrità). Quindi hai ancora (approssimativamente) prestazioni di ricerca O(1).

Answer 2

__hash__ sarà sempre chiamata; __eq__ verrà chiamato se l'oggetto è effettivamente nel dizionario o se un altro oggetto con lo stesso hash si trova nel dizionario. Il valore di hash viene utilizzato per restringere la scelta delle chiavi possibili. Le chiavi sono raggruppate in "bucket" per valore di hash, ma per la ricerca Python deve ancora controllare ogni chiave nel bucket per uguaglianza con la chiave di ricerca. Vedi http://wiki.python.org/moin/DictionaryKeys. Guarda questi esempi:

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

In questo esempio, è possibile vedere __hash__ è sempre chiamato. __eq__ viene chiamato una volta per ogni ricerca quando l'oggetto è nel dict, poiché hanno tutti valori hash distinti, quindi un controllo di uguaglianza è sufficiente per verificare che l'oggetto con quel valore hash sia effettivamente quello interrogato. __eq__ non viene chiamato nell'ultimo caso, perché nessuno degli oggetti nel dict ha lo stesso valore hash di Foo(4), quindi Python non deve continuare con __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 

In questa versione, tutti gli oggetti hanno lo stesso valore di hash. In questo caso viene sempre chiamato, a volte più volte, __eq__ perché l'hash non fa distinzione tra i valori, quindi Python ha bisogno di controllare esplicitamente l'uguaglianza su tutti i valori nel dict finché non trova uno uguale (o trova che nessuno di loro è uguale quello che sta cercando). A volte lo trova al primo tentativo (Foo(1) in dict sopra), a volte deve controllare tutti i valori.

Answer 3

__hash__ definisce il bucket in cui viene inserito l'oggetto, __eq__ viene chiamato solo quando gli oggetti si trovano nello stesso bucket.