Hashmap et Hashset sont deux membres importants du cadre de la collection Java. HashMap est une classe d'implémentation commune pour l'interface MAP, et HashSet est une classe d'implémentation commune pour l'interface définie. Bien que les spécifications d'interface implémentées par HashMap et HashSet soient différentes, leur mécanisme de stockage de hachage sous-jacent est exactement le même, et même HashSet lui-même utilise HashMap pour l'implémenter.
En fait, il existe de nombreuses similitudes entre Hashset et Hashmap. Pour HashSet, le système utilise l'algorithme de hachage pour déterminer l'emplacement de stockage des éléments de collecte, afin de s'assurer que les éléments de collecte peuvent être stockés et récupérés rapidement; Pour Hashmap, la valeur de clé du système est traitée dans son ensemble, et le système calcule toujours l'emplacement de stockage de la valeur clé en fonction de l'algorithme de hachage, de sorte que les paires de valeurs clés de la carte peuvent être stockées et récupérées rapidement.
Avant d'introduire le stockage de collection, il convient de souligner que bien qu'une collection prétend stocker des objets Java, il ne met pas réellement des objets Java dans la collection de sets, mais conserve uniquement les références à ces objets dans la collection de sets. C'est-à-dire qu'une collection Java est en fait une collection de variables de référence multiples qui pointent vers l'objet Java réel.
1. Caractéristiques de base de Hashmap
Après avoir lu les commentaires dans le code source JDK Hashmap.class, vous pouvez résumer de nombreuses fonctionnalités de hashmap.
HashMap permet à la clé et à la valeur d'être nuls, tandis que le hashtable ne le fait pas.
Hashmap est l'insecture par thread, tandis que le hashtable est en filetage
L'ordre des éléments dans Hashmap n'est pas toujours le même, et la position du même élément peut également changer avec le temps (le cas du redimensionnement)
La complexité temporelle de la traversée d'un hashmap est proportionnelle à sa capacité et au nombre d'éléments existants. Si vous souhaitez assurer l'efficacité de la traversée, la capacité initiale ne peut pas être réglée trop élevée ou le facteur d'équilibre ne peut pas être réglé trop bas.
Semblable à la liste connexe précédente, puisque HashMap est insérée par thread, l'échec sera généré lorsque l'itérateur essaie de modifier la structure du conteneur pendant le processus d'itération. Un hashmap synchronisé peut être obtenu par le biais de collections.
2. Analyse de la structure des données de la table de hachage
La table de hachage (table de hachage, table de hachage) est une structure de données qui accède directement aux emplacements de stockage de mémoire en fonction des mots clés. C'est-à-dire que le tableau de hachage établit une cartographie directe entre les mots clés et les adresses de stockage
Comme le montre la figure ci-dessous, la clé obtient une position d'index des seaux à travers la fonction de hachage.
L'obtention de l'indice par le biais de la fonction de hachage se produira inévitablement la même situation, c'est-à-dire le conflit. Voici quelques façons de résoudre les conflits:
Adresse ouverte: L'idée de base de cette méthode est de numériser des positions n sous le tableau en séquence lors de la rencontre de conflits et de remplir s'il y en a un libre. L'algorithme spécifique ne sera plus expliqué, ce qui suit est un diagramme schématique:
Chaîne séparé: L'idée de base de cette méthode est de chaîner la série avec la même valeur d'index dans une liste liée lors de la rencontre de conflits. L'algorithme spécifique ne sera plus expliqué, ce qui suit est un diagramme schématique:
La méthode pour résoudre les conflits dans Hashmap dans JDK consiste à utiliser la méthode de chaînage distincte.
3. Analyse du code source Hashmap (JDK1.7)
1. Hashmap Lire et écrire des éléments
Entrée
Les éléments stockés dans Hashmap sont de type d'entrée. Le code d'entrée source dans le code source est donné ci-dessous:
Entrée de classe statique <k, v> implémente Map.Entry <k, v> {Final K Key; V valeur v; Entrée <k, v> Suivant; int hash; Entrée (int h, k k, v v, entrée <k, v> n) {value = v; suivant = n; clé = k; hash = h; } // Les méthodes Get and Set de Key, la valeur sont omises, les opérations Get and Set seront utilisées dans les itérateurs suivants ... public final booléen égaux (objet o) {if (! (O instanceof map.entry)) return false; Map.entry e = (map.entry) o; Objet k1 = getKey (); Objet k2 = e.getKey (); if (k1 == k2 || (k1! = null && k1.equals (k2))) {objet v1 = getValue (); Objet v2 = e.getValue (); if (v1 == v2 || (v1! = null && v1.equals (v2))) return true; } return false; } // Ici, faites ou utilisez le HashCode de Key et le HashCode de valeur pour obtenir le HashCode de l'entrée publique final int hashcode () {return objets.hashcode (getKey ()) ^ objets.hashcode (getValue ()); } public final String toString () {return getKey () + "=" + getValue (); } / ** * Cette méthode est invoquée chaque fois que la valeur d'une entrée est * écrasée par une invocation de put (k, v) pour une clé k qui est déjà * dans le hashmap. * / void RecordAccess (hashmap <k, v> m) {} / ** * Cette méthode est invoquée chaque fois que l'entrée est * supprimée du tableau. * / void RecordRemoval (hashmap <k, v> m) {}}Une entrée comprend une clé, une valeur, un hachage et une référence à la prochaine entrée. Il est évident qu'il s'agit d'une seule liste liée, qui met en œuvre l'interface Map.Entry.
Recordacess (hashmap <k, v> et enregistrement record (hashmap <k, v>) ne sont pas mis en œuvre dans hashmap. Cependant, les deux méthodes de LinkedHashmap sont utilisées pour implémenter l'algorithme LRU.
Get: Lisez les éléments pour obtenir l'entrée correspondante de HashMap. Ce qui suit est le code source de GET:
public v get (object key) {// La situation où la clé est null if (key == null) return getFornullkey (); // Trouver une entrée en fonction de la saisie de clé d'entrée <k, v> entrée = GetEntry (clé); retourner null == entrée? null: entry.getValue (); }Code source GetFornullkey
private v getFornullKey () {if (size == 0) {return null; } // Transtraighten la chaîne de conflit pour (entrée <k, v> e = table [0]; e! = Null; e = e.next) {if (e.key == null) return e.value; } return null; }L'entrée avec une clé null est stockée dans le tableau [0], mais la chaîne de conflit dans le tableau [0] n'a pas nécessairement une clé comme nul, il doit donc être traversé.
Obtenez l'entrée en fonction de la clé:
Entrée finale <k, v> GetEntry (clé d'objet) {if (size == 0) {return null; } int hash = (key == null)? 0: Hash (clé); // Obtenez la position d'index dans le tableau via le hachage, puis parcourez la liste liée conflictuelle pour trouver la 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; } return null; }Ce qui précède est le processus de la lecture de HashMap une entrée et de son code source. Complexité du temps O (1)
PUT: Écrivez des éléments
L'opération de put dans HashMap est relativement compliquée car il y aura une opération d'extension HashMap pendant l'opération de vente.
Lorsqu'un nouvel élément est écrit, s'il existe une clé pour écrire l'élément dans HashMap, le fonctionnement du remplacement de la valeur est effectué, ce qui équivaut à la mise à jour. Voici le code source de put:
public v put (k key, v valeur) {// Si la table est vide, remplissez if (table == vide_table) en fonction du seuil de taille {inflatiable (threshold); } // Remplissez l'entrée avec la clé comme null if (key == null) return putFornullKey (valeur); // générer du hash pour obtenir le mappage de l'index index int hash = hash (key); int i = indexfor (hash, table.length); // transsulez la chaîne de conflit de l'indice actuel pour découvrir s'il existe une clé correspondante pour (entrée <k, v> e = table [i]; e! = Null; e = e.next) {objet k; // Si la clé correspondante existe, remplacez OldValue et Return OldValue if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.Value; e.Value = valeur; e.recordAccess (this); Retour OldValue; }} // La clé de l'entrée nouvellement écrite n'existe pas dans la chaîne de conflit ModCount ++; // insérer un nouvel adredry d'entrée (hachage, clé, valeur, i); retourner null; }Addentry et CreateEntry Code source:
void Addentry (hash int, k key, V valeur V, int bucketIndex) {// Avant d'insérer une nouvelle entrée, jugez d'abord la taille du hashmap actuel et sa taille de seuil, et sélectionnez s'il faut étendre if ((taille> = threshold) && (null! = table [bucketIndEx])) {redimensit (2 * TableN.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]; // Méthode d'insertion de la tête, l'entrée nouvellement écrite est insérée à l'avant de la première entrée de la chaîne de conflits à la position d'index actuelle. table [bucketIndex] = nouvelle entrée <> (hachage, clé, valeur, e); taille ++; }Ce qui précède est le processus d'écriture d'une entrée dans un hashmap et son code source. Complexité du temps O (1)
Retirer l'élément de suppression:
Entrée finale <k, v> removeNentRyForkey (clé d'objet) {if (size == 0) {return null; } // Calculez la valeur de hachage en fonction de la clé et obtenez l'index int hash = (key == null)? 0: Hash (clé); int i = indexfor (hash, table.length); // Supprimer la liste liée, définir deux pointeurs, PRE représente l'entrée du prédécesseur <k, v> prev = table [i]; Entrée <k, v> e = prev; // Transtraiteur de la chaîne de conflit et supprimez toutes les touches while (e! = Null) {entrée <k, v> Next = e.Next; Objet K; // si trouvé (e.hash == hash && ((k = e.key) == key || (key! = Null && key.equals (k)))) {modCount ++; taille--; // Trouver le premier nœud est le nœud à supprimer si (prev == e) tableau [i] = suivant; else prev.Next = Suivant; e.recordRemoval (this); retour e; } prev = e; e = suivant; } return e; }Ce qui précède est le processus de suppression de HashMap une entrée et de son code source. Complexité du temps O (1)
2. Principe de hachage de hashmap (fonction de hachage)
La mise en œuvre de la fonction de hachage dans HashMap est effectuée via Hash (Object K) et IndexFor (int h, intylgage). Jetons un coup d'œil au code source ci-dessous:
Final int hash (objet k) {int h = hashseed; if (0! = H && k instance de chaîne) {return Sun.Misc.hashing.StringHash32 ((String) K); } h ^ = k.hashcode (); // Cette fonction garantit que les codes de hashs qui différents sont différents par // les multiples constants à chaque position de bits ont un nombre de collisions délimitées (environ 8 au facteur de charge par défaut). // afin de réduire le risque de conflit h ^ = (h >>> 20) ^ (h >>> 12); retour h ^ (h >>> 7) ^ (h >>> 4); }Obtenez le code source de l'index de l'index:
static int indexfor (int h, int le long) {// Assert Integer.BitCount (longueur) == 1: "la longueur doit être une puissance non nulle de 2"; retour h & (longueur-1); }HashMap Map Map Keys to Index dans l'intervalle de [0, table.length] via une fonction de hachage. Il existe généralement deux types de méthodes d'indexation:
hash (key)% table.lengle, où la longueur doit être un nombre premier. Hashtable utilise cette implémentation dans JDK.
Pour des raisons spécifiques de l'utilisation de nombres premiers, vous pouvez trouver des preuves de données d'algorithme pertinentes, qui ne seront pas énoncées ici.
hash (key) & (table.length - 1) où la longueur doit être à la puissance exponentielle 2. HashMap dans JDK utilise cette méthode d'implémentation.
Parce que la taille de la longueur est de 2 temps exponentiels, le hachage (clé) et (Table.Length - 1) seront toujours entre [0, longueur - 1]. Cependant, si vous faites cela seul, il y aura un gros problème avec le conflit, car la valeur du code de hash en Java est de 32 bits. Lorsque la capacité de hashmap est faible, par exemple, lorsque 16, lorsque le fonctionnement XOR, le bit élevé est toujours rejeté, mais après le fonctionnement de bit faible, la probabilité de conflit se produit augmente.
Par conséquent, afin de réduire la probabilité d'occurrence des conflits, de nombreuses opérations de bits et des opérations exclusives ou des opérations sont effectuées dans le code.
3. Stratégie d'allocation de la mémoire Hashmap
Capacité variable du membre et chargeur
La capacité de capacité requise est un multiple exponentiel de 2 dans Hashmap, et la capacité par défaut est 1 << 4 = 16. Il existe également un facteur de solde (chargement de charge) dans HashMap. Des facteurs excessivement élevés réduiront l'espace de stockage, mais le temps de recherche (recherche, y compris les méthodes de put et d'obtention dans Hashmap) augmentera. La valeur par défaut de LoadFactor est de 0,75, ce qui est la valeur optimale donnée en pesant la complexité temporelle et la complexité de l'espace.
static final int default_initial_capacity = 1 << 4; // aka 16 static final int maximum_capacity = 1 << 30; float final statique default_load_factor = 0,75f;
Constructeur de hashmap
La construction de Hashmap est de régler la capacité et la valeur initiale de LoadFactor
public hashmap (int initialCapacity, float loadfactor) {if (initialCapacity <0) lance un nouveau IllégalArgumentException ("Capacité initiale illégale:" + 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 (); } J'ai déjà dit que cette capacité dans Hashmap devait être des temps exponentiels de 2, et il n'y a pas de limite dans le constructeur. Alors, comment s'assurer que cette valeur de capacité est des temps exponentiels de 2?
Pendant l'opération de put, le code source déterminera si la table de hachage actuelle est une table vide. Si c'est le cas, appelez l'inflativable (int tosize)
private void inflatetable (int toSize) {// trouver une puissance de 2> = tosize int Capacity = RoundUpToPowerOf2 (toSize); threshold = (int) math.min (capacité * chargefactor, maximum_capacity + 1); table = nouvelle entrée [capacité]; inithashseedasneed (capacité); }où RoundUptOprowerOf2 est d'obtenir la puissance n de 2 supérieure ou égale au paramètre donné
private static int RoundUpToPowerOf2 (int n °) {// Assert Number> = 0: "Le nombre doit être non négatif"; Numéro de retour> = maximum_capacité? Maximum_capacity: (nombre> 1)? Integer.HighestOnebit ((nombre - 1) << 1): 1; }Integer.HightOnebitbit (INT) est une opération qui conserve le bit le plus élevé d'un paramètre donné et modifie les 0 restants. En termes simples, il s'agit de modifier le paramètre INT en n pouvoirs inférieurs ou égaux à son maximum 2.
Si le nombre est n puissance de 2, le bit le plus élevé est au deuxième bit d'origine après décrémentation 1, puis déplacez-vous 1 bit à gauche pour être toujours positionné à la position le plus élevée. Si le nombre n'est pas une puissance n de 2, le bit le plus élevé est toujours le bit le plus élevé d'origine après décrément 1 bit à gauche pour déplacer 1 bit à gauche pour être
Élargir la capacité:
Hashmap aura un comportement de redimensionnement lors de la mise en service. Le code source spécifique est le suivant:
void Resize (int newCapacity) {entrée [] oldTable = table; int oldcapacity = oldTable.length; // Le tableau de hachage a atteint sa capacité maximale, 1 << 30 if (oldcapacity == maximum_capacity) {threshold = Integer.max_value; retour; } Entrée [] newtable = new Entry [newCapacity]; // Transférer l'entrée dans l'OldTable vers le newtable // La valeur de retour d'IniThashSeedasneed détermine s'il faut recalculer le transfert de valeur de hachage (Newtable, InithAshSeedasneed (newCapacity)); table = newtable; // Recalculer le seuil de seuil = (int) math.min (newCapacity * LoadFactor, maximum_capacity + 1); } void transfert (entrée [] newtable, boolean rehash) {int newcapacity = newtable.length; // transweep oldTable pour (entrée <k, v> e: table) {// transveldep chain de conflit while (null! = E) {entrée <k, v> next = e.next; if (rehash) {// recalculer la valeur de hachage e.hash = null == e.key? 0: Hash (E.Key); } int i = indexFor (e.hash, newCapacity); // insérer l'élément dans la tête, la méthode d'insertion d'en-tête e.next = newtable [i]; newtable [i] = e; e = suivant; }}}Ce qui précède est l'ensemble du processus d'allocation de mémoire HashMap. En résumé, lorsque HashMap met une entrée, il vérifiera la capacité actuelle et la taille du seuil pour sélectionner s'il faut étendre la capacité. La taille de chaque expansion est de 2 * Tableau.Length. Au cours de la période d'expansion, il déterminera si la valeur de hachage doit être recalculée en fonction de l'iNithashseedAneed.
4. Itérateur de hashmap
Les itérateurs tels que Valueterator, Keyiterator, Entryiterator et autres dans HashMap sont tous basés sur Hashitator. Jetons un coup d'œil à son code source:
classe abstraite privée Hashiterator <E> implémente iterator <e> {entrée <k, v> Next; // Entrée suivante pour retourner int attendModCount; // pour index int rapide; // l'emplacement actuel, entrée d'index de table <k, v> courant; // Hashitator d'entrée de courant () {attendModCount = modCount; // Trouvez la première entrée de la table de hachage if (taille> 0) {entrée [] t = table; while (index <t.length && (next = t [index ++]) == null); }} public final boolean hasnext () {return net! = null; } Entrée finale <k, v> NextEntry () {// hashmap est non-thread-safe, et lors de la traversée, déterminez toujours s'il y a une modification de la structure de la table if (modCount! = attendModCount) Jetez de nouveaux mododification ConcurrentException (); Entrée <k, v> e = suivant; if (e == null) lancez new nosuchementElementException (); if ((next = e.next) == null) {// Trouvez l'entrée suivante [] t = table; while (index <t.length && (next = t [index ++]) == null); } courant = e; retour e; } public void dissovel () {if (current == null) lancez new illégalStateException (); if (modCount! = attendModCount) lancez un nouveau concurrentModificationException (); Objet k = current.key; courant = null; Hashmap.CoS.Removeentryforkey (K); attendModCount = modCount; }}Les trois itérateurs, la clé, la valeur et l'entrée, sont encapsulés et deviennent trois perspectives de collecte: leset de touche, les valeurs et l'entrée. Ces trois perspectives de collecte prennent en charge les opérations Supprimer, Removeall et claire de HashMap, et ne prennent pas en charge les opérations d'ajout et d'addition.