He estado jugando con la función hash de Python . Para enteros pequeños, aparece 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ñ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.
fuente
n+1 == 2**61-1
n
para todo el rango int de 64 bits.2147483647
igual asys.maxint
(nosys.maxint+1
), y si 'n = 0b111111111111111111111111111111111111111111111111111111111' entonces no esn+1 == 2**61
on == 2**61-1
(non+1 == 2**61-1
)?Respuestas:
Basado en la documentación de Python en el
pyhash.c
archivo: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.h
archivo de encabezado que para una máquina de 64 bits se ha definido como 61 (puede leer más explicaciones en elpyconfig.h
archivo).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
:También puedes usar
math.frexp
para obtener la mantisa y el exponente de lossys.maxint
cuales para una máquina de 64 bits muestra que max int es 2 63 :Y puedes ver la diferencia con una simple prueba:
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.Junto con el módulo que describí en las líneas anteriores, también puede obtener el
inf
valor de la siguiente manera:fuente
sys.hash_info
para completarlo.2305843009213693951
es2^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 que2^61 = 1 mod 2^61-1
, solo necesita considerar el(exponent) mod 61
.Ver: https://en.wikipedia.org/wiki/Mersenne_prime
fuente
x == y
garantíashash(x) == hash(y)
entre tipos? (Los números comoDecimal('1e99999999')
son especialmente problemáticos, por ejemplo: no desea tener que expandirlos al entero correspondiente antes de aplicar el hash).int
,float
,Decimal
yFraction
los objetos y quex == y
implicahash(x) == hash(y)
incluso cuandox
yy
tener 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.La función hash devuelve un int simple, lo que significa que el valor devuelto es mayor que
-sys.maxint
y menor quesys.maxint
, lo que significa que si le pasa elsys.maxint + x
resultado sería-sys.maxint + (x - 2)
.Mientras tanto,
2**200
es unan
vez mayor quesys.maxint
, supongo que el hash sobrepasaría 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 anteriores.Entonces, generalmente, para cualquier n <= sys.maxint :
Nota: esto es cierto para Python 2.
fuente
sys.maxint
y que usa una función hash diferente).La implementación para el tipo int en cpython se puede encontrar aquí.
Simplemente devuelve el valor, excepto por
-1
, que devuelve-2
:fuente
PyLong
lugar dePyInt
.