1. Analyse du code source ArrayList (JDK7)
ArrayList maintient un tableau d'objets dynamique en interne. L'addition dynamique et la suppression de ArrayList est l'addition dynamique et la suppression de cette paire de groupes.
1. Construction et initialisation ArrayList
ArrayList Instance Variable // ArrayList Capacité par défaut Private Static Final int default_capacity = 10; // Array d'objet vide par défaut, utilisé pour définir une ArrayListPrivate Final Object [] vide_elementData = {}; // ArrayList storist l'objet objet Private Transient Object [] ElementData; // le nombre d'éléments dans ArrayList Private INT SIZE;Constructeur ArrayList:
Aucun constructeur de paramètres: c'est-à-dire construire un objet vide []
public ArrayList () {super (); this.elementData = vide_elementData;} Spécifiez la construction de la taille de la capacité:
public ArrayList (int initialCapacity) {super (); if (InitialCapacity <0) lancez un nouveau IllégalArgumentException ("Capacité illégale:" + InitialCapacity); this.elementData = nouvel objet [initialCapacity];} Spécifiez une structure de collecte qui implémente l'interface de collecte:
Public ArrayList (Collection <? Étend E> C) {ElementData = C.ToArray (); size = elementData.length; // C.ToArray pourrait (incorrectement) non retour objet [] (voir 6260652) if (elementData.getClass ()! = objet []. class) elementData = arrays.copyof (elementData, size, objet []. class);}Cela explique également le rôle de la collection, et la raison pour laquelle Java-Collection-Framwork conçoit l'interface de collection au lieu d'utiliser directement la liste, le réglage et d'autres interfaces.
2. Mécanisme d'allocation de capacité d'ArrayList
Cap de capacité pour ArrayList: ArrayList La capacité est une limite supérieure, et les théories permettent l'allocation d'Integer.max_value - 8 taille de taille. Cependant, la quantité peut être allouée dépend des paramètres de pile, et les paramètres de machine virtuelle doivent être définis
Final statique privé int max_array_size = Integer.max_value - 8;
Étendre le volume lors de l'appel de la méthode ADD
public booléen add (e e) {assurecapacityInternal (taille + 1); // incréments modCount !! elementData [size ++] = e; Retour Vrai; }La méthode AssurecapacityInternal (INT) détermine en fait une taille d'expansion minimale.
private void assurecapacityInternal (int mincapacity) {if (elementData == vide_elementData) {mincapacity = math.max (default_capacity, mincapacity); } assure lacapacité (mincapacité); } private void assureExplicitCapacity (int mincapacity) {modCount ++; // code consciente du trop-plein if (mincapacity - elementData.length> 0) se développer (mincapacité); } À propos de ModCount: ModCount est défini dans la classe abstraite AbstractList. Les commentaires du code source expliquent essentiellement son utilisation: lors de l'utilisation d'Iterator pour traverser, il est utilisé pour vérifier si les éléments de la liste ont des modifications structurelles (un nombre du nombre d'éléments de liste a changé). Il est principalement utilisé dans un environnement multi-thread pour empêcher un thread d'itérer et un autre thread modifiant la structure de cette liste.
La méthode de croissance est une méthode d'extension réelle
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); }Il existe également une méthode HugeCapacity pour l'élargissement de la capacité
Private Static int HugeCapacity (int Mincapacity) {if (mincapacity <0) // débordera de nouveaux OutofMemoryError (); return (mincapacity> max_array_size)? Integer.max_value: max_array_size; } Résumer:
Chaque expansion est accompagnée d'une copie du tableau, donc donner la bonne capacité à la fois améliorera un peu les performances.
Le chiffre suivant est l'ensemble du processus d'extension que je résume:
3.ArrayList Iterator
Il y a deux principaux itérateurs de ArrayList et de ListIrTR, mais un ARRAYLISTPLITERATOR est également ajouté dans JDK1.8. Apprenons respectivement l'analyse du code source de l'ITR et de la liste.
(1) ITR: ne peut reculer
classe privée ITR implémente Iterator <E> {int Cursor; // Index de l'élément suivant pour retourner int lastret = -1; // Index du dernier élément renvoyé; -1 Si aucune telle // attendModCount est une copie de modCount int attendModCount = modCount; public boolean hasnext () {return Cursor! = size; } @SuppressWarnings ("Unchecked") public e suivant () {checkForComodification (); // Enregistrez la position actuelle int i = curseur; if (i> = size) lancez new nosuchementElementException (); Object [] elementData = arrayList.this.ElementData; if (i> = elementData.Length) lancez de nouveaux mododification ConcurrentException (); // la position du curseur de l'élément suivant = i + 1; return (e) elementData [lastret = i]; } // Utilisez la méthode de suppression de l'Iterator public void retire () {if (lastret <0) lance un nouveau illégalStateException (); checkForComodification (); Essayez {// Notez comment la classe intérieure appelle la classe extérieure ArrayList.This.Remove (lastret); // Après avoir retiré, vous devez réajuster la position de chaque curseur de pointeur = lastret; lastret = -1; attendModCount = modCount; } catch (indexoutofboundSexception ex) {lancez new concurrentModificationException (); }} final void checkForComodification () {if (modCount! = attendModCount) New concurrentModificationException (); }} À partir du code source, on peut voir que l'ITRIRATEUR ITR est un iterateur avancé, qui fournit une méthode suivante pour obtenir des éléments dans l'arrayList.
CheckForComodification est un mécanisme de détection d'erreurs fasciné dans le travail de co-collection Java. L'opération sur le même ensemble dans un environnement multi-thread peut déclencher le mécanisme de faillite et lancer une exception en conception concurrentModificationException.
L'ITERATOR ITR définit une copie du modCount de disques attendumodCount. Lorsque ArrayList effectue des opérations pour modifier la structure, telles que les méthodes ADD, Supprimer et effacer, la valeur de ModCount changera.
Grâce au code source ITR, on peut voir que l'appel des méthodes suivantes et supprimera déclencher la vérification rapide. Pour le moment, si une exception se produit lorsque d'autres threads effectuent des opérations qui modifient la structure de l'ensemble tout en traversant l'ensemble.
(2) Listitr: prend en charge la traversée vers l'avant et vers l'arrière. Jetons un coup d'œil au code source de ListItrment:
classe privée ListeTR étend ITR implémente ListIterator <E> {listTr (int index) {super (); curseur = index; } public boolean hasprevious () {return Cursor! = 0; } public int nextIndex () {return Cursor; } public int promedIndex () {return Cursor - 1; } @SuppressWarnings ("Unchecked") public e précédemment () {checkForComodification (); // la position de l'élément précédent de l'arrayList int i = curseur - 1; if (i <0) lancer un nouveau nosuchementElementException (); Object [] elementData = arrayList.this.ElementData; if (i> = elementData.Length) lancez de nouveaux mododification ConcurrentException (); curseur = i; return (e) elementData [lastret = i]; } // La méthode de jeu est ajoutée à cet iterator public void set (e e) {if (lastret <0) lance un nouveau illégalStateException (); checkForComodification (); essayez {arrayList.this.set (lastret, e); } catch (indexoutofboundSexception ex) {lancez new concurrentModificationException (); }} // Cet itérateur ajoute la méthode ADD public void add (e e) {checkForComodification (); essayez {int i = curseur; ArrayList.This.add (i, e); // Remarquez le curseur de position du pointeur = i + 1; lastret = -1; attendModCount = modCount; } catch (indexoutofboundSexception ex) {lancez new concurrentModificationException (); }}}L'implémentation de ListIRTR est essentiellement la même que l'ITR, en ajoutant des méthodes qui peuvent être traversées précédemment, ainsi que des méthodes d'ajout et de définition.
(3) Utilisez CopyOnwriteArrayList dans java.util.concurrent pour résoudre un problème de fail rapide
CopyOnwriteArrayList est thread-safe. Pour plus de détails, jetons un coup d'œil à son code source de méthode ADD:
public boolean add (e e) {final reentrantlock lock = this.lock; lock.lock (); essayez {objet [] elements = getArray (); int len = elements.length; Objet [] newelements = arrays.copyof (éléments, len + 1); newelements [len] = e; setArray (newelements); Retour Vrai; } enfin {lock.unlock (); }} CopyOnwriteArrayList est un arraylist copié sur Write. Lors du démarrage du fonctionnement des données d'écriture, les arrays.copyof sont un nouveau tableau, qui n'affectera pas l'opération de lecture.
Ce coût est de perdre de la mémoire et de poser des problèmes de performance. Lorsque CopyOnwriteArrayList est écrit, un objet de copie est généré en mémoire et l'objet d'origine existe toujours.
CopyOnWriteArrayList ne peut garantir la cohérence des données en temps réel, il ne peut garantir que la cohérence des résultats. Convient à des scénarios tels que Cache lors de la lecture plus et d'écriture plus et d'écriture moins dans des situations simultanées.
(4) Autres méthodes Code source de ArrayList:
Une méthode privée BatchRemove (Collection <?> C, booléen complément), c'est-à-dire l'opération de suppression par lots
booléen privé batchRemove (collection <?> c, booléen complément) {// La raison de l'utilisation de final est mentionnée ci-dessous l'objet final [] elementData = this.elementData; int r = 0, w = 0; booléen modifié = false; essayez {// transmence à travers les éléments de la liste et vérifiez pour (; r <size; r ++) if (c.Contains (elementData [r]) == complément) elementData [w ++] = elementData [r]; } Enfin {// Si une exception se produit dans TRY, assurez-vous la cohérence des données et effectuez l'opération de copie suivante if (r! = size) {System.ArrayCopy (elementData, r, elementData, w, size - r); w + = taille - r; } // nettoyer les éléments inutilisés et informer GC pour recycler if (w! = Size) {// Effacer pour laisser GC faire son travail pour (int i = w; i <size; i ++) elementData [i] = null; modCount + = size - w; taille = w; modifié = true; }} return modifié; } La variable modifiée par final fait référence à la même référence pour maintenir la cohérence des données ultérieurement.
Dans cette méthode, lorsque vous souhaitez conserver des éléments dans la collection C, la valeur du complément est vraie; Lorsque vous souhaitez supprimer des éléments en C, la valeur du complément est fausse. Cela devient respectivement les méthodes de retenue et de removeall.
Swap: échangez les deux positions dans l'arraylist
2. Analyse du code source liédlist (JDK7)
LinkedList est une liste liée. Par rapport à la table de commande, la liste liée n'a pas besoin d'utiliser des unités de mémoire continue pour stocker les données. Réduit le problème des éléments mobiles causés par la modification de la structure du conteneur, et l'accès séquentiel est relativement efficace.
1. Définition du nœud
LinkedList dans JDK est une liste liée bidirectionnelle, chaque nœud stocke respectivement des informations sur le nœud précédent et le nœud suivant. Sa définition est la suivante:
Node de classe statique privée <E> {e item; Node <e> Suivant; Nœud <e> prev; Nœud <e> (nœud <e> prev, e élément, nœud <e> suivant) {this.item = élément; this.next = suivant; this.prev = prev; }}2. Construction et initialisation liés
Membre: 3 variables membre sont maintenues dans Linkedlist pour enregistrer le nombre de nœuds dans la liste liée, le prédécesseur et le successeur des nœuds
transitoire int size = 0; nœud transitoire <e> d'abord; nœud transitoire <e> dernier;
Constructeur: le constructeur par défaut est de construire une liste liée vide
Public LinkedList () {}Ou construire basé sur d'autres conteneurs, et plus tard, nous écrivons un constructeur pour former une liste de liens commandés.
Public LinkedList (Collection <? Étend E> C) {this (); addall (c);}Voici un peu plus. Pour la différence entre le modificateur générique? Super T et étend t, voir cet article sur la différence entre super T et étend t dans les génériques.
3. Fonctionnement structurel de Linkedlist
Méthode d'insertion de l'en-tête: c'est-à-dire insérer un élément dans l'en-tête de la liste liée
private void linkFirst (e e) {nœud final <e> f = premier; Node final <e> newNode = new nœud <> (null, e, f); premier = newNode; // juger s'il s'agit d'une liste liée vide si (f == null) last = newNode; else f.prev = newNode; taille ++; modCount ++; } Méthode d'insertion de queue: c'est-à-dire insérer un élément à la fin de la liste liée
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 ++; } Avant d'insérer dans le nœud actuel: trouvez le lecteur avant du nœud actuel
void linkBefore (e e, nœud <e> succ) {// Déterminez si le nœud n'est pas vide bien sûr nœud final <e> pred = succ.prev; Node final <e> newNode = new nœud <> (Pred, E, succ); succ.prev = newNode; // Déterminez si le nœud actuel est le premier nœud if (pred == null) first = newNode; else pred.next = newNode; taille ++; modCount ++; } Méthode de suppression de l'en-tête: Supprimer le premier nœud de la liste liée
privé e unlinkFirst (nœud <e> f) {// Affirmer f == First && f! = null; élément e final = f.item; Node final <e> next = f.next; f.item = null; f.next = null; // Aide GC First = Suivant; if (suivant == null) dernier = null; else suiv.prev = null; taille--; modCount ++; élément de retour; } Méthode de suppression de la queue: Supprimer le dernier nœud de la liste liée
Private E UnlinkLast (nœud <e> l) {// Assurez-vous que l == dernier et l! = null final e element = l.item; Node final <e> prev = l.prev; l.item = null; l.prev = null; // aide GC dure = prev; if (prev == null) d'abord = null; else prev.next = null; taille--; modCount ++; élément de retour; }4. Maintenir la cohérence entre l'interface de la liste et la déshabitation
L'interface de liste permet à l'utilisation des indices d'implémentation d'accès aléatoire aux conteneurs, et il est facile d'implémenter un accès aléatoire à des tableaux comme celui-ci. Pour les listes liées, JDK utilise également logiquement le nombre de nœuds dans les listes liées pour donner l'implémentation d'un accès aléatoire
Node <e> node (int index) {// assure la correction de l'index if (index <(size>> 1)) {node <e> x = premier; pour (int i = 0; i <index; i ++) x = x.next; retour x; } else {node <e> x = dernier; pour (int i = size - 1; i> index; i--) x = x.prev; retour x; }} L'index est le nombre de la première moitié, recherche depuis le début. L'indice appartient au nombre de la seconde moitié et recherche de la fin. Faites un usage complet des caractéristiques des listes liées bidirectionnelles.
Par conséquent, Add (int index, t t), get (int), set (int) et d'autres méthodes peuvent être facilement implémentés.
LinkedList implémente l'interface DEQI, c'est-à-dire LinkedList implémente la méthode des conteneurs de file d'attente à double extrémité. Voici un résumé de l'API.
5. Linkedlist Traversal
Étant donné que LinkedList est une liste liée à double sens, vous pouvez naturellement le traverser dans les deux sens. Comme ArrayList, LinkedList a également des problèmes de faillite en ce qui concerne l'opération de conteneur multi-threading.
La question de l'échec a été expliquée dans l'article précédent, donc je n'en parlerai pas ici.
En ce qui concerne les itérateurs, LinkedList a un itérateur bidirectionnel de ListIterator et un itérateur inverse descendingiterator. Tous sont très simples. Le code source n'est pas analysé
Si vous traversez des éléments, le coût de l'accès aléatoire est relativement élevé.
3. LinkedList, ArrayList, Résumé vecteur
1. LinkedList et ArrayList
ArrayList implémente une structure de données basée sur des tableaux dynamiques, et LinkedList est basé sur une structure de données basée sur une liste liée.
Pour un accès aléatoire à Get and Set, ArrayList se sent mieux que LinkedList car LinkedList déplace le pointeur.
Pour les opérations nouvelles et supprimées, ajoutez et supprimez, LinedList a un meilleur avantage car ArrayList doit déplacer des données. Cela dépend de la situation réelle. Si une seule partie des données est insérée ou supprimée, la vitesse d'ArrayList est meilleure que celle de LinkedList. Cependant, si les données sont insérées au hasard par lots, la vitesse de Linkedlist est bien meilleure que celle de ArrayList. Étant donné que chaque fois qu'un ArrayList insère des données, il est nécessaire de déplacer le point d'insertion et toutes les données par la suite.
2. ArrayList et vecteur
Le vecteur est synchrone, il est donc également enfile, tandis que ArrayList est Thread-Asyn, ce qui n'est pas sûr. Si les facteurs de sécurité des fils ne sont pas pris en compte, ArrayList est généralement plus efficace.
Si le nombre d'éléments dans l'ensemble est supérieur à la longueur du réseau de set actuel, le taux de croissance du vecteur est de 100% de la longueur actuelle du tableau et le taux de croissance de la liste de balises est de 50% de la longueur actuelle du tableau. Si vous utilisez des données avec des quantités relativement importantes de données dans l'ensemble, l'utilisation du vecteur présente certains avantages.
Si vous recherchez des données dans un emplacement spécifié, le temps utilisé par Vector et ArrayList est le même, à la fois 0 (1), et vous pouvez utiliser Vector et ArrayList pour le moment. Si le temps passé à déplacer les données à un emplacement spécifié est de 0 (ni) n, qui est la longueur totale, vous devriez envisager d'utiliser LinkList, car il faut 0 (1) pour déplacer les données à un emplacement spécifié, et le temps passé à interroger les données à un emplacement spécifié est 0 (i).
ArrayList et Vector utilisent des tableaux pour stocker des données. Le nombre d'éléments dans ce tableau est plus grand que les données stockées réelles pour ajouter et insérer des éléments. Les deux autorisent les éléments d'indice du numéro de série direct. Cependant, l'insertion de données doit être conçue pour déplacer des éléments de tableau et d'autres opérations de mémoire, de sorte que les données d'index sont rapides et lentes pour insérer des données. Vector utilise la méthode synchronisée (sécurité de thread), donc les performances sont pires que ArrayList. LinkedList utilise une liste liée bidirectionnelle pour stocker les données. Les données d'indexation en fonction du numéro de série nécessitent une traversée vers l'avant ou vers l'arrière, mais lors de l'insertion de données, seuls les éléments avant et arrière de cet élément sont enregistrés, donc l'insertion de plusieurs degrés est plus rapide!