Ho giocato con Python hash function. Per numeri interi piccoli, appare sempre hash(n) == n
. Tuttavia questo non si estende ai grandi numeri:Quando è hash (n) == n in Python?
>>> hash(2**100) == 2**100
False
Non sono sorpreso, ho capito che hash richiede un intervallo limitato di valori. Qual è quella gamma?
Ho provato ad utilizzare binary search per trovare il più piccolo numero 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
Cosa c'è di speciale in 2305843009213693951? Prendo atto che è meno di sys.maxsize == 9223372036854775807
Edit: sto usando Python 3. Ho eseguito la stessa ricerca binaria su Python 2 e ottenuto un risultato diverso 2147483648, che rilevo è sys.maxint+1
Ho anche giocato con a stimare il range della funzione di hash. Il massimo è costantemente inferiore a n sopra. Confrontando il minimo, sembra che l'hash di Python 3 sia sempre valutato positivamente, mentre l'hash di Python 2 può assumere valori negativi.
Avete controllato rappresentazione binaria del numero? –
'0b11111111111111111111111111111111111111111111111111111111111111111' curioso! Quindi 'n + 1 == 2 ** 61-1' –
sembra essere dipendente dal sistema. Con il mio python, l'hash è 'n' per l'intero intervallo int a 64 bit. – Daniel