Co się stanie, jeśli zmieni się obiekt __hash__?

Question

W Pythonie wiem, że wartość __hash__ zwracana dla danego obiektu ma być taka sama dla okresu istnienia tego obiektu. Ale z ciekawości, co się stanie, jeśli tak nie jest? Jakie spustoszenie mogłoby to spowodować?

class BadIdea(object): 
    def __hash__(self): 
    return random.randint(0, 10000) 

wiem __contains__ i __getitem__ będzie zachowywać się dziwnie, a dicts i zestawy będzie działać dziwne z tego powodu. Możesz także skończyć z "osieroconymi" wartościami w dykcie/zestawie.

Co jeszcze może się wydarzyć? Czy może to spowodować awarię tłumacza lub zepsucie wewnętrznych struktur?

Answer 1

Twoim głównym problemem byłaby dyktatura i zestawy. Jeśli wstawisz obiekt do dyktatury/zestawu i zmiany hasza tego obiektu, wtedy, gdy spróbujesz pobrać ten obiekt, skończysz szukać w innym miejscu w podstawowej tablicy dict/set, a tym samym nie znajdziesz obiekt. Właśnie dlatego klucze dyktowania zawsze powinny być niezmienne.

Oto mały przykład: powiedzmy, że stawiamy o w dict i o „s początkowy hash to 3. Chcemy zrobić coś takiego (nieznaczne uproszczenie ale dostaje punkt w poprzek):

 
Hash table: 

    0 1 2 3 4 5 6 7 
+---+---+---+---+---+---+---+---+ 
| | | | o | | | | | 
+---+---+---+---+---+---+---+---+ 
      ^
       we put o here, since it hashed to 3 

Teraz powiedzmy hash z o zmian na 6. Jeśli chcemy odzyskać o z dyktatu, przyjrzymy się miejscu 6, ale nic tam nie ma! Spowoduje to fałszywy wynik negatywny podczas sprawdzania struktury danych. W rzeczywistości, każdy element powyższej tablicy może mieć "wartość" związaną z tym w przypadku dyktowania, a w jednym miejscu może być wiele elementów (na przykład hash collision). Ponadto, zwykle decydujemy o wartości modulo wartości tablicy przy podejmowaniu decyzji, gdzie umieścić element. Niezależnie od tych wszystkich szczegółów, powyższy przykład nadal dokładnie przekazuje, co może pójść nie tak, gdy zmienia się kod skrótu obiektu.

Czy może to spowodować awarię tłumacza lub uszkodzenie struktur wewnętrznych?

Nie, to się nie stanie. Kiedy mówimy, że zmiana hash obiektu jest "niebezpieczna", mamy na myśli niebezpieczną w tym sensie, że w zasadzie pokonuje ona cel hashowania i czyni kod trudnym, jeśli nie niemożliwym do uzasadnienia. Nie mówimy o niebezpieczeństwie w tym sensie, że może powodować awarie.

Answer 2

Istnieje świetny wpis na Github na ten temat: What happens when you mess with hashing. Po pierwsze, trzeba wiedzieć, że Python oczekuje (cytat z artykułu):

• Haszysz obiektu nie zmienia się po drugiej stronie życia obiektu (innymi słowy, hashable obiekt powinien być niezmienny).

• a == b implikuje hash(a) == hash(b) (należy pamiętać, że odwrotny może nie być w przypadku kolizji mieszania).

Oto przykład kodu, który pokazuje problem mieszania wariantu, z nieco innym przykładzie klasy, ale idea pozostaje ta sama:

>>> class Bad(object): 
...  def __init__(self, arg): 
...   self.arg = arg 
...  def __hash__(self): 
...   return hash(self.arg) 
... 
>>> Bad(1) 
<__main__.Bad object at ...> 
>>> hash(Bad(1)) 
1 
>>> a = Bad(1) 
>>> b = {a:1} 
>>> a.arg = 2 
>>> hash(a) 
2 
>>> b[a] 
Traceback (most recent call last): 
... 
KeyError: <__main__.Bad object at ...> 

Tutaj niejawnie zmienił hash a poprzez mutację argumentu używanego do obliczenia skrótu. W rezultacie obiekt nie znajduje się już w słowniku, który używa hasza do znalezienia obiektu.

Zauważ, że Python nie przeszkadza mi w zrobieniu tego. Mogę to zrobić, jeśli chcę, podnosząc __setattr__ podnosząc AttributeError, ale nawet wtedy mógłbym zmienić go siłą, modyfikując obiekt __dict__. To właśnie ma na myśli, gdy mówimy, że Python jest językiem "dorosłych wyrażających zgodę".

To nie uczyni Pythona katastrofę ale nieoczekiwane zachowanie stanie się z dict/zestaw, a wszystko w oparciu o obiektu hash.