hashing diverse tuple in python danno risultati identici

Question

Sto lavorando con insiemi di matrici di interi, e ho pensato rappresentandoli come tuple aveva senso, in quanto sono lavabili. Tuttavia la funzione di hash() mi ha dato strani risultati per le tuple:

hash(((1, -1, 0), (1, 0, 0), (1, 0, -1))) 

Out[147]: -697649482279922733 

hash(((1, 0, -1), (1, 0, 0), (1, -1, 0))) 

Out[148]: -697649482279922733 

Come si può vedere, questi due tuple differenti hanno lo stesso valore di hash. Si noti che sono in realtà abbastanza simili (scambio del primo e dell'ultimo sottotitolo), tuttavia non sono riuscito a trovare un esempio più minimale: ((0,1),(0,0)) e ((0,0),(0,1)) hanno valori di hash diversi, ad esempio.

Qualsiasi indizio di cosa sta succedendo? Non posso credere che sia solo una sfortuna ... Ora che ho trovato il problema è che potrei aggirarlo facilmente, ma ho pensato che valesse la pena parlarne qui comunque.

Answer 1

L'hash di una tupla si basa sulle hash del contenuto utilizzando la seguente formula (dalla tuplehash() function):

long mult = 1000003L; 
x = 0x345678L; 
p = v->ob_item; 
while (--len >= 0) { 
    y = PyObject_Hash(*p++); 
    if (y == -1) 
     return -1; 
    x = (x^y) * mult; 
    /* the cast might truncate len; that doesn't change hash stability */ 
    mult += (long)(82520L + len + len); 
} 
x += 97531L; 
if (x == -1) 
    x = -2; 
return x; 

Come accade, che formula produce la stessa uscita esatta per (1, 0, -1) e (1, -1, 0):

>>> hash((1, -1, 0)) 
-2528505496374624146 
>>> hash((1, 0, -1)) 
-2528505496374624146 

interi perché gli hash per il 3 contenuti sono 1, 0 e -2:

>>> hash(1) 
1 
>>> hash(0) 
0 
>>> hash(-1) 
-2 

e scambiare il 0 e -2 ha alcuna effettiva influenza sul risultato.

Quindi gli hash per le 3 tuple contenute non cambiano tra i due esempi, quindi l'hash finale non cambia neanche.

Questa è solo una coincidenza, in pratica questo non accade tutto che spesso e dizionari e set già in grado di gestire le collisioni più che bene.

Answer 2

sembra strano, ma non usano hash in entrambi i casi: https://docs.python.org/2/library/functions.html#hash

[hash viene] utilizzato per confrontare rapidamente le chiavi del dizionario nel corso di una consultazione dei dizionari.

In realtà non è stato creato per l'hashing generico - i dizionari hanno controlli extra oltre alla semplice uguaglianza di hash. Per l'hashing di uso generale, utilizzare hashlib