Les développeurs n'ont pas à travailler autour de la question de collisions de hachage dans la table de hachage afin de réaliser le programme de justesse.
Il ya un couple de choses importantes à comprendre ici:
- Les Collisions sont inhérents à la fonction de hachage, et ils doivent l'être. Le nombre de valeurs possibles (Chaînes dans votre cas, mais elle s'applique à d'autres types d') est beaucoup plus importante que la gamme de nombres entiers.
- Chaque utilisation de hachage a une façon de gérer les collisions, et le Java Collections (y compris HashMap) n'est pas une exception.
- Le hachage n'est pas impliqué dans l'égalité des tests. Il est vrai que les objets égaux doivent avoir les mêmes hashcodes, mais l'inverse n'est pas vrai: beaucoup de valeurs ont le même hashcode. Donc, ne pas essayer en utilisant un hashcode comparaison comme un substitut pour l'égalité. Les Collections ne sont pas. Ils utilisent de hachage pour sélectionner une sous-collection (appelé un seau dans la Java des Collections de monde), mais ils utilisent .equals() pour vérifier l'égalité.
- Non seulement vous n'avez pas à vous soucier de collisions causant des résultats incorrects dans une collection, mais pour la plupart des applications, vous aussi *en général* de ne pas avoir à vous soucier de la performance de Java haché Collections de faire un assez bon travail de gestion de la hashcodes.
- Mieux encore, pour le cas vous m'avez demandé (Chaînes de caractères comme des touches de), vous n'avez même pas à vous soucier de la hashcodes eux-mêmes, parce que Java de la classe String génère une assez bonne hashcode. Alors ne la plupart des classes Java.
Un peu plus en détail, si vous le souhaitez:
La façon de hachage œuvres (en particulier, dans le cas de haché collections de Java table de hachage, qui est ce que vous m'avez demandé) est-ce:
La table de hachage stocke les valeurs que vous donnez en une collection de sous-collections, appelé seaux. Ce sont effectivement mis en œuvre comme les listes chaînées. Il y a un nombre limité de ces: iirc, de 16 à commencer par défaut, et le nombre augmente à mesure que vous mettez plus d'objets dans la carte. Il devrait toujours y avoir plus de seaux de valeurs. Pour donner un exemple, en utilisant les valeurs par défaut, si vous ajoutez 100 entrées d'une table de hachage, il y aura 256 seaux.
Chaque valeur qui peut être utilisé comme une clé, une carte doit être en mesure de générer une valeur entière, appelé le hashcode.
La table de hachage utilise cette hashcode pour sélectionner un seau. En fin de compte, cela signifie de prendre la valeur entière modulo le nombre de seaux, mais avant cela, Java de la table de hachage est une méthode interne (appelés hash()), ce qui modifie la hashcode pour réduire certaines sources connues de l'agglomération.
Lorsque l'on cherche une valeur, la table de hachage sélectionne le seau, et recherche l'élément un par un linéaire de recherche de la liste liée, à l'aide de .equals().
Donc: vous n'avez pas à travailler autour de collisions pour la correction, et généralement vous n'avez pas à vous inquiéter au sujet de leur rendement, et si vous êtes en utilisant natif des classes Java (comme String), vous n'avez pas à vous soucier de la génération de la hashcode valeurs.
Dans le cas où vous n'avez qu'à écrire votre propre méthode hashcode (ce qui signifie que vous avez écrit une classe avec un composé de la valeur, comme un prénom/nom de la paire), les choses deviennent un peu plus compliqué. C'est tout à fait possible de se tromper ici, mais ce n'est pas la science de fusée. Tout d'abord, sachez ceci: la seule chose que vous devez faire afin d'assurer l'exactitude est de s'assurer que les objets égaux rendement égal hashcodes. Donc, si vous écrivez un hashcode() méthode pour votre classe, vous devez également écrire une méthode equals (), et vous devez examiner les mêmes valeurs de chaque.
Il est possible d'écrire un hashcode() méthode qui est mauvaise, mais bon, je veux dire qu'il serait à même de satisfaire les "objets égaux doivent rendement égal hashcodes" contrainte, mais toujours effectuer très mal, par le fait d'avoir beaucoup de collisions.
L'canonique dégénérer pire des cas, ce serait d'écrire une méthode qui retourne une valeur constante (par exemple, 3) pour tous les cas. Cela signifie que chaque valeur doit être haché dans le même seau.
Il serait encore du travail, mais les performances ne se dégradent que d'une liste chaînée.
De toute évidence, vous n'aurez pas à écrire une terrible hashcode() de la méthode. Si vous utilisez un décent IDE, il est capable de générer pour vous. Depuis StackOverflow aime code, voici le code pour le prénom/nom de la classe ci-dessus.
public class SimpleName {
private String firstName;
private String lastName;
public SimpleName(String firstName, String lastName) {
super();
this.firstName = firstName;
this.lastName = lastName;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result
+ ((lastName == null) ? 0 : lastName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
SimpleName other = (SimpleName) obj;
if (firstName == null) {
if (other.firstName != null)
return false;
} else if (!firstName.equals(other.firstName))
return false;
if (lastName == null) {
if (other.lastName != null)
return false;
} else if (!lastName.equals(other.lastName))
return false;
return true;
}
}
