Implémentation interne de java.util.HashMap et HashSet

Question

J'ai essayé de comprendre l'implémentation interne de java.util.HashMap et java.util.HashSet.

Voici les nouveaux doutes surgissent dans mon esprit pendant un certain temps:

1. Quel est l'importance du @Override public int hashcode() dans un HashMap/HashSet? Où est ce code de hachage utilisé en interne?
2. J'ai généralement vu la clé de la HashMap être String comme myMap<String,Object>. Puis-je mapper les valeurs par rapport à someObject (au lieu de String) comme myMap<someObject, Object>? Quels sont tous les contrats que j'ai besoin d'obéir pour que cela se passe avec succès?

Merci d'avance!

EDIT:

1. Sommes-nous en train de dire que le code de hachage de la clé (vérifier!) Est la chose réelle contre laquelle la valeur est mise en correspondance dans la table de hachage? Et quand nous faisons myMap.get(someKey); java appelle en interne someKey.hashCode() pour obtenir le nombre dans la table de hachage à rechercher la valeur résultante?

Réponse: Oui.

EDIT 2:

2. Dans un java.util.HashSet, d'où est la clé générée pour la table de hachage? Est-ce de l'objet que nous ajoutons par exemple. mySet.add(myObject); puis myObject.hashCode() va décider où cela est placé dans la table de hachage? (car nous ne donnons pas de clés dans un HashSet).

Réponse: L'objet ajouté devient la clé. La valeur est dummy!

Answer 1

La réponse à la question 2 est facile - oui, vous pouvez utiliser n'importe quel objet que vous aimez. Les mappes qui ont des clés de type chaîne sont largement utilisées car ce sont des structures de données typiques pour les services de nommage. Mais en général, vous pouvez mapper deux types comme Map<Car,Vendor> ou Map<Student,Course>.

Pour la méthode hashcode(), c'est comme avant - chaque fois que vous remplacez equals(), vous devez remplacer hashcode() pour obéir au contrat. D'un autre côté, si vous êtes satisfait de l'implémentation standard de equals(), vous ne devriez pas toucher hashcode() (car cela pourrait casser le contrat et aboutir à des hashcodes identiques pour les objets inégaux).

