Detaillierte Quellcode-Erklärung gängiger Methoden von ArrayList

Ich glaube, dass fast alle Studierenden in schriftlichen Tests und Interviews nach den Gemeinsamkeiten und Unterschieden zwischen ArrayList und LinkedList gefragt werden. Diejenigen, die ein wenig vorbereitet sind, sind mit diesen Problemen bereits vertraut. Ersteres basiert auf der Implementierung einer verknüpften Liste, während das Löschen und Einfügen an bestimmten Positionen langsam ist Der wahlfreie Zugriff ist langsam, das Löschen und Einfügen an bestimmten Positionen ist schnell; beide sind threadunsicher, Unterschiede zwischen Listen und Arrays und mehr.

Einer der großen Unterschiede zwischen Listen und Arrays besteht darin, dass die Größe von Arrays während der Initialisierung angepasst werden muss und nicht dynamisch erweitert werden kann, während Listen dynamisch erweitert werden können. ArrayList wird basierend auf Arrays implementiert. Wie wird also eine dynamische Erweiterung erreicht?
Es gibt drei Möglichkeiten, ArrayList zu initialisieren:
Bei der ersten Standardkonstruktionsmethode initialisiert ArrayList nicht die Kapazität, sondern verweist die Elementdatenreferenz der Liste auf ein leeres Array.

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

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

Anders als JDK1.6 initialisiert JDK1.6 die Kapazität auch beim Aufruf des Standardkonstruktors, JDK1.7 jedoch sicherlich Wenn es initialisiert und nicht verwendet wird, wird der Speicherplatz verschwendet. Warten Sie einfach, bis er hinzugefügt wird, und initialisieren Sie dann die Kapazität.

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

Erstellen Sie für die zweite Konstruktionsmethode direkt ein Array der angegebenen Größe und verweisen Sie die Elementarray-Referenz der Liste darauf.

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

Die dritte Konstruktionsmethode kann eine Sammlung als Parameter übergeben, aber die Elemente in der Sammlung müssen von den Elementen in der ArrayList erben.

//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);
}

Es gibt einen oben erwähnten Fehler, der dazu führt, dass beim Konvertieren einer Sammlung in ein Array möglicherweise versehentlich Object[] nicht zurückgegeben wird.

 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 }

Laufergebnisse:

Das obige Beispiel zeigt, dass toArray nicht immer Object[] zurückgibt, wenn das Objekt [] zurückgegeben wird, kann das Object-Element nicht eingefügt werden, daher hat das JDK diesen Fehler in „6260652“ behoben.

Als nächstes schauen wir uns andere Methoden wie das Einfügen und Löschen von Elementen an.

//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);    //容量不够则进行扩容}

Es gibt eine modCount-Variable (Modify Count), die in der secureEcplicitCapacity-Methode inkrementiert wird.

protected transient int modCount = 0;

Diese Variable erhöht sich in der Add-Methode nicht nur von selbst, sondern wird auch aufgezeichnet und um 1 erhöht, wenn eine Änderung an der ArrayList-Struktur erfolgt, z. B. Hinzufügung oder Löschung Es gibt viele Gründe dafür. Es hängt mit der Iterator-Durchquerung unter Threads zusammen. Es gibt auch eine entsprechende Variable in AbstractList$Itr.

//AbstractList$Itrint expectedModCount = modCount;

Die checkForComodification-Methode wird in AbstractList$Itr#next aufgerufen.

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

Wenn es sich bei der aktuell ausgeführten Umgebung um eine Single-Threaded-Umgebung handelt, wird unerwartetModCount immer angezeigt, unabhängig davon, welche Vorgänge in der Liste ausgeführt werden, z. B. Hinzufügen, Ändern, Löschen usw gleich modCount, aber wenn die aktuell ausgeführte Umgebung multithreadig ist, ist es sehr wahrscheinlich, dass ein Thread iteriert und durchläuft, während ein anderer Thread sie hinzufügt oder ändert. In diesem Fall lässt eine ConcurrentModificationException zu Hier spielt die Variable modCount eine Rolle.
Kehren Sie zur ArrayList#add-Methode zurück. Wenn die Listenkapazität nicht ausreicht, wird die Grow-Methode aufgerufen, um die Kapazität zu erweitern.

//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 ruft die Element-Get-Methode an der angegebenen Indexposition ab.

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

Da ArrayList auf Arrays basiert, ist diese Methode relativ einfach. Sie kann feststellen, ob sie außerhalb der Grenzen liegt. Wenn nicht, kann sie die Elemente entsprechend indizieren und zurückgeben zum Array-Index. Die Methode „remove“ löscht das Element an der angegebenen Position. ​

//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;
}

Der Code ist relativ einfach und spiegelt auch das Effizienzproblem von ArrayList basierend auf der Array-Praxis beim Löschen bestimmter Elemente wider. Informationen zu den Methoden Arrays.copyOf und System.arraycopy finden Sie unter „Der Unterschied zwischen System.arraycopy(src, srcPos, dest, destPos, length) und Arrays.copyOf(original, newLength)“

Das obige ist der detaillierte Inhalt vonDetaillierte Quellcode-Erklärung gängiger Methoden von ArrayList. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!