Je ne l'ai pas implémenté et je n'ai pas parlé à ceux qui l'ont fait. Mais je peux signaler quelques choses.
(Avant de continuer, notez que je parle ici spécifiquement des codes de hachage pour l'équilibrage des tables de hachage où le contenu de la table est choisi par des utilisateurs non hostiles. la vérification de la redondance ou la garantie d'une bonne performance d'une table de hachage lorsque certains utilisateurs montent des attaques par déni de service contre le fournisseur de tables dépassent le cadre de cette discussion.)
L'algorithme met en œuvre le contrat requis de GetHashCode. Cela pourrait être sous-optimal pour vos objectifs, mais c'est légal. Tout ce qui est requis est que les choses qui comparent égal ont des codes de hachage égaux.
Alors, quels sont les «bons à avoir» en plus de ce contrat? Une bonne implémentation du code de hachage doit être:
1) Rapide. Très vite! Rappelez-vous, tout le point du code de hachage en premier lieu à rapidement trouver un emplacement relativement vide dans une table de hachage. Si le calcul O (1) du code de hachage est en pratique plus lent que le temps O (n) pris pour effectuer la recherche naïvement alors la solution de code de hachage est une perte nette.
2) Bien répartie sur l'espace des entiers de 32 bits pour la distribution donnée des entrées. Plus la distribution est mauvaise, plus la recherche linéaire naïve de la table de hachage sera bonne.Alors, comment feriez-vous un algorithme de hachage pour les types de valeurs arbitraires étant donné que ces deux conflits de objectifs? Chaque fois que vous dépensez sur un algorithme de hachage complexe qui garantit une bonne distribution, le temps est mal dépensé.
Une suggestion courante consiste à "hacher tous les champs et ensuite XOR ensemble les codes de hachage résultants". Mais c'est implorer la question; XOR deux 32 bits ints ne donne une bonne distribution lorsque les entrées elles-mêmes sont très bien distribués et non liés les uns aux autres, et qui est un scénario improbable:
// (Updated example based on good comment!)
struct Control
{
string name;
int x;
int y;
}
Quelle est la probabilité que x et y sont bien distribué sur toute la gamme des entiers 32 bits? Très lent. Les chances sont beaucoup mieux qu'ils sont à la fois petit et près de l'autre, auquel cas XOR leurs codes de hachage rend les choses ensemble pire, pas mieux. La coexistence d'entiers proches les uns des autres met à zéro la plupart des bits.
De plus, c'est O (n) dans le nombre de champs! Un type de valeur avec beaucoup de petits champs prendrait un temps relativement long pour calculer le code de hachage.
Fondamentalement, la situation dans laquelle nous sommes ici est que l'utilisateur n'a pas fourni lui-même une implémentation de code de hachage; soit ils s'en fichent, soit ils ne s'attendent pas à ce que ce type soit utilisé comme clé dans une table de hachage. Étant donné que vous avez aucune information sémantique sur le type, quelle est la meilleure chose à faire? La meilleure chose à faire est ce qui est rapide et donne de bons résultats la plupart du temps.
La plupart du temps, deux instances de struct qui diffèrent diffèrent en plus de leurs champs, et pas seulement un de leurs champs, de sorte que la cueillette un d'entre eux et en espérant que c'est celui qui est différent semble raisonnable. La plupart du temps, deux instances struct qui diffèrent auront une certaine redondance dans leurs champs, donc combiner les valeurs de hachage de plusieurs champs ensemble est susceptible de diminuer, et non d'augmenter, l'entropie dans la valeur de hachage, même si elle consomme le temps que l'algorithme de hachage est conçu pour enregistrer.
Comparez cela avec la conception de types anonymes en C#. Avec les types anonymes, nous savons qu'il est fort probable que le type soit utilisé comme clé pour une table. Nous savons qu'il est très probable qu'il y aura une redondance entre les instances de types anonymes (parce qu'elles sont le résultat d'un produit cartésien ou d'une autre jointure). Et donc, nous combinons les codes de hachage de tous les champs en un seul code de hachage. Si cela vous donne de mauvaises performances en raison du nombre excessif de codes de hachage calculés, vous êtes libre d'utiliser un type nominal personnalisé plutôt que le type anonyme.
Votre exemple de Point n'était pas bon. Vous obtiendrez un «bon» hash de celui-là. J'ai laissé un post pour décrire pourquoi c'est différent. –
En supposant que vous ne faites pas juste un XOR, la combinaison de plusieurs hashcodes corrélés ne diminuera généralement pas l'entropie - et il n'y a pas de raison particulièrement pressante de faire un XOR. –
@EamonNerbonne: Le seul avantage que je peux voir pour XOR est que dans les langages qui n'ont aucun moyen de demander une arithmétique signée "non vérifiée", il permet la gamme complète des valeurs de sortie sans masquage manuel. Sinon, c'est dans tous les sens que je peux voir inférieur à '+ '. L'addition est aussi rapide que xor dans les langages qui peuvent supporter une arithmétique signée non vérifiée, et fonctionne correctement dans les cas courants où deux champs sont toujours égaux ou diffèrent par une constante. – supercat