Was macht Hash in Python?

Ich habe ein Beispiel für Code gesehen, bei dem die hashFunktion auf ein Tupel angewendet wird. Infolgedessen wird eine negative Ganzzahl zurückgegeben. Ich frage mich, was macht diese Funktion? Google hilft nicht. Ich habe eine Seite gefunden, die erklärt, wie Hash berechnet wird, aber nicht erklärt, warum wir diese Funktion benötigen.

Ein Hash ist eine Ganzzahl fester Größe, die einen bestimmten Wert identifiziert . Jeder Wert muss einen eigenen Hash haben, sodass Sie für denselben Wert denselben Hash erhalten, auch wenn es sich nicht um dasselbe Objekt handelt.

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

Hash-Werte müssen so erstellt werden, dass die resultierenden Werte gleichmäßig verteilt sind, um die Anzahl der Hash-Kollisionen zu verringern. Hash-Kollisionen treten auf, wenn zwei verschiedene Werte denselben Hash haben. Daher führen relativ kleine Änderungen häufig zu sehr unterschiedlichen Hashes.

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

Diese Zahlen sind sehr nützlich, da sie eine schnelle Suche nach Werten in einer großen Sammlung von Werten ermöglichen. Zwei Beispiele für ihre Verwendung sind Pythons setund dict. In ein list, wenn Sie in der Liste , wenn ein Wert überprüfen wollen , ist, mit if x in values:, muss Python durch die ganze Liste gehen und vergleichen Sie xmit jedem Wert in der Liste values. Dies kann lange dauern list. In a verfolgt setPython jeden Hash, und wenn Sie eingeben if x in values:, erhält Python den Hash-Wert für x, sucht ihn in einer internen Struktur nach und vergleicht ihn dann nur xmit den Werten, die denselben Hash wie haben x.

Die gleiche Methode wird für die Suche nach Wörterbüchern verwendet. Dies macht Nachschlagen in setund dictsehr schnell, während Nachschlagen in listlangsam ist. Dies bedeutet auch, dass Sie nicht hashbare Objekte in a haben können list, aber nicht in a setoder als Schlüssel in a dict. Das typische Beispiel für nicht hashbare Objekte ist jedes Objekt, das veränderbar ist. Dies bedeutet, dass Sie seinen Wert ändern können. Wenn Sie ein veränderbares Objekt haben, sollte es nicht hashbar sein, da sich sein Hash im Laufe seiner Lebensdauer ändert, was viel Verwirrung stiften würde, da ein Objekt unter dem falschen Hashwert in einem Wörterbuch landen könnte.

Beachten Sie, dass der Hash eines Werts nur für einen Python-Lauf identisch sein muss. In Python 3.3 ändern sie sich tatsächlich für jeden neuen Lauf von Python:

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

Dies ist schwieriger zu erraten, welchen Hash-Wert eine bestimmte Zeichenfolge haben wird. Dies ist ein wichtiges Sicherheitsmerkmal für Webanwendungen usw.

Hash-Werte sollten daher nicht dauerhaft gespeichert werden. Wenn Sie Hash-Werte dauerhaft verwenden müssen, können Sie sich die "schwerwiegenderen" Arten von Hashes, kryptografischen Hash-Funktionen ansehen , mit denen überprüfbare Prüfsummen von Dateien usw. erstellt werden können.

TL; DR:

Bitte beziehen Glossar : hash()als Abkürzung verwendet , um Objekte zu vergleichen, wird ein Objekt als hashable wenn es zu anderen Objekten verglichen werden kann. Deshalb verwenden wir hash(). Es ist auch für den Zugriff auf dictund setElemente , die als implementiert sind resizable Hash - Tabellen in CPython .

Technische Überlegungen

• Normalerweise ist der Vergleich von Objekten (die mehrere Rekursionsstufen umfassen können) teuer.
• vorzugsweise ist die hash()Funktion eine Größenordnung (oder mehrere) weniger teuer.
• Das Vergleichen von zwei Hashes ist einfacher als das Vergleichen von zwei Objekten. Hier befindet sich die Verknüpfung.

