Hashing verschiedene Tupel in Python geben identische Ergebnis

Question

Ich arbeite mit Mengen von Integer-Matrizen, und ich dachte, sie als Tupel sinnvoll darzustellen, da sie hashable sind. Doch die Hash() Funktion gab mir seltsame Ergebnisse für Tupeln:

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 

Wie Sie sehen können, diese beiden unterschiedlichen Tupel haben den gleichen Hash-Wert. Beachten Sie, dass sie tatsächlich ziemlich ähnlich sind (Austausch der ersten und letzten Subtrahle), jedoch konnte ich kein minimaleres Beispiel finden: ((0,1),(0,0)) und ((0,0),(0,1)) haben unterschiedliche Hashwerte.

Irgendwelche Ahnung von was ist los? Ich kann nicht glauben, dass es nur unglaublich schlechtes Glück ist ... Jetzt, wo ich das Problem gefunden habe, konnte ich es leicht umgehen, aber ich dachte, es wäre trotzdem erwähnenswert.

Answer 1

Der Hash eines Tupels auf den Hash-Werten des Inhalts basiert die folgende Formel (vom tuplehash() function) unter Verwendung von:

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; 

Wie es passiert, erzeugt diese Formel exakt die gleiche Ausgabe für (1, 0, -1) und (1, -1, 0):

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

weil die Hashes für die 3 enthaltenen ganzen Zahlen sind 1, 0 und -2:

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

und die 0 und die -2 Swapping hat keinen tatsächlichen Einfluss auf das Ergebnis.

Also die Hashes für die 3 enthaltenen Tupel nicht zwischen den beiden Beispielen ändern, so ändert sich der endgültige Hash auch nicht.

Dies ist nur ein Zufall, in der Praxis passiert dies nicht alle , dass oft und Wörterbücher und Sätze können schon mit Kollisionen gut umgehen.

Answer 2

scheint seltsam, aber nicht verwenden hash oder so: https://docs.python.org/2/library/functions.html#hash

[Hash] verwendet, um schnell Dictionary-Schlüssel während eines Wörterbuchsuche zu vergleichen.

Es ist nicht wirklich für allgemeine Zwecke Hashing gemacht - Wörterbücher haben zusätzliche Prüfungen über einfache Hash-Gleichheit. Für allgemeine Zwecke verwenden Sie hashlib