modules - python libraries list
¿Cuándo es hash(n)== n en Python? (4)
He estado jugando con la
función hash
de Python.
Para enteros pequeños, parece
hash(n) == n
siempre.
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ño
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
¿Qué tiene de especial 2305843009213693951?
sys.maxsize == 9223372036854775807
que es menor que
sys.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é con
[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 arriba.
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.
Basado en la documentación de Python en el archivo
pyhash.c
:
Para los tipos numéricos, el hash de un número x se basa en la reducción del módulo x el primo
P = 2**_PyHASH_BITS - 1. Está diseñado para quehash(x) == hash(y)siempre que x e y sean numéricamente iguales, incluso si x e y tienen diferentes tipos.
Entonces, para una máquina de 64/32 bits, la reducción sería 2
_PyHASH_BITS
- 1, pero ¿qué es
_PyHASH_BITS
?
Puede encontrarlo en el archivo de encabezado
pyhash.h
que para una máquina de 64 bits se ha definido como 61 (puede leer más explicaciones en el archivo
pyconfig.h
).
#if SIZEOF_VOID_P >= 8
# define _PyHASH_BITS 61
#else
# define _PyHASH_BITS 31
#endif
En primer lugar, se basa en su plataforma, por ejemplo, en mi plataforma Linux de 64 bits, la reducción es 2
61
-1, que es
2305843009213693951
:
>>> 2**61 - 1
2305843009213693951
También puede usar
math.frexp
para obtener la mantisa y el exponente de
sys.maxint
que 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 de 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 he descrito en las líneas anteriores, también puede obtener el valor
inf
siguiente manera:
>>> hash(float(''inf''))
314159
>>> sys.hash_info.inf
314159
La implementación para el tipo int en cpython se puede encontrar aquí.
Simplemente devuelve el valor, excepto
-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;
}
La función hash devuelve
plain int
que significa que el valor devuelto es mayor que
-sys.maxint
y menor que
sys.maxint
, lo que significa que si pasa
sys.maxint + x
a su resultado 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**200
es
n
veces mayor que
sys.maxint
: supongo que el hash sobrepasará el rango
-sys.maxint..+sys.maxint
n veces hasta que se detenga en un entero simple en ese rango, como en los fragmentos de código encima..
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.
2305843009213693951
es
2^61 - 1
2305843009213693951
.
Es el primer 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 gran Mersenne prime es una buena opción: es fácil de calcular y garantiza una distribución uniforme de posibilidades. (Aunque 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
.