La plupart des développeurs Java utilisent la carte, en particulier HashMap. Hashmap est un moyen simple mais puissant de stocker et d'obtenir des données. Mais combien de développeurs savent comment fonctionne HashMap en interne? Il y a quelques jours, j'ai lu beaucoup de code source de java.util.hashmap (y compris Java 7 et Java 8) pour acquérir une compréhension approfondie de cette structure de données de base. Dans cet article, je vais expliquer la mise en œuvre de Java.util.hashmap, décrire les nouvelles fonctionnalités ajoutées dans l'implémentation Java 8 et discuter des performances, de la mémoire et de certains problèmes connus lors de l'utilisation de HashMap.
Stockage interne
La classe Java Hashmap implémente l'interface MAP <k, v>. Les principales méthodes de cette interface comprennent:
V put (clé k, valeur v) v get (clé d'objet) v supprimer (clé d'objet) booléen contientyy (clé d'objet)
Hashmap utilise une entrée de classe interne <k, v> pour stocker les données. Cette classe intérieure est une simple paire de valeurs clés avec deux données supplémentaires:
Une référence à une autre entrée, afin que HashMap puisse stocker des objets comme les listes de liens.
Une valeur de hachage utilisée pour représenter la clé. Le stockage de cette valeur peut empêcher HashMap de régénérer la valeur de hachage correspondant à la clé à chaque fois qu'il est nécessaire.
Voici une partie du code pour l'entrée <k, v> sous Java 7:
Entrée de classe statique <k, v> implémente Map.Entry <k, v> {Key final k; Vale V; entrée <k, v> Next; int hash;…}Hashmap stocke les données dans plusieurs listes unidirectionnelles (parfois appelées seaux ou orbins de conteneurs). Toutes les listes sont enregistrées dans un tableau d'entrée (entrée <k, v> [] tableau), et la longueur par défaut de ce tableau interne est de 16.
La figure suivante décrit le stockage interne d'une instance HashMap, qui contient un tableau d'objets nullables. Chaque objet est connecté à un autre objet, formant ainsi une liste liée.
Toutes les clés avec la même valeur de hachage seront placées dans la même liste liée (seau). Les clés avec des hachages différents peuvent se retrouver dans le même seau.
Lorsque les appels utilisateur put (Key K, V Valeur) ou GET (clé objet), le programme calcule l'index du seau dans lequel l'objet doit être.
Dans le cas de l'appel get (), le programme renverra l'objet d'entrée correspondant à la valeur (si l'objet d'entrée existe).
Pour que l'appel à mettre (clé k, valeur V), si l'objet d'entrée existe déjà, le programme remplacera la valeur par une nouvelle valeur, sinon le programme créera une nouvelle entrée (clé et valeur dans le paramètre) à l'en-tête de la liste liée à sens unique.
L'index du seau (liste liée) est généré via 3 étapes de la carte:
Obtenez d'abord le code de hachage de la clé.
Le programme répète le code de hachage pour bloquer les mauvaises fonctions de hachage pour les clés, car cela a le potentiel de mettre toutes les données sur le même index (godet) du tableau interne.
Le programme prend le code de hachage en double et utilise un masque à bid de la longueur du tableau (minimum 1) pour cela. Cette opération garantit que l'indice ne sera pas supérieur à la taille du tableau. Vous pouvez le considérer comme une fonction de module optimisée calculée.
Voici le code source pour générer l'index:
// La fonction "Rehash" dans Java 7 qui prend le code de hash du hachage Keystatic int (int h) {h ^ = (h >>> 20) ^ (h >>> 12); retour h ^ (h >>> 7) ^ (h >>> 4);} // la fonction "re-rehash" dans Java 8 qui prend directement la finale Keystatic Inth hash ( 0: (h = key.hashcode ()) ^ (h >>> 16);} // La fonction qui renvoie l'index de l'index hashstatique remanié (int h, int le long) {return h & (longueur-1);}Pour travailler plus efficacement, la taille du tableau intérieur doit être une puissance de 2. Voyons pourquoi:
En supposant que la longueur du tableau est de 17, la valeur du masque est de 16 (longueur du tableau-1). La représentation binaire de 16 est 0… 010000, de sorte que pour toute valeur h, le résultat de "H & 16" est 16 ou 0. Cela signifie que les tableaux de longueur 17 ne peuvent être appliqués qu'à deux seaux: l'un est 0 et l'autre est 16, ce qui n'est pas très efficace. Mais si vous définissez la longueur du tableau sur une puissance de 2, par exemple 16, alors l'indexation du bit fonctionne sur "H & 15". La représentation binaire de 15 est de 0… 001111, et la sortie de valeur par la formule d'index peut varier de 0 à 15, de sorte qu'un tableau de longueur 16 peut être entièrement utilisé. Par exemple:
Si H = 952, sa représentation binaire est de 0..01110111000, et l'index correspondant est 0… 01000 = 8
Si H = 1576, sa représentation binaire est de 0..011000101000, et l'index correspondant est 0… 01000 = 8
Si H = 12356146, sa représentation binaire est de 0..010111001000101010010, l'index correspondant est 0… 00010 = 2
Si H = 59843, sa représentation binaire est de 0..01110100111000011, son index correspondant est de 0… 00011 = 3
Ce mécanisme est transparent pour le développeur: s'il sélectionne un hashmap de la longueur 37, la carte sélectionnera automatiquement la prochaine valeur de puissance supérieure à 37 (64) comme longueur du réseau interne.
Redimensionner automatiquement
Après avoir obtenu l'index, les méthodes get (), put () ou supprimer () accéderont à la liste liée correspondante pour voir si l'objet d'entrée pour la clé spécifiée existe déjà. Sans modification, ce mécanisme peut entraîner des problèmes de performances, car cette méthode nécessite une itération de toute la liste pour voir si l'objet d'entrée existe. Supposons que la durée du tableau interne prend la valeur par défaut de 16 et que vous devez stocker 2 000 000 enregistrements. Dans le meilleur des cas, il y aura 125 000 objets d'entrée par liste liée (2 000 000/16). Les méthodes get (), retire () et put () nécessitent 125 000 itérations chaque fois qu'elles sont exécutées. Pour éviter cela, HashMap peut augmenter la longueur du réseau interne, garantissant ainsi que seuls quelques objets d'entrée sont conservés dans la liste liée.
Lorsque vous créez un hashmap, vous pouvez spécifier une longueur initiale et un chargeur de charge via le constructeur suivant:
</ pre> public hashmap (int initialCapacity, float chargefactor) <pre>
Si vous ne spécifiez pas de paramètres, la valeur de capacité initiale par défaut est 16 et la valeur de chargement par défaut est de 0,75. InitialCapacity représente la longueur de la liste liée du tableau interne.
Lorsque vous utilisez la méthode put (…) pour ajouter une nouvelle paire de valeurs clés à la carte, la méthode vérifie si la longueur du tableau intérieur doit être augmentée. Pour y parvenir, la carte stocke 2 données:
Taille de la carte: il représente le nombre d'enregistrements dans HashMap. Nous mettons à jour la valeur lorsque nous l'insérons ou le supprimons dans le hashmap.
Seuil: il est égal à la longueur du tableau interne * LoadFactor, et ce seuil sera également mis à jour en même temps chaque fois que la longueur du réseau interne est ajustée.
Avant d'ajouter un nouvel objet d'entrée, la méthode put (…) vérifie si la taille de la carte actuelle est supérieure au seuil. S'il est supérieur au seuil, il crée un nouveau tableau avec deux fois la longueur du réseau interne actuel. Étant donné que la taille du nouveau tableau a changé, la fonction d'index (c'est-à-dire le résultat de l'opération de bit qui renvoie la "valeur de hachage de la clé et (longueur du tableau -1)") change également. Le redimensionnement du tableau crée deux nouveaux seaux (listes liées) et réaffecte tous les objets d'entrée existants dans le seau. L'objectif d'ajuster la taille du tableau est de réduire la taille de la liste liée, réduisant ainsi le temps d'exécution de put (), retire () et get (). Pour tous les objets d'entrée correspondant aux clés avec la même valeur de hachage, ils sont alloués au même seau après le redimensionnement. Cependant, si les valeurs de hachage des deux objets d'entrée sont différentes, mais qu'elles étaient sur le même seau avant, puis après ajustement, il n'y a aucune garantie qu'ils sont toujours sur le même seau.
Cette image décrit la situation des tableaux internes pré-ajustement et après réajustement. Avant d'ajuster la longueur du tableau, afin d'obtenir l'objet d'entrée E, la carte doit itérer sur une liste liée contenant 5 éléments. Après avoir ajusté la longueur du tableau, la même méthode GET () n'a besoin que de traverser une liste liée contenant 2 éléments, de sorte que la vitesse d'exécution de la méthode get () après ajustement de la longueur du tableau est augmentée de 2 fois.
Sécurité en fil
Si vous êtes déjà très familier avec Hashmap, vous savez certainement qu'il n'est pas sûr de fil, mais pourquoi? Par exemple, supposons que vous ayez un fil d'écrivain qui n'insertera que les données existantes dans la carte, un thread de lecteur qui lira les données de la carte, alors pourquoi cela ne fonctionne-t-il pas?
Parce que dans le mécanisme de redimensionnement automatique, si le thread essaie d'ajouter ou d'obtenir un objet, la carte peut utiliser l'ancienne valeur d'index, de sorte que le nouveau seau où se trouve l'objet d'entrée ne sera pas trouvé.
Dans le pire des cas, lorsque 2 threads insérer des données en même temps, 2 appels put () commenceront en même temps et le tableau redimensionnera automatiquement. Étant donné que deux threads modifient la liste liée en même temps, il est possible que la carte quitte dans la boucle interne d'une liste liée. Si vous essayez d'obtenir des données d'une liste avec une boucle intérieure, la méthode get () ne se terminera jamais.
HashTable fournit une implémentation en filetage qui empêche ce qui précède. Cependant, car toutes les opérations de crud synchrones sont très lentes. Par exemple, si les appels du thread 1 obtiennent (Key1), puis le thread 2 appelle (Key2) et que le thread 2 appelle (Key3), puis à un moment spécifié, un seul thread peut obtenir sa valeur, mais les 3 threads peuvent accéder à ces données en même temps.
Depuis Java 5, nous avons une mise en œuvre de HashMap meilleure et à filetage: concurrenthashmap. Pour ConcurrentMap, seuls les seaux sont synchronisés, de sorte que si plusieurs threads n'utilisent pas le même godet ou ne redimensionnent pas le tableau interne, ils peuvent appeler les méthodes get (), retire () ou put () en même temps. Dans une application multithread, cette approche est un meilleur choix.
Invariance des obligations
Pourquoi est-ce une bonne implémentation d'utiliser des chaînes et des entiers comme clés de hashmap? Principalement parce qu'ils sont immuables! Si vous choisissez de créer vous-même une classe comme clé, mais que vous ne pouvez pas garantir que la classe est immuable, vous pouvez perdre des données à l'intérieur de HashMap.
Examinons les cas d'utilisation suivants:
Vous avez une clé dont la valeur interne est "1".
Si vous insérez un objet dans un hashmap, sa clé est "1".
Hashmap génère des valeurs de hachage à partir du code de hachage de la clé (c'est-à-dire "1").
MAP stocke cette valeur de hachage dans l'enregistrement nouvellement créé.
Vous modifiez la valeur interne de la clé et la modifiez en "2".
La valeur de hachage de la clé a changé, mais HashMap ne le sait pas (parce que l'ancienne valeur de hachage est stockée).
Vous essayez d'obtenir l'objet correspondant par la clé modifiée.
La carte calcule la valeur de hachage de la nouvelle clé (c'est-à-dire "2") pour trouver la liste liée (seau) où se trouve l'objet d'entrée.
Cas 1: Puisque vous avez modifié la clé, MAP essaiera de rechercher l'objet d'entrée dans le mauvais seau, mais il n'est pas trouvé.
Cas 2: Vous avez de la chance que le seau généré par la touche modifiée et le seau généré par l'ancienne clé soient les mêmes. La carte traversera ensuite la liste liée et un objet d'entrée avec la même clé a été trouvé. Mais pour trouver la clé, MAP comparera d'abord la valeur de hachage de la clé en appelant la méthode equals (). Étant donné que la touche modifiée générera différentes valeurs de hachage (les anciennes valeurs de hachage sont stockées dans l'enregistrement), MAP n'a aucun moyen de trouver l'objet d'entrée correspondant dans la liste liée.
Voici un exemple Java où nous insérons deux paires de valeurs clés dans la carte, puis je modifie la première clé et essaye d'obtenir les deux objets. Vous constaterez que seul le deuxième objet est retourné de la carte, le premier objet a été "perdu" dans le hashmap:
classe publique MutableKeyTest {public static void main (String [] args) {class myKey {Integer i; public void seti (entier i) {this.i = i;} public myKey (entier i) {this.i = i;} @ overdepublic int hashcode () {return i;} @ overnidepubl MyKey) {return i.equals (((myKey) obj) .i);} elsereturn false;}} map <myKey, string> mymap = new hashmap <> (); myKey key1 = newykey (1); myKey key2 = new myKey (2); mymap.put (key1, "test" + 1); key1key1.seti (3); string test1 = mymap.get (key1); string test2 = mymap.get (key2); System.out.println ("test1 =" + test1 + "test2 =" + test2);}}La sortie du code ci-dessus est "test1 = null test2 = test 2". Comme nous nous attendons, MAP n'a pas la capacité d'obtenir la chaîne 1 correspondant à la clé modifiée 1.
Améliorations en Java 8
Dans Java 8, l'implémentation interne dans HashMap a beaucoup été modifiée. En effet, Java 7 utilise 1000 lignes de code pour l'implémenter, tandis que Java 8 utilise 2000 lignes de code. La plupart de ce que j'ai décrit précédemment est toujours correct dans Java 8, sauf en utilisant des listes liées pour enregistrer les objets d'entrée. Dans Java 8, nous utilisons toujours des tableaux, mais il sera enregistré dans Node, qui contient les mêmes informations que l'objet d'entrée précédent et utilise également une liste liée:
Voici une partie du code qui implémente le nœud dans Java 8:
Classe statique Node <k, v> implémente map.entry <k, v> {final int hash; key final k; V valeur v; nœud <k, v> suivant;Alors, quelle est la grande différence par rapport à Java 7? Eh bien, le nœud peut être étendu à Treenode. Treenode est une structure de données d'un arbre rouge et noir qui peut stocker plus d'informations, afin que nous puissions ajouter, supprimer ou obtenir un élément sous la complexité de O (log (n)). L'exemple suivant décrit toutes les informations enregistrées par Treenode:
classe finale statique Treenode <k, v> étend LinkedHashmap.entry <k, v> {final int hash; // Hérité de Node <K, V> Clé finale K; // hérité de la valeur nœud <k, v> v; // Hérité du nœud <k, v> nœud <k, v> suivant; // Hérité de Node <k, v> entrée <k, v> avant, après; // hérité de LinkedHashmap.entry <k, v> parent; Treenode <k, v> gauche; treenode <k, v> droit; treenode <k, v> prev; booléen rouge;Les arbres rouges et noirs sont des arbres de recherche binaires auto-équilibrés. Son mécanisme interne garantit que sa longueur est toujours log (n), que nous ajoutions ou supprimons les nœuds. L'avantage le plus important de l'utilisation de ce type d'arbre est qu'il est le cas que de nombreuses données dans la table interne ont le même index (godet). À l'heure actuelle, la complexité de la recherche de l'arborescence est O (log (n)), et pour la liste liée, la complexité est O (n) pour effectuer la même opération.
Comme vous pouvez le voir, nous stockons plus de données dans l'arbre que les listes liées. Selon le principe de l'héritage, la table interne peut contenir du nœud (liste liée) ou du Treenode (arbre rouge et noir). Oracle décide d'utiliser ces deux structures de données selon les règles suivantes:
- Pour l'index spécifié (seau) dans la table interne, si le nombre de nœuds est supérieur à 8, la liste liée sera convertie en arbre rouge et noir.
- Pour l'index spécifié (seau) dans la table interne, si le nombre de nœuds est inférieur à 6, l'arbre rouge et noir sera converti en liste liée.
Cette image décrit un tableau interne dans un hashmap Java 8, qui contient à la fois des listes d'arbre (seau 0) et des listes liées (seau 1, 2 et 3). Le seau 0 est une structure d'arbre car il contient plus de 8 nœuds.
Au-dessus de la mémoire
Java 7
L'utilisation de hashmap consomme une certaine mémoire. Dans Java 7, HashMap encapsule les paires de valeurs clés dans les objets d'entrée, un objet d'entrée contient les informations suivantes:
Référence à l'enregistrement suivant Une valeur de hachage pré-calculée (entier)
Une référence à une clé et une référence à une valeur
De plus, Hashmap dans Java 7 utilise un tableau interne d'objets d'entrée. Supposons qu'un hashmap Java 7 contient des éléments n et que son réseau interne a une capacité, alors la consommation de mémoire supplémentaire est de savoir:
Sizeof (entier) * n + sizeof (référence) * (3 * n + c)
dans:
La taille d'un entier est de 4 octets
La taille de la référence dépend du JVM, du système d'exploitation et du processeur, mais est généralement de 4 octets.
Cela signifie que les frais généraux de mémoire totale sont généralement des octets de capacité de 16 * n + 4 *.
Remarque: Une fois la carte automatique, la valeur de la capacité est la prochaine plus petite puissance de 2 supérieure à N.
Remarque: À partir de Java 7, Hashmap adopte un mécanisme de chargement paresseux. Cela signifie que même si vous spécifiez la taille de HashMap, le tableau interne utilisé (consommant 4 * octets de capacité) qui n'est pas alloué en mémoire avant d'utiliser d'abord la méthode put ().
Java 8
Dans les implémentations Java 8, l'utilisation de la mémoire de calcul devient plus compliquée car le nœud peut stocker les mêmes données que l'entrée, ou ajouter 6 références et une propriété booléenne (spécifiant s'il s'agit d'un Treenode).
Si tous les nœuds ne sont que des nœuds, la mémoire consommée par Java 8 Hashmap est la même que celle consommée par Java 7 Hashmap.
Si tous les nœuds sont Treenode, alors la mémoire consommée par Java 8 Hashmap devient:
N * sizeof (entier) + n * sizeof (booléen) + sizeof (référence) * (9 * n + capacité)
Dans la plupart des JVM standard, le résultat de la formule ci-dessus est de 44 * n + 4 * octets de capacité.
Problèmes de performance
Hashmap asymétrique vs hashmap équilibré
Dans le meilleur des cas, les méthodes GET () et put () n'ont que la complexité O (1). Cependant, si vous ne vous souciez pas de la fonction de hachage de la clé, vos méthodes put () et get () peuvent s'exécuter très lentement. L'exécution efficace des méthodes put () et get () dépend des données allouées à différents indices du tableau interne (seau). Si la fonction de hachage de la clé n'est pas conçue correctement, vous obtiendrez une partition asymétrique (quelle que soit la taille des données internes). Toutes les méthodes put () et get () utiliseront la plus grande liste liée, qui sera lente à exécuter car elle nécessite une itération de tous les enregistrements de la liste liée. Dans le pire des cas (si la plupart des données se trouvent sur le même seau), votre complexité temporelle devient O (n).
Voici un exemple visuel. Le premier graphique décrit un hashmap asymétrique et le deuxième graphique décrit un hashmap égalisé.
asymétrique
Dans ce hashmap asymétrique, il faudra du temps pour exécuter les méthodes get () et put () sur le seau 0. Obtenir un enregistrement k prend 6 itérations.
Dans ce hashmap équilibré, il faut que 3 itérations pour obtenir l'enregistrement K. Ces deux hashmaps stockent la même quantité de données et les tableaux internes sont de la même taille. La seule différence est la fonction de hachage de la clé, qui est utilisée pour distribuer des enregistrements à différents seaux.
Voici un exemple extrême écrit en Java, dans lequel j'utilise une fonction de hachage pour mettre toutes les données dans la même liste liée (seau), puis j'ai ajouté 2 000 000 de données.
Test de classe publique {public static void main (String [] args) {class myKey {Integer i; public myKey (Integer i) {this.i = i;} @ overRidepublic int hashcode () {return 1;} @ overRidepublic booléan equals (objet obj) {…}} date begin = new date (); mapy <myKey, string> mymap = newy Hashmap <> (2_500_000,1); for (int i = 0; i <2_000_000; i ++) {mymap.put (new myKey (i), "test" + i);} date End = new Date (); system.out.println ("durée (ms)" + (end.gettime () - beginTime ());}}Ma configuration de la machine est Core i5-2500K @ 3,6g, et il faut plus de 45 minutes pour fonctionner sous Java 8U40 (j'ai arrêté le processus après 45 minutes). Si j'exécute le même code, mais j'utilise la fonction de hachage comme ceci:
@OverridePublic int hashcode () {int key = 2097152-1; return key + 2097152 * i;}Il faut 46 secondes pour l'exécuter, ce qui est bien meilleur qu'avant! La nouvelle fonction de hachage est plus raisonnable que l'ancienne fonction de hachage lors du traitement des partitions de hachage, donc appeler la méthode put () est plus rapide. Si vous exécutez le même code maintenant, mais utilisez la fonction de hachage ci-dessous, il fournit une meilleure partition de hachage:
@OverridePublic int hashcode () {return i;}Maintenant, cela ne prend que 2 secondes!
J'espère que vous pourrez réaliser à quel point les fonctions de hachage sont importantes. Si vous exécutez le même test sur Java 7, le premier et le deuxième seront pires (car la méthode put () dans Java 7 a une complexité O (n), tandis que la complexité de Java 8 a O (log (n)).
Lorsque vous utilisez HashMap, vous devez trouver une fonction de hachage pour les touches qui peuvent répartir les clés du seau le plus probable. Pour ce faire, vous devez éviter les conflits de hachage. Un objet String est une très bonne clé car il a une bonne fonction de hachage. L'entier est également bon car son hachage est sa propre valeur.
Redimensionner les frais généraux
Si vous avez besoin de stocker une grande quantité de données, vous devez spécifier une capacité initiale lors de la création d'un hashmap, qui doit être proche de la taille souhaitée.
Si vous ne le faites pas, la carte utilisera la taille par défaut, c'est-à-dire 16, et la valeur du facteur est de 0,75. Les 11 premiers appels à mettre () la méthode seront très rapides, mais le 12e (16 * 0,75) appel créera un nouveau tableau interne avec la longueur 32 (et la liste / arbre lié correspondant), et le 13e au 22e appel à mettre () sera très rapide, mais le 23rd (32 * 0.75) sera recruté (à nouveau) un nouveau tableau interne, et la longueur de l'arrivée sera doublé. Ensuite, l'opération de redimensionnement interne sera déclenchée lorsque la méthode put () est appelée 48th, 96th, 192nd…. Si la quantité de données n'est pas importante, le fonctionnement de la reconstruction du tableau interne sera très rapide, mais lorsque la quantité de données est importante, le temps passé peut aller de secondes à quelques minutes. En spécifiant la taille souhaitée de la carte pendant l'initialisation, vous pouvez éviter la consommation causée par les opérations de redimensionnement.
Mais il y a aussi un inconvénient ici: si vous définissez le tableau pour être très grand, par exemple 2 ^ 28, mais que vous utilisez simplement 2 ^ 26 seaux dans le tableau, alors vous gaspillerez beaucoup de mémoire (environ 2 ^ 30 octets dans cet exemple).
en conclusion
Pour les cas d'utilisation simples, vous n'avez pas besoin de savoir comment fonctionne HashMap, car vous ne verrez pas la différence entre O (1), O (n) et O (log (n)). Mais il est toujours avantageux de comprendre le mécanisme derrière cette structure de données fréquemment utilisée. De plus, il s'agit d'une question d'entrevue typique pour les positions des développeurs Java.
Pour les volumes de données importants, il devient très important de comprendre comment fonctionne HashMap et de comprendre l'importance d'une fonction de hachage pour les clés.
J'espère que cet article peut vous aider à avoir une compréhension approfondie de la mise en œuvre de HashMap.