Co robi hash w Pythonie?

Widziałem przykład kodu, w którym hashfunkcja jest stosowana do krotki. W rezultacie zwraca ujemną liczbę całkowitą. Zastanawiam się, do czego służy ta funkcja? Google nie pomaga. Znalazłem stronę, która wyjaśnia, w jaki sposób obliczany jest hash, ale nie wyjaśnia, dlaczego potrzebujemy tej funkcji.

Skrót to liczba całkowita o stałym rozmiarze, która identyfikuje określoną wartość . Każda wartość musi mieć swój własny hash, więc dla tej samej wartości otrzymasz ten sam hash, nawet jeśli nie jest to ten sam obiekt.

>>> hash("Look at me!")
4343814758193556824
>>> f = "Look at me!"
>>> hash(f)
4343814758193556824

Wartości skrótu należy tworzyć w taki sposób, aby wynikowe wartości były równomiernie rozłożone, aby zmniejszyć liczbę otrzymywanych kolizji. Kolizje skrótów występują, gdy dwie różne wartości mają ten sam skrót. Dlatego stosunkowo niewielkie zmiany często skutkują bardzo różnymi skrótami.

>>> hash("Look at me!!")
6941904779894686356

Liczby te są bardzo przydatne, ponieważ umożliwiają szybkie wyszukiwanie wartości w dużym zbiorze wartości. Dwa przykłady ich użycia to Python seti dict. W a list, jeśli chcesz sprawdzić, czy wartość znajduje się na liście, za pomocą if x in values:Python musi przejrzeć całą listę i porównać xz każdą wartością na liście values. Może to zająć dużo czasu list. W a set, Python śledzi każdy hash, a kiedy piszesz if x in values:, Python pobierze wartość skrótu dla x, wyszuka ją w wewnętrznej strukturze, a następnie porówna tylko xz wartościami, które mają taki sam skrót jak x.

Ta sama metodologia jest używana do wyszukiwania w słowniku. To sprawia, że ​​wyszukiwanie do wewnątrz seti jest dictbardzo szybkie, podczas gdy wyszukiwanie w listjest wolne. Oznacza to również, że możesz mieć obiekty niehashowalne w a list, ale nie w a setani jako klucze w a dict. Typowym przykładem obiektów, których nie można haszować, jest każdy obiekt, który jest zmienny, co oznacza, że ​​można zmienić jego wartość. Jeśli masz zmienny obiekt, nie powinien on być hashowany, ponieważ jego skrót zmieni się w czasie jego życia, co spowodowałoby wiele zamieszania, ponieważ obiekt może znaleźć się pod niewłaściwą wartością skrótu w słowniku.

Zauważ, że hash wartości musi być taki sam tylko dla jednego uruchomienia Pythona. W Pythonie 3.3 będą się one faktycznie zmieniać przy każdym nowym uruchomieniu Pythona:

$ /opt/python33/bin/python3
Python 3.3.2 (default, Jun 17 2013, 17:49:21) 
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash("foo")
1849024199686380661
>>> 
$ /opt/python33/bin/python3
Python 3.3.2 (default, Jun 17 2013, 17:49:21) 
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash("foo")
-7416743951976404299

Ma to na celu utrudnienie odgadnięcia, jaką wartość skrótu będzie miał dany ciąg, co jest ważną funkcją bezpieczeństwa w aplikacjach internetowych itp.

Dlatego wartości skrótu nie powinny być przechowywane na stałe. Jeśli chcesz używać wartości skrótu w sposób trwały, możesz przyjrzeć się bardziej "poważnym" typom skrótów , kryptograficznym funkcjom mieszania , które mogą być używane do tworzenia weryfikowalnych sum kontrolnych plików itp.

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.

Dokumentacja Pythona dotyczącahash() stanu:

Wartości skrótu są liczbami całkowitymi. Służą do szybkiego porównywania kluczy słownika podczas przeszukiwania słownika.

Słowniki Pythona są implementowane jako tabele skrótów. Za każdym razem, gdy korzystasz ze słownika,hash() wywoływane są klucze, które przekazujesz w celu przypisania lub wyszukania.

Ponadto w dokumentach dicttypu :

Wartości, które nie podlegają hashowaniu , to znaczy wartości 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 wyszukiwania obiektu. Dobrym punktem wyjścia jest artykuł Wikipedii na temat tabel skrótów .

Możesz użyć Dictionarytypu danych w Pythonie. Jest bardzo podobny do skrótu - i obsługuje również zagnieżdżanie, podobnie jak w przypadku zagnieżdżonego skrótu.

Przykład:

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}
dict['Age'] = 8; # update existing entry
dict['School'] = "DPS School" # Add new entry

print ("dict['Age']: ", dict['Age'])
print ("dict['School']: ", dict['School'])

Aby uzyskać więcej informacji, zapoznaj się z tym samouczkiem dotyczącym typu danych w słowniku .