Entrer dans la zone grise de la "sur/hors sujet", mais nécessaires pour éviter toute confusion concernant Oscar Reyes suggestion que plus les collisions de hachage est une bonne chose, car cela réduit le nombre d'éléments dans la table de hachage. Je peut mal comprendre ce que Oscar est dire, mais je ne semble pas être le seul: kdgregory, delfuego, Nash0, et j'ai tous semblent partager le même (sig)de la compréhension.
Si je comprends ce que Oscar est dit à propos de la même classe avec le même hashcode, il propose qu'une seule instance d'une classe avec un hashcode sera inséré dans la table de hachage. Par exemple, si j'ai une instance de SomeClass avec un hashcode de 1 et une deuxième instance de SomeClass avec un hashcode de 1, une seule instance de SomeClass est inséré.
La Java pastebin exemple à http://pastebin.com/f20af40b9 semble indiquer ci-dessus correctement résume ce que Oscar propose.
Indépendamment de toute compréhension ou d'incompréhension, ce qui se passe est différentes instances de la même classe de ne pas obtenir inséré qu'une seule fois dans la table de hachage si elles ont le même hashcode - pas jusqu'à ce qu'elle a déterminé si les touches sont égaux ou non. Le hashcode contrat exige que l'égalité des objets ont le même hashcode; toutefois, il ne nécessite pas que l'inégalité des objets sont différents hashcodes (même si cela peut être souhaitable pour d'autres raisons)[1].
L'pastebin.com/f20af40b9 exemple (Oscar renvoie au moins à deux reprises), mais légèrement modifié pour utiliser JUnit affirmations plutôt que printlines. Cet exemple est utilisé à l'appui de la proposition que le même hashcodes provoquer des collisions et lorsque les classes sont les mêmes qu'une entrée est créée (par exemple, une seule Chaîne de caractères dans ce cas précis):
@Test
public void shouldOverwriteWhenEqualAndHashcodeSame() {
String s = new String("ese");
String ese = new String("ese");
// same hash right?
assertEquals(s.hashCode(), ese.hashCode());
// same class
assertEquals(s.getClass(), ese.getClass());
// AND equal
assertTrue(s.equals(ese));
Map map = new HashMap();
map.put(s, 1);
map.put(ese, 2);
SomeClass some = new SomeClass();
// still same hash right?
assertEquals(s.hashCode(), ese.hashCode());
assertEquals(s.hashCode(), some.hashCode());
map.put(some, 3);
// what would we get?
assertEquals(2, map.size());
assertEquals(2, map.get("ese"));
assertEquals(3, map.get(some));
assertTrue(s.equals(ese) && s.equals("ese"));
}
class SomeClass {
public int hashCode() {
return 100727;
}
}
Cependant, le hashcode n'est pas l'histoire complète. Ce que le pastebin exemple néglige le fait que les deux s et ese sont égaux: ils sont à la fois la chaîne "ese". Ainsi, l'insertion ou de l'obtention du contenu de la carte à l'aide de s ou ese ou "ese" que les clés sont toutes équivalentes, car s.equals(ese) && s.equals("ese").
Un deuxième test démontre qu'il est erroné de conclure que les mêmes hashcodes sur la même classe est la raison pour laquelle la clé -> valeur s -> 1 est remplacé par ese -> 2 lorsque map.put(ese, 2) est appelé en tester un. Dans l'essai deux, s et ese ont toujours le même hashcode (vérifiée par assertEquals(s.hashCode(), ese.hashCode());) ET ils sont de la même classe. Toutefois, s et ese sont MyString cas dans ce test, pas de Java String des cas, avec la seule différence pertinente pour ce test étant l'égale: String s equals String ese dans le test ci-dessus, tandis que MyStrings s does not equal MyString ese dans le test de deux:
@Test
public void shouldInsertWhenNotEqualAndHashcodeSame() {
MyString s = new MyString("ese");
MyString ese = new MyString("ese");
// same hash right?
assertEquals(s.hashCode(), ese.hashCode());
// same class
assertEquals(s.getClass(), ese.getClass());
// BUT not equal
assertFalse(s.equals(ese));
Map map = new HashMap();
map.put(s, 1);
map.put(ese, 2);
SomeClass some = new SomeClass();
// still same hash right?
assertEquals(s.hashCode(), ese.hashCode());
assertEquals(s.hashCode(), some.hashCode());
map.put(some, 3);
// what would we get?
assertEquals(3, map.size());
assertEquals(1, map.get(s));
assertEquals(2, map.get(ese));
assertEquals(3, map.get(some));
}
/**
* NOTE: equals is not overridden so the default implementation is used
* which means objects are only equal if they're the same instance, whereas
* the actual Java String class compares the value of its contents.
*/
class MyString {
String i;
MyString(String i) {
this.i = i;
}
@Override
public int hashCode() {
return 100727;
}
}
Basé sur un commentaire plus tard, Oscar semble à l'inverse de ce qu'il a dit plus tôt, et reconnaît l'importance d'égal à égal. Cependant, il semble encore la notion d'égale que c'est ce qui importe, pas la "même catégorie", n'est pas claire (l'emphase est mienne):
"Pas vraiment. La liste est créée que si le hash est le même, mais la clé est différente. Par exemple, si une Chaîne de caractères donner hashcode 2345 et Entier et donne le même hashcode 2345, alors l'entier est inséré dans la liste parce que la Chaîne.equals( Entier ) est faux. Mais si vous avez la même classe ( ou au moins .equals vrai ) alors la même entrée est utilisée. Par exemple, new String("un") et " new String("un") utilisés comme des clés, utiliser la même entrée. En fait ce qui est le point de l'ENSEMBLE de la table de hachage en premier lieu! Voyez vous-même: pastebin.com/f20af40b9 – Oscar de los Reyes"
rapport au commentaire précédent qui traitent explicitement de l'importance à l'identique de la classe et même hashcode, sans mention d'égal à égal:
"@delfuego: Voir par vous-même: pastebin.com/f20af40b9 Donc, dans cette question de la même classe est utilisé ( attendez une minute, dans la même classe est utilisé à droite? ) Ce qui implique que lorsque la même valeur de hachage est utilisée de la même entrée est utilisée et il n'y a pas de "liste" d'entrées. – Oscar De Los Reyes"
ou
"En fait, ce serait d'augmenter les performances. Le plus de collisions eq moins d'entrées dans la table de hachage eq. moins de travail à faire. N'est pas le hachage ( qui a l'air bien ), ni la table de hachage ( qui fonctionne très bien ), je parierais que c'est sur la création de l'objet où la performance est dégradant. – Oscar De Los Reyes"
ou
"@kdgregory: Oui, mais seulement si la collision se produit avec différentes classes, de la même classe ( ce qui est le cas ) de la même entrée est utilisée. – Oscar De Los Reyes"
Encore une fois, je peut mal comprendre ce que Oscar était en fait en train de dire. Cependant, ses commentaires d'origine ont causé assez de confusion qu'il semble prudent de tout clair avec quelques explicite les tests, donc il n'y a pas de doutes qui subsistent.
[1] - De Efficace Java, Deuxième Édition par Joshua Bloch:
Chaque fois qu'elle est invoquée sur le même objet plus d'une fois au cours de l'exécution d'une application, la méthode hashCode doit constamment revenir l'
même entier, pas fourni d'information utilisés dans l'égalité de s des comparaisons sur les
l'objet est modifié. Cet entier n'a pas besoin de rester cohérent à partir d'une exécution d'une application à une autre exécution de la même application.
Si deux objets sont égaux selon l'égalité s(Obj ect) méthode, puis en appelant la méthode hashCode sur chacun des deux objets doivent produire les mêmes
résultat sous forme d'entier.
Il n'est pas nécessaire que si deux objets sont inégales selon l'égalité s(Objet) de la méthode, puis en appelant la méthode hashCode sur chacun des deux objets
doit produire integer distinctes résultats. Toutefois, le programmeur doit être
conscient que la production d'un integer distinctes résultats de l'inégalité des objets peut améliorer
la performance de tables de hachage.
