donné deux chaînes différentes, est-ce toujours le cas que est-ce que le nombre d'entiers distincts est inférieur au nombre de chaînes distinctes? s.gethashcode ()! = s1.gethashcode () ?
3 Réponses :
non. Tout comme une expérience de pensée simple: combien de chaînes y a-t-il (indice: beaucoup plus de 2 32 et ainsi combien de codes de hachage uniques peuvent y avoir (indice: 2 32 . Voir le problème? )
Les codes de hachage sont juste requis pour être égaux chaque fois que Notez l'omission des variantes respectives. Ce n'est pas une équivalence, juste deux implications.
Pour citer Documentation :
Une fonction de hachage doit avoir les propriétés suivantes:
Si deux objets comparent comme étant égales, la méthode GetHashCode pour chaque objet doit renvoyer la même valeur. Toutefois, si deux objets ne comparent pas comme étant égaux, les méthodes GetHashCode pour les deux objets ne doivent pas nécessairement renvoyer différentes valeurs.
La méthode gethashcode pour un objet doit renvoyer systématiquement le même code de hachage tant qu'il n'y a aucune modification à l'état d'objet qui détermine la valeur de retour de la méthode des égaux de l'objet. Notez que cela n'est vrai que pour l'exécution actuelle d'une application et qu'un code de hachage différent peut être renvoyé si l'application est à nouveau exécutée.
Pour la meilleure performance, une fonction de hachage doit générer une distribution aléatoire pour toutes les entrées.
est égal à renvoie que les deux objets sont égaux. En outre, chaque fois que deux codes de hachage sont pas égaux, les objets eux-mêmes ne peuvent pas être égaux. Il n'y a pas d'autre exigence, mais ils doivent doivent être bien distribués afin que les tables de hachage puissent bien performer. Donc, fondamentalement, c'est:
Le problème que vous faites allusion à votre ligne d'ouverture est connu sous le nom de Principe du trou de Pigeon - Plus de pigeons que Vous avez des trous de pigeon.
Je sais, mais apparemment, tous les lecteurs ne peuvent, certes. Je l'ai édité.
Pour ajouter à la déclaration de @ Joey, vous Principalement ne peut pas que les hashcodes soient toujours inégales.
Il y a 2 ^ 32 codes de hachage possibles mais des chaînes d'entrée infinies.
Les collisions de hachage sont garantis pour arriver suffisamment (2 ^ 32 + 1) valeurs d'entrée.
En fait, les collisions de hachage sont beaucoup plus communes qu'on pourrait penser à la Problème d'anniversaire . Lorsque j'ai fait le math, un moment de retour pour un système utilisant des codes de hachage de 64 bits (qui ont Way plus de valeurs de hash possibles que des codes de hachage 32 bits, pas seulement doublement comme on pourrait penser naïvement), avec 100 millions de valeurs d'entrée Il était très possible qu'il y aurait au moins une collision de hasch. Je pense que la probabilité était d'environ 1%.
Non garanti, mais en moyenne, il y a 1 collision par (2 ^ 32 + 1) valeurs d'entrée
@ fjch1997 J'en doute à ce sujet. Si la fonction de hachage est utilisée pour calculer le hachage de données de chaîne, le paradoxe anniversaire prendrait bien avant le point que vous avez mis en évidence. Si mon calcul est correct, vous devez avoir au moins 50% de probabilité de collision donnée 2 ^ 16 entrées (en supposant que l'espace hash est 2 ^ 32) quelle que soit la fonction de hachage: en.wikipedia.org/wiki/birthday_problem (qui dit si vous avez (2 ^ 32) + 1 entrées, alors vous obtenez ma clématiquement une collision qui s'est produite. Est Toujours dire que vous avez 4 pièces de monnaie et trois portefeuille, un portefeuille contiendra une pièce de monnaie.
@Skary tu as raison. Merci pour l'explication!
aussi loin que je connais Vous ne pouvez donc pas avoir de duplicate de hashcode (dans la même appdomaine) à un moment donné, mais vous pourriez avoir un doupleur au fil du temps (le même index peut être attribué plus d'une fois lors de l'exécution de l'application).
La question est également discutée ici:
Implémentation par défaut pour objet.GetHashCode () objet.gethashcode () ne fournit pas une fonction de hachage sur l'objet (donc je suppose que la considération de Joey n'est pas correcte dans ce cas), il ne renvoie qu'une index unique attribuée à l'objet par CLR lorsque l'objet est créé et libéré lorsque l'objet est déposé collecté.
Voir blogs.msdn .COM / B / ERICLIPPERT / Archive / 2011/02/28 / ...