Note pratique: eclipse (et probablement d'autres IDE) peut générer automatiquement une paire d'implémentations de type equals() et hashcode() pour votre classe, basée uniquement sur les membres de la classe.

Modifier

Pour votre autre question: oui, exactement. Regardez le code source de HashMap.get (clé d'objet); il appelle la clé.hashcode pour calculer la position (bin) dans la table de hachage interne et renvoie la valeur à cette position (s'il y en a une). Mais attention aux méthodes hashcode/equals 'handmade' - si vous utilisez un objet comme clé, assurez-vous que le hashcode ne change pas par la suite, sinon vous ne trouverez plus les valeurs mappées. En d'autres termes, les champs que vous utilisez pour calculer l'égalité et le code hash doivent être définitifs (ou 'inchangeable' après la création de l'objet).

Supposons que nous ayons un contact avec String name et String phonenumber et que nous utilisions les deux champs pour calculer l'équation() et le hashcode(). Maintenant, nous créons "John Doe" avec son numéro de téléphone mobile et le mapper à son magasin de beignets préféré. hashcode() est utilisé pour calculer l'index (bin) dans la table de hachage et c'est là que le beignet est stocké.

Maintenant, nous apprenons qu'il a un nouveau numéro de téléphone et nous changeons le champ de numéro de téléphone de l'objet John Doe. Cela entraîne un nouveau code de hachage. Et ce hashcode se résout à un nouvel index de table de hachage - qui n'est généralement pas la position où la boutique Donut préférée de John Does a été stockée. Le problème est clair: dans ce cas, nous voulions faire correspondre "John Doe" à la boutique Donut, et non "John Doe avec un numéro de téléphone spécifique". Donc, nous devons être prudent avec equals/hashcode autogenerated pour s'assurer qu'ils sont ce que nous voulons vraiment, parce qu'ils pourraient utiliser des champs non désirés, introduisant des problèmes avec HashMaps et HashSets.

Edit 2

Si vous ajoutez un objet à un HashSet, l'objet est la clé de la table de hachage interne, la valeur est définie mais non utilisée (juste une instance statique de l'objet). Voici la mise en œuvre de l'openjdk 6 (b17):

// Dummy value to associate with an Object in the backing Map 
private static final Object PRESENT = new Object(); 
private transient HashMap<E,Object> map; 

public boolean add(E e) { 
    return map.put(e, PRESENT)==null; 
} 

Answer 2

Quelle est l'importance du hashcode public @Override() dans un HashMap/HashSet?

Cela permet à l'instance de la carte de produire un code de hachage utile en fonction du contenu de la carte. Deux cartes avec le même contenu produiront le même code de hachage. Si le contenu est différent, le code de hachage sera différent.

Où est ce code de hachage utilisé en interne?

Jamais. Ce code n'existe que pour vous permettre d'utiliser une carte comme clé dans une autre carte.

Puis-je mapper les valeurs contre someObject (au lieu de String) comme myMap<someObject, Object>?

Oui mais someObject doit être une classe, pas un objet (votre nom l'indique que vous voulez passer dans l'objet, il devrait être SomeObject de préciser que vous faites référence au type).

De quels contrats ai-je besoin pour que cela se passe avec succès?

La classe doit implémenter hashCode() et equals().

[EDIT]

disons-nous que le code de hachage de la clé (vérifier!) Est la chose réelle contre laquelle la valeur est mise en correspondance dans la table de hachage?

Oui.

Answer 3

Il existe une relation complexe entre equals(), hashcode() et les tables de hachage en général en Java (et .NET aussi, d'ailleurs). Pour citer la documentation:

public int hashCode()

Renvoie une valeur de code de hachage pour l'objet. Cette méthode est prise en charge au profit des tables de hachage telles que celles fournies par java.util.Hashtable.

Le contrat général de hashCode est:

• Chaque fois qu'il est invoqué sur le même objet plus d'une fois lors d'une exécution d'une application Java, la méthode hashCode doit revenir constamment le même entier, fourni aucune information utilisée en égales, les comparaisons sur l'objet sont modifiées. Cet entier n'a pas besoin de rester cohérent d'une exécution d'une application à une autre exécution de la même application.
• Si deux objets sont égaux selon la méthode equals (Object), l'appel de la méthode hashCode sur chacun des deux objets doit produire le même résultat entier.
• Il n'est pas obligatoire que si deux objets sont inégaux selon la méthode égale (java.lang.Object), l'appel de la méthode hashCode sur chacun des deux objets doit produire des résultats entiers distincts. Cependant, le programmeur doit être conscient que la production de résultats entiers distincts pour des objets inégaux peut améliorer les performances des tables de hachage.

Autant que cela est raisonnablement possible, la méthode hashCode définie par la classe Object renvoie des entiers distincts pour des objets distincts. (Ceci est généralement mis en œuvre en convertissant l'adresse interne de l'objet dans un entier, mais cette technique de mise en œuvre n'est pas nécessaire par le langage de programmation Java ™.)

La ligne

@Overrides public int hashCode() 

juste indique que la méthode hashCode() est substituée.C'est habituellement un signe qu'il est sûr d'utiliser le type comme clé dans un HashMap.

Et oui, vous pouvez utiliser aesily tout objet qui obéit au contrat de equals() et hashCode() dans un HashMap comme la clé.

Answer 4

1. Tout Object en Java doit avoir une méthode hashCode(); HashMap et HashSet ne sont aucune exécution. Ce code de hachage est utilisé si vous insérez la carte ou l'ensemble de hachage dans une autre carte/ensemble de hachage. Un type de classe peut être utilisé comme clé dans un HashMap/HashSet. Cela nécessite que la méthode hashCode() renvoie des valeurs égales pour des objets égaux, et que la méthode equals() soit implémentée en fonction du contrat (réflexif, transitif, symétrique). Les implémentations par défaut de Object obéissent déjà à ces contrats, mais vous pouvez les remplacer si vous souhaitez une égalité de valeur au lieu de l'égalité de référence.

Answer 5

Oui. Vous pouvez utiliser n'importe quel objet comme clé dans une HashMap. Pour ce faire, voici les étapes à suivre.

1. Le remplacement est égal à.

2. Overhide hashCode.

Les contrats pour les deux méthodes sont très clairement mentionnés dans la documentation de java.lang.Object. Et oui la méthode hashCode() est utilisée en interne par HashMap et donc le retour de la valeur correcte est important pour les performances.

Voici la méthode hashCode() de HashMap

public V put(K key, V value) { 
    if (key == null) 
     return putForNullKey(value); 
    int hash = hash(key.hashCode()); 
    int i = indexFor(hash, table.length); 
    for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
     Object k; 
     if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
      V oldValue = e.value; 
      e.value = value; 
      e.recordAccess(this); 
      return oldValue; 
     } 
    } 

    modCount++; 
    addEntry(hash, key, value, i); 
    return null; 
} 

Il est clair à partir du code ci-dessus que hashCode de chaque touche est non seulement utilisé pour hashCode() de la carte, mais aussi pour trouver le seau placer la clé, la paire de valeurs. C'est pourquoi hashCode() est lié à la performance de la HashMap

Answer 6

Aaron Digulla est absolument correct. Une remarque supplémentaire intéressante que les gens ne semblent pas réaliser est que la méthode hashCode() de l'objet clé n'est pas utilisée verbatim. Il est, en fait, repris par le HashMap, c'est-à-dire qu'il appelle hash(someKey.hashCode)), où hash() est une méthode de hachage interne.

