Co robi hash w Pythonie?

TL;DR:

Proszę zapoznać się ze słowniczkiem : hash() jest używany jako skrót do porównywania obiektów, obiekt jest uważany za hashable, jeśli można go porównać z innymi obiektami. dlatego używamy hash(). Jest również używany do dostępu do elementów dict i set, które są zaimplementowane jako tabele hash o rozmiarze w CPython.

Względy techniczne

• zazwyczaj porównywanie obiektów (które mogą obejmować kilka poziomów rekurencji) jest drogie.
• najlepiej, aby funkcja hash() była 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 jak słowniki są implementowane , używają tabel skrótów, co oznacza, że wyprowadzenie klucza z obiektu jest kamieniem węgielnym do pobierania obiektów w słownikach w O(1). To jednak bardzo zależy od funkcji hash, aby być odporne na kolizje . najgorszy przypadek uzyskania elementu w słowniku jest w rzeczywistości O(n).

Z tego względu, mutowalne obiekty zazwyczaj nie są hashowalne. Właściwość hashable oznacza, że możesz użyć obiektu jako klucza. Jeśli wartość skrótu zostanie użyta jako klucz i zawartość tego samego obiektu ulegnie zmianie, to co powinna zwrócić funkcja skrótu? To ten sam klucz czy inny? To zależy od tego, jak zdefiniujesz swoją funkcję haszującą.

Nauka przez przykład:

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 SSN nigdy nie zmienia się dla jednostki (nawet nie wiem, gdzie właściwie zweryfikować ten fakt z autorytatywnego źródła).

I mamy Boba:

>>> bob = Person('bob', '1111-222-333', None)

Bob idzie do sędziego, aby zmienić imię:

>>> jim = Person('jim bo', '1111-222-333', 'sf bay area')

Oto co wiemy:

>>> bob == jim
True

Ale są to dwa różne obiekty z inną przydzieloną pamięcią, Tak jak dwa różne rekordy tej samej osoby:

>>> bob is jim
False

Teraz pojawia się 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

>>> 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ład, pokazuję, że nawet przy kolizji, porównanie jest wykonywane, obiekty nie są już równe, co oznacza, że z powodzeniem podnosi KeyError.

Python docs for hash() państwo:

Wartości Hash są liczbami całkowitymi. Są one używane do szybkiego porównywania kluczy słownikowych podczas wyszukiwania słownika.

Słowniki Pythona są zaimplementowane jako tabele skrótów. Więc za każdym razem, gdy używasz słownika, hash() jest wywoływany na kluczach, które przekazujesz do przypisania lub wyszukiwania.

Dodatkowo, docs for the dict type state:

Wartości, które nie są , czyli wartości klucze zawierające listy, słowniki lub inne zmienne typy (które są porównywane według wartości, a nie według tożsamości obiektu) nie mogą być używane jako klucze.

Hash jest używany przez słowniki i zestawy do szybkiego wyszukania obiektu. Dobrym punktem wyjścia jest artykuł Wikipedii na tabele hash.