Explication détaillée du code source des méthodes courantes d'ArrayList

Je pense que presque tous les étudiants seront interrogés sur les similitudes et les différences entre ArrayList et LinkedList lors de tests écrits et d'entretiens. Ceux qui sont un peu préparés connaissent déjà ces problèmes. La première est basée sur l'implémentation de tableaux, et la seconde est basée sur l'implémentation de listes chaînées ; la méthode aléatoire du premier est rapide, tandis que la suppression et l'insertion à des positions spécifiées sont lentes, tandis que celle du second est lente. l'accès aléatoire est lent, la suppression et l'insertion à des positions spécifiées sont rapides ; les deux sont des différences dangereuses pour les threads entre les listes et les tableaux et plus encore ;

L'une des grandes différences entre les listes et les tableaux est que les tableaux doivent être dimensionnés lors de l'initialisation et ne peuvent pas être développés dynamiquement, tandis que les listes peuvent être développées dynamiquement. ArrayList est implémenté sur la base de tableaux, alors comment réalise-t-il une expansion dynamique ?
Il existe trois façons d'initialiser ArrayList :
Pour la première méthode de construction par défaut, ArrayList n'initialise pas la capacité, mais pointe la référence des données d'élément de la liste vers un tableau vide.

private transient Object[] elementData;private static final Object[] EMPTY_ELEMENTDATA = {};

//1.ArrayList默认构造方法public ArrayList() {    super();this.elementData = EMPTY_ELEMENTDATA;
}

Différent du JDK1.6, le JDK1.6 initialisera la capacité même lors de l'appel du constructeur par défaut, le JDK1.7 le fera certainement. apporte certains avantages. S'il est initialisé et non utilisé, l'espace de stockage sera gaspillé. Attendez simplement qu'il soit ajouté, puis initialisez la capacité.

//JDK1.6 ArrayListpublic ArrayList() {this(10);
}

Pour la deuxième méthode de construction, créez directement un tableau de la taille spécifiée et pointez vers lui la référence du tableau d'éléments de la liste.

//2.ArrayList带有初始化大小的构造方法public ArrayList(int initialCapacity) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+   initialCapacity);this.elementData = new Object[initialCapacity];
}

La troisième méthode de construction peut passer une collection en paramètre, mais les éléments de la collection doivent hériter des éléments de l'ArrayList.

//3.可将一个集合作为ArrayList的参数构造成ArrayListpublic ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();    //将集合转换为数组size = elementData.length;    //集合中的元素大小// c.toArray might (incorrectly) not return Object[] (see 6260652) 这里是个bug，参考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

Il y a un bug mentionné ci-dessus, ce qui signifie que lors de la conversion d'une collection en tableau, Object[] ne peut pas être renvoyé par erreur, à titre d'exemple.

 1 package com.algorithm.sort; 2  3 import java.util.ArrayList; 4 import java.util.Arrays; 5 import java.util.List; 6  7 /** 8  * bug编号:6260652。toArray有可能不会返回Object[] 9  * Created by yulinfeng on 2017/6/26.10  */11 public class Test {12     public static void main(String[] args) {13         correctly();14         incorrectly();15     }16     17     /**18      * 返回Object[]19      */20     private static void correctly() {21         List<String> list = new ArrayList<String>();22         list.add("test");23         System.out.println(list.getClass());24         Object[] objArray = list.toArray();25         System.out.println(objArray.getClass());26     }27     /**28      * 不返回Object[]29      */30     private static void incorrectly() {31         List<String> list = Arrays.asList("test");32         System.out.println(list.getClass());33         Object[] objArray = list.toArray();34         System.out.println(objArray.getClass());35     }36 }

Résultats d'exécution :

L'exemple ci-dessus montre que toArray ne renvoie pas toujours Object[] , lorsque l'Object [] est renvoyé, l'élément Object ne peut pas être inséré, le JDK a donc corrigé ce bug dans "6260652".