Wenn Sie lesen, wie Wörterbücher implementiert werden , verwenden sie Hash-Tabellen. Das Ableiten eines Schlüssels von einem Objekt ist ein Eckpfeiler für das Abrufen von Objekten in Wörterbüchern in O(1). Dies hängt jedoch stark von Ihrer Hash-Funktion ab, um kollisionssicher zu sein . Der schlimmste Fall, um ein Element in ein Wörterbuch aufzunehmen, ist tatsächlich O(n).

In diesem Sinne sind veränderbare Objekte normalerweise nicht hashbar. Die Eigenschaft hashable bedeutet, dass Sie ein Objekt als Schlüssel verwenden können. Wenn der Hash-Wert als Schlüssel verwendet wird und sich der Inhalt desselben Objekts ändert, was sollte die Hash-Funktion dann zurückgeben? Ist es der gleiche oder ein anderer Schlüssel? Dies hängt davon ab, wie Sie Ihre Hash-Funktion definieren.

Mit gutem Beispiel lernen:

Stellen Sie sich vor, wir haben diese Klasse:

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

Bitte beachten Sie: Dies alles basiert auf der Annahme, dass sich die SSN für eine Person niemals ändert (Sie wissen nicht einmal, wo Sie diese Tatsache tatsächlich aus einer maßgeblichen Quelle überprüfen können).

Und wir haben Bob:

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

Bob geht zu einem Richter, um seinen Namen zu ändern:

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

Das wissen wir:

>>> bob == jim
True

Dies sind jedoch zwei verschiedene Objekte mit unterschiedlichem Speicher, genau wie zwei verschiedene Datensätze derselben Person:

>>> bob is jim
False

Jetzt kommt der Teil, in dem hash () praktisch ist:

>>> dmv_appointments = {}
>>> dmv_appointments[bob] = 'tomorrow'

Erraten Sie, was:

>>> dmv_appointments[jim] #?
'tomorrow'

Über zwei verschiedene Datensätze können Sie auf dieselben Informationen zugreifen. Versuchen Sie jetzt Folgendes:

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

Was ist gerade passiert? Das ist eine Kollision. Da hash(jim) == hash(hash(jim))es sich übrigens um ganze Zahlen handelt, müssen wir die Eingabe __getitem__mit allen kollidierenden Elementen vergleichen . Das eingebaute inthat kein ssnAttribut und löst daher aus.

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

In diesem letzten Beispiel zeige ich, dass selbst bei einer Kollision der Vergleich durchgeführt wird und die Objekte nicht mehr gleich sind, was bedeutet, dass a erfolgreich ausgelöst wird KeyError.

Die Python- Dokumente fürhash() state:

Hash-Werte sind Ganzzahlen. Sie werden verwendet, um Wörterbuchschlüssel während einer Wörterbuchsuche schnell zu vergleichen.

Python-Wörterbücher werden als Hash-Tabellen implementiert. Jedes Mal, wenn Sie ein Wörterbuch verwenden, werden hash()die Schlüssel aufgerufen, die Sie zur Zuweisung oder zum Nachschlagen übergeben.

Zusätzlich werden die Dokumente für den dictTyp Zustand:

Werte, die nicht hashbar sind, dh Werte, die Listen, Wörterbücher oder andere veränderbare Typen enthalten (die eher nach Wert als nach Objektidentität verglichen werden), dürfen nicht als Schlüssel verwendet werden.

Der Hash wird von Wörterbüchern und Sets verwendet, um das Objekt schnell nachzuschlagen. Ein guter Ausgangspunkt ist der Artikel von Wikipedia über Hash-Tabellen .

Sie können den DictionaryDatentyp in Python verwenden. Es ist dem Hash sehr, sehr ähnlich - und es unterstützt auch das Verschachteln, ähnlich dem verschachtelten Hash.

Beispiel:

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'])

Weitere Informationen finden Sie in diesem Tutorial zum Datentyp des Wörterbuchs .