Qu'est ce qu'un " appropriée GetHashCode()` algorithme pour un 2D point struct (en évitant les affrontements)
Considérons le code suivant:
struct Vec2 : IEquatable<Vec2>
{
double X,Y;
public bool Equals(Vec2 other)
{
return X.Equals(other.X) && Y.Equals(other.Y);
}
public override bool Equals(object obj)
{
if (obj is Vec2)
{
return Equals((Vec2)obj);
}
return false;
}
//this will return the same value when X, Y are swapped
public override int GetHashCode()
{
return X.GetHashCode() ^ Y.GetHashCode();
}
}
Au-delà de la conversation de la comparaison de double pour l'égalité (c'est juste le code de démonstration), ce que je crains, c'est que il y a une table de hachage choc lorsque les valeurs X, Y sont échangés. Par exemple:
Vec2 A = new Vec2() { X=1, Y=5 };
Vec2 B = new Vec2() { X=5, Y=1 };
bool test1 = A.Equals(B); //returns false;
bool test2 = A.GetHashCode() == B.GetHashCode() //returns true !!!!!
qui devrait semer le chaos dans un dictionnaire de la collection. Donc, la question est de savoir comment bien la forme de la GetHashCode()
fonction pour 2, 3 ou même 4 valeurs à virgule flottante à ce que les résultats ne sont pas symétriques et les hachages de ne pas clash.
Edit 1:
Point
met en œuvre inappropriée x ^ y
solution, et PointF
enveloppements ValueType.GetHashCode()
.
Rectangle
a très particulière (((X ^ ((Y << 13) | (Y >> 19))) ^ ((Width << 26) | (Width >> 6))) ^ ((Height << 7) | (Height >> 25)))
expression pour le code de hachage, qui semble fonctionner comme prévu.
Edit 2:
'Système.Double' a une jolie mise en œuvre, car il ne considère pas chaque bit aussi important
public override unsafe int GetHashCode() //from System.Double
{
double num = this;
if (num == 0.0)
{
return 0;
}
long num2 = *((long*) &num);
return (((int) num2) ^ ((int) (num2 >> 32)));
}
- C'est bien de viser à minimiser les collisions, mais votre code doit attendre d'eux; ils seront toujours arriver
- Hachages en découdront -
int
a une petite plage de valeurs possibles quedouble
, et c'est encore plus petit comparativement àdouble
xdouble
. Aussi, vous pourriez envisager un looser comparaison d'égalité - en raison de l'arrondissement, à deux les valeurs flottantes peuvent être très proches l'un de l'autre (ce que toute personne faisant une comparaison "à l'œil" permettrait de considérer l'égalité), mais encore de ne pas être exactement égal. - Ce n'est pas juste que (A,B) entre en collision avec (B,A). Grâce au fait que X^X --> 0 (C,C) entre en collision avec l'ensemble (D,D), et qui est beaucoup plus grand espace de collisions.
- double possible de Créer un hashcode de deux nombres
Vous devez vous connecter pour publier un commentaire.
Jon skeet a ce couvert:
Quel est le meilleur algorithme pour un substituée Système.Objet.GetHashCode?
Aussi, changer votreEquals(object)
mise en œuvre pour:Notez cependant que cela pourrait percevoir un type dérivé à être égaux. Si vous ne voulez pas que vous auriez à comparer le runtime typeMerci pour le tuyau, c'est un struct, LukHother.GetType()
avectypeof(FVector2)
(et n'oubliez pas la nullité des contrôles)Resharper a une belle génération de code pour l'égalité et le code de hachage, donc si vous avez resharper vous pouvez laisser faire sa chose
Equals(object)
mise en œuvre ne peut pas être modifiée pour utiliseras
. Il n'y a rien de mal avec l'OP actuelleEquals(object)
méthode.Double.GetHashCode()
vous remarquerez qu'un examen plus attentif important bits est utilisé, et je tiens à le suivre.Collisions de hachage ne pas faire des ravages dans une collection de dictionnaires. Ils vont réduire l'efficacité si vous êtes assez malheureux pour les obtenir, mais les dictionnaires ont à faire face avec eux.
Les Collisions doivent être rares, si c'est possible, mais ils ne signifient pas la mise en œuvre est incorrect. XORs sont souvent mauvais pour les raisons que vous avez donné (haute collisions) - ohadsc a posté un exemple que j'ai donné avant pour une alternative, ce qui doit être fine.
Note qu'il serait impossible à mettre en œuvre
Vec2
avec pas collisions - il y a seulement 232 valeurs de retour possibles à partir deGetHashCode
, mais il y a plutôt plus possible les valeurs X et Y, même après que vous avez retiré de NaN et de valeurs infinies...Eric Lippert a un blog sur
GetHashCode
qui pourraient vous être utiles.Ce sont des limites raisonnables pour les coordonnées?
Sauf s'il peut être possible toutes les valeurs de type entier, vous pourriez tout simplement:
const SOME_LARGE_NUMBER=100000;
retour SOME_LARGE_NUMBER * x + y;
int
s trop avecint.MaxValue
avecunchecked
clauseSi la taille de votre code de hachage est moindre que celui de la taille de votre structure, puis les affrontements sont inévitables, de toute façon.
Les codes de hachage est une approche qui fonctionne pour entier coordonnées, mais n'est pas recommandé pour les valeurs à virgule flottante. Avec des coordonnées d'un point, on peut créer un point-set/piscine en utilisant une séquence ordonnée de la structure.
Une séquence triée est une feuille version équilibrée arbre binaire.
Ici les clés seraient les coordonnées d'un point.
GetHashCode()
non déterministe, mais je ne comprends pas comment vous proposons de contourner ce problème.IEquatable<>
et ainsi de hachage est nécessaire de remplacer. Pouvez-vous s'il vous plaît montrer un peu de code pour que nous puissions comprendre de quoi vous parlez.