Ensuite, examinons d'autres méthodes telles que l'insertion et la suppression d'éléments.

//ArrayList#addpublic boolean add(E e) {
    ensureCapacityInternal(size + 1);  //确保容量是否充足elementData[size++] = e;    //将元素添加至数组return true;
}

//ArrayList#ensureCapacityInternalprivate void ensureCapacityInternal(int minCapacity) {if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);     //如果此时还没有初始化列表容量大小，则对其初始化，默认容量为10    }
    ensureExplicitCapacity(minCapacity); //检查容量是否充足}

//ArrayList#ensureEcplicitCapacityprivate void ensureExplicitCapacity(int minCapacity) {
    modCount++;    //注意此变量if (minCapacity - elementData.length > 0)
        grow(minCapacity);    //容量不够则进行扩容}

Il existe une variable modCount (modifier le nombre) qui est incrémentée dans la méthode EnsureEcplicitCapacity.

protected transient int modCount = 0;

Cette variable augmentera non seulement d'elle-même dans la méthode add, mais sera enregistrée et incrémentée de 1 chaque fois qu'il y a une modification dans la structure ArrayList telle qu'un ajout ou une suppression . Il y a plusieurs raisons à cela. Cela est lié au parcours de l'itérateur sous les threads. Il existe également une variable qui lui correspond dans AbstractList$Itr.

//AbstractList$Itrint expectedModCount = modCount;

La méthode checkForComodification est appelée dans AbstractList$Itr#next.

//AbstractList$Itr#checkForComodificationfinal void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();
}

Si l'environnement d'exécution actuel est monothread, quelles que soient les opérations effectuées sur la liste, telles que l'ajout, la modification, la suppression, etc., inattenduModCount sera toujours est égal à modCount, mais si l'environnement en cours d'exécution est multithread, il est très probable qu'un thread le parcourt pendant qu'un autre thread l'ajoute ou le modifie. Pour le moment, une exception ConcurrentModificationException. sera lancé. C'est là que la variable modCount joue un rôle.
Retour à la méthode ArrayList#add Lorsque la capacité de la liste est insuffisante, la méthode grow sera appelée pour augmenter la capacité.

//ArrayList#growprivate void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);    //扩容策略为，每次新增容量的大小为旧容量的一半。也就是说如果默认容量为10，则第一次扩容大小为10 / 2 = 5，第二次扩容大小为15 / 2 = 7。if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;    //扩容策略扩得太小if (newCapacity - MAX_ARRAY_SIZE > 0)    //扩容策略扩得太大，大于最大数组大小时，最多等于Integer.MAX_VALUEnewCapacity = hugeCapacity(minCapacity);
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

　 ArrayList obtient la méthode get de l'élément à la position d'index spécifiée.

public E get(int index) {
    rangeCheck(index);    //检查索引是否越界return elementData(index);
}

Étant donné qu'ArrayList est implémenté sur la base de tableaux, cette méthode est relativement simple. Elle peut déterminer si elle est hors limites. Sinon, elle peut indexer et renvoyer les éléments en fonction. à l'indice du tableau. La méthode Remove supprime l'élément à la position spécifiée. ​

//ArrayList#removepublic E remove(int index) {
    rangeCheck(index);    //检查索引是否越界modCount++;    //记录modCount，上面已提及E oldValue = elementData(index);    //取出指定索引元素int numMoved = size - index - 1;    //移动的元素个数if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //将最后一个数组元素置为null，方便GCreturn oldValue;
}

Le code est relativement simple et reflète également le problème d'efficacité d'ArrayList basé sur la pratique des tableaux lors de la suppression d'éléments spécifiés. Pour plus d'informations sur les méthodes Arrays.copyOf et System.arraycopy, veuillez vous référer à "La différence entre System.arraycopy(src, srcPos, dest, destPos, length) et Arrays.copyOf(original, newLength)"

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!