Hashmap est également une collection que nous utilisons beaucoup. Il s'agit d'une implémentation de l'interface MAP basée sur des tables de hachage et existe sous la forme d'une valeur clé. Dans Hashmap, la valeur clé est toujours traitée dans son ensemble. Le système calculera l'emplacement de stockage de la valeur clé en fonction de l'algorithme de hachage. Nous pouvons toujours stocker et récupérer rapidement la valeur via la clé. Analysons l'accès à Hashmap.
1. Définition
Hashmap implémente l'interface de carte et hérite de l'abstractmap. L'interface MAP définit les règles de cartographie des clés aux valeurs, et la classe AbstractMap fournit l'implémentation de la squelette de l'interface MAP pour minimiser le travail requis pour implémenter cette interface. En fait, la classe AbstractMap a implémenté MAP. Je pense qu'il devrait être plus clair de marquer Map LZ ici!
classe publique Hashmap <k, v> étend AbstractMap <k, v> implémente la carte <k, v>, clonable, sérialisable
2. Fonction du constructeur
Hashmap fournit trois constructeurs:
Hashmap (): construit un hashmap vide avec la capacité initiale par défaut (16) et le facteur de chargement par défaut (0,75).
Hashmap (int initialCapacity): construit un hashmap vide avec la capacité initiale spécifiée et le facteur de chargement par défaut (0,75).
Hashmap (int initialCapacity, float chargefactor): construit un hashmap vide avec une capacité initiale et un facteur de charge initial spécifié.
Deux paramètres sont mentionnés ici: Capacité initiale, facteur de chargement. Ces deux paramètres sont des paramètres importants qui affectent les performances du hashmap. La capacité représente le nombre de seaux dans la table de hachage. La capacité initiale est la capacité lors de la création d'une table de hachage. Le facteur de chargement est une échelle que le tableau de hachage peut atteindre avant que sa capacité n'augmente automatiquement. Il mesure le degré d'utilisation d'un espace de table de hachage. Plus le facteur de charge indique que plus le degré de chargement de la table de hachage est élevé et vice versa. Pour les tables de hachage à l'aide de la méthode de liste liée, le temps moyen pour trouver un élément est O (1 + a). Par conséquent, si le facteur de charge est plus grand, l'espace sera plus pleinement utilisé, mais la conséquence est une diminution de l'efficacité de la recherche; Si le facteur de charge est trop petit, les données de la table de hachage seront trop rares, provoquant des déchets graves à l'espace. Le facteur de charge par défaut du système est de 0,75 et nous n'avons généralement pas besoin de le modifier.
Hashmap est une structure de données qui prend en charge un accès rapide. Pour comprendre ses performances, vous devez comprendre sa structure de données.
Iii. Structure de données
Nous savons que les deux structures les plus couramment utilisées en Java sont des tableaux et des pointeurs simulés (références). Presque toutes les structures de données peuvent être implémentées en combinaison avec ces deux, et il en va de même pour HashMap. En fait, HashMap est un "hachage de liste lié", comme suit sa structure de données:
D'après la figure ci-dessus, nous pouvons voir si la mise en œuvre sous-jacente de HashMap est ou un tableau, mais chaque élément du tableau est une chaîne. La capacité initiale du paramètre représente la longueur du tableau. Ce qui suit est le code source du constructeur HashMap:
public hashmap (int initialCapacity, float chargefactor) {// La capacité initiale ne peut pas être <0 if (initialCapacity <0) lancez new illégalArgumentException ("Capacité initiale illégale:" + InitialCapacity); // La capacité initiale ne peut pas> valeur de capacité maximale, la capacité maximale de hashmap est 2 ^ 30 if (initialCapacity> maximum_capacity) initialCapacity = maximum_capacity; // Le facteur de charge ne peut pas être <0 if (loadFactor <= 0 || float.isnan (loadfactor)) lancez un nouveau IllégalArgumentException ("Facteur de charge illégal:" + LoadFactor); // Calculez la valeur N-puissance des 2 plus petits supérieurs à la capacité initiale. Capacité int = 1; tandis que (capacité <initialCapacity) capacité << = 1; this.loadFactor = LoadFactor; // Définissez la limite de capacité de Hashmap. Lorsque la capacité de HashMAP atteint cette limite, le fonctionnement d'expansion de la capacité sera effectué seuil = (int) (capacité * chargefactor); // Initialisez la table Table Table = Nouvelle entrée [Capacité]; init (); } Comme le montre le code source, un tableau de table sera initialisé chaque fois qu'un nouveau hashmap est créé. L'élément du tableau de table est un nœud d'entrée.
Entrée de classe statique <k, v> implémente Map.Entry <k, v> {Final K Key; V valeur v; Entrée <k, v> suivant; Hash INT final; / ** * Crée 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; } .....}Parmi eux, l'entrée est la classe intérieure de HashMap, qui contient la clé de clé, la valeur de la valeur, le nœud suivant suivant et la valeur de hash. C'est très important. C'est précisément parce que l'entrée forme les éléments du tableau de table en tant que liste liée.
Ce qui précède analyse brièvement la structure de données de HashMap, et ci-dessous explorera comment HashMap implémente un accès rapide.
4. Implémentation du stockage: put (clé, vlaue)
Tout d'abord, regardons le code source
public v put (ke key, v valeur) {// Lorsque la clé est nul, appelez la méthode PutFornullkey pour enregistrer la première position de Null et de la table. C'est pourquoi HashMap permet à Null if (key == null) return putFornullKey (valeur); // Calculez la valeur de hachage de la clé int hash = hash (key.hashcode ()); ----- (1) // Calculez la position de la valeur de hachage clé dans le tableau de table int i = indexFor (hash, table.length); ----- (2) // itérate de i et trouvez l'emplacement où la clé est enregistrée pour (entrée <k, v> e = table [i]; e! = Null; e = e.next) {objet k; // juger s'il y a la même valeur de hachage sur la chaîne (la clé est la même) // si la même chose existe, écrasez directement la valeur et renvoyez l'ancienne valeur if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldvalue = e.Value; // ancienne valeur = nouvelle valeur e.Value = valeur; e.recordAccess (this); Retour OldValue; // Renvoie l'ancienne valeur}} // augmenter le nombre de modifications par 1 modCount ++; // Ajouter une clé et une valeur à l'addentry de position I (hachage, clé, valeur, i); retourner null; }Grâce au code source, nous pouvons clairement voir que le processus de données de sauvegarde de hashmap est: Déterminez d'abord si la clé est nul. S'il est nul, appelez directement la méthode PutFornullkey. S'il n'est pas vide, calculez d'abord la valeur de hachage de la clé, puis recherchez la position d'index dans le tableau de table en fonction de la valeur de hachage. S'il y a un élément à cette position, comparez si la même clé existe. S'il existe, écrasez la valeur de la clé d'origine, sinon économisez l'élément à la tête de la chaîne (le premier élément enregistré est placé à la fin de la chaîne). Si le tableau n'a aucun éléments là-bas, il sera enregistré directement. Ce processus semble simple, mais il a en fait des informations profondes. Il y a plusieurs points comme suit:
1. Regardons d'abord l'itération. La raison de l'itération ici est d'empêcher l'existence de la même valeur de clé. Si deux valeurs de hachage (clés) sont les mêmes, la méthode de traitement de HashMap est de remplacer l'ancienne valeur par la nouvelle valeur. La clé n'est pas traitée ici, ce qui explique qu'il n'y a pas deux clés identiques dans Hashmap.
2. Dans la vue (1) et (2). C'est l'essence de Hashmap. Tout d'abord, il existe la méthode de hachage, qui est un calcul mathématique pur, qui est de calculer la valeur de hachage de h.
statique int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); retour h ^ (h >>> 7) ^ (h >>> 4); }Nous savons que pour les tables de hashmap, la distribution des données doit être uniforme (il est préférable d'avoir un seul élément pour chaque élément, afin qu'il puisse être trouvé directement). Il ne peut pas être trop serré ou trop lâche. Trop serré entraînera une vitesse de requête lente, et trop lâche gaspillera de l'espace. Après avoir calculé la valeur de hachage, comment pouvons-nous nous assurer que les éléments de la table sont répartis également? Nous penserons à l'acquisition de moisissures, mais parce que l'acquisition de moisissure consomme beaucoup, HashMap le gère comme ceci: appelez la méthode IndexFor.
static int indexfor (int h, int long) {return h & (longueur-1); }La longueur du tableau sous-jacent de hashmap est toujours à la puissance n 2, et il existe dans le constructeur: capacité << = 1; Cela peut toujours garantir que la longueur du tableau sous-jacente de hashmap est à la puissance n 2. Lorsque la longueur est à n, la puissance de 2, H & (longueur - 1) équivaut à prendre le module de longueur, et la vitesse est beaucoup plus rapide que de prendre le module directement. Il s'agit d'une optimisation du hashmap en termes de vitesse. Quant à savoir pourquoi il est 2 à la nième puissance, l'explication suivante est.
Revenons à la méthode IndexFor, qui n'a qu'une seule instruction: H & (longueur - 1). En plus de l'opération de module ci-dessus, cette phrase a également une responsabilité très importante: distribuer uniformément les données de la table et utiliser pleinement l'espace.
Ici, nous supposons que la longueur est de 16 (2 ^ n) et 15, et H est 5, 6 et 7.
Lorsque n = 15, les résultats de 6 et 7 sont les mêmes, ce qui signifie que leurs emplacements stockés dans le tableau sont les mêmes, c'est-à-dire qu'une collision se produit et 6 et 7 formeront une liste liée à un endroit, ce qui entraînera une diminution de la vitesse de requête. Il est vrai que seuls trois nombres sont analysés ici, mais pas beaucoup, alors regardons 0-15.
D'après le graphique ci-dessus, nous voyons un total de 8 collisions, et en même temps, nous constatons que l'espace gaspillé est très grand, sans enregistrement en 1, 3, 5, 7, 9, 11, 13 et 15 endroits, c'est-à-dire aucune donnée n'est stockée. En effet, lorsqu'ils effectuent et fonctionnent avec 14, le dernier morceau du résultat qu'ils obtiennent sera toujours 0, c'est-à-dire qu'il est impossible de stocker des données aux emplacements de 0001, 0011, 0101, 0111, 1001, 1011, 1101, 1111 et 1111. L'espace est réduit et le risque de collision sera encore augmenté, ce qui entraînera une vitesse de query ralentie. Lorsque la longueur = 16, la longueur 1 = 15 est 1111. Ensuite, lors de l'exécution du bit bas et de l'opération, la valeur est toujours la même que la valeur de hachage d'origine, et lors de l'exécution de l'opération à haut bit, sa valeur est égale à sa valeur de faible bit. Par conséquent, lorsque la longueur = 2 ^ n, la probabilité de collision entre différentes valeurs de hachage est relativement faible, ce qui rendra les données réparties uniformément dans le tableau de table et la vitesse de requête est plus rapide.
Ici, nous passons en revue le processus de vente: lorsque nous voulons ajouter une paire de valeurs de clé à un hashmap, le système calculera d'abord la valeur de hachage de la clé, puis confirmera l'emplacement stocké dans le tableau en fonction de la valeur de hachage. S'il n'y a pas d'élément à cette position, insérez-le directement. Sinon, itérez sur la liste des éléments à ce moment-là et comparez la valeur de hachage de sa clé en conséquence. Si les deux valeurs de hachage sont égales et que les valeurs de clé sont égales (e.hash == hash && ((k = e.key) == key || key.equals (k))), la valeur du nœud d'origine est écrasée avec la valeur de la nouvelle entrée. Si les deux valeurs de hachage sont égales mais que les valeurs de clé ne sont pas égales, insérez le nœud dans l'en-tête de la liste liée. Pour le processus de mise en œuvre spécifique, consultez la méthode d'addentry, comme suit:
void Addentry (int hash, k key, v valeur, int bucketIndex) {// Obtenez l'entrée d'entrée <k, v> e = table [bucketIndex]; // Mettez l'entrée nouvellement créée dans l'index BucketIndex et laissez le nouvel entrée pointer de la table d'entrée d'origine [BucketIndex] = nouvelle entrée <k, v> (hachage, clé, valeur, e); // Si le nombre d'éléments dans le hashmap dépasse la limite, la capacité sera deux fois plus grande si (taille ++> = threshold) redimensionner (2 * table.length); }Il y a deux points à noter dans cette méthode:
L'une est la génération de chaînes. C'est un design très élégant. Le système ajoute toujours un nouvel objet d'entrée au BucketIndex. S'il y a un objet sur BucketIndex, l'objet d'entrée nouvellement ajouté pointera vers l'objet d'entrée d'origine, formant une chaîne d'entrée. Cependant, s'il n'y a pas d'objet d'entrée sur BucketIndex, c'est-à-dire e == null, alors l'objet d'entrée nouvellement ajouté pointe vers Null, et aucune chaîne d'entrée ne sera générée.
2. Expansion de la capacité.
À mesure que le nombre d'éléments dans le hashmap augmente, la probabilité de collision devient de plus en plus élevée, et la longueur de la liste de liens générée deviendra de plus en plus longue. Cela affectera inévitablement la vitesse du hashmap. Afin d'assurer l'efficacité du hashmap, le système doit étendre la capacité à un certain point critique. Ce point critique est lorsque le nombre d'éléments dans HASHMAP est égal à la longueur de la longueur du tableau *. Mais la mise à l'échelle est un processus très long car il nécessite de recalculer l'emplacement de ces données dans le nouveau tableau de table et de les copier. Donc, si nous avons prédit le nombre d'éléments dans Hashmap, le nombre d'éléments prédéfinis peut efficacement améliorer les performances de HashMap.
5. Implémentation de la lecture: Get (Key)
Par rapport au stockage de HashMap, le retrait est relativement simple. Trouvez l'entrée à l'index dans le tableau de table via la valeur de hachage de la clé, puis renvoyez la valeur correspondant à la clé.
public v get (clé d'objet) {// Si null, appelez la méthode getFornullkey pour renvoyer la valeur correspondante if (key == null) return getFornullkey (); // Calculez son code de hash en fonction de la valeur HashCode de la clé int hash = hash (key.hashcode ()); // supprime la valeur à l'index spécifié dans le tableau de table pour (entrée <k, v> e = table [indexfor (hash, table.length)]; e! = Null; e = e.next) {objet k; // Si la touche recherchée est la même que la touche recherchée, renvoyez la valeur correspondante if (e.hash == hash && ((k = e.key) == key || key.equals (k))) return e.Value; } return null; } Ici, la valeur qui peut être rapidement récupérée en fonction de la clé n'est pas seulement inséparable à partir de la structure de données de HashMap, mais a également beaucoup à voir avec l'entrée. Comme mentionné précédemment, HashMap ne stocke pas la clé et la valeur séparément dans la procédure stockée, mais est traitée comme une valeur de clé entière, qui est l'objet d'entrée. Dans le même temps, la valeur n'est qu'équivalent à l'attachement de la clé. Pendant le processus de stockage, le système détermine l'emplacement de stockage de l'entrée dans le tableau de table en fonction du code de hash de la clé, et dans le processus de récupération, l'objet d'entrée correspondant est également retiré en fonction du code de hash de la clé.
Lien original: http://www.cnblogs.com/chenssy/p/3521565.html
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.