2016-06-03 24 views
95

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.

+8

Avete controllato rappresentazione binaria del numero? –

+3

'0b11111111111111111111111111111111111111111111111111111111111111111' curioso! Quindi 'n + 1 == 2 ** 61-1' –

+2

sembra essere dipendente dal sistema. Con il mio python, l'hash è 'n' per l'intero intervallo int a 64 bit. – Daniel

risposta

67

Sulla base di documentazione di pitone in pyhash.c di file:

per i tipi numerici, l'hash di un numero x si basa sulla riduzione del x modulo del primo P = 2**_PyHASH_BITS - 1. È progettato in modo che hash(x) == hash(y) ogni volta che xey siano numericamente uguali, anche se xe y hanno tipi diversi.

Così, per una macchina di 64/32 bit, la riduzione sarebbe 2 _PyHASH_BITS - 1, ma che cosa è _PyHASH_BITS?

È possibile trovarlo nel file di intestazione pyhash.h che per una macchina a 64 bit è stato definito come 61 (è possibile leggere ulteriori spiegazioni nel file pyconfig.h).

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

Quindi, in primo luogo fuori tutto si basa sulla vostra piattaforma per esempio nel mio 64bit piattaforma Linux la riduzione è del 2 -1, che è 2305843009213693951:

>>> 2**61 - 1 
2305843009213693951 

Inoltre è possibile utilizzare math.frexp in per ottenere la mantissa e l'esponente di sys.maxint che per una macchina a 64 bit mostra che max int è 2 :

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

E si può vedere la differenza da un semplice test:

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

leggere la documentazione completa su algoritmo di hashing pitone https://github.com/python/cpython/blob/master/Python/pyhash.c#L34

Come accennato nel commento è possibile utilizzare sys.hash_info (in python 3.x) che ti fornirà una sequenza struct di parametri utilizzati per calcolare gli hash .

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

Accanto al modulo che ho descritto in precedenti linee, è anche possibile ottenere il valore inf come segue:

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

Sarebbe bello parlare di 'sys.hash_info', per completezza. –

+0

@MarkDickinson Grazie per il commento, appena aggiornato. – Kasramvd

-1

Il implementation for the int type in cpython can be found here.

Semplicemente restituisce il valore, tranne -1, che restituisce -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; 
} 
+5

Questo non include valori grandi, che sono implementati da 'PyLong' piuttosto che' PyInt'. – interjay

8

funzione hash restituisce pianura int che significa che il valore restituito è maggiore di -sys.maxint e inferiore di sys.maxint, il che significa che se si passa sys.maxint + x al risultato risulterebbe -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 

Nel frattempo 2**200 è un n volte maggiore di sys.maxint - la mia ipotesi è che hash sarebbe andare oltre gamma -sys.maxint..+sys.maxint n volte fino a quando non si ferma su intero semplice in tale intervallo, come in frammenti di codice di cui sopra ..

Quindi in generale, per qualsiasi n = < sys.maxint:

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

Nota: questo è vero per python 2.

+8

Questo può essere vero per Python 2, ma sicuramente non per Python 3 (che non ha 'sys.maxint', e che usa una diversa funzione di hash). – interjay

76

2305843009213693951 è 2^61 - 1. È il più grande primo di Mersenne che si adatta a 64 bit.

Se si deve fare un hash semplicemente prendendo il valore mod un numero, allora un grande Mersenne primo è una buona scelta: è facile da calcolare e garantisce una distribuzione uniforme delle possibilità. (Anche se personalmente non farei mai un hash in questo modo)

È particolarmente conveniente calcolare il modulo per i numeri in virgola mobile. Hanno un componente esponenziale che moltiplica l'intero numero per 2^x. Dal 2^61 = 1 mod 2^61-1, è sufficiente considerare lo (exponent) mod 61.

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

+8

Hai detto che non avresti mai fatto un hash in questo modo. Avete suggerimenti alternativi su come potrebbe essere fatto in un modo che renda ragionevolmente efficiente calcolare per interi, float, decimali, frazioni _e_ assicura che 'x == y' garantisce' hash (x) == hash (y) 'tra i tipi? (Numeri come 'Decimal ('1e99999999')' sono particolarmente problematici, ad esempio: non vuoi doverli espandere al numero intero corrispondente prima dell'hashing.) –

+0

@MarkDickinson Sospetto che stia cercando di fare una distinzione tra questo semplice hash rapido alleggerimento, e hash crittografici che si preoccupano anche di rendere l'output casuale. –

+4

@MarkDickinson Il modulo è un buon inizio, ma lo mescolerei un po 'di più, specialmente mescolando alcuni dei bit più alti in basso. Non è raro vedere sequenze di interi divisibili per potenze di 2. Non è raro vedere tabelle hash con capacità che sono potenze di 2. In Java, ad esempio, se si ha una sequenza di numeri interi che sono divisibili per 16, e li usi come chiavi in ​​una HashMap, userai solo 1/16 dei bucket (almeno nella versione della fonte che sto guardando)! Penso che gli hash debbano essere almeno un po 'casuali per evitare questi problerms –

Problemi correlati