Wann ist Hash (n) == n in Python?

100

Ich habe mit Pythons Hash-Funktion gespielt . Bei kleinen Ganzzahlen wird es hash(n) == nimmer angezeigt . Dies erstreckt sich jedoch nicht auf große Zahlen:

>>> hash(2**100) == 2**100
False

Ich bin nicht überrascht, ich verstehe, dass Hash einen endlichen Wertebereich hat. Was ist das für ein Bereich?

Ich habe versucht, mithilfe der binären Suche die kleinste Zahl zu findenhash(n) != n

>>> import codejamhelpers # pip install codejamhelpers
>>> help(codejamhelpers.binary_search)
Help on function binary_search in module codejamhelpers.binary_search:

binary_search(f, t)
    Given an increasing function :math:`f`, find the greatest non-negative integer :math:`n` such that :math:`f(n) \le t`. If :math:`f(n) > t` for all :math:`n \ge 0`, return None.

>>> f = lambda n: int(hash(n) != n)
>>> n = codejamhelpers.binary_search(f, 0)
>>> hash(n)
2305843009213693950
>>> hash(n+1)
0

Was ist das Besondere an 2305843009213693951? Ich stelle fest, es ist weniger alssys.maxsize == 9223372036854775807

Bearbeiten: Ich verwende Python 3. Ich habe die gleiche binäre Suche in Python 2 ausgeführt und ein anderes Ergebnis 2147483648 erhalten, das ich notiere sys.maxint+1

Ich habe auch mit gespielt [hash(random.random()) for i in range(10**6)], um den Bereich der Hash-Funktion abzuschätzen. Das Maximum liegt konstant unter n über. Wenn man die min vergleicht, scheint der Hash von Python 3 immer positiv bewertet zu sein, während der Hash von Python 2 negative Werte annehmen kann.

Oberst Panik
quelle
9
Haben Sie die binäre Darstellung der Zahl überprüft?
John Dvorak
3
'0b11111111111111111111111111111111111111111111111111111111111' neugierig! Also n+1 == 2**61-1
Colonel Panic
2
scheint systemabhängig zu sein. Bei meinem Python gilt der Hash nfür den gesamten 64-Bit-Int-Bereich.
Daniel
1
Beachten Sie den angegebenen Zweck des Hash-Werts: Sie werden verwendet, um Wörterbuchschlüssel während einer Wörterbuchsuche schnell zu vergleichen. Mit anderen Worten, implementierungsdefiniert und aufgrund der Tatsache, dass sie kürzer als viele Werte sind, die Hash-Werte haben können, können Kollisionen auch in vernünftigen Eingaberäumen auftreten.
ein CVn
2
Ähm, ist nicht 2147483647gleich sys.maxint(nicht sys.maxint+1), und wenn 'n = 0b1111111111111111111111111111111111111111111111111111111111111111' dann nicht n+1 == 2**61oder n == 2**61-1(nicht n+1 == 2**61-1)?
Phoog

Antworten:

73

Basierend auf der Python-Dokumentation in der pyhash.cDatei:

Bei numerischen Typen basiert der Hash einer Zahl x auf der Reduzierung von x modulo the prime P = 2**_PyHASH_BITS - 1. Es ist so konzipiert, dass hash(x) == hash(y)immer dann , wenn x und y numerisch gleich sind, x und y unterschiedliche Typen haben.

Für eine 64/32-Bit-Maschine wäre die Reduzierung also 2 _PyHASH_BITS - 1, aber was ist das _PyHASH_BITS?

Sie können es in finden pyhash.hHeader - Datei , die für eine 64 - Bit - Maschine ist als 61 definiert (Sie können mehr Erklärung in Lesen - pyconfig.hDatei).

#if SIZEOF_VOID_P >= 8
#  define _PyHASH_BITS 61
#else
#  define _PyHASH_BITS 31
#endif

Zunächst einmal basiert es auf Ihrer Plattform, zum Beispiel auf meiner 64-Bit-Linux-Plattform beträgt die Reduzierung 2 61 -1, was bedeutet 2305843009213693951:

>>> 2**61 - 1
2305843009213693951

Sie können auch verwenden math.frexp, um die Mantisse und den Exponenten zu erhalten, von sys.maxintdenen für eine 64-Bit-Maschine angezeigt wird, dass max int 2 63 ist :

>>> import math
>>> math.frexp(sys.maxint)
(0.5, 64)

Und Sie können den Unterschied durch einen einfachen Test erkennen:

>>> hash(2**62) == 2**62
True
>>> hash(2**63) == 2**63
False

Lesen Sie die vollständige Dokumentation zum Python-Hashing-Algorithmus https://github.com/python/cpython/blob/master/Python/pyhash.c#L34

Wie im Kommentar erwähnt, können Sie sys.hash_info(in Python 3.X) eine Struktursequenz von Parametern verwenden, die für die Berechnung von Hashes verwendet werden.

>>> sys.hash_info
sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash24', hash_bits=64, seed_bits=128, cutoff=0)
>>> 

Neben dem Modul, das ich in den vorhergehenden Zeilen beschrieben habe, können Sie auch den inffolgenden Wert erhalten:

>>> hash(float('inf'))
314159
>>> sys.hash_info.inf
314159
Kasravnd
quelle
3
Der sys.hash_infoVollständigkeit halber wäre es schön zu erwähnen .
Mark Dickinson
78

