HashMap est une implémentation d'interface MAP basée sur les tables de hachage, fournissant toutes les opérations de cartographie facultative et permettant des valeurs nulles et une construction nul, hors synchronisation et aucune garantie d'ordre de cartographie. Enregistrons le principe de mise en œuvre de Hashmap.
Stockage interne hashmap
Dans Hashmap, toutes les relations de paires de valeurs clés sont stockées en maintenant un tableau de tableaux de variables instantanés (également appelés seau). Le seau est un tableau d'objets d'entrée. La taille du seau peut être redimensionnée au besoin, et la longueur doit être une puissance de 2. Le code suivant:
/ ** * Un tableau d'entrée vide, la valeur par défaut du seau * / entrée finale statique <? ,?> [] vide_table = {}; / ** * Bodet, redimensionner selon les besoins, mais doit être une puissance de 2 * / entrée transitoire <k, v> [] table = (entrée <k, v> []) vide_table;Capacité initiale et facteur de charge
Hashmap a deux paramètres qui affectent les performances, la capacité initiale et le facteur de charge. La capacité est le nombre de seaux dans la table de hachage, la capacité initiale n'est que la capacité de la table de hachage lorsqu'elle est créée, et le facteur de charge est une échelle où la table de hachage peut atteindre la pleine augmentation de sa capacité. Lorsque le nombre d'entrées dans le tableau de hachage dépasse le produit du facteur de charge et de la capacité actuelle, le tableau de hachage doit être rétabli (c'est-à-dire reconstruire la structure des données internes) et que la reconstruction est créée à deux fois le nombre de capacité actuelle. La capacité initiale et le facteur de charge peuvent être définis via le constructeur. La capacité initiale par défaut est de 16 entrées, la capacité maximale est de 2 ^ 30 entrées et le facteur de charge par défaut est de 0,75
Un seau est comme un seau qui stocke l'eau. Sa capacité de stockage initiale par défaut est de 16 unités d'eau. Lorsque l'eau est versée à 16 * 0,75, la capacité sera étendue d'abord à 32 unités lorsque les données seront ajoutées la prochaine fois. 0,75 est le facteur de charge, et la capacité initiale et le facteur de charge peuvent être définis lors de la création d'un seau. La capacité maximale d'un seau est de 2 unités d'eau à la puissance de 30. Lorsque le nombre de réglages de capacité initiale est supérieur à la capacité maximale, la capacité maximale doit prévaloir. Lors de l'expansion, il sera retourné directement s'il est supérieur ou égal à la capacité maximale.
Ce qui suit fait partie du code source de Hashmap, qui définit la capacité initiale par défaut, le facteur de charge et certaines autres constantes:
/ ** * La capacité initiale par défaut doit être la puissance de 2. * / Statique final int default_initial_capacity = 1 << 4; // aka 16 / ** * Capacité maximale, si la capacité initiale est supérieure à la capacité maximale par le paramètre du constructeur, la capacité sera également utilisée comme capacité initiale * doit être la puissance de 2 et inférieure ou égale à la 30e puissance de 2 * / statique final int maximum_capacity = 1 << 30; / ** * Le facteur de charge par défaut peut être spécifié par le constructeur * / static final float default_load_factor = 0.75f; / ** * une table de tableau vide, lorsque le seau n'est pas initialisé * / entrée finale statique <? ,?> [] vide_table = {}; / ** * Bodet, stocke toutes les entrées de paire de valeurs clés et peut être redimensionnée au besoin, et la longueur doit être une puissance de 2 * / entrée transitoire <k, v> [] table = (entrée <k, v> []) vide_table; / ** * Le nombre de paires de valeurs clés dans la carte, la taille sera +1 ou -1 de l'opération à chaque fois qu'elle est ajoutée ou supprimée. * / transitoire INT size; / ** * La valeur critique de la valeur de charge, qui doit être redimensionnée est: (Capacité * Facteur de charge). Après chaque redimensionnement, la nouvelle capacité sera calculée en utilisant la nouvelle capacité. * @Serial * / // Si table == vide_table alors il s'agit de la capacité initiale à laquelle la table // sera créée lorsqu'elle sera gonflée. seuil int; / ** * Facteur de charge, s'il n'est pas spécifié dans le constructeur, le facteur de charge par défaut est utilisé, * * @Serial * / Final Float LoadFactor; / ** * Nombre de fois les modifications de la structure HashMap, modifiez le nombre de cartes dans le hashmap ou modifiez sa structure interne lorsque la structure est modifiée (par exemple, la méthode * Rehash, reconstruisez la structure de données interne). Ce champ est utilisé dans * Les itérateurs générés sur la vue de collection HashMap sont traités dans Fast Echec * / Transient int modCount;Capacité initiale et ajustement des performances du facteur de charge
En règle générale, le facteur de charge par défaut (0,75) recherche un compromis en temps et en espace. Bien que le facteur de charge soit trop élevé, il augmente également le coût de la requête (cela se reflète dans la plupart des opérations de hashmap, y compris les opérations Get and Put). Lors de la définition de la capacité initiale, le nombre d'entrées requis dans la carte et son facteur de charge doit être pris en compte afin de minimiser le nombre d'opérations de remaniement. Si la capacité initiale est supérieure au nombre maximum d'entrées divisé par le facteur de charge, l'opération de rechash ne se produira pas.
Si de nombreuses relations de cartographie doivent être stockées dans une instance HashMap, la création d'une capacité initiale suffisamment importante rendra la relation de cartographie plus efficacement stockée par rapport à l'exécution des opérations de re-rehash à la demande pour augmenter la capacité du tableau.
Ce qui suit est le code pour reconstruire la structure des données HashMap:
void Resize (int newCapacity) {entrée [] oldTable = table; int oldcapacity = oldTable.length; if (oldcapacity == maximum_capacity) {// Si la capacité a atteint la limite maximale, définissez la valeur de charge et retournez directement sur threshold = integer.max_value; retour; } // Créer une nouvelle table pour stocker la saisie de données [] newtable = new Entry [newCapacity]; // transférer les données de l'ancienne table vers la nouvelle table, cette étape prendra beaucoup de temps pour transférer (Newtable, inithashseedasneed (newCapacity)); table = newtable; // Définissez enfin la valeur de charge du seuil de redimensionnement suivant = (int) math.min (newCapacity * LoadFactor, maximum_capacity + 1);}Méthode de construction de hashmap
La quatrième méthode de construction consiste à créer un nouveau hashmap avec une carte existante. Parlons-en plus tard. En fait, les trois premières méthodes de construction sont appelées dans la troisième méthode finale avec deux paramètres. Si aucun paramètre n'est passé, la valeur par défaut est utilisée. Le code est le suivant:
/ ** * Construit une <tt> hashmap </ tt> vide avec la capacité initiale par défaut * (16) et le facteur de charge par défaut (0,75). * / public hashmap () {this (default_initial_capacity, default_load_factor); } / ** * Construit une <tt> hashmap </ tt> vide <tt> avec la capacité initiale * spécifiée et le facteur de charge par défaut (0,75). * * @param InitialCapacity La capacité initiale. * @throws illégalargumentException si la capacité initiale est négative. * / public hashmap (int initialCapacity) {this (initialCapacity, default_load_factor); } / ** * Construit un <tt> HashMap </ tt> vide avec le facteur de capacité et de charge initiale spécifiée. * * @param InitialCapacity La capacité initiale * @param chargefactor le facteur de charge * @throws illégalArgumentException si la capacité initiale est négative * ou le facteur de charge est non positif * / hashmap public (int initialCapacity, float chargefactor) {if (initialCapacity <0) lancez new illégalargumentException ("illégal Initial Capible:" + initialCapacity); if (initialCapacity> maximum_capacity) initialCapacity = maximum_capacity; if (loadFactor <= 0 || float.isnan (loadfactor)) lancez un nouveau IllégalArgumentException ("Facteur de charge illégal:" + LoadFactor); this.loadFactor = LoadFactor; threshold = initialCapacity; init (); }Comme on peut le voir à partir de ce qui précède, dans le constructeur, si la capacité initiale est supérieure à la capacité maximale, la capacité maximale sera remplacée directement.
mettre la méthode
Ensuite, jetons un coup d'œil aux parties les plus importantes de Hashmap
/ ** * Dans cette carte, la valeur spécifiée et la version spécifiée sont associées. Si la carte contenait précédemment une relation de mappage de la clé, l'ancienne valeur a été remplacée * * @param spécifie la clé à association * @param spécifie la valeur à association * @return L'ancienne valeur associée à la clé, si la clé n'a pas de relation de mappage, elle renvoie Null (retour nul {inflatiable (seuil); } if (key == null) return putFornullKey (value); int hash = hash (key); int i = indexfor (hash, table.length); pour (entrée <k, v> e = table [i]; e! = null; e = e.next) {objet k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.Value; e.Value = valeur; e.recordAccess (this); Retour OldValue; }} modCount ++; Addentry (hachage, clé, valeur, i); retourner null; }1. Premièrement, dans la méthode de put, déterminez d'abord si le seau est à l'état non initialisé par défaut. S'il n'est pas initialisé, appelez la méthode inflatuable pour l'initialiser, puis déterminez si la clé de paramètre est nul. S'il est nul, appelez PutFornullkey spécifiquement pour mettre les données avec la clé comme null. La méthode PutFornullkey est en fait la même que la étape suivante 3, sauf que l'emplacement de stockage par défaut des données avec la clé comme null est le premier, c'est-à-dire que l'indice par défaut est 0.
2. Si la clé n'est pas nul, appelez la méthode hash () pour obtenir la valeur de hachage de la clé. Vous pouvez calculer la position où la clé peut être placée dans le seau en fonction de la valeur de hachage et de la longueur du seau.
3. Il y a un attribut suivant dans l'objet d'entrée, qui peut former une liste liée à sens unique pour stocker des éléments avec la même valeur de hachage. Par conséquent, lorsque la valeur de hachage de la clé est calculée, l'emplacement de stockage sera également répété. Jugez simplement si l'élément de l'emplacement de stockage et la liste d'attribut suivants de l'élément sont exactement les mêmes que la valeur de hachage de la clé et de la clé données. S'il y en a un complètement cohérent, cela signifie qu'il existe déjà, remplacez l'ancienne valeur et renvoyez l'ancienne valeur directement en tant que valeur de retour.
4. augmenter le nombre de modifications structurelles de 1
5. Appelez la méthode Addentry pour ajouter la nouvelle paire de valeurs clés au hashmap. La méthode d'additation détermine d'abord si les données de saisie actuelles sont supérieures ou égales à la valeur de charge (la capacité du facteur de charge du seau *) et la position spécifiée du seau n'est pas nulle. S'il est déjà supérieur à et que la position spécifiée n'est pas nulle, la capacité du seau d'ajustement est le double de la capacité de courant. La capacité du seau de réglage est référencée au répertoire de réglage des performances de capacité et de charge initiale ci-dessus. Recalculez la valeur de hachage et calculez l'emplacement de stockage. Appelez la méthode CreateEntry pour le stocker dans le seau
void Addentry (int hash, k key, v valeur, int bucketIndex) {if ((size> = threshold) && (null! = table [bucketIndex])) {redimensit (2 * table.length); hash = (null! = key)? hash (clé): 0; BucketIndex = indexFor (hash, table.length); } createEntry (hash, key, valeur, bucketIndex); } void CreateEntry (int hash, k key, Vale V, int bucketIndex) {entrée <k, v> e = table [bucketIndex]; table [bucketIndex] = nouvelle entrée <> (hachage, clé, valeur, e); taille ++; } / ** * Méthode du constructeur d'entrée pour créer une nouvelle entrée. * / Entrée (int h, k k, v v, entrée <k, v> n) {value = v; suivant = n; clé = k; hash = h; }6. Dans la méthode CreateEntry, obtenez d'abord l'entrée à l'emplacement spécifié, puis générez une nouvelle entrée. Lors de la génération de l'entrée, stockez l'entrée d'origine dans la propriété suivante de l'entrée nouvellement générée (reportez-vous à la méthode de construction de l'entrée) et remplacez l'entrée à l'emplacement spécifié par celui nouvellement généré.
Parce que lors de l'ajout de nouvelles entrées, la valeur de hachage doit être calculée et lorsque la longueur n'est pas suffisante, la longueur doit être ajustée. Lorsqu'il y a des éléments dans l'emplacement de stockage calculé, la liste liée doit être stockée, donc l'efficacité de l'utilisation de HashMap pour ajouter de nouvelles opérations n'est pas trop élevée.
Obtenir la méthode
Regardons d'abord le code source de la méthode GET:
/ ** * Renvoie la valeur mappée par la clé spécifiée; Si cette carte ne contient aucune relation de mappage pour cette clé, elle renvoie NULL * renvoyer une valeur nul ne signifie pas nécessairement que la carte ne contient pas le mappage de la clé et peut également changer le mappage en null. Vous pouvez utiliser l'opération CONTAINSKEY pour distinguer ces deux situations * @see #put (objet, objet) * / public v get (clé d'objet) {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> GetEntry (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;}La méthode GET est simple à mettre en œuvre, et les éléments suivants sont quelques étapes:
En regardant le code source de GET, nous pouvons constater que la méthode GET calcule l'emplacement de stockage à travers la valeur de hachage de la clé et la longueur du seau. Fondamentalement, vous pouvez localiser l'élément que vous recherchez. Même si vous traversez quelques clés avec des valeurs de hachage répétées, c'est très rapide. Parce que la valeur de hachage est relativement unique, HashMap est très rapide pour la recherche.
Objet personnalisé comme clé de hashmap
class user {// numéro d'identification protégé int idNumber; Utilisateur public (int id) {idNumber = id; }} classe publique TesUser {public static void main (String [] args) {map <user, string> map = new hashmap <user, string> (); pour (int i = 0; i <5; i ++) {map.put (nouvel utilisateur (i), "name:" + i); } System.out.println ("nom de l'utilisateur:" + map.get (nouvel utilisateur (3))); }} Sortie: User3 Nom: NULLComme mentionné ci-dessus, lors de l'utilisation d'une instance de classe utilisateur personnalisée comme objet HashMap, le nom de l'utilisateur3 ne peut être trouvé lors de l'impression, car la classe utilisateur hérite automatiquement de l'objet de classe de base, de sorte que la méthode de HashCode de l'objet sera automatiquement utilisée pour générer une valeur de hachage, et il utilise l'adresse de l'objet pour calculer la valeur de hachage par défaut. Par conséquent, la valeur de hachage de la première instance générée par le nouvel utilisateur (3) est différente de la valeur de hachage de la deuxième instance générée. Cependant, si vous n'avez besoin que de simplement remplacer la méthode HashCode, cela ne fonctionnera pas correctement, à moins que vous ne prenne en charge la méthode égale en même temps, cela fait également partie de l'objet. Hashmap utilise equals () pour déterminer si la clé actuelle est la même que les clés présents dans le tableau. Vous pouvez vous référer à la méthode Get ou Put ci-dessus.
La méthode Equals () correcte doit répondre aux 5 conditions suivantes: --- Reportez-vous à "Réflexions de programmation Java" - Page 489
Encore une fois : l'objet par défaut.equals () n'est que l'adresse de l'objet de comparaison, donc un nouvel utilisateur (3) n'égale pas un autre nouvel utilisateur (3). Par conséquent, si vous souhaitez utiliser votre propre classe comme clé de HashMap, vous devez surcharger à la fois HashCode () et Equals ().
Le code suivant fonctionne normalement:
class user {// numéro d'identification protégé int idNumber; Utilisateur public (int id) {idNumber = id; } @Override public int hashcode () {return idNumber; } @Override public boolean equals (objet obj) {return obj instanceof user && (idNumber == ((user) obj) .idNumber); }} classe publique TesUser {public static void main (String [] args) {map <user, string> map = new hashmap <user, string> (); pour (int i = 0; i <5; i ++) {map.put (nouvel utilisateur (i), "name:" + i); } System.out.println ("nom de l'utilisateur:" + map.get (nouvel utilisateur (3))); }} Sortie: Nom de l'utilisateur3: Nom: 3Ce qui précède renvoie simplement IDNumber comme la seule discrimination dans HashCode, et les utilisateurs peuvent également implémenter leurs propres méthodes en fonction de leur propre entreprise. Dans la méthode Equals, l'instance de vérifiera silencieusement si l'objet est nul. Si le paramètre à gauche de l'instance est nul, false sera renvoyé. Si le paramètre d'Equals () n'est pas nul et que le type est correct, la comparaison sera basée sur l'ombrage ID réel dans chaque objet. Comme le montre la sortie, la méthode actuelle est correcte.
se référer à:
"Réflexions de programmation Java"
JDK 1.6 Chinois Help Manual
Ce qui précède est tout le contenu de cet article. J'espère que le contenu de cet article sera d'une aide à l'étude ou au travail de chacun. J'espère également soutenir plus Wulin.com!