¿Cuándo es hash (n) == n en Python?

100

He estado jugando con la función hash de Python . Para enteros pequeños, aparece hash(n) == nsiempre. Sin embargo, esto no se extiende a grandes cantidades:

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

No me sorprende, entiendo que el hash toma un rango finito de valores. ¿Cuál es ese rango?

Intenté usar la búsqueda binaria para encontrar el número más pequeñohash(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

¿Qué tiene de especial 2305843009213693951? Noto que es menos desys.maxsize == 9223372036854775807

Editar: estoy usando Python 3. Ejecuté la misma búsqueda binaria en Python 2 y obtuve un resultado diferente 2147483648, que noto es sys.maxint+1

También jugué [hash(random.random()) for i in range(10**6)]para estimar el rango de la función hash. El máximo está constantemente por debajo de n por encima. Comparando el mínimo, parece que el hash de Python 3 siempre se valora positivamente, mientras que el hash de Python 2 puede tomar valores negativos.

Coronel Panic
fuente
9
¿Ha verificado la representación binaria del número?
John Dvorak
3
'0b11111111111111111111111111111111111111111111111111111111111' ¡curioso! Entonces n+1 == 2**61-1
Coronel Panic
2
parece depender del sistema. Con mi python, el hash es npara todo el rango int de 64 bits.
Daniel
1
Tenga en cuenta el propósito declarado del valor hash: se utilizan para comparar rápidamente claves de diccionario durante una búsqueda de diccionario. En otras palabras, definido por la implementación, y en virtud de ser más corto que muchos valores que pueden tener valores hash, puede muy bien tener colisiones incluso en espacios de entrada razonables.
a CV el
2
Um, ¿no es 2147483647igual a sys.maxint(no sys.maxint+1), y si 'n = 0b111111111111111111111111111111111111111111111111111111111' entonces no es n+1 == 2**61o n == 2**61-1(no n+1 == 2**61-1)?
phoog

Respuestas:

73

Basado en la documentación de Python en el pyhash.carchivo:

Para los tipos numéricos, el hash de un número x se basa en la reducción de x módulo el primo P = 2**_PyHASH_BITS - 1. Está diseñado para que hash(x) == hash(y)siempre que xey sean numéricamente iguales, incluso si xey tienen tipos diferentes.

Entonces, para una máquina de 64/32 bits, la reducción sería 2 _PyHASH_BITS - 1, pero ¿cuál es _PyHASH_BITS?

Puede encontrarlo en el pyhash.harchivo de encabezado que para una máquina de 64 bits se ha definido como 61 (puede leer más explicaciones en el pyconfig.harchivo).

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

Así Primero de todo se basa en su plataforma por ejemplo en mi plataforma Linux de 64 bits, la reducción es de 2 61 -1, que es 2305843009213693951:

>>> 2**61 - 1
2305843009213693951

También puedes usar math.frexp para obtener la mantisa y el exponente de los sys.maxintcuales para una máquina de 64 bits muestra que max int es 2 63 :

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

Y puedes ver la diferencia con una simple prueba:

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

Lea la documentación completa sobre el algoritmo hash de Python https://github.com/python/cpython/blob/master/Python/pyhash.c#L34

Como se mencionó en el comentario, puede usar sys.hash_info (en Python 3.X) que le dará una secuencia de estructura de parámetros utilizados para calcular hashes.

>>> 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)
>>> 

Junto con el módulo que describí en las líneas anteriores, también puede obtener el infvalor de la siguiente manera:

>>> hash(float('inf'))
314159
>>> sys.hash_info.inf
314159
Kasravnd
fuente
3
Sería bueno mencionarlo sys.hash_infopara completarlo.
Mark Dickinson
78

2305843009213693951es 2^61 - 1. Es el principal Mersenne más grande que cabe en 64 bits.

Si tiene que hacer un hash simplemente tomando el valor mod algún número, entonces un primo grande de Mersenne es una buena opción: es fácil de calcular y garantiza una distribución uniforme de posibilidades. (Aunque yo personalmente nunca haría un hash de esta manera)

Es especialmente conveniente calcular el módulo para números de coma flotante. Tienen un componente exponencial que multiplica el número entero por 2^x. Dado que 2^61 = 1 mod 2^61-1, solo necesita considerar el(exponent) mod 61 .

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

Matt Timmermans
fuente
8
Dices que nunca harías un hash de esta manera. ¿Tiene sugerencias alternativas sobre cómo se podría hacer de una manera que lo haga razonablemente eficiente para calcular ints, floats, decimales, fracciones y garantice las x == ygarantías hash(x) == hash(y)entre tipos? (Los números como Decimal('1e99999999')son especialmente problemáticos, por ejemplo: no desea tener que expandirlos al entero correspondiente antes de aplicar el hash).
Mark Dickinson
@MarkDickinson Sospecho que está tratando de establecer una distinción entre este simple hash rápido y rápido y los hash criptográficos que también se preocupan por hacer que la salida parezca aleatoria.
Mike Ounsworth
4
@MarkDickinson El módulo es un buen comienzo, pero luego lo mezclaría un poco más, especialmente mezclando algunos de los bits altos con los bajos. No es raro ver secuencias de enteros divisibles por potencias de 2. Tampoco es raro ver tablas hash con capacidades que son potencias de 2. En Java, por ejemplo, si tiene una secuencia de enteros que son divisibles por 16, y los usa como claves en un HashMap, solo usará 1/16 de los cubos (al menos en la versión de la fuente que estoy viendo). Creo que los hashes deben tener al menos un aspecto un poco aleatorio para evitar estos problemas
Matt Timmermans
Sí, los hashes de estilo de mezcla de bits son muy superiores a los inspirados en las matemáticas. Las instrucciones de mezcla de bits son tan económicas que puede tener muchas al mismo costo. Además, los datos del mundo real parecen no tener patrones que no funcionen bien con la mezcla de bits. Pero hay patrones que son horribles para el módulo.
usr
9
@usr: Claro, pero un hash de bits de mezcla es inviable aquí: el requisito de que el trabajo de hash para int, float, Decimaly Fractionlos objetos y que x == yimplica hash(x) == hash(y)incluso cuando xy ytener diferentes tipos impone algunas limitaciones bastante severas. Si fuera solo una cuestión de escribir una función hash para números enteros, sin preocuparse por los otros tipos, sería un asunto completamente diferente.
Mark Dickinson
9

La función hash devuelve un int simple, lo que significa que el valor devuelto es mayor que -sys.maxinty menor que sys.maxint, lo que significa que si le pasa el sys.maxint + xresultado sería -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

Mientras tanto, 2**200es una nvez mayor que sys.maxint, supongo que el hash sobrepasaría el rango -sys.maxint..+sys.maxintn veces hasta que se detenga en un entero simple en ese rango, como en los fragmentos de código anteriores.

Entonces, generalmente, para cualquier n <= sys.maxint :

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

Nota: esto es cierto para Python 2.

Andriy Ivaneyko
fuente
8
Esto puede ser cierto para Python 2, pero definitivamente no para Python 3 (que no tiene sys.maxinty que usa una función hash diferente).
interjay
0

La implementación para el tipo int en cpython se puede encontrar aquí.

Simplemente devuelve el valor, excepto por -1, que devuelve -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
fuente
6
Esto no incluye valores grandes, que se implementan mediante en PyLonglugar de PyInt.
Interjay