2305843009213693951ist 2^61 - 1. Es ist die größte Mersenne-Primzahl, die in 64 Bit passt.

Wenn Sie einen Hash erstellen müssen, indem Sie den Wert mod auf eine bestimmte Zahl setzen, ist eine große Mersenne-Primzahl eine gute Wahl - sie ist einfach zu berechnen und sorgt für eine gleichmäßige Verteilung der Möglichkeiten. (Obwohl ich persönlich niemals einen Hash auf diese Weise machen würde)

Es ist besonders praktisch, den Modul für Gleitkommazahlen zu berechnen. Sie haben eine exponentielle Komponente, die die ganze Zahl mit multipliziert 2^x. Da 2^61 = 1 mod 2^61-1müssen Sie nur die berücksichtigen (exponent) mod 61.

Siehe: https://en.wikipedia.org/wiki/Mersenne_prime

Matt Timmermans
quelle
8
Sie sagen, Sie würden niemals einen Hash auf diese Weise erstellen. Haben Sie alternative Vorschläge, wie es in einer Art und Weise getan werden könnte , dass es einigermaßen effizient macht Ints, Schwimmern zu berechnen für, Dezimalzahlen, Brüche und stellt sicher , dass x == yGarantien hash(x) == hash(y)für Typen? (Zahlen wie Decimal('1e99999999')sind besonders problematisch, zum Beispiel: Sie möchten sie nicht vor dem Hashing auf die entsprechende Ganzzahl erweitern müssen.)
Mark Dickinson
@MarkDickinson Ich vermute, er versucht, zwischen diesem einfachen blitzschnellen Hash und kryptografischen Hashes zu unterscheiden, bei denen es auch darum geht, dass die Ausgabe zufällig aussieht.
Mike Ounsworth
4
@ MarkDickinson Der Modul ist ein guter Anfang, aber ich würde ihn dann noch etwas mischen, insbesondere einige der hohen Bits in die niedrigen. Es ist nicht ungewöhnlich, Folgen von Ganzzahlen zu sehen, die durch Potenzen von 2 teilbar sind. Es ist auch nicht ungewöhnlich, Hash-Tabellen mit Kapazitäten zu sehen, die Potenzen von 2 sind. In Java beispielsweise, wenn Sie eine Folge von Ganzzahlen haben, die durch 16 und 2 teilbar sind Wenn Sie sie als Schlüssel in einer HashMap verwenden, verwenden Sie nur 1/16 der Buckets (zumindest in der Version der Quelle, die ich betrachte)! Ich denke, Hashes sollten zumindest ein bisschen zufällig aussehen, um diese Probleme zu vermeiden
Matt Timmermans
Ja, Hashes im Bit-Mixing-Stil sind den von der Mathematik inspirierten Hashes weit überlegen. Bitmischanweisungen sind so billig, dass Sie viele zum gleichen Preis haben können. Außerdem scheinen Daten aus der realen Welt keine Muster zu haben, die beim Bitmischen nicht gut funktionieren. Aber es gibt Muster, die für den Modul schrecklich sind.
usr
9
@usr: Sicher, aber ein bisschen Misch Hash ist hier nicht machbar: die Anforderung , dass die Hash - Arbeit für int, float, Decimalund FractionObjekte und das x == ybedeutet , hash(x) == hash(y)auch wenn xund yhaben verschiedene Arten , einige ziemlich strenge Beschränkungen auferlegt. Wenn es nur darum ginge, eine Hash-Funktion für ganze Zahlen zu schreiben, ohne sich um die anderen Typen zu kümmern, wäre es eine ganz andere Sache.
Mark Dickinson
9

Die Hash-Funktion gibt plain int zurück. Dies bedeutet, dass der zurückgegebene Wert größer -sys.maxintund kleiner als sys.maxintist. Wenn Sie also sys.maxint + xan ihn übergeben, ist das Ergebnis -sys.maxint + (x - 2).

hash(sys.maxint + 1) == sys.maxint + 1 # False
hash(sys.maxint + 1) == - sys.maxint -1 # True
hash(sys.maxint + sys.maxint) == -sys.maxint + sys.maxint - 2 # True

In der Zwischenzeit 2**200ist es ein nMal größer als sys.maxint- ich vermute, dass Hash -sys.maxint..+sys.maxintn-mal über den Bereich gehen würde, bis er auf einer einfachen Ganzzahl in diesem Bereich stoppt, wie in den obigen Code-Schnipsel.

Im Allgemeinen gilt für jedes n <= sys.maxint :

hash(sys.maxint*n) == -sys.maxint*(n%2) +  2*(n%2)*sys.maxint - n/2 - (n + 1)%2 ## True

Hinweis: Dies gilt für Python 2.

Andriy Ivaneyko
quelle
8
Dies gilt möglicherweise für Python 2, aber definitiv nicht für Python 3 (das keine hat sys.maxintund eine andere Hash-Funktion verwendet).
Interjay
0

Die Implementierung für den int-Typ in cpython finden Sie hier.

Es wird nur der Wert zurückgegeben, mit Ausnahme von -1: Dann wird Folgendes zurückgegeben -2:

static long
int_hash(PyIntObject *v)
{
    /* XXX If this is changed, you also need to change the way
       Python's long, float and complex types are hashed. */
    long x = v -> ob_ival;
    if (x == -1)
        x = -2;
    return x;
}
Jieter
quelle
6
Dies beinhaltet keine großen Werte, die PyLongeher von als implementiert werden PyInt.
Interjay