Analyse du principe de Hashmap en Java

Regardons d'abord une question d'entrevue:

Une série de paires de valeurs clés stockées dans un hashmap, où la clé est un certain type que nous personnalisons. Après avoir mis HashMap, nous modifions les attributs d'une clé à l'extérieur, puis nous utilisons cette clé pour supprimer les éléments du hashmap. Que reviendra Hashmap pour le moment?

Des exemples de code et de réponses ont été donnés dans l'article, mais aucune explication n'est donnée sur le principe de Hashmap.

1. Caractéristiques

Nous pouvons utiliser n'importe quelle classe comme clé HashMap, mais quelles sont les restrictions sur ces classes? Regardons le code suivant:

 Personne de classe publique {nom de chaîne privée; Personne publique (nom de chaîne) {this.name = name; }} Map <personne, string> testmap = new hashmap <> (); testmap.put (new personne ("bonjour"), "world"); testmap.get (new personne ("bonjour")); // ---> null

Je voulais à l'origine obtenir la valeur de la classe de personne avec des valeurs de champ égales, mais le résultat était nul. Quiconque a un peu de connaissance de Hashmap peut voir que la classe de personne n'a pas de méthode de code Hashcode Override, ce qui conduit à son héritage du code hashcode d'objet (le retour est son adresse mémoire). C'est aussi la raison pour laquelle des classes invariantes telles que la chaîne (ou entier, etc.) sont couramment utilisées comme clé de HashMap. Alors, comment HashMap utilise-t-il HashCode pour indexer rapidement la clé?

2. Principe

Tout d'abord, jetons un coup d'œil à une simple solution d'implémentation HashMap dans "Thinking in Java":

 //: conteneurs / Simplehashmap.java // une démonstration hachée de hachage.import java.util. *; import net.mindview.util. *; public class Simplehashmap <k, v> étend abstractmap <k, v> {// Choisissez un numéro privil // Vous ne pouvez pas avoir un tableau physique de génériques, mais vous pouvez upcast à un: @SuppressWarnings ("Unchecked") LinkedList <MapEntry <k, v >> [] Buckets = new LinkedList [size]; public v put (k key, v valeur) {v oldvalue = null; int index = math.abs (key.hashcode ())% taille; if (buckets [index] == null) Buckets [index] = new LinkedList <MapEntry <k, v >> (); LinkedList <Mapentry <k, v >> Bucket = Buckets [index]; Mapentry <k, v> paire = new mapentry <k, v> (clé, valeur); booléen trouvé = false; ListIterator <mapentry <k, v >> it = Bucket.ListIterator (); while (it.hasnext ()) {mapentry <k, v> ipair = it.next (); if (ipair.getKey (). equals (key)) {oldvalue = ipair.getValue (); it.set (paire); // Remplacez l'ancien par nouveau trouvé = true; casser; }} if (! Found) Bucket [index] .add (paire); Retour OldValue; } public v get (clé d'objet) {int index = math.abs (key.hashcode ())% taille; if (Buckets [index] == null) renvoie null; for (mapentry <k, v> ipair: Buckets [index]) if (ipair.getKey (). equals (key)) return ipair.getValue (); retourner null; } public set <map.entry <k, v >> entryset () {set <map.entry <k, v >> set = new hashset <map.entry <k, v >> (); pour (LinkedList <MapEntry <k, v >> Bucket: Bucket) {if (bucket == null) continue; pour (mapentry <k, v> mpair: godet) set.add (mpair); } return set; } public static void main (string [] args) {SimpleHashmap <string, string> m = new SimpleHashMap <String, String> (); M.Putall (pays.Capitals (25)); System.out.println (M); System.out.println (m.get ("Érythrée")); System.out.println (M.EntrySet ()); }}

SimpleHashMap construit une table de hachage pour stocker les clés. La fonction de hachage est la taille du module de l'opération Math.abs (key.hashcode ()), et le conflit de hachage est résolu en utilisant la méthode de liste liée; Chaque fente de seaux stocke map.Entry avec la même valeur d'index (hachage), comme indiqué dans la figure ci-dessous:

Le principe de mise en œuvre de HashMap de JDK est similaire à celui, qui utilise le tableau de hachage de l'adresse de la chaîne pour stocker Map.Entry:

 / ** * Le tableau, redimensionné si nécessaire. La longueur doit toujours être une puissance de deux. * / entrée transitoire <k, v> [] table = (entrée <k, v> []) vide_table; entrée de classe statique <k, v> implémente map.entry <k, v> {key final k; V valeur v; Entrée <k, v> suivant; int hash; …}

L'indice de Map.Entry est obtenu en hachant le code de hash de la clé. Lorsque vous souhaitez obtenir la valeur correspondant à la clé, calculez son index pour la clé, puis retirez la carte. Entry dans le tableau pour l'obtenir. Pour plus de détails, consultez le code:

 public v get (object key) {if (key == null) return getFornullKey (); Entrée <k, v> entrée = GetEntry (clé); retourner null == entrée? null: entry.getValue ();} Entrée finale <k, v> gentry (clé d'objet) {if (size == 0) {return null; } int hash = (key == null)? 0: Hash (clé); pour (entrée <k, v> e = table [indexfor (hash, table.length)]; e! = null; e = e.next) {objet k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) return e; } retourner null;}

On peut voir que HashCode affecte directement l'efficacité de la fonction de hachage de HashMap - un bon code HashCode réduira considérablement les conflits de hachage et améliorera les performances de la requête. Dans le même temps, cela explique également les deux questions soulevées au début: si une classe personnalisée fait la clé HashMap, le calcul de la code HashCode devrait couvrir tous les champs du constructeur, sinon il est possible de devenir nul.