Nous avons analysé les deux ensembles de ArrayList et LinkedList. Nous savons que ArrayList est implémenté en fonction des tableaux, et LinkedList est implémenté en fonction des listes liées. Chacun a ses propres avantages et inconvénients. Par exemple, ArrayList sera meilleur que LinkedList lors du positionnement et de la recherche d'éléments, tandis que LinkedList sera meilleur que ArrayList lors de l'ajout et de la suppression des éléments. Le hashmap introduit dans cet article combine les avantages des deux. Sa couche sous-jacente est implémentée sur la base d'une table de hachage. Si le conflit de hachage n'est pas pris en compte, la complexité du temps de HashMap en outre en outre les opérations de suppression, de modification et de recherche peut atteindre un O (1) étonnant. Regardons d'abord la structure de la table de hachage sur laquelle il est basé.
Comme le montre la figure ci-dessus, une table de hachage est une structure composée d'un tableau et d'une liste liée. Bien sûr, la figure ci-dessus est un mauvais exemple. Une bonne fonction de hachage devrait essayer de moyenne la distribution des éléments dans le tableau, de réduire les conflits de hachage et de réduire la durée de la liste liée. Plus la longueur de la liste liée signifie que plus elle doit être traversée lors de la recherche, plus les performances de la table de hachage seront pires. Ensuite, jetons un coup d'œil à certaines variables membres de Hashmap.
// Capacité initiale par défaut statique final int default_initial_capacity = 1 << 4; // par défaut maximum capacité statique final int maximum_capacity = 1 << 30; // le facteur de chargement par défaut fait référence à la quantité de table de hachage peut atteindre le float final statique default_load_factor = 0.75f; // Tableau de hachage vide Entrée <k, v> [] table = (entrée <k, v> []) vide_table; // taille de hashmap, c'est-à-dire le nombre de paires de valeurs clés stockées dans la taille du tableau transitoire de hashmap; // le seuil de paires de valeurs clés est utilisé pour déterminer si la capacité de la table de hachage doit être amplifiée pour le threshold; Mécanisme échoué transitoire int modCount; // Utilisez le seuil par défaut du hachage alternatif statique final int alternative_hashing_threshold_default = Integer.max_value; // La graine de hachage aléatoire aide à réduire le nombre de collisions de hachage transitoires int hashseed = 0;
Comme le montrent les variables des membres, la capacité initiale par défaut de HashMAP est de 16 et le facteur de charge par défaut est de 0,75. Le seuil est le seuil de la paire de valeurs clés qui peut être stocké dans l'ensemble. La valeur par défaut est le facteur de chargement de capacité initiale *, c'est-à-dire 16 * 0,75 = 12. Lorsque la paire de valeurs clés doit dépasser le seuil, cela signifie que la table de hachage est déjà saturée à ce moment. Si les éléments continuent d'être ajoutés, le conflit de hachage sera ajouté, ce qui dégradera les performances de HashMap. À l'heure actuelle, le mécanisme d'expansion de la capacité automatique sera déclenché pour garantir les performances de Hashmap. Nous pouvons également voir que la table de hachage est en fait un tableau d'entrée, et chaque entrée stockée dans le tableau est le nœud d'en-tête de la liste liée à sens unique. Cette entrée est une classe intérieure statique de hashmap, jetons un coup d'œil aux variables d'entrée des membres.
Entrée de classe statique <k, v> implémente Map.Entry <k, v> {Final K Key; // Valeur de clé V; // Entrée de valeur <k, v> suivant; // la référence au hachage INT de l'entrée suivante; // Histocode ... // omettez le code suivant}Une instance d'entrée est une paire de valeurs de clé qui contient la clé et la valeur. Chaque instance d'entrée a une référence à l'instance d'entrée suivante. Pour éviter les calculs répétés, chaque instance d'entrée stocke également le code de hachage correspondant. On peut dire que le tableau d'entrée est au cœur de HashMap, et toutes les opérations sont effectuées pour ce tableau. Étant donné que le code source HashMap est relativement long, il est impossible d'introduire toutes ses méthodes de manière complète, nous ne nous concentrons donc que sur les points clés pour les introduire. Ensuite, nous serons axés sur les problèmes et explorerons le mécanisme interne de HashMap en profondeur pour les problèmes suivants.
1. Quelles opérations font Hashmap pendant la construction?
// Constructeur, passez dans la capacité d'initialisation et le facteur de charge hashmap public (int initialCapacity, float chargefactor) {if (initialCapacity <0) {lancez new illégalargumentException ("Capacité initiale illégale:" + InitialCapacity); } // Si la capacité d'initialisation est supérieure à la capacité maximale, définissez-la sur la capacité maximale if (initialCapacity> maximum_capacity) {initialCapacity = maximum_capacity; } // Si le facteur de charge est inférieur à 0 ou si le facteur de charge n'est pas un numéro de point flottant, une exception est lancée if (LoadFactor <= 0 || float.isnan (LoadFactor)) {Throw New illégalArgumentException ("Facteur de charge illégal:" + LoadFactor); } // Définissez le facteur de chargement this.loadFactor = LoadFactor; // Le seuil est le seuil de capacité d'initialisation = InitialCapacity; init ();} void init () {}Tous les constructeurs appellent ce constructeur. Dans ce constructeur, nous voyons qu'en plus de faire une certaine vérification des paramètres, il fait deux choses: définir le facteur de charge sur le facteur de charge entrant et définir le seuil sur la taille de l'initialisation entrante. La méthode init est vide et ne fait rien. Notez qu'à ce moment, aucun nouveau tableau d'entrée n'est créé en fonction de la taille d'initialisation entrante. Alors, quand créerons-nous un nouveau tableau? Continuez à lire.
2. Quelles opérations seront effectuées lorsque HashMap ajoutera des paires de valeurs clés?
// put les paires de valeurs de clé dans hashmap public v put (k key, v valeur) {// initialiser if (table == vide_table) {// initialiser la table de hash inflatiable (threshold); } if (key == null) {return putFornullKey (value); } // Calculez le code de hachage de la clé int hash = hash (key); // Positionnez la position de la table de hachage en fonction du code de hash int i = indexFor (hash, table.length); pour (entrée <k, v> e = table [i]; e! = null; e = e.next) {objet k; // Si la clé correspondante existe déjà, remplacez sa valeur de valeur et renvoyez la valeur d'origine if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.Value; e.Value = valeur; e.recordAccess (this); Retour OldValue; }} modCount ++; // S'il n'y a pas de clé correspondante, ajoutez l'entrée à HashMap Addentry (hachage, clé, valeur, i); // retour null retour null;}Vous pouvez voir que lors de l'ajout de paires de valeurs clés, vous vérifierez d'abord si la table de hachage est une table vide, et s'il s'agit d'une table vide, elle sera initialisée. Ensuite, effectuez des opérations ultérieures et appelez la fonction de hachage pour calculer le code de hachage de la clé passée. Positionnez la fente spécifiée du tableau d'entrée en fonction du code de hachage, puis parcourez la liste liée à sens unique de la fente. Si le passé existe déjà, effectuez une opération de remplacement, sinon une nouvelle entrée sera créée et ajoutée à la table de hachage.
3. Comment le tableau de hachage est-il initialisé?
// Initialisez le tableau de hachage et la capacité du tableau de hachage se développera, car il est possible que la capacité entrante ne soit pas une puissance de 2 inflatuables vides privés (int tosize) {// La capacité du tableau de hachage doit être une puissance de 2 int la capacité = RoundUptoPowerOf2 (tosize); // Définit le seuil, voici généralement la capacité * LoadFactor Threshold = (int) math.min (capacité * LoadFactor, maximum_capacity + 1); // Créez une nouvelle table de hachage avec une table de capacité spécifiée = nouvelle entrée [capacité]; // Initialisez les graines de hachage inithashseedasneed (capacité);}Comme nous le savons ci-dessus, lors de la construction d'un hashmap, nous ne créerons pas un nouveau tableau d'entrée, mais vérifiez si la table de hachage actuelle est une table vide pendant l'opération de vente. S'il s'agit d'une table vide, appelez la méthode inflatuable d'initialisation. Le code de cette méthode est publié ci-dessus. Vous pouvez voir que la capacité du réseau d'entrée sera recalculée à l'intérieur de la méthode, car la taille d'initialisation transmise lors de la construction du hashmap peut ne pas être une puissance de 2, vous devez donc convertir ce numéro en une puissance de 2, puis créer un nouveau tableau d'entrée basé sur la nouvelle capacité. Lors de l'initialisation de la table de hachage, réinitialisez à nouveau le seuil et le seuil est généralement de capacité * chargement. De plus, la graine de hachage (graines de hasard) sera initialisée lors de l'initialisation de la table de hachage. Cette graine de hachage est utilisée pour optimiser la fonction de hachage. La valeur par défaut est 0, et aucun algorithme de hachage alternatif n'est utilisé, mais vous pouvez également définir la valeur de hachage par vous-même pour réaliser l'effet d'optimisation. Cela sera discuté en détail ci-dessous.
4. Quand HashMap détermine-t-il s'il doit élargir la capacité et comment il augmente la capacité?
// Ajouter la méthode d'entrée et déterminer d'abord si vous souhaitez étendre l'addentry de la capacité vide (int hash, k key, valeur v, int bucketIndex) {// si la taille de hashmap est supérieure à celle du seuil et de la valeur de la fente correspondante de la table de hachage Seuil, il indique qu'un conflit de hachage est sur le point de se produire, alors élargissez la redimensionnement de la capacité (2 * Tableau.Length); hash = (null! = key)? hash (clé): 0; BucketIndex = indexFor (hash, table.length); } // Il est montré ici que la taille de HashMap ne dépasse pas le seuil, il n'est donc pas nécessaire d'élargir la capacité CreateEntry (hachage, clé, valeur, bucketIndex);} // étendez le tableau de hachage void redimensit (int newcapacity) {entrée [] oldtable = table; int oldcapacity = oldTable.length; // Si la capacité maximale actuelle est déjà utilisée, vous ne pouvez augmenter que le seuil si (oldcapacity == maximum_capacity) {threshold = Integer.max_value; retour; } // Sinon, élargissez l'entrée de capacité [] newtable = new Entry [newCapacity]; // la méthode pour migrer le transfert de table de hachage (newtable, inithashseedasneeded (newCapacity)); // Définissez la table de hachage actuelle sur la nouvelle table de hachage de hachage = newtable; // Mette à jour le thème de la table de hachage = (int) math.min (newCapacity * LoadFactor, maximum_capacity + 1);}Lorsque vous appelez la méthode de put pour ajouter une paire de valeurs de clé, s'il n'y a pas de clé dans la collection, appelez la méthode d'addentry et créez une nouvelle entrée. Lorsque vous voyez le code d'addentry publié ci-dessus, avant de créer une nouvelle entrée, vous déterminera d'abord si la taille de l'élément de collecte actuel dépasse le seuil. Si le seuil dépasse le seuil, appelez le redimensionnement pour l'expansion. La nouvelle capacité réalisée est le double de la table de hachage d'origine. Dans la méthode de redimensionnement, un nouveau tableau d'entrée avec une capacité de deux fois la table de hachage d'origine sera créée. Ensuite, tous les éléments de l'ancienne table de hachage sont migrés vers la nouvelle table de hachage, où la nouvelle réévaluation peut être effectuée, et il faut effectuer la réalisation de Re-Rash en fonction de la valeur calculée par la méthode InithashSeedasneed. Une fois la migration de la table de hachage terminée, la table de hachage actuelle est remplacée par une nouvelle, et enfin la valeur seuil du hashmap est recalculée en fonction de la nouvelle capacité de table de hachage.
5. Pourquoi la taille du tableau d'entrée doit-elle être une puissance de 2?
// retourne l'index du tableau correspondant au code de hash static int indexfor (int h, int le long) {return h & (longueur-1); }La méthode IndexFor calcule l'indice correspondant dans le tableau en fonction du code de hachage. Nous pouvons voir que l'opérateur (&) est utilisé à l'intérieur de cette méthode. L'opération consiste à effectuer des opérations de bit sur deux opérandes. Si les deux bits correspondants sont 1, le résultat est 1, sinon il est 0. Les opérations sont souvent utilisées pour éliminer les valeurs d'opérandes élevés, telles que: 01011010 & 00001111 = 00001010. Revenons au code et voyons ce que fait H & (longueur-1).
Il est connu que la longueur passée est la longueur du réseau d'entrée. Nous savons que l'indice du tableau est calculé à partir de 0, donc l'indice maximum du tableau est la longueur-1. Si la longueur est une puissance de 2, alors les bits binaires de longueur 1 sont suivis par 1. À l'heure actuelle, la fonction de H & (longueur-1) est de supprimer la valeur élevée de H et de ne laisser que la valeur faible de H comme indice du tableau. À partir de cela, nous pouvons voir que la taille du tableau d'entrée est définie comme une puissance de 2 afin d'utiliser cet algorithme pour déterminer l'indice du tableau.
6. Comment la fonction de hachage calcule-t-elle le code de hachage?
// La fonction qui génère du code de hachage final inth hash (objet k) {int h = hashseed; // Si la clé est de type de chaîne, utilisez un autre algorithme de hachage if (0! = H && k instanceof String) {return Sun.Misc.Hashing.StringHash32 ((String) K); } h ^ = k.hashcode (); // la fonction de perturbation h ^ = (h >>> 20) ^ (h >>> 12); retour h ^ (h >>> 7) ^ (h >>> 4);}Les deux dernières lignes de la méthode de hachage sont l'algorithme qui calcule vraiment la valeur de hachage. L'algorithme qui calcule le code de hachage est appelé la fonction de perturbation. La soi-disant fonction de perturbation est de tout mélanger ensemble. Vous pouvez voir que quatre opérations de changement de droite à droite sont utilisées ici. Le but est de mélanger la valeur élevée de H et la faible valeur pour augmenter l'aléatoire de la faible valeur. Comme ci-dessus, nous savons que l'indice du tableau de positionnement est déterminé en fonction de la valeur faible du code du code de hachage. Le code de hash de la clé est généré par la méthode HashCode, et la faible valeur du code de hash généré par une mauvaise méthode HashCode peut avoir beaucoup de répétition. Afin de rendre le code de hachage cartographié relativement uniformément sur le tableau, la fonction de perturbation est utile, combinant les caractéristiques de la valeur élevée dans la valeur faible, augmentant l'aléatoire de la valeur de faible bit, rendant ainsi la distribution de hachage plus lâche, améliorant ainsi les performances. Le chiffre suivant donne un exemple pour aider à comprendre.
7. Que se passe-t-il avec le hachage de remplacement?
Nous voyons que dans la méthode de hachage, les graines de hachage seront d'abord affectées à h. Cette graine de hachage est une graine de hachage, qui est une valeur aléatoire, et est utilisée pour aider à optimiser la fonction de hachage. Les graines de hachage par défaut sont 0, ce qui signifie que l'algorithme de hachage alternatif n'est pas utilisé par défaut. Alors, quand utiliser les graines de haschie? Tout d'abord, vous devez définir le hachage alternatif pour activer et définir la valeur de jdk.map.althashing.threshold dans la propriété système. Cette valeur est -1 par défaut dans la propriété système. Lorsqu'il est -1, la valeur seuil de l'utilisation du hachage alternatif est Integer.max_value. Cela signifie également que vous ne pouvez jamais utiliser de hachage de remplacement. Bien sûr, vous pouvez définir ce seuil un peu plus petit, de sorte qu'une graine de hachage aléatoire sera générée lorsque l'élément défini atteint le seuil. Cela augmente l'aléatoire de la fonction de hachage. Pourquoi utiliser un hachage alternatif? Lorsque l'élément défini atteint le seuil que vous définissez, cela signifie que le tableau de hachage est relativement saturé et que la possibilité de conflits de hachage augmentera considérablement. À l'heure actuelle, l'utilisation d'une fonction de hachage plus aléatoire pour les éléments ajoutées peut rendre les éléments ajoutés plus répartis au hasard dans la table de hachage.
Remarque: Toute l'analyse ci-dessus est basée sur JDK1.7, et il y aura des changements majeurs entre différentes versions, les lecteurs doivent faire attention.