Cet article analyse le code source de ArrayList. Permettez-moi de parler des tableaux avant de les analyser. Les tableaux peuvent être l'une des premières structures de données avec lesquelles nous sommes entrés en contact. Ils divisent un espace d'adressage continu en mémoire pour stocker des éléments. Puisqu'il fonctionne directement sur la mémoire, les performances des tableaux sont meilleures que celles des classes de collecte, qui est un avantage majeur de l'utilisation des tableaux. Mais nous savons que le tableau a une faille mortelle, c'est-à-dire que la taille du tableau doit être spécifiée lors de l'initialisation, et la taille du tableau ne peut pas être modifiée dans les opérations suivantes. Dans les situations réelles, nous rencontrons plus de choses que nous ne savons pas combien d'éléments seront stockés au début, mais espérons plutôt que le conteneur puisse étendre automatiquement sa propre capacité afin qu'il puisse stocker plus d'éléments. ArrayList peut très bien répondre à ces besoins, et il peut agrandir automatiquement la taille pour s'adapter à l'augmentation continue des éléments de stockage. Sa couche sous-jacente est implémentée en fonction des tableaux, il a donc certaines caractéristiques des tableaux, tels que la recherche de modifications est rapide et l'insertion et la suppression sont lentes. Dans cet article, nous allons approfondir le code source pour voir comment il résume les tableaux. Regardez d'abord ses variables membre et les trois principaux constructeurs.
// Capacité d'initialisation par défaut Private Static Final int default_capacity = 10; // Array d'objet vide objet final statique privé [] vide_elementData = {}; // objet d'objet Objet transitoire privé [] ElementData; // Nombre d'éléments de collecte Int Size; // Méthode de constructeur pour passer dans la capacité initiale ArrayList public (int initialCapacity) {super (); if (InitialCapacity <0) {Throw New illégalArgumentException ("Capacité illégale:" + InitialCapacity); } // Créez un nouveau tableau de type d'objet de la capacité spécifiée this.elementData = nouvel objet [initialCapacity];} // Constructeur sans paramètres public arrayList () {super (); // passe une instance de tableau vide à elementData this.elementData = vide_elementData;} // méthode constructeur pour passer dans une liste publique de collection externe (collection <? Étend e> c) {// maintenez l'élément de référence du tableau interne transmis dans la collection elementData = C.ToArray (); // Mette à jour le nombre d'éléments de la collection taille = elementData.length; // juge le type de référence du tableau et convertir la référence en une référence du tableau d'objet if (elementData.getClass ()! = Objet []. Class) {elementData = arrays.copyof (elementData, size, object []. Class); }}Vous pouvez voir que la structure de stockage interne de ArrayList est un tableau de type d'objet, afin qu'il puisse stocker des éléments de tout type. Lors de la construction d'un arrayList, si la taille initiale est transmise, elle créera un nouveau tableau d'objets de capacité spécifiée. Si la taille initiale n'est pas définie, elle n'alloue pas d'espace mémoire mais n'utilisera pas un tableau d'objets vide, puis alloue la mémoire lorsque l'élément doit réellement être placé. Jetons un coup d'œil à ses méthodes d'ajout, de supprimer, de modifier et de rechercher.
// augmenter (ajouter) public booléen add (e e) {// Vérifiez si le tableau doit être élargi avant d'ajouter, la longueur minimale du tableau est de taille + 1 assurecapacityInternal (taille + 1); // Ajouter un élément à la fin du tableau ElementData [taille ++] = E; return true;} // augmenter (insert) public void add (int index, e élément) {// insérer la plage de position vérifie RangECHECKForAdd (index); // Vérifiez si la capacité doit être étendue à s'assurervapacityInternal (taille + 1); // déplace l'élément derrière le système de position d'insertion.ArrayCopy (elementData, index, elementData, index + 1, taille - index); // attribue une nouvelle valeur elementData [index] = élément; size ++;} // supprimer le public e supprime (int index) {// index ne peut pas être supérieur à la taille de RangeCheck (index); modCount ++; E oldValue = elementData (index); int numMoved = size - index - 1; if (numMoved> 0) {// Déplacez l'élément derrière l'index vers l'avant par un System.ArrayCopy (élémentData, index + 1, elementData, index, numMoved); } // ElementData de référence vide [- taille] = null; return OldValue;} // Changement public e set (int index, e élément) {// index ne peut pas être supérieur à la taille RangECHeck (index); E oldValue = elementData (index); // remplace par un nouvel élément ElementData [index] = élément; return OldValue;} // Vérifiez public e get (int index) {// index ne peut pas être supérieur à la taille de RangeCheck (index); // renvoie l'élément de position spécifié return elementData (index);} Chaque fois qu'un élément est ajouté à la collection, il vérifie d'abord si la capacité est suffisante, sinon la capacité sera élargie. Les détails de l'expansion de la capacité seront discutés ci-dessous. Examinons d'abord les points spécifiques auxquels faire attention lors de l'ajout, de la suppression, de la modification et de la vérification.
Ajouter (ajouter): Ajoutez simplement cet élément à la fin. Fonctionnement rapide.
Ajouter (insérer): l'opération est plus lente car l'élément derrière la position d'insertion doit être déplacé et la copie du tableau est impliquée.
Supprimer: Étant donné que les éléments derrière la position de suppression doivent être avancés, la copie du tableau sera également conçue, donc l'opération est lente.
Changement: modifiez directement les éléments à l'emplacement spécifié, sans impliquer le mouvement des éléments ou la copie du tableau, et l'opération est rapide.
Vérifier: renvoyez directement l'élément de tableau de l'indice spécifié et l'opération est rapide.
À partir du code source, on peut voir que comme la recherche et la modification sont directement positionnées sur l'indice du tableau, cela n'implique pas le mouvement des éléments et la copie du tableau, il est donc plus rapide. Cependant, comme les éléments doivent être déplacés, il implique une copie de tableau, donc l'opération est plus lente. De plus, chaque opération d'addition peut également effectuer une expansion du tableau, ce qui affectera également les performances. Voyons comment ArrayList élargit dynamiquement sa capacité.
private void assurecapacityInternal (int mincapacity) {// Si le tableau est toujours vide à ce moment si (elementData == vide_elementData) {// comparez avec la capacité par défaut, prenez la valeur plus grande mincapacité = math.max (default_capacity, mincapacity); } // Si le tableau a été initialisé, effectuez cette étape assurez-vous d'assurer la réduction de laCapacité (mincapacité);} private void assureExplicitCapacity (int Mincapacity) {modCount ++; // Si la capacité minimale est supérieure à la longueur du tableau, amplifiez le tableau if (mincapacity - elementData.length> 0) {Grow (mincapacity); }} // Capacité maximale de la collection Private Static Final int max_array_size = Integer.max_value - 8; // Augmentez la longueur du tableau Private Void Grow (int Mincapacity) {// Obtenez la capacité d'origine du tableau int oldcapacity = elementData.Length; // Capacité du nouveau tableau, ajoutez la moitié de la base d'origine int newCapacity = OldCapacity + (OldCapacity >> 1); // Vérifiez si la nouvelle capacité est inférieure à la capacité minimale si (newCapacity - Mincapacity <0) {newCapacity = mincapacity; } // Vérifiez si la nouvelle capacité dépasse la capacité de tableau maximale if (newCapacity - max_array_size> 0) {newCapacity = HugeCapacity (Mincapacity); } // Copiez le tableau d'origine dans le nouveau tableau ElementData = Arrays.copyof (ElementData, NewCapacity);} Avant d'ajouter des éléments, Assurecapacity Internet sera appelé pour le contrôle de la capacité de collecte. À l'intérieur de cette méthode, il vérifiera si le tableau interne de la collection actuelle est toujours un tableau vide. Si c'est le cas, créez un nouveau tableau d'objets avec la taille par défaut de 10. Sinon, il prouve que la collection actuelle a été initialisée. Ensuite, appelez la méthode AssurezplicitCapacity pour vérifier si la capacité du tableau actuel répond à la capacité minimale requise. S'il n'est pas satisfait, appelez la méthode de croissance pour se développer. Dans la méthode de croissance, vous pouvez voir que chaque expansion consiste à augmenter la moitié de la longueur d'origine du tableau. L'expansion est en fait de créer un nouveau tableau à plus grande capacité, de copier tous les éléments du tableau d'origine sur le nouveau tableau, puis de jeter le tableau d'origine et d'utiliser le nouveau tableau. Jusqu'à présent, nous avons analysé les méthodes les plus couramment utilisées dans ArrayList, et certains des points clés à noter:
1. L'implémentation sous-jacente de ArrayList est basée sur les tableaux, de sorte que la recherche et la modification des indices spécifiées sont plus rapides, mais les opérations de suppression et d'insertion sont plus lentes.
2. Lors de la construction d'une arraylist, essayez de spécifier la capacité autant que possible pour réduire les opérations de copie de tableau causées par l'expansion. Si vous ne connaissez pas la taille, vous pouvez attribuer la capacité par défaut à 10.
3. Avant d'ajouter des éléments, vérifiez si l'expansion de la capacité est nécessaire. Chaque expansion de capacité est la moitié de la capacité d'origine.
4. Chaque fois que le fonctionnement de l'indice est exploité, un contrôle de sécurité sera effectué. Si le tableau est hors limites, une exception sera immédiatement lancée.
5. Toutes les méthodes de ArrayList ne sont pas synchronisées, donc elle n'est pas sûre de fil.
6. L'analyse ci-dessus est basée sur JDK1.7, et d'autres versions auront quelques différences, donc elle ne peut pas être généralisée.
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.