Eingebaute Python-Hash () -Funktion

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?

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.

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.

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.

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

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

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.

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

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

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

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

Versuchen:

PYTHONHASHSEED python -c 'print(hash('http://stackoverflow.com'))'

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.