Pendant longtemps, la liste de données utilisée plus fréquemment dans le code est principalement la liste, et elles sont toutes ArrayList. On dirait que cette chose suffit. ArrayList est une classe d'outils de wrapper utilisée pour implémenter des tableaux dynamiques, de sorte que lors de l'écriture de code, vous pouvez s'arrêter et sortir, itérer et traverser, ce qui est assez pratique.
Je ne sais pas quand j'ai commencé à démarrer lentement les classes d'outils telles que HashMap et Hashset apparaissent souvent dans le code. Il convient de dire que HashMap est plus courant, et c'est aussi une question d'entrevue classique, donc j'en lirai plus dans la vie quotidienne. Lorsque j'ai commencé à l'utiliser, je l'ai simplement compris comme une table correspondante de valeur clé, et il est plus pratique d'utiliser des clés pour trouver des données. Après une enquête plus approfondie, j'ai découvert
Cette chose a des secrets, surtout après la nouvelle version de JDK modifie Hashmap en arbre, le code est un peu compliqué.
J'ai commencé à utiliser Set moins, mais j'ai accidentellement trouvé un arbre dans un code. J'ai trouvé que cette classe peut être en douceur. C'était assez intéressant. J'ai progressivement découvert que c'est aussi un bon outil.
Si vous écrivez trop de code, vous ressentirez l'importance des bases, alors j'écris ici un court article pour organiser brièvement des connaissances sur la collection.
Ok, trierons-le brièvement:
• Liste: c'est-à-dire une liste, qui prend en charge les fonctions des tableaux et des listes liées, et est généralement linéaire.
• Carte: il s'agit d'une table de mappage, qui stocke la relation correspondante entre les clés et les valeurs.
• Définir: signifie définir, principalement utilisé pour trier les données et trier
Jetons un coup d'œil à la liste d'abord
La liste est une fenêtre pour stocker des données linéaires, telles que: ArrayList pour les tableaux et lishedlist pour les listes liées.
Arraylist
Il s'agit d'une liste de tableaux, mais il fournit une fonction d'extension automatique pour réaliser l'interface de liste. Les opérations externes sont accessibles via la méthode de déclaration d'interface, qui est sûre et pratique.
La clé de ArrayList est l'expansion automatique de la capacité. La capacité initiale peut être définie lorsque l'objet est initialisé ou que la capacité par défaut peut être mesurée. Si la taille du tableau n'est pas particulièrement claire, la taille initiale ne peut pas être spécifiée. S'il est clair, une taille peut être spécifiée, ce qui réduit le décalage causé par l'expansion dynamique. En parlant de cela, nous devons parler de la façon dont l'expansion est mise en œuvre. Regardez le code suivant:
Private void Grow (int mincapacity) {// CODE CONSCIEUX OFFOW INT OLDCAPACITY = ElementData.Length; int newcapacity = oldcapacity + (oldcapacity >> 1); if (newcapacity - mincapacity <0) newCapacity = mincapacity; if (newCapacity - max_array_size> 0) newCapacity = HugeCapacity (mincapacity); // La mincapacité est généralement proche de la taille, il s'agit donc d'une victoire: elementData = arrays.copyof (elementData, newcapacity); }Grow est une méthode qui déclenche ArrayList lors de l'ajout d'éléments ou des vérifications faciles. Processus principal:
1. Obtenez la longueur du tableau et déplacez-le à droite, ce qui équivaut à OldCapacity / 2, et obtenez la nouvelle longueur
2. Si cette longueur est inférieure à la capacité minimale, il est facile de l'utiliser directement.
3. S'il est supérieur au maximum, prenez une valeur maximale. Une méthode HugeCapacity sera appelée ici, principalement pour comparer la mincapacité avec max_array_size. Si la mincapacité est supérieure à max_array_size, prenez Integer.max_value, sinon, prenez max_array_size. Fait intéressant, Max_Array_Size prend Integer.max_value - 8; Je ne sais pas quelle est la signification de faire ceci
4. Enfin, appelez une méthode de copie pour copier le numéro existant dans un nouveau tableau.
En raison de ce processus de copie, si le tableau est relativement important, alors l'expansion entraînera certainement un décalage. Donc, si vous connaissez la valeur maximale depuis le début et qu'il est facile de passer à cette valeur, en spécifiant la taille lors du démarrage de l'initialisation aura un certain effet.
Listin lié
Il s'agit d'une classe d'outils pour les listes liées. Les avantages des listes liées sont qu'ils ajoutent et suppriment les choses plus rapidement, mais ils les trouveront plus lentement.
Quant au code, il semble que rien de spécial est qu'il est lié ensemble par une chaîne de pointeurs. Bien sûr, Java utilise plutôt des objets pour créer un objet de nœud. Le nœud lui-même pointe vers le nœud précédent et le nœud suivant. Ceci est la structure de la liste liée:
Node de classe statique privée <E> {e item; Node <e> Suivant; Nœud <e> prev; Nœud (nœud <e> prev, e élément, nœud <e> suivant) {this.item = élément; this.next = suivant; this.prev = prev; }}Ensuite, utilisez deux nœuds pour pointer la tête et la queue et c'est fait. Le code suivant:
/ ** * pointeur vers le premier nœud. * Invariant: (premier == null && last == null) || * (first.prev == null && first.item! = null) * / transity nœud <e> premier; / ** * pointeur vers le dernier nœud. * Invariant: (premier == null && last == null) || * (last.next == null && last.item! = null) * / transity nœud <e> dernier;
Voir une opération d'ajout:
/ ** * Liens E comme dernier élément. * / void linkLast (e e) {nœud final <e> l = dernier; Node final <e> newNode = new nœud <> (l, e, null); dernier = newNode; if (l == null) first = newNode; else l.next = newNode; taille ++; modCount ++; }Le passé est:
1. Obtenez le dernier nœud et mettez-le en L
2. Créez un nouveau nœud et récupérez les données dans ce nœud. Le processus de création pointera le PREV du nouveau nœud à L, afin qu'il soit connecté à la chaîne.
3. Puis pointez-vous en dernier vers ce nouveau nœud
4. Déterminez ensuite si L est nul. Si Null est nul, cela signifie qu'il s'agit d'une liste liée vide. Le nouveau nœud est le premier élément. De cette façon, le premier doit également pointer vers NewNode
5. S'il n'est pas vide, pointez le prochain L à NewNode
6. Compteur d'accumulation
L'opération de suppression est également le nœud avant et arrière pointant vers l'opération de déplacement de ce nœud.
Jetons un coup d'œil à la carte
La carte est une application d'une table de mappage pour les clés et les valeurs. Les principales classes d'implémentation: hashmap, hashtable, treeMap
Hashmap et hashtable
Hashmap est celui qui utilise l'algorithme de hachage pour la cartographie des valeurs clés. Hashtable est une classe de filetage avec synchronisation. C'est la principale différence entre eux. Le principe est similaire et ils sont tous réalisés grâce à une combinaison Bucket + Chain. Le seau est utilisé pour stocker les clés et la valeur doit être stockée dans une liste liée en raison de la collision de hachage.
• L'importance du seau réside dans l'efficacité et peut être positionnée en une étape à travers les calculs de hachage.
• La signification des listes liées est d'accéder aux données du hachage répété
Le principe spécifique que j'ai écrit un "Notes d'étude: hashtable et hashmap" avant
Mais je viens de voir que HashMap de JDK1.8 a changé sa structure de stockage et adopte une structure d'arbres rouge et noire. Cela peut résoudre l'efficacité de la recherche de liste liée? Aucune étude détaillée n'a été menée.
Tramper
Après avoir lu le code de Treemap, j'ai trouvé que j'utilise toujours la structure des arbres, les arbres rouges et noirs. Étant donné que les arbres rouges et noirs sont commandés, ils ont naturellement la fonction de tri. Bien sûr, vous pouvez également spécifier la méthode de comparaison via le comparateur pour obtenir un tri spécifique.
Étant donné que la structure des arbres est utilisée pour stocker, il sera plus difficile d'ajouter et de supprimer des données. Jetons un coup d'œil au code de vente:
public v put (k key, v valeur) {entrée <k, v> t = root; if (t == null) {compare (key, key); // type (et possible null) vérifier root = new entrée <> (clé, valeur, null); taille = 1; modCount ++; retourner null; } int cmp; Entrée <k, v> parent; // Comparateur divisé et comparateur de chemins comparables <? super k> cpr = comparateur; if (cpr! = null) {do {parent = t; CMP = cpr .......... if (cmp <0) t = t.left; else if (cmp> 0) t = t.right; else return t.setValue (valeur); } while (t! = null); } else {if (key == null) lance un nouveau nullpointerException (); @SuppressWarnings ("non contrôlé") comparable <? super k> k = (comparable <? super k>) touche; faire {parent = t; cmp = k ..compareto (t.key); if (cmp <0) t = t.left; else if (cmp> 0) t = t.right; else return t.setValue (valeur); } while (t! = null); } Entrée <k, v> e = nouvelle entrée <> (clé, valeur, parent); if (cmp <0) parent.left = e; else Parent.Right = e; FIXAFTERInSertion (E); taille ++; modCount ++; retourner null; }1. Vérifiez d'abord si le nœud racine existe. S'il n'existe pas, cela signifie qu'il s'agit du premier élément de données et est directement utilisé comme racine de l'arbre.
2. Déterminez s'il y a un comparateur. S'il y en a, utilisez le comparateur pour trouver l'emplacement de stockage des données. Si le résultat du rendement du comparateur est inférieur à 0, prenez la gauche et prenez la droite, sinon remplacez directement la valeur du nœud actuel.
3. S'il n'y a pas de comparateur, la clé est directement comparée à la clé du nœud. La comparaison est la même que la méthode précédente.
4. L'étape suivante consiste à créer un nœud enfant sur le parent trouvé et à le mettre dans les nœuds enfants gauche ou droit.
5. FixAfteRinsertion est des nœuds de couleur
6. Traitement de l'accumulateur
Ce sera également un peu gênant lors de la suppression des données. En plus de supprimer les données, vous devez également rééquilibrer les arbres rouges et noirs.
De plus, Treemap implémente l'interface NavigableMap <k, v>, donc il fournit également quelques opérations de retour sur l'ensemble de données.
Enfin, jetez un œil à l'ensemble
Définit principalement deux types d'applications: Hashset et Treeset.
Hashset
La signification littérale est très claire, en utilisant une collection de hachage. La caractéristique de cette collection est d'utiliser l'algorithme de hachage pour stocker les données, de sorte que les données ne sont pas dupliquées et l'accès est relativement rapide. Comment cela a-t-il été fait?
public boolean add (e e) {return map.put (e, présent) == null; }Il s'avère qu'il y a un objet MAP. Regardons ce qu'est la carte?
Hashmap transitoire privé <e, objet> carte;
C'est un hashmap. Ceux qui connaissent Hashmap comprendront que ces données ne seront pas répétées. Parce que l'objet lui-même est stocké comme une clé lors de la dépôt, une seule copie existera dans le hashmap.
Après avoir compris cela et d'autres choses, vous comprendrez très bien.
Arbre
Cet ensemble est utilisé pour trier l'ensemble, ce qui signifie qu'en plus de la possibilité de trier lourd, il peut également avoir sa propre fonction de tri. Mais après avoir regardé le code de Treeset, j'ai constaté qu'il avait été implémenté dans les bases de Treemap. Plus précisément, ce devrait être une classe dérivée de NavigableMap. TreeSet est basé sur Treemap sans spécifier la carte par défaut.
public arreset () {this (new Treemap <e, objet> ()); }Alors, à quoi nous pouvons prêter plus d'attention ici, c'est comment Treeset est lourd? Jetons un coup d'œil à la méthode d'ajout:
public booléen add (e e) {return m.put (e, présent) == null; }Il est quelque peu similaire à Hashset, qui sont tous deux basés sur les caractéristiques de MAP pour obtenir une charge lourde. C'est vraiment simple et efficace.
Ce qui précède est l'explication détaillée de l'ensemble, de la liste et de la carte en Java que l'éditeur vous apporte. J'espère que vous pourrez soutenir Wulin.com plus ~