wake-up-neo.com

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

Ich habe mit Pythons hash-Funktion gespielt. Bei kleinen Ganzzahlen erscheint hash(n) == n immer. Dies gilt jedoch nicht für 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, mit binary search die kleinste Zahl zu finden hash(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 bemerke, dass es weniger als sys.maxsize == 9223372036854775807 ist.

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

Ich habe auch mit [hash(random.random()) for i in range(10**6)] gespielt, um die Reichweite der Hash-Funktion zu schätzen. Das Maximum liegt konstant unter n. Vergleicht man die Min., So scheint es, als wäre der Hash von Python 3 immer positiv bewertet, während der Hash von Python 2 negative Werte annehmen kann.

pythonpython-2.7python-3.xhashpython-internals
97
Colonel Panic

Basierend auf der Python-Dokumentation in pyhash.c file:

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

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

Sie finden es in der pyhash.h header-Datei, die für eine 64-Bit-Maschine als 61 definiert wurde (weitere Erklärungen finden Sie in der pyconfig.h-Datei).

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

Zunächst einmal basiert alles auf Ihrer Plattform. In meiner 64-Bit-Linux-Plattform beträgt die Reduzierung 261-1, was 2305843009213693951 ist:

>>> 2**61 - 1
2305843009213693951

Sie können auch math.frexp verwenden, um die Mantisse und den Exponenten von sys.maxint abzurufen, der für eine 64-Bit-Maschine zeigt, dass max int 2 ist63: 

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

Und Sie können den Unterschied anhand eines einfachen Tests erkennen:

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

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

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

>>> 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 den inf-Wert auch wie folgt erhalten:

>>> hash(float('inf'))
314159
>>> sys.hash_info.inf
314159
70
Kasrâmvd

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

Wenn Sie einen Hashwert erstellen müssen, indem Sie nur den Wert mod angeben, ist eine große Mersenne-Primzahl eine gute Wahl - sie ist leicht zu berechnen und gewährleistet eine gleichmäßige Verteilung der Möglichkeiten. (Obwohl ich persönlich nie einen Hash auf diese Weise machen würde)

Es ist besonders praktisch, den Modul für Fließkommazahlen zu berechnen. Sie haben eine Exponentialkomponente, die die ganze Zahl mit 2^x multipliziert. Seit 2^61 = 1 mod 2^61-1 müssen Sie nur noch den (exponent) mod 61 berücksichtigen.

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

77
Matt Timmermans

Die Hash-Funktion gibt plain int zurück. Dies bedeutet, dass der zurückgegebene Wert größer als -sys.maxint und niedriger als sys.maxint ist. Wenn Sie also sys.maxint + x übergeben, wäre -sys.maxint + (x - 2) das Ergebnis.

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

Inzwischen ist 2**200 eine n-mal größer als sys.maxint - meine Vermutung ist, dass hash den Bereich -sys.maxint..+sys.maxint n-mal durchläuft, bis er auf reelle Ganzzahl in diesem Bereich stoppt, wie in den obigen Code-Snippets.

Also im Allgemeinen für alle 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.

9
Andriy Ivaneyko

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

Es gibt nur den Wert mit Ausnahme von -1 als -2 zurück:

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;
}
0
Jieter