Eingebaute Python-Hash () -Funktion

82

Windows XP, Python 2.5:

hash('http://stackoverflow.com') Result: 1934711907

Google App Engine ( http://shell.appspot.com/ ):

hash('http://stackoverflow.com') Result: -5768830964305142685

Warum ist das so? Wie kann ich eine Hash-Funktion haben, die auf verschiedenen Plattformen (Windows, Linux, Mac) dieselben Ergebnisse liefert?

Denis T.
quelle
14
Dies ist der Tatsache zu verdanken, dass Ihr WinXP eine 32-Bit-Plattform ist, während
Googles

Antworten:

56

Verwenden hashlib wie hash() wurde entwickelt , um verwendet zu werden :

Vergleichen Sie schnell die Wörterbuchschlüssel während einer Wörterbuchsuche

und garantiert daher nicht, dass es für alle Python-Implementierungen gleich ist.

SilentGhost
quelle
5
Sind die Hash-Funktionen hashlibfür nicht kryptografische Zwecke nicht etwas langsam?
Brandon Rhodes
8
Sie sind im Vergleich zu allgemeinen Hash-Funktionen wie Jenkins, Bernstein, FNV, MurmurHash und vielen anderen sehr langsam. Wenn Sie Ihre eigene Hash-Tabellen-ähnliche Struktur erstellen möchten,
empfehle
45
Benchmarks: hash95 ns, binascii.crc32570 ns, hashlib.md5.digest()1,42 us, murmur.string_hash234 ns
temoto
hashverwendet bei jeder Python-Sitzung einen neuen zufällig generierten Salt-Wert. Es wird sich also zwischen Python-Sitzungen ändern.
Kochfelder
89

Wie in der Dokumentation angegeben, ist die integrierte Funktion hash () nicht dafür ausgelegt, resultierende Hashes irgendwo extern zu speichern. Es wird verwendet, um den Hashwert des Objekts bereitzustellen, sie in Wörterbüchern zu speichern und so weiter. Es ist auch implementierungsspezifisch (GAE verwendet eine modifizierte Version von Python). Auschecken:

>>> class Foo:
...     pass
... 
>>> a = Foo()
>>> b = Foo()
>>> hash(a), hash(b)
(-1210747828, -1210747892)

Wie Sie sehen können, unterscheiden sie sich, da hash () die Objektmethode __hash__anstelle von 'normalen' Hashing-Algorithmen wie SHA verwendet.

In Anbetracht des oben Gesagten besteht die rationale Wahl darin, das Hashlib- Modul zu verwenden.

Mike Hordecki
quelle
Danke dir! Ich kam hierher und fragte mich, warum ich immer unterschiedliche Hash-Werte für identische Objekte erhalten würde, was zu unerwartetem Verhalten mit Dikten führen würde (die nach Hash + Typ indizieren, anstatt auf Gleichheit zu prüfen). Eine schnelle Möglichkeit, aus hashlib.md5 einen eigenen int-Hash zu generieren, ist int(hashlib.md5(repr(self)).hexdigest(), 16)(vorausgesetzt, er self.__repr__wurde als identisch definiert, wenn Objekte identisch sind). Wenn 32 Bytes zu lang sind, können Sie die Größe natürlich reduzieren, indem Sie die Hex-Zeichenfolge vor der Konvertierung in Scheiben schneiden.
Alan Plum
1
Beim zweiten Gedanken, wenn __repr__es einzigartig genug ist, könnten Sie es einfach verwenden str.__hash__(dh hash(repr(self))), da Diktate nicht ungleiche Objekte mit demselben Hash verwechseln. Dies funktioniert nur, wenn das Objekt so trivial ist, dass der Repräsentant offensichtlich Identität darstellen kann.
Alan Plum
Also, in Ihrem Beispiel mit zwei Objekten aund bwie könnte ich das Hashlib-Modul verwenden, um zu sehen, dass die Objekte identisch sind?
Garrett
32

Die Antwort ist absolut keine Überraschung: in der Tat

In [1]: -5768830964305142685L & 0xffffffff
Out[1]: 1934711907L

Wenn Sie also zuverlässige Antworten auf ASCII-Zeichenfolgen erhalten möchten, erhalten Sie einfach die unteren 32 Bit als uint. Die Hash-Funktion für Strings ist 32-Bit-sicher und nahezu portabel.

Auf der anderen Seite können Sie sich überhaupt nicht darauf verlassen, dass Sie hash()ein Objekt abrufen, für das Sie die __hash__Methode nicht explizit als invariant definiert haben.

Über ASCII-Zeichenfolgen funktioniert dies nur, weil der Hash für die einzelnen Zeichen berechnet wird, die die Zeichenfolge bilden, wie folgt:

class string:
    def __hash__(self):
        if not self:
            return 0 # empty
        value = ord(self[0]) << 7
        for char in self:
            value = c_mul(1000003, value) ^ ord(char)
        value = value ^ len(self)
        if value == -1:
            value = -2
        return value

wobei die c_mulFunktion die "zyklische" Multiplikation (ohne Überlauf) wie in C ist.

umgeschrieben
quelle
18

Die meisten Antworten deuten darauf hin, dass dies auf unterschiedliche Plattformen zurückzuführen ist, aber es steckt noch mehr dahinter. Aus der Dokumentation vonobject.__hash__(self) :

Standardmäßig werden die __hash__()Werte von str, bytesund datetimesind Objekte „gesalzen“ mit einem unberechenbaren Zufallswert. Obwohl sie innerhalb eines einzelnen Python-Prozesses konstant bleiben, sind sie zwischen wiederholten Aufrufen von Python nicht vorhersehbar.

Dies soll Schutz vor einem Denial-of-Service bieten, der durch sorgfältig ausgewählte Eingaben verursacht wird, die die Worst-Case-Leistung einer Dikt-Einfügung, O (n²) -Komplexität, ausnutzen. Weitere Informationen finden Sie unter http://www.ocert.org/advisories/ocert-2011-003.html .

Hash - Werte ändern , wirkt sich die Iterationsreihenfolge von dicts, sets und andere Abbildungen. Python hat niemals Garantien für diese Reihenfolge gegeben (und sie variiert normalerweise zwischen 32-Bit- und 64-Bit-Builds).

Selbst das Ausführen auf demselben Computer führt zu unterschiedlichen Ergebnissen bei verschiedenen Aufrufen:

$ python -c "print(hash('http://stackoverflow.com'))"
-3455286212422042986
$ python -c "print(hash('http://stackoverflow.com'))"
-6940441840934557333

Während:

$ python -c "print(hash((1,2,3)))"
2528502973977326415
$ python -c "print(hash((1,2,3)))"
2528502973977326415

Siehe auch die Umgebungsvariable PYTHONHASHSEED:

Wenn diese Variable nicht gesetzt ist oder eingestellt randomwird ein Zufallswert verwendet , um die Hash - Werte von Saatgut str, bytesund datetimeObjekte.

Wenn PYTHONHASHSEEDein ganzzahliger Wert festgelegt ist, wird er als fester Startwert zum Generieren der hash()von der Hash-Randomisierung abgedeckten Typen verwendet.

Der Zweck besteht darin, wiederholbares Hashing zuzulassen, z. B. für Selbsttests für den Interpreter selbst, oder einem Cluster von Python-Prozessen zu ermöglichen, Hash-Werte gemeinsam zu nutzen.

Die Ganzzahl muss eine Dezimalzahl im Bereich sein [0, 4294967295]. Durch Angabe des Werts 0wird die Hash-Randomisierung deaktiviert.

Beispielsweise:

$ export PYTHONHASHSEED=0                            
$ python -c "print(hash('http://stackoverflow.com'))"
-5843046192888932305
$ python -c "print(hash('http://stackoverflow.com'))"
-5843046192888932305
Arekolek
quelle
3
Dies gilt nur für Python 3.x, aber da Python 3 die Gegenwart und die Zukunft ist und dies die einzige Antwort ist, die dies anspricht, +1.
Alexander Huszagh
8

Die Hash-Ergebnisse variieren zwischen 32-Bit- und 64-Bit-Plattformen

Wenn ein berechneter Hash auf beiden Plattformen gleich sein soll, sollten Sie die Verwendung in Betracht ziehen

def hash32(value):
    return hash(value) & 0xffffffff
Tzury Bar Yochay
quelle
6

Vermutlich verwendet AppEngine eine 64-Bit-Implementierung von Python (-5768830964305142685 passt nicht in 32 Bit), und Ihre Implementierung von Python ist 32 Bit. Sie können sich nicht darauf verlassen, dass Objekt-Hashes zwischen verschiedenen Implementierungen sinnvoll vergleichbar sind.

George V. Reilly
quelle
6

Dies ist die Hash-Funktion, die Google in der Produktion für Python 2.5 verwendet:

def c_mul(a, b):
  return eval(hex((long(a) * b) & (2**64 - 1))[:-1])

def py25hash(self):
  if not self:
    return 0 # empty
  value = ord(self[0]) << 7
  for char in self:
    value = c_mul(1000003, value) ^ ord(char)
  value = value ^ len(self)
  if value == -1:
    value = -2
  if value >= 2**63:
    value -= 2**64
  return value
Andrin von Rechenberg
quelle
7
Können Sie einen Kontext darüber teilen, wofür diese Hash-Funktion verwendet wird und warum?
Amcnabb
5

Was ist mit Zeichenbit?

Beispielsweise:

Der Hex-Wert steht 0xADFE74A5für vorzeichenlos 2919134373und signiert -1375832923. Der korrekte Wert muss signiert sein (Vorzeichenbit = 1), aber Python konvertiert ihn als vorzeichenlos und wir haben nach der Übersetzung von 64 auf 32 Bit einen falschen Hashwert.

Seien Sie vorsichtig mit:

def hash32(value):
    return hash(value) & 0xffffffff
Löwe
quelle
3

Polynom-Hash für Strings. 1000000009und 239sind beliebige Primzahlen. Es ist unwahrscheinlich, dass es versehentlich zu Kollisionen kommt. Modulare Arithmetik ist nicht sehr schnell, aber um Kollisionen zu verhindern, ist dies zuverlässiger, als wenn man Modulo eine Potenz von nimmt 2. Natürlich ist es leicht, absichtlich eine Kollision zu finden.

mod=1000000009
def hash(s):
    result=0
    for c in s:
        result = (result * 239 + ord(c)) % mod
    return result % mod
Sergey Orshanskiy
quelle
2

Der Wert von PYTHONHASHSEED kann zum Initialisieren der Hashwerte verwendet werden.

Versuchen:

PYTHONHASHSEED python -c 'print(hash('http://stackoverflow.com'))'
blau gefärbt
quelle
-3

Wahrscheinlich wird nur die vom Betriebssystem bereitgestellte Funktion und nicht der eigene Algorithmus abgefragt.

Verwenden Sie , wie in anderen Kommentaren angegeben, die Hashlib oder schreiben Sie Ihre eigene Hash-Funktion.

ewanm89
quelle