Pour voir cela, un coup d'oeil à la source: http://kickjava.com/src/java/util/HashMap.java.htm

La raison est que certaines personnes mettent en œuvre la fonction hashCode() mal et le hachage() donne une meilleure répartition de hachage. C'est essentiellement fait pour des raisons de performance.

Answer 7

En réponse à la question 2, bien que vous puissiez avoir n'importe quelle classe qui peut être utilisée comme clé dans Hashmap, la meilleure pratique consiste à utiliser des classes immuables comme clés pour le HashMap. Ou à tout le moins, si votre implémentation "hashCode" et "égal" dépend de certains attributs de votre classe, vous devez veiller à ne pas fournir de méthodes pour modifier ces attributs.

Answer 8

Les conteneurs de hachage tels que HashMap et HashSet offrent un accès rapide aux éléments qui y sont stockés en divisant leur contenu en "compartiments".

Par exemple, la liste des nombres: 1, 2, 3, 4, 5, 6, 7, 8 stockée dans un List ressemblerait (conceptuellement) en mémoire quelque chose comme: [1, 2, 3, 4, 5, 6, 7, 8].

Le stockage du même ensemble de nombres dans un Set ressemblerait plus à ceci: [1, 2] [3, 4] [5, 6] [7, 8]. Dans cet exemple, la liste a été divisée en 4 compartiments.Maintenant, imaginez que vous voulez trouver la valeur 6 sur les deux List et Set. Avec une liste vous devriez commencer au début de la liste et vérifier chaque valeur jusqu'à ce que vous arriviez à 6, cela prendra 6 étapes. Avec un ensemble que vous trouvez le seau correct, le vérifier chacun des articles dans ce seau (seulement 2 dans notre exemple) en faisant un processus en trois étapes. La valeur de cette approche augmente considérablement le nombre de données que vous avez.

Mais attendez comment savions-nous quel seau regarder? C'est là qu'intervient la méthode hashCode. Pour déterminer le compartiment dans lequel rechercher un élément, les conteneurs de hachage Java appellent hashCode puis appliquez une fonction au résultat. Cette fonction tente d'équilibrer le nombre de compartiments et le nombre d'éléments pour la recherche la plus rapide possible.

Lors de la recherche une fois que le bon compartiment a été trouvé, chaque élément de ce compartiment est comparé un à la fois comme dans une liste. C'est pourquoi lorsque vous remplacez hashCode, vous devez également remplacer equals. Donc, si un objet de n'importe quel type a à la fois une méthode equals et une méthode hashCode, il peut être utilisé comme une clé dans un Map ou une entrée dans un Set. Il y a un contrat qui doit être suivi pour mettre en œuvre ces méthodes correctement le texte canonique à ce sujet est de grand livre Effective Java de Josh Bloch: Item 8: Always override hashCode when you override equals

Answer 9

méthode hashCode pour les classes de collecte comme HashSet, Hashtable, HashMap etc - code Hash retourne le nombre entier pour l'objet qui est pris en charge pour le hachage. Il est implémenté en convertissant l'adresse interne de l'objet en un entier. La méthode de code de hachage doit être substituée dans chaque classe qui remplace la méthode equals. Trois contact général pour la méthode hashCode

• Pour deux objets égaux selon. Pour égaliser la méthode, puis en appelant HashCode pour les deux objets, il doit produire la même valeur entière.

• S'il est appelé plusieurs fois pour un seul objet, il doit renvoyer une valeur entière constante.

• Pour deux objets inégaux acc. Pour égaliser la méthode, puis appeler la méthode HashCode pour les deux objets, il n'est pas obligatoire qu'elle produise une valeur distincte.