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




scraping data with beautifulsoup (3)

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

Für numerische Typen basiert der Hash einer Zahl x auf der Reduktion von x Modulo der Primzahl P = 2**_PyHASH_BITS - 1 . Es ist so konzipiert, dass hash(x) == hash(y) immer dann, wenn x und y numerisch gleich sind, auch wenn x und y unterschiedliche Typen haben.

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

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

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

2305843009213693951 basiert es auf Ihrer Plattform, zum Beispiel auf meiner 64-Bit-Linux-Plattform. Die Reduzierung beträgt 2 61 -1, das ist 2305843009213693951 :

>>> 2**61 - 1
2305843009213693951

Sie können auch math.frexp verwenden, um die Mantisse und den Exponenten von sys.maxint was für eine 64-Bit-Maschine zeigt, 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 sehen:

>>> 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) verwenden, um eine strukturierte Folge 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 in den vorhergehenden Zeilen beschriebenen Modul können Sie den inf Wert auch wie folgt ermitteln:

>>> hash(float('inf'))
314159
>>> sys.hash_info.inf
314159

Ich habe mit Pythons Hash-Funktion gespielt . Für kleine ganze Zahlen erscheint immer ein hash(n) == n . Dies gilt jedoch nicht für große Stückzahlen:

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

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

Ich habe versucht, mit der binären Suche den kleinsten 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 sys.maxsize == 9223372036854775807 fest, es ist weniger als sys.maxsize == 9223372036854775807

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

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


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

Es gibt nur den Wert mit Ausnahme von -1 , als es -2 zurückgibt:

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

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

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

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

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







python-internals