Wie verbessern bitverschobene Werte in dieser GetHashCode-Methode Hashing?

Question

Ich fand zwei Datentypen mit Hash-Code Methoden in einer Code-Basis auf ich arbeite, die ich nicht ganz verstehen, warum sie gewählt wurden:

public override int GetHashCode() 
{ 
    return x.GetHashCode()^y.GetHashCode() << 2; 
} 

public override int GetHashCode() 
{ 
    return x.GetHashCode()^y.GetHashCode() << 2^z.GetHashCode() >> 2; 
} 

Wie funktioniert das Bit Schaltvorgang macht diese Hash-Werte etwas besser?

Answer 1

Nehmen wir an, Sie haben eine Point Datenstruktur, die durch eine Variable x und y dargestellt wird. Ohne die Bitverschiebung wäre der Wert des Hash-Codes für 1, und der Hash-Code für (0,1) wäre auch 1. Jetzt tun die gleiche Sache mit der Bitverschiebung, für (1,0) wir einen Hash-Code von 1 bekommen, aber für (0,1) wir jetzt einen Hash-Code von 4

Was die Bitverschiebung bietet erhalten, wenn Sie die gleichen Eingaben aber in eine haben andere Reihenfolge, die Sie verschiedene Hash-Codes erhalten möchten, auf diese Weise (1,0) und (0,1) nicht am Ende in den gleichen Hash-Bucket fallen und Ihre Hashset/Wörterbuch Leistung verschlechtern.

Normalerweise würden Sie einen viel größeren Offset als nur zweimal zweimal verschieben. Bitshifting bewirkt auch, dass Daten abgeschnitten werden, wenn Hash-Codes in der Nähe von Int32.MaxValue behandelt werden. Hier ist das Muster, das normalerweise I

public override int GetHashCode() 
{ 
    unchecked 
    { 
     var hashCode = X; 
     hashCode = (hashCode*397)^Y; 
     hashCode = (hashCode*397)^Z; 
     return hashCode; 
    } 
} 

verwenden (dies ist die Standardimplementierung, die mit ReSharper der „Insert Vergleichsmethode“ Feature kommt. Um weitere Felder hinzufügen, die Sie gerade hashCode = (hashCode*397)^XXXXXXX weiterhin tun)

Durch die Verwendung von * mit unchecked anstelle von << überläuft jeder Wert, der größer als Int32.MaxValue ist, einfach ohne Fehler.