Aperçu de HashMap
Hashmap est une implémentation asynchrone de l'interface MAP basée sur la table de hachage. Cette implémentation fournit toutes les opérations de mappage en option et permet l'utilisation de valeurs nulles et de clés nulles. Cette classe ne garantit pas l'ordre des mappages, en particulier il ne garantit pas que l'ordre durera.
Structure de données de Hashmap
Dans le langage de programmation Java, il existe deux structures de base, l'une est un tableau et l'autre est un pointeur simulé (référence). Toutes les structures de données peuvent être construites en utilisant ces deux structures de base, et HashMap ne fait pas exception. Hashmap est en fait une structure de données "Liste liée", c'est-à-dire la structure des tableaux et des listes liées, mais dans JDK1.8
L'implémentation de l'arbre rouge et noir est ajoutée. Lorsque la longueur de la liste liée est supérieure à 8, elle est convertie en structure de l'arbre rouge et noir.
Comme le montre la figure ci-dessus, HashMap utilise la méthode d'adresse de chaîne en Java. La méthode d'adresse de liaison, tout simplement, est une combinaison de tableaux et de listes liées. Il existe une structure de liste liée sur chaque élément de tableau. Lorsque les données sont hachées, l'indice du tableau est obtenu et les données sont placées sur la liste liée des éléments des indices correspondants.
* / Node de classe statique <k, v> implémente map.entry <k, v> {final int hash; // utilisé pour localiser la position de l'index du tableau Final k touche; V valeur v; Nœud <k, v> suivant; // nœud suivant dans la liste liée nœud (int hash, key k, valeur v, noeud <k, v> suivant) {this.hash = hash; this.key = key; this.value = valeur; this.next = suivant; }Le nœud est une classe interne de hashmap, qui implémente l'interface map.entry, qui est essentiellement une carte (paire de valeurs clés).
Parfois, deux clés sont positionnées à la même position, indiquant qu'une collision de hachage s'est produite. Bien sûr, plus les résultats de calcul de l'algorithme de hachage sont uniformes, plus la probabilité de collision de hachage est faible et plus l'efficacité d'accès est faible de la carte.
Il y a un champ très important dans la classe HashMap, qui est le tableau de nœud [], c'est-à-dire le tableau de godet de hachage. C'est évidemment un éventail de nœuds.
Si le réseau de godets de hachage est grand, même le mauvais algorithme de hachage sera plus dispersé. Si le tableau du tableau de baquet de hachage est petit, même un bon algorithme de hachage aura plus de collisions, il est donc nécessaire de peser le coût de l'espace et le coût du temps. En fait, il s'agit de déterminer la taille de la matrice de hachage en fonction de la situation réelle, et sur cette base, l'algorithme de hachage conçu réduira les collisions de hachage. Alors, comment pouvons-nous contrôler les cartes pour que la probabilité de collisions de hachage soit petite, et les tableaux de seaux de hachage (tables de nœud) prennent moins de place? La réponse est un bon algorithme de hachage et un mécanisme d'expansion de la capacité.
Avant de comprendre le processus de hachage et d'expansion, nous devons comprendre plusieurs domaines de hashmap. À partir du code source du constructeur par défaut de HashMap, on peut voir que le constructeur initialise les champs suivants, le code source est le suivant:
seuil int; // La valeur de clé qui peut être hébergée est Ultimate Float LoadFactor; // Facteur de charge int modCount; Taille int;
Premièrement, la longueur d'initialisation du tableau du nœud [] (la valeur par défaut est 16), le facteur de charge est le facteur de charge (la valeur par défaut est de 0,75), et le seuil est le nombre de nœuds (paires de valeurs clés) de la quantité maximale de données que HashMap peut s'adapter. Threshold = longueur * Facteur de charge. C'est-à-dire que, après que le tableau a défini sa longueur, plus le facteur de charge est grand, plus il peut accueillir les paires de valeurs clés.
Sur la base de la formule de définition du facteur de charge, on peut voir que le seuil est le nombre maximal d'éléments autorisés en fonction de ce facteur de charge et de ce long (longueur du tableau). Si ce nombre dépasse cela, redimensionnez (capacité d'agrandissement). La capacité de hashmap élargie est le double de la capacité précédente. Le facteur de charge par défaut 0,75 est un choix équilibré pour l'espace et l'efficacité du temps. Il est recommandé de ne pas le modifier, sauf dans le cas de temps et d'espace spéciaux, s'il y a beaucoup d'espace mémoire et des exigences d'efficacité de temps élevée, la valeur du facteur de charge de charge peut être réduite; Au contraire, si l'espace mémoire est serré et que les exigences d'efficacité du temps ne sont pas élevées, la valeur du facteur de charge de chargement peut être augmentée, ce qui peut être supérieur à 1.
Le champ de taille est en fait facile à comprendre, c'est le nombre de paires de valeurs clés qui existent réellement dans Hashmap. Remarquez la différence entre la longueur du tableau et le nombre de seuils qui s'adaptent aux paires de valeurs de clé maximales. Le champ ModCount est principalement utilisé pour enregistrer le nombre de changements dans la structure interne de HashMAP, et est principalement utilisé pour la défaillance rapide de l'itération. Pour souligner, les changements dans la structure interne se réfèrent aux changements de la structure, tels que de mettre de nouvelles paires de valeurs clés, mais la valeur correspondant à une clé est écrasée et n'appartient pas aux changements structurels.
Dans Hashmap, la longueur de la table du tableau de godet de hachage doit être dans la puissance N de 2 (doit être un nombre composite). Il s'agit d'un design non conventionnel. La conception conventionnelle consiste à concevoir la taille du seau comme numéro premier. Relativement parlant, la probabilité de conflit causée par des nombres premiers est inférieure à celle des nombres composites. Pour des preuves spécifiques, veuillez vous référer à //www.vevb.com/article/100911.htm. Le hachage initialise la taille du seau à 11, qui est l'application de la taille du seau conçu comme des nombres premiers (le hashtable ne peut pas être garanti comme des nombres premiers après l'expansion). Hashmap adopte cette conception non conventionnelle, principalement pour optimiser quand le modulo et l'expansion. Dans le même temps, pour réduire les conflits, Hashmap ajoute également le processus de participation élevée à l'informatique lors de la localisation de la position de l'indice du seau de hachage.
Il y a un problème ici. Même si le facteur de charge et l'algorithme de hachage sont conçus raisonnablement, il y aura inévitablement une situation où la fermeture éclair est trop longue. Une fois que la fermeture éclair est trop longue, elle affectera sérieusement les performances de Hashmap. Par conséquent, dans la version JDK1.8, la structure des données a été encore optimisée et l'arbre rouge et noir a été introduit. Lorsque la longueur de la liste liée est trop longue (la valeur par défaut est supérieure à 8), la liste liée est convertie en arbre rouge et noir. Les caractéristiques de l'addition rapide des arbres rouges et noires, des suppressions, des modifications et des recherches seront utilisées pour améliorer les performances du hashmap. L'insertion, la suppression et la recherche d'arbres rouges et noirs seront utilisés pour insérer, supprimer et rechercher des algorithmes tels que l'arbre rouge et noir.
Déterminez la position d'index du réseau de seau de hachage
Implémentation du code:
// Méthode 1: static final int hash (clé d'objet) {//jdk1.8 & jdk1.7 int h; // h = key.hashcode () obtient la valeur de code de hash pour la première étape // h ^ (h >>> 16) participer au fonctionnement du deuxième retour (key == null)? 0: (h = key.hashcode ()) ^ (h >>> 16);} // Méthode 2: static int indexFor (int h, int le long) {//jdk1.7 code source, JDK1.8 n'a pas cette méthode, mais le principe d'implémentation est le même retour H & (longueur-1); // La troisième étape prend l'opération du module}L'algorithme de hachage ici est essentiellement trois étapes: la prise de la valeur de code de hash de la clé, le fonctionnement élevé et le fonctionnement du module.
Pour tout objet donné, tant que sa valeur de retour HashCode () est la même, le code de hachage calculé par la méthode d'appel de programme est toujours le même. La première chose à laquelle nous pensons est de modulo la valeur de hachage à la longueur du tableau, de sorte que la distribution des éléments est relativement uniforme. Cependant, la consommation d'opérations du module est relativement importante. Cela se fait dans HashMap: Méthode d'appel deux pour calculer quel index l'objet doit être stocké dans le tableau de table.
Cette méthode est très intelligente. Il obtient les bits enregistrés de l'objet via H & (Table.Length -1), et la longueur du tableau sous-jacent de hashmap est toujours à la puissance N 2, qui est l'optimisation de Hashmap en termes de vitesse. Lorsque la longueur est toujours à la puissance N de 2, l'opération H & (Longueur-1) est équivalente à la longueur du modulo, c'est-à-dire la longueur de H%, mais et a une efficacité plus élevée que%.
Dans la mise en œuvre de JDK1.8, l'algorithme pour les opérations élevées est optimisé, et la mise en œuvre de HashCode (): (h = k = k. Cela peut garantir que lorsque la longueur de la table de tableau est relativement faible, il peut également garantir que les bits sont impliqués dans les calculs de hachage qui tiennent compte du haut et qu'il n'y aura pas de frais généraux excessifs.
Voici un exemple, n est la longueur de la table.
Implémentation de la méthode de put HashMap
L'idée générale de la fonction de put est:
Le code spécifique est implémenté comme suit:
public v put (k key, v valeur) {return putVal (hash (key), key, valeur, false, true); } / ** * Méthode de génération de hash * / statique final int hash (clé d'objet) {int h; return (key == null)? 0: (h = key.hashcode ()) ^ (h >>> 16); } final v putVal (hash int, k key, Vale V, booléen uniquementifabsent, boolean evict) {node <k, v> [] onglet; Node <k, v> p; int n, i; // juger si le tableau est vide, if ((tab = table) == null || (n = tab.length) == 0) n = (tab = redimensit ()). Longueur; // Créer un nouveau tableau de table et obtenir la longueur de la clé de la clé de la clé de la clé. Si table [i] == null, créez directement un nouveau nœud et ajoutez if ((p = onglet [i = (n - 1) & hash]) == null) tab [i] = newNode (hash, key, valeur, valeur, null); else {// Si le nœud correspondant a le nœud <k, v> e; K K; // juger si le premier élément de la table [i] est le même que la clé, si le même, écrase directement la valeur if (p.hash == hash && ((k = p.key) == key || (key! = Null && key.equals (k)))) e = p; // juge si le tableau [i] est un treenode, c'est-à-dire si le tableau [i] est un arbre rouge-noir. S'il s'agit d'un arbre rouge-noir, insérez directement la paire de valeurs de clé dans l'arborescence else if (p instanceof Treenode) e = ((Treenode <k, v>) p) .puttreeval (this, tab, hash, key, valeur); // Cette chaîne est une liste liée Else {// Transipate via la table [i] pour déterminer si la longueur de la liste liée est supérieure à Treeify_Threshold (la valeur par défaut est 8). S'il est supérieur à 8, convertissez la liste liée en un arbre rouge-noir et effectuez l'opération d'insertion dans l'arbre rouge-noir. Sinon, le fonctionnement de l'insertion de la liste liée est effectué; S'il est constaté que la clé a déjà une valeur d'écrasement direct pendant le processus de traversée; pour (int bincount = 0 ;; ++ bincount) {if ((e = p.next) == null) {p.next = newNode (hash, key, valeur, null); if (binCount> = treeify_threshold - 1) // -1 pour 1st TreifyBin (onglet, hash); casser; } if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k))))) bris; p = e; }} // écrire if (e! = Null) {// mappage existant pour key v oldvalue = e.Value; if (! OnlyIfABSent || oldvalue == null) e.Value = valeur; Après-midi (E); Retour OldValue; }} ++ modCount; // Une fois l'insertion réussie, déterminez si le nombre réel de paires de valeurs clés dépasse le seuil de capacité maximum. S'il dépasse la capacité, développez si (++ taille> threshold) redimensit (); après-midiinsertion (expulsion); retourner null; }Hashmap obtenir l'implémentation de la méthode
L'idée est la suivante:
1. Le premier nœud du seau, frappe directement;
2. S'il y a un conflit, utilisez Key.Equals (k) pour trouver l'entrée correspondante
S'il s'agit d'un arbre, recherchez dans l'arborescence via Key.equals (k), o (Logn);
S'il s'agit d'une liste liée, recherchez Key.equals (k) dans la liste liée, o (n).
public v get (clé d'objet) {node <k, v> e; return (e = getNode (hash (key), key)) == null? NULL: E.Value; } Node final <k, v> getNode (int hash, clé d'objet) {node <k, v> [] tab; Nœud <k, v> premier, e; int n; K K; if ((tab = table)! = null && (n = tab.length)> 0 && (premier = tab [(n - 1) & hash])! = null) {// Hit directement if (first.hash == hash && // Chaque fois qu'il est vérifié le premier nœud ((k = first.key) == key || (key! = null && key.equals (k)))) // manqué if ((e = first.next)! = Null) {// get if (première instanceof Treenode) return ((Treenode <k, v>) premier) .getTreenode (hash, key); // get do {if (e.hash == hash && ((k = e.key) == key || (key! = Null && key.equals (k)))) return e; } while ((e = e.next)! = null); }} return null; }Mécanisme d'expansion de la capacité
Le redimensionnement signifie recalculer la capacité et ajouter constamment des éléments à l'objet HashMap. Lorsque le tableau à l'intérieur de l'objet HashMap ne peut pas charger plus d'éléments, l'objet doit étendre la longueur du tableau afin que plus d'éléments puissent être chargés. Bien sûr, les tableaux en Java ne peuvent pas être automatiquement élargis. La méthode consiste à utiliser un nouveau tableau au lieu de tableaux existants avec une petite capacité, tout comme nous utilisons un petit seau pour remplir de l'eau. Si nous voulons remplir plus d'eau, nous devons le remplacer par un grand seau.
Nous analysons le code source de redimensionnement. Étant donné que JDK1.8 intègre des arbres rouges et noirs, il est plus compliqué. Afin de faciliter la compréhension, nous utilisons toujours le code JDK1.7, ce qui est plus facile à comprendre. Il y a peu de différence d'essence. Parlons des différences spécifiques plus tard.
void Resize (int NewCapacity) {// Pause Nouvelle Capacité Entrée [] OldTable = Table; // référence le tableau d'entrée avant l'expansion int oldcapacity = oldTable.length; if (oldcapacity == maximum_capacity) {// Si la taille du tableau avant l'expansion a atteint le thrésine du maximum (2 ^ 30) = Integer.max_value; // modifie le seuil à la valeur maximale d'int (2 ^ 31-1), afin que la capacité ne soit pas élargie dans le retour futur; } Entrée [] newtable = new Entry [newCapacity]; // initialiser un nouveau transfert de tableau d'entrée (NewTable); //! ! Transférer des données vers la nouvelle table de tableau d'entrée = NewTable; // L'attribut de table de HashMap fait référence au nouveau tableau d'entrée threshold = (int) (newCapacity * loadFactor); // modifie le seuil}Ici, nous utilisons un tableau avec une plus grande capacité au lieu d'un tableau existant avec une plus petite capacité. La méthode transfert () copie les éléments du tableau d'entrée d'origine sur le nouveau tableau d'entrée.
void transfert (entrée [] newtable) {entrée [] src = table; // src fait référence à l'ancien tableau d'entrée int newCapacity = newtable.length; for (int j = 0; j <src.length; j ++) {// transmence via l'ancienne entrée du tableau d'entrée <k, v> e = src [j]; // Obtenez chaque élément de l'ancien tableau d'entrée if (e! = Null) {src [j] = null; // relâchez la référence d'objet de l'ancien tableau d'entrée (après la boucle pour, l'ancien tableau d'entrée ne se réfère plus à aucun objet) do {entrée <k, v> Next = e.next; int i = indexFor (e.hash, newcapacity); //! ! Recalculer la position de chaque élément dans le tableau e.next = newtable [i]; // tag [1] newtable [i] = e; // Mettez l'élément sur le tableau E = Suivant; // accéder à l'élément de la chaîne d'entrée suivante} while (e! = Null); }}}La référence à NewTable [i] est affectée à E.Next, ce qui signifie que la méthode d'insertion d'en-tête d'une seule liste liée est utilisée. De nouveaux éléments à la même position seront toujours placés à la tête de la liste liée; De cette façon, les éléments placés sur un indice seront éventuellement placés à la fin de la chaîne d'entrée (si un conflit de hachage se produit). Ceci est différent de JDK1.8, qui est expliqué en détail ci-dessous. Les éléments de la même chaîne d'entrée dans l'ancien tableau peuvent être placés à différentes positions dans le nouveau tableau après avoir recalculé la position d'index.
Voici un exemple pour illustrer le processus d'expansion de la capacité. Supposons que notre algorithme de hachage utilise simplement le mod clé pour obtenir la taille de la table (c'est-à-dire la longueur du tableau). La taille de la table du tableau du seau de hachage = 2, donc la clé = 3, 7, 5, et l'ordre de put est de 5, 7 et 3. Après le mod 2, le conflit est dans le tableau [1]. Ici, il est supposé que le facteur de charge chargefactor = 1, c'est-à-dire lorsque la taille réelle de la paire de valeurs clés est supérieure à la taille réelle de la table, il est étendu. Les trois étapes suivantes sont le processus de redimensionnement du réseau de baquets de hachage à 4, puis de réhabiliter tous les nœuds.
Expliquons quelles optimisations ont été faites dans JDK1.8. Après observation, nous pouvons constater que nous utilisons une puissance de deux expansion (se référant à la longueur de deux fois l'original), donc la position de l'élément est soit dans la position d'origine, soit déplace à nouveau la position de la puissance de deux à la position d'origine. En regardant la figure ci-dessous, vous pouvez comprendre le sens de cette phrase. n est la longueur de la table. La figure (a) représente un exemple de la position d'index des deux clés qui déterminent la position d'index des Key1 et Key2 avant l'expansion. La figure (b) représente un exemple de la position d'index des Key1 et Key2 après l'expansion. Où HASH1 est le résultat du hachage et de l'opération élevée correspondant à Key1.
Une fois que l'élément a recalculé le hachage, puisque N devient 2 fois, la plage de masque de N-1 est 1 bits (rouge) au point élevé, donc le nouvel index changera comme ceci:
Par conséquent, lorsque nous élargissons HashMap, nous n'avons pas besoin de recalculer le hachage comme la mise en œuvre de JDK1.7. Il nous suffit de voir si le bit ajouté à la valeur de hachage d'origine est 1 ou 0. S'il est 0, l'index n'a pas changé. S'il est 1, l'index devient "Index d'origine + OldCap". Vous pouvez voir le chiffre suivant comme le diagramme de redimensionnement avec 16 extension à 32:
Cette conception est en effet très intelligente, ce qui permet non seulement de gagner du temps pour recalculer la valeur de hachage, mais aussi, car le 1 bits nouvellement ajouté est 0 ou 1, il peut être considéré comme aléatoire, donc le processus de redimensionnement distribue uniformément les nœuds conflictuels précédents au nouveau seau. Il s'agit du nouveau point d'optimisation ajouté par JDK1.8. Il y a un peu d'attention à la différence. Lorsque Rehash dans JDK1.7, lorsque les anciennes listes liées migrent de nouvelles listes liées, si la position d'index du tableau du nouveau tableau est la même, les éléments de liste liés seront inversés, mais comme on peut le voir à partir de la figure ci-dessus, JDK1.8 ne sera pas inversé. Les étudiants intéressés peuvent étudier le code source de redimensionnement de JDK1.8, ce qui est très bon, comme suit:
Node final <k, v> [] redimensit () {node <k, v> [] oldtab = table; int oldcap = (oldtab == null)? 0: OldTab.Length; int oldthrh = threshold; int newCap, newthr = 0; if (oldcap> 0) {// Si la valeur maximale dépasse, elle ne sera plus élargie, je dois donc entrer en collision avec vous si (oldcap> = maximum_capacity) {threshold = Integer.max_value; Retour Oldtab; } // Si la valeur maximale n'est pas dépassée, elle sera étendue à 2 fois l'original if ((newcap = oldcap << 1) <maximum_capacity && oldcap> = default_initial_capacity) newthr = oldthr << 1; // Double seuil} else if (Oldthrh> 0) // La capacité initiale a été placée dans le seuil newcap = oldthr; else {// zéro seuil initial signifie utiliser defaults newcap = default_initial_capacity; newthrhr = (int) (default_load_factor * default_initial_capacity); } // Calculez la nouvelle limite supérieure redimensive if (newthr == 0) {float ft = (float) newCap * loadFactor; newthrhr = (newCap <maximum_capacity && ft <(float) maximum_capacity? (int) ft: Integer.max_value); } threshold = newthr; @SuppressWarnings ({"RawTypes", "Unchecked"}) Node <K, v> [] newtab = (node <k, v> []) nouveau nœud [newcap]; table = newtab; if (oldtab! = null) {// déplacez chaque seau dans les nouveaux seaux pour (int j = 0; j <oldcap; ++ j) {node <k, v> e; if ((e = oldtab [j])! = null) {oldtab [j] = null; if (e.next == null) newtab [e.hash & (newcap - 1)] = e; else if (e instanceof Treenode) ((Treenode <k, v>) e) .split (this, newtab, j, oldcap); else {// préserver le nœud d'ordre <k, v> lohead = null, lOTail = null; Node <k, v> hiead = null, hitail = null; Node <k, v> suivant; do {next = e.next; // index d'origine if ((e.hash & oldcap) == 0) {if (lotail == null) lohead = e; else lOTail.next = e; LOTAIL = E; } // index d'origine + oldcap else {if (hitail == null) hiead = e; else hitail.next = e; hitail = e; }} while ((e = suivant)! = null); // Mettez l'index d'origine dans le seau if (Lotail! = Null) {Lotail.next = null; newtab [j] = lohead; } // Mettez l'index d'origine + OldCap dans le seau if (hitail! = Null) {hitail.next = null; newtab [j + oldcap] = hihead; }}}}} return newtab;}Résumer
Nous pouvons maintenant répondre à plusieurs questions au début pour approfondir notre compréhension de Hashmap:
1. Quand Hashmap sera-t-il utilisé? Quelles sont ses caractéristiques?
Il est basé sur la mise en œuvre de l'interface MAP. Lors du stockage des paires de valeurs clés, il peut recevoir des valeurs de clés nuls, qui sont asynchrones. HashMap Stores Stores Entry (Hash, Key, Value, Next) Objets.
2. Savez-vous comment fonctionne Hashmap?
Grâce à la méthode de hachage, les objets sont stockés et obtenus par put et obtenez. Lors du stockage d'un objet, lorsque nous passons K / V à la méthode de put, il appelle HashCode pour calculer le hachage pour obtenir l'emplacement du seau et le stocker plus loin. Hashmap ajustera automatiquement la capacité en fonction de l'occupation actuelle du seau (si elle dépasse la facotr de charge, le redimensionnement est le double de l'original). Lors de l'obtention de l'objet, nous passons K pour obtenir, qui appelle HashCode pour calculer le hachage pour obtenir la position du seau, et appelle en outre la méthode equals () pour déterminer la paire de valeurs clés. Si une collision se produit, HashMap organise les éléments qui génèrent des conflits de collision via la liste liée. Dans Java 8, si les éléments qui entrent en collision dans un seau dépassent une certaine limite (la valeur par défaut est 8), un arbre rouge et noir est utilisé pour remplacer la liste liée pour augmenter la vitesse.
3. Connaissez-vous les principes de Get and Put? Quelles sont les fonctions d'Equals () et de HashCode ()?
En hachant le HashCode () de la clé et calculez l'indice (N-1 & Hash), la position des seaux est obtenue. Si une collision se produit, utilisez la méthode key.equals () pour rechercher le nœud correspondant dans la liste ou l'arbre lié
4. Connaissez-vous la mise en œuvre du hachage? Pourquoi dois-je faire cela?
Dans la mise en œuvre de Java 1.8, il est implémenté via le haut 16 bits X-OR 16 bits de HashCode (): (h = k.hashcode ()) ^ (h >>> 16), qui est principalement pris en compte à partir de la vitesse, de l'efficacité et de la qualité. Cela peut garantir que lorsque le N du seau est relativement petit, il peut également garantir que les bits élevés et faibles sont impliqués dans le calcul du hachage, et il n'y aura pas de frais généraux excessifs.
5. Et si la taille de HashMap dépasse la capacité définie par le facteur de charge?
Si le facteur de charge est dépassé (par défaut 0,75), un hashmap avec deux fois la longueur d'origine sera redimensionné et la méthode de hachage sera à nouveau appelée.
La feuille de triche sur les collections Java est décrite comme suit:
Le tableau de hachage de hachage implémenté avec le tableau d'entrée [], et la valeur de hachage de la clé peut être utilisée pour obtenir l'indice du tableau.
Lors de l'insertion d'un élément, si deux clés se situent dans le même seau (par exemple, après que les valeurs de hachage 1 et 17 sont modulo 16, les deux appartiennent au premier seau de hachage), l'entrée utilise une propriété suivante pour implémenter plusieurs entrées dans une liste liée à sens unique et l'entrée qui entre dans les points de seau à côté de l'entrée actuelle du seau.
Lorsque vous recherchez une clé avec une valeur de hachage de 17, localisez d'abord le premier seau de hachage, puis parcourez tous les éléments du seau avec une liste liée et comparez leurs valeurs clés une par une.
Lorsque le nombre d'entrée atteint 75% des seaux (de nombreux articles affirment que le nombre de seaux utilisés atteint 75%, mais selon le code, le réseau de seaux sera élargi de façon exponentielle et que toute l'entrée d'origine sera réaffectée, il est donc préférable d'avoir une valeur estimée ici.
L'opération de bit (Hash & (ArrayLength-1)) sera plus rapide, donc la taille du tableau est toujours à la puissance n de 2. Si vous donnez une valeur initiale telle que 17, il sera converti en 32. La valeur initiale par défaut lorsque l'élément est placé pour la première fois est 16.
Iterator () traverse le réseau de seau de hachage, qui ressemble à un détente.
6. Que se passe-t-il lorsque le code de hash de deux objets est le même?
Parce que le HashCode est le même, leur position de seau est la même et une «collision» se produira. Étant donné que HashMap utilise une liste liée pour stocker des objets, cette entrée (l'objet Map.Entry contenant des paires de valeurs de clé) est stocké dans la liste liée.
7. Si le code de hash de deux clés est le même, comment obtenez-vous l'objet de valeur?
Après avoir trouvé l'emplacement du seau, la méthode Keys.equals () sera appelée pour trouver le nœud correct dans la liste liée et enfin trouver l'objet de valeur à trouver. Par conséquent, lors de la conception du type de clé de hashmap, si un objet immuable est déclaré final et que les méthodes Equals () et HashCode () appropriées sont utilisées, la survenue de collisions sera réduite et l'efficacité sera améliorée. L'immuabilité peut mettre en cache des codes de hash pour différentes clés, ce qui augmentera la vitesse d'obtenir l'ensemble de l'objet. L'utilisation de classes en wrapper comme String et Interger comme clés est un très bon choix.
8. Et si la taille de HashMap dépasse la capacité définie par le facteur de charge?
La taille du facteur de charge par défaut est de 0,75. C'est-à-dire que lorsqu'une carte remplit des seaux à 75%, comme d'autres classes de collecte (telles que ArrayList, etc.), un tableau de seau qui fait deux fois plus de taille du hashmap d'origine sera créé pour redimensionner la carte et mettre l'objet d'origine dans le nouveau tableau de seau. Ce processus est appelé remaniement car il appelle la méthode de hachage pour trouver le nouvel emplacement du seau
9. Comprenez-vous ce qui ne va pas avec le redimensionnement du hashmap?
Lors du redimensionnement de HashMap, il y a en effet une concurrence conditionnelle, car si les deux fils constatent que HashMap doit être redimensionné, ils essaieront de redimensionner en même temps. Pendant le processus de redimensionnement, l'ordre des éléments stockés dans la liste liée sera inversé, car lors du passage à la nouvelle position de seau, Hashmap ne place pas les éléments à la fin de la liste liée, mais à la tête, qui doit éviter la traversée de la queue. Si la compétition conditionnelle se produit, il y a un cercle vicieux. Par conséquent, dans un environnement simultané, nous utilisons CurrentHashMap pour remplacer Hashmap
10. Pourquoi les classes d'emballage comme la chaîne et l'interger sont-elles adaptées comme clés?
Parce que la chaîne est immuable et finale, et les méthodes equals () et hashcode () ont été réécrites. D'autres classes en wrapper ont également cette fonctionnalité. L'immuabilité est nécessaire car pour calculer HashCode (), vous devez empêcher la valeur de la valeur clé. Si la valeur clé renvoie un HashCode différent lors de la mise en place et de l'obtention, vous ne pouvez pas trouver l'objet que vous souhaitez du hashmap. L'immuabilité présente d'autres avantages tels que la sécurité des fils. Si vous pouvez garantir que le HashCode est inchangé simplement en déclarant un champ comme final, veuillez le faire. Parce que les méthodes Equals () et HashCode () sont utilisées lors de l'obtention d'objets, il est très important de réécrire correctement ces deux méthodes. Si deux objets inégaux renvoient des codes de hashcodes différents, les chances de collision seront plus petites, ce qui améliorera les performances de Hashmap
Merci d'avoir lu, j'espère que cela peut vous aider. Merci pour votre soutien à ce site!