TL; DR:
Zapoznaj się ze słownikiem : hash()służy jako skrót do porównywania obiektów, obiekt jest uznawany za haszowalny, jeśli można go porównać z innymi obiektami. dlatego używamy hash(). Jest również używany do uzyskiwania dostępu dicti setelementów, które są implementowane jako tabele skrótów o zmiennym rozmiarze w CPythonie .
Uwagi techniczne
- zwykle porównywanie obiektów (które może obejmować kilka poziomów rekurencji) jest kosztowne.
- korzystnie
hash()funkcja jest o rząd wielkości (lub kilka) tańsza.
- porównywanie dwóch skrótów jest łatwiejsze niż porównywanie dwóch obiektów, tutaj znajduje się skrót.
Jeśli czytasz o implementacji słowników , używają one tablic mieszających, co oznacza, że wyprowadzenie klucza z obiektu jest kamieniem węgielnym do pobierania obiektów ze słowników w formacie O(1). Jest to jednak bardzo zależne od odporności funkcji skrótu na kolizje . W rzeczywistości najgorszym przypadkiem jest umieszczenie elementu w słowniku O(n).
W związku z tym zmienne obiekty zwykle nie podlegają hashowaniu. Właściwość hashable oznacza, że możesz użyć obiektu jako klucza. Jeśli wartość skrótu jest używana jako klucz, a zawartość tego samego obiektu ulegnie zmianie, to co powinna zwrócić funkcja skrótu? Czy to ten sam klucz czy inny? To zależy od tego, jak zdefiniujesz swoją funkcję skrótu.
Uczenie się na przykładzie:
Wyobraź sobie, że mamy tę klasę:
>>> class Person(object):
... def __init__(self, name, ssn, address):
... self.name = name
... self.ssn = ssn
... self.address = address
... def __hash__(self):
... return hash(self.ssn)
... def __eq__(self, other):
... return self.ssn == other.ssn
...
Uwaga: wszystko to opiera się na założeniu, że numer SSN nigdy nie zmienia się dla osoby (nawet nie wiem, gdzie faktycznie zweryfikować ten fakt z wiarygodnego źródła).
Mamy Boba:
>>> bob = Person('bob', '1111-222-333', None)
Bob idzie do sędziego, aby zmienić swoje imię:
>>> jim = Person('jim bo', '1111-222-333', 'sf bay area')
Oto, co wiemy:
>>> bob == jim
True
Ale to są dwa różne obiekty z różną alokacją pamięci, tak jak dwa różne rekordy tej samej osoby:
>>> bob is jim
False
Teraz przychodzi część, w której hash () jest przydatny:
>>> dmv_appointments = {}
>>> dmv_appointments[bob] = 'tomorrow'
Zgadnij co:
>>> dmv_appointments[jim]
'tomorrow'
Z dwóch różnych rekordów możesz uzyskać dostęp do tych samych informacji. Teraz spróbuj tego:
>>> dmv_appointments[hash(jim)]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 9, in __eq__
AttributeError: 'int' object has no attribute 'ssn'
>>> hash(jim) == hash(hash(jim))
True
Co się stało? To jest kolizja. Ponieważ przy hash(jim) == hash(hash(jim))okazji, które są obydwoma liczbami całkowitymi, musimy porównać dane wejściowe __getitem__ze wszystkimi zderzającymi się elementami. Wbudowany intnie ma ssnatrybutu, więc wyłącza się.
>>> del Person.__eq__
>>> dmv_appointments[bob]
'tomorrow'
>>> dmv_appointments[jim]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: <__main__.Person object at 0x7f611bd37110>
W tym ostatnim przykładzie pokazuję, że nawet przy kolizji następuje porównanie, obiekty nie są już równe, co oznacza, że pomyślnie podnosi KeyError.