Dieser Artikel analysiert den Quellcode von ArrayList. Lassen Sie mich über Arrays sprechen, bevor ich sie analysiere. Arrays können eine der ersten Datenstrukturen sein, mit denen wir in Kontakt gekommen sind. Sie teilen einen kontinuierlichen Adressraum im Speicher, um Elemente zu speichern. Da es direkt den Speicher betreibt, ist die Leistung von Arrays besser als die von Sammelklassen, was ein wesentlicher Vorteil der Verwendung von Arrays ist. Wir wissen jedoch, dass das Array einen fatalen Fehler hat, dh die Arraygröße muss während der Initialisierung angegeben werden, und die Größe des Arrays kann in nachfolgenden Operationen nicht geändert werden. In tatsächlichen Situationen begegnen wir mehr Dingen, von denen wir nicht wissen, wie viele Elemente zu Beginn gespeichert werden müssen, sondern hoffen, dass der Container seine eigene Kapazität automatisch erweitern kann, damit er mehr Elemente speichern kann. ArrayList kann solchen Anforderungen sehr gut erfüllen und die Größe automatisch erweitern, um sich an die kontinuierliche Erhöhung der Speicherelemente anzupassen. Die zugrunde liegende Ebene wird basierend auf Arrays implementiert, sodass einige Merkmale von Arrays enthält, z. In diesem Artikel werden wir tief in den Quellcode einsteigen, um zu sehen, wie er Arrays zusammenfasst. Schauen Sie sich zunächst seine Mitgliedsvariablen und die drei Hauptkonstruktoren an.
// Standardinitialisierungskapazität private statische endgültige int default_capacity = 10; // leeres Objekt Array privates statisches endgültiges Objekt [] leere_elementData = {}; // Objektarray Private Transient Object [] elementData; // Anzahl der Sammlungselemente private int Größe; // Constructor -Methode in der anfänglichen Kapazität öffentliche Arraylist (int infitalcapacity) {Super (). if (initialCapacity <0) {werfen neuer illegalArgumentException ("illegale Kapazität:"+ initialCapacity); } // Erstellen Sie ein neues Objekttyp -Array der angegebenen Kapazität. // Übergeben Sie eine leere Array -Instanz an elementData this.elementData = leer_elementData;} // Konstruktor -Methode, um in die externe Sammlung zu übergeben, öffentliche ArrayList (Sammlung <? Erweitert E> c) {// Halten Sie das Referenzelement des internen Array, das in die Sammlung elementdata = c.toarray () übergeben wurde. // Die Anzahl der Elemente der Sammlungsgröße = elementData.length aktualisieren; // Beurteilen Sie den Array -Referenzart und konvertieren Sie die Referenz in eine Objektarray -Referenz if (elementData.getClass ()! }}Sie können sehen, dass die interne Speicherstruktur von ArrayList ein Array von Objekttypen ist, sodass Elemente jeglicher Art gespeichert werden können. Wenn die Erstellung einer ArrayList erstellt wird, wird bei der Übergabe der anfänglichen Größe ein neues Objektarray der angegebenen Kapazität erstellt. Wenn die anfängliche Größe nicht festgelegt ist, wird kein Speicherplatz zugewiesen, sondern ein leeres Objektarray verwendet und dann Speicher zugewiesen, wenn das Element tatsächlich platziert werden soll. Schauen wir uns die Methoden zum Hinzufügen, Löschen, Ändern und Suchen an.
// Erhöhen (add) öffentliches boolean add (e e) {// prüfen, ob das Array vor dem Hinzufügen erweitert werden muss, die minimale Arraylänge beträgt Größe + 1 sealecapacityInternal (Größe + 1); // Element zum Ende des Array -ElementData [Größe ++] = E hinzufügen; return true;} // erhöhen (einfügen) public void add (int index, e element) {// Positionsbereichsprüfung rangecheckForAdd (Index); // Überprüfen Sie, ob die Kapazität erweitert werden muss, um die sersealcapacityInternal (Größe + 1) zu erweitern. // Bewegen Sie das Element hinter dem Insertionspositionssystem.ArrayCopy (ElementData, Index, ElementData, Index + 1, Größe - Index); // eine neue Wertelementdata [index] = Element zuweisen; Größe ++;} // public e remove (int index) {// Index kann nicht größer sein als die Größe Rangecheck (Index); ModCount ++; E oldValue = elementData (index); int nummoved = Größe - Index - 1; if (nummoved> 0) {// Verschieben Sie das Element hinter Index nach einem System weiter. } // leere ReferenzelementData [-Größe] = null; oldValue zurückgeben;} // öffentliche e -set (int index, e element) {// Index kann nicht größer sein als die Größe Rangecheck (Index); E oldValue = elementData (index); // Ersetzen Sie durch ein neues ElementelementData [INDEX] = Element; oldValue zurückgeben;} // public e get (int index) {// Index kann nicht größer sein als die Größe Rangecheck (Index); // Rückgabe des angegebenen Positionselements return elementData (Index);} Jedes Mal, wenn ein Element zur Sammlung hinzugefügt wird, wird zunächst prüfen, ob die Kapazität ausreicht, andernfalls wird die Kapazität erweitert. Die Details der Kapazitätserweiterung werden nachstehend erörtert. Schauen wir uns zunächst die spezifischen Punkte an, um beim Hinzufügen, Löschen, Ändern und Überprüfen zu achten.
Hinzufügen (hinzufügen): Fügen Sie dieses Element einfach zum Ende hinzu. Schneller Betrieb.
Hinzufügen (Einfügen): Die Operation ist langsamer, da das Element hinter der Insertionsposition bewegt und das Kopieren des Arrays beteiligt ist.
Löschen: Da die Elemente hinter der Löschposition vorwärts gebracht werden müssen, wird auch die Array -Kopie entworfen, sodass der Betrieb langsam ist.
Änderung: Ändern Sie die Elemente direkt am angegebenen Ort, ohne dass Elementbewegungen oder Array -Kopien einbezogen werden, und die Operation ist schnell.
Überprüfen Sie: Geben Sie das Array -Element des angegebenen Index direkt zurück und der Vorgang ist schnell.
Aus dem Quellcode ist ersichtlich, dass die Suche und Änderung direkt auf das Array -Untergang positioniert ist, sondern keine Elementbewegung und das Array -Kopieren beinhaltet, sodass er schneller ist. Da die Elemente jedoch bewegt werden müssen, beinhaltet dies das Array -Kopieren, sodass der Betrieb langsamer ist. Darüber hinaus kann jeder Additionsvorgang auch eine Array -Expansion durchführen, die auch die Leistung beeinflusst. Schauen wir uns an, wie ArrayList seine Kapazität dynamisch erweitert.
private void sealecapacityInternal (int mincapacity) {// Wenn das Array zu diesem Zeitpunkt noch leer ist, if (elementData == leere_elementData) {// Vergleiche mit der Standardkapazität, nehmen Sie den größeren Wert mincapacity = math.max (default_capacity, mincapacity); } // Wenn das Array initialisiert wurde, führen Sie diesen Schritt sicher, dass explicitCapacity (mincapacity);} private void sicherstellen, dass die Ausführung von Kapituren (int mincapacity) {modcount ++; // Wenn die minimale Kapazität größer als die Arraylänge ist, amplifizieren Sie das Array if (mincapacity - elementData.length> 0) {Grow (mincapacity); }} // Maximale Kapazität der Sammlung private statische endgültige int max_array_size = integer.max_value - 8; // Erhöhen Sie die Array -Länge private Leere (int mincapacity) {// Erhalten Sie die ursprüngliche Kapazität des Array int oldcapacity = elementData.länge; // Kapazität des Neuarrays, die Hälfte auf der ursprünglichen Basis hinzufügen in int newCapacity = OldCapacity + (OldCapacity >> 1); // Überprüfen Sie, ob die neue Kapazität geringer ist als die Mindestkapazität, wenn (NewCapacity - Mincapacity <0) {newCapacity = mincapacity; } // Überprüfen Sie, ob die neue Kapazität die maximale Array -Kapazität überschreitet, wenn (NewCapacity - max_array_size> 0) {newCapacity = Hugcapacity (mincapacity); } // das ursprüngliche Array in das neue Array elementData = arrays.copyof (ElementData, NewCapacity);} kopieren;};}; Vor dem Hinzufügen von Elementen wird die SealEcapacityInternal für die Überprüfung der Sammelkapazität eingereicht. In dieser Methode wird überprüft, ob das interne Array der aktuellen Sammlung immer noch ein leeres Array ist. Wenn dies der Fall ist, erstellen Sie ein neues Objektarray mit der Standardgröße von 10. Wenn nicht, beweist dies, dass die aktuelle Sammlung initialisiert wurde. Rufen Sie dann die Methode für die Versicherungsprüfung an, um zu überprüfen, ob die Kapazität des aktuellen Arrays die erforderliche Mindestkapazität erfüllt. Wenn es nicht erfüllt ist, rufen Sie die Grow -Methode an, um zu erweitern. Bei der Wachstumsmethode können Sie feststellen, dass jede Ausdehnung die Hälfte der ursprünglichen Arraylänge erhöhen soll. Die Erweiterung besteht tatsächlich darin, ein neues Array mit größerer Kapazität zu erstellen, alle Elemente des ursprünglichen Arrays in das Neue Array zu kopieren und dann das ursprüngliche Array zu verwerfen und das Neue Array zu verwenden. Bisher haben wir die häufiger verwendeten Methoden in ArrayList und einige der wichtigsten Punkte analysiert, die es wert sind, zu bemerken:
1. Die zugrunde liegende Implementierung von ArrayList basiert auf Arrays, sodass die Suche und Änderung bestimmter Einweisungen schneller ist, aber die Lösch- und Insertionsoperationen langsamer sind.
2. Versuchen Sie beim Bau einer ArrayList, die Kapazität so weit wie möglich anzugeben, um die durch Erweiterung verursachten Array -Kopiervorgänge zu reduzieren. Wenn Sie die Größe nicht kennen, können Sie die Standardkapazität 10 zuweisen.
3. Vor dem Hinzufügen von Elementen prüfen Sie, ob eine Kapazitätserweiterung erforderlich ist. Jede Kapazitätserweiterung ist die Hälfte der ursprünglichen Kapazität.
V. Wenn das Array außerhalb der Grenzen ist, wird eine Ausnahme sofort geworfen.
5. Alle Methoden der ArrayList sind nicht synchronisiert, daher ist es nicht sicher.
6. Die obige Analyse basiert auf JDK1.7, und andere Versionen haben einige Unterschiede, sodass sie nicht verallgemeinert werden kann.
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.