[JAVA] Liste und fröhliche Klassen

Einführung

Ich habe einen Kommentar in Vorheriger Artikel erhalten, daher werde ich schreiben, dass ich daran interessiert war, ein wenig zu schreiben. Wenn ich in Bezug auf Java List-bezogene Klassen den Quellcode anderer betrachte, während ich normalerweise arbeite, frage ich mich, ob es nur wenige Menschen gibt, die sich dessen bewusst sind.

Klassen unter Liste und was in diesem Artikel beschrieben wird

Informationen zur Klasse, die die List-Schnittstelle implementiert, finden Sie unter "Alle bekannten Implementierungsklassen" in hier. Wie Sie sehen können, gibt es viele. Unter ihnen werde ich über die folgenden drei Klassen schreiben, die relativ berühmt sind (?). · Anordnungsliste ・ LinkedList ・ Arrays $ ArrayList (Ich habe noch nie etwas anderes verwendet, daher bin ich damit nicht vertraut.)

ArrayList initialCapacity Sie wissen, dass ArrayList eine Klasse ist, die jeder häufig verwendet, aber haben Sie jemals von initialCapacity gewusst? Dies ist wahrscheinlich der beste Weg, um eine ArrayList-Instanz zu schreiben.

Capacity.java

List<?> list = new ArrayList<>()

Wussten Sie andererseits, dass Sie auf diese Weise instanziieren können?

Capacity.java

List<?> list = new ArrayList<>(100)

Int 100 wird als Argument des Konstruktors angegeben. Diese 100 ist die Anfangskapazität. Gibt die Anzahl der Elemente an, die in ArrayList initialisiert werden sollen. Was ist, wenn ich kein Argument spezifiziere? Werfen wir einen Blick auf die Quelle von ArrayList.

ArrayList.Klasse (Auszug: Konstruktor 1)

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

Irgendwie wird ein leeres Array in elementData gespeichert. Ich bin mir nicht sicher, ob das alles ist. Schauen wir uns als nächstes den Inhalt der add () -Methode an.

ArrayList.Klasse (Auszug: um hinzufügen)

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

Unmittelbar nach add () wird die Methode verifyCapacityInternal () aufgerufen. In sureCapacityInternal () wird die Methode verifyExplicitCapacity () nach dem Festlegen von minCapacity aufgerufen. Wenn Sie initialCapacity nicht im Konstruktor festgelegt haben, wie Sie zuvor gesehen haben, wird elementData auf DEFAULTCAPACITY_EMPTY_ELEMENTDATA (ein leeres Array) festgelegt, sodass die Bedingung der if-Anweisung erfüllt ist und "minCapacity = Math.max (DEFAULT_CAPACITY, minCapacity)" festgelegt ist. Es ist vollbracht. Infolgedessen wird minCapacity auf 10 (DEFAULT_CAPACITY) festgelegt und übergeben, um ExplicitCapacity () sicherzustellen. sureExplicitCapacity () ist eine Methode zum Sichern der Kapazität des Arrays. Mit anderen Worten, wenn im Konstruktor von ArrayList kein Argument festgelegt ist, werden die in ArrayList gespeicherten Elemente von einem Array mit 10 Elementen verwaltet. Was ist also mit dem Konstruktor für diejenigen, die initialCapacity angeben?

ArrayList.Klasse (Auszug 3)

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

Wenn Sie eine andere Ganzzahl als 0 angeben, wird anstelle eines leeren Arrays ein Array für die angegebene Anzahl von Elementen generiert. Das Verhalten bei add () ist grundsätzlich dasselbe, außer dass es die if-Anweisung der Methode verifyCapacityInternal () nicht durchläuft.

Was bedeutet es, initialCapacity anzugeben?

Was bedeutet es, initialCapacity anzugeben? Sie können dies sehen, indem Sie sich das Verhalten ansehen, wenn Sie mehr Elemente als die durch initialCapacity angegebene Anzahl hinzufügen. Dies ist der Implementierungsteil (Fortsetzung von sureCapacityInternal ()).

ArrayList.Java (Auszug)

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

In der Methode verifyExplicitCapacity () wird die Methode grow () aufgerufen, wenn die Bedingung erfüllt ist. Der Punkt ist "int newCapacity = oldCapacity + (oldCapacity >> 1)" der grow () -Methode. Wenn die Anzahl der durch initialCapacity gesicherten Elemente durch Hinzufügen von Elementen überschritten wird, wird die Kapazität mit 1,5 (Bruch) multipliziert. Kürzung).

• ">>" ist eine Schichtoperation. Siehe hier Wie ändert sich die Anzahl der Elemente in elementData, wenn Sie einer ArrayList insgesamt 100 Elemente nacheinander hinzufügen, wobei initialCapacity auf 10 festgelegt ist?

Anfangswert: 10 11. Element hinzugefügt: 10 * 1,5 = 15 16. Element hinzugefügt: 15 * 1,5 = 22 23. Element hinzugefügt: 22 * 1,5 = 33 34. Element hinzugefügt: 33 * 1,5 = 49 50. Element hinzugefügt: 49 * 1,5 = 73 74. Element hinzugefügt: 73 * 1,5 = 109 Ich konnte hier endlich 100 Elemente hinzufügen.

Leistungsunterschied in Abhängigkeit von der anfänglichen Kapazitätseinstellung

Diese Bewegung wird wahrscheinlich einen gewissen Overhead verursachen, nicht wahr? Wie viel kostet das? Ich habe tatsächlich die Ausführungszeit beim Hinzufügen () gemessen, während 100.000 Daten geloopt wurden. Dies ist das Programm, das für die eigentliche Messung verwendet wird.

DefaultListSize.java

import java.util.ArrayList;
import java.util.List;

public class DefaultListSize {
    private static final int CNT = 100000;
    public static void main(String... args) {
        //initialCapacity nicht angegeben
        List<Integer> defaultList = new ArrayList<>();

        long startDefautl = System.currentTimeMillis();
        for (int i = 0; i < CNT; i++) {
            defaultList.add(i);
        }
        long endDefautl = System.currentTimeMillis();
        System.out.println("Ausführungszeit (Millisekunden):" + (endDefautl - startDefautl));

        //initialCapacity-Spezifikation
        List<Integer> list = new ArrayList<>(CNT);
        long start = System.currentTimeMillis();
        for (int i = 0; i < CNT; i++) {
            list.add(i);
        }
        long end = System.currentTimeMillis();
        System.out.println("Ausführungszeit (Millisekunden):" + (end - start));
    }
}

Ausführungsergebnis

Ausführungszeit (Millisekunden):4
Ausführungszeit (Millisekunden):1

Wenn Sie initialCapacity nicht angegeben haben, waren es 4 Millisekunden, und wenn Sie 100.000 angegeben haben, war es 1 Millisekunde. Übrigens, als 10 Millionen angegeben wurden, waren es 731 Millisekunden und 258 Millisekunden. Ich kann nichts über die Anzahl der Sekunden sagen, da dies mit den Spezifikationen des PCs zusammenhängt, aber Sie können sehen, dass durch Angabe der Anfangskapazität keine zusätzliche Verarbeitung erfolgt und die Geschwindigkeit entsprechend erhöht wird. Wenn Sie wissen, dass Sie mit einer großen Datenmenge umgehen, ist es besser, diese richtig anzugeben.

LinkedList

Charakteristisch

Als nächstes kommt die LinkedList. LinkedList kann gut Elemente hinzufügen und löschen, aber keinen wahlfreien Zugriff. Der wahlfreie Zugriff erfolgt auf Quellcodeebene auf list.get (i). Die Ursache für diese Funktion ist die Art und Weise, wie Elemente verwaltet werden. Es wird verwaltet, indem das i-te Element mit dem i-1. Und i + 1. Element verknüpft wird. Um ein Element zu erhalten, folgen Sie einfach dem Link von Anfang oder Ende, und um es zu löschen, ersetzen Sie einfach den Link.

Ich denke, der Unterschied wird deutlich, wenn Sie ihn mit ArrayList vergleichen. ArrayList eignet sich gut für den Direktzugriff, da Sie Elemente direkt über den Index abrufen können.

Wenn Sie es jedoch löschen, müssen Sie das Array neu erstellen, was den Overhead erhöht.

Unterschiede im Direktzugriffsverhalten

Aufgrund dieser Funktion verhalten sich ArrayList und LinkedList beim Direktzugriff unterschiedlich. Im Fall von ArrayList können Sie das Element sofort abrufen, selbst wenn Sie mit list.get (i) zufällig darauf zugreifen, sodass Sie sofort antworten können. Das ist das Bild.

Im Fall von LinkedList kann das Zielelement nur abgerufen werden, wenn die Elemente in der Reihenfolge vom ersten Element aus verfolgt werden. Wenn Sie list.get (4) schreiben, können Sie das Zielelement schließlich erreichen, indem Sie der Reihenfolge 1 → 2 → 3 → 4 folgen. Das ist das Bild.

LinkedList kann auch in umgekehrter Reihenfolge gescannt werden, sodass list.get (7) im obigen Beispiel sicherlich in der Reihenfolge 10 → 9 → 8 → 7 folgt.

Was ist die Leistung beim Schleifen einer großen Datenmenge?

Bis zu diesem Punkt denke ich, dass es "Hmm. Was ist, wenn Sie viele Daten und "list.get (i)" durchlaufen? Wenn Sie eine solche Klasse haben, wissen Sie insbesondere, was passiert, wenn Sie beim Aufrufen dieser Methode eine LinkedList mit einer großen Datenmenge als Argument übergeben? Der Punkt ist, dass list.get (i) während der Schleife ausgeführt wird.

ListSizeLoop.java

class ListSizeLoop {
    public void listSizeLoop(List<String> list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

Ich habe diesen Artikel gefunden. Das ist genau das. Das kann passieren. Eine Geschichte, bei der ich eine Pause eingelegt habe, wenn ich LinkedList mit einem leichten Gefühl verwendet habe

Was soll ich machen?

Verwenden Sie, wie im vorherigen Artikel erwähnt, die Erweiterung für (oder Iterator), anstatt eine Schleife mit list.size () zu erstellen. Iterator wird intern durch die Erweiterung for for List erweitert (genauer gesagt für Klassen, die die Iterable-Schnittstelle implementieren). Iterator ist eines der Entwurfsmuster und eine Schnittstelle, die auf sequentielle Verarbeitung spezialisiert ist. Dies allein vermeidet einen wahlfreien Zugriff. Dies kann passieren, wenn Sie eine Schleife mit list.size () ausführen. Verwenden Sie daher die erweiterte Option für, es sei denn, Sie haben einen eindeutigen Grund dafür.

Arrays$ArrayList

Arrays $ ArrayList ist eine Liste mit fester Länge

Das letzte ist Arrays $ ArrayList. Es heißt ArrayList, unterscheidet sich aber von der bekannten java.util.ArrayList. In der Klasse "java.util.Arrays" befindet sich eine innere Klasse mit dem Namen "ArrayList", die die List-Schnittstelle implementiert ("$" ist ein von Java reserviertes Wort, das angibt, dass es sich um eine innere Klasse handelt). Dies ist eine praktische Liste zum Konvertieren eines Arrays in eine Liste oder zum Festlegen von Elementen im Voraus beim Erstellen einer Instanz und unter der Annahme einer festen Länge. Die Verwendung ist wie folgt.

ArraysAsList.java

import java.util.Arrays;
import java.util.List;

public class ArraysAsList {
    public static void main(String... args) {
        String[] strList = new String[3];
        strList[0] = "a";
        strList[1] = "b";
        strList[2] = "c";
        //Konvertieren Sie ein Array in eine Liste
        List<String> list1 = Arrays.asList(strList);
        for (String str : list1) {
            System.out.println(str);
        }

        //Generieren Sie eine Liste, die von Anfang an Elemente enthält
        List<String> list2 = Arrays.asList("d", "e", "f");
        for (String str : list2) {
            System.out.println(str);
        }
    }
}

Was passiert, wenn ich () hinzufüge?

Ich habe bereits erwähnt, dass es eine feste Länge annimmt, aber was passiert, wenn Sie () hinzufügen?

ArraysAsList2.java

import java.util.Arrays;
import java.util.List;

public class ArraysAsList2 {
    public static void main(String... args) {
        //Nach der Instanziierung hinzufügen()Methodenaufruf
        List<String> list = Arrays.asList("d", "e", "f");
        list.add("a");
        for (String str : list) {
            System.out.println(str);
        }
    }
}

Ausführungsergebnis

Exception in thread "main" java.lang.UnsupportedOperationException
	at java.util.AbstractList.add(AbstractList.java:148)
	at java.util.AbstractList.add(AbstractList.java:108)
	at ArraysAsList2.main(ArraysAsList2.java:8)

Eine UnsupportedOperationException ist aufgetreten. Werfen wir einen Blick auf Arrays $ ArrayList.

Arrays.java

public class Arrays {
    @SafeVarargs
    @SuppressWarnings("varargs")
    public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }

    /**
     * @serial include
     */
    private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable
    {
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;

        ArrayList(E[] array) {
            a = Objects.requireNonNull(array);
        }

        @Override
        public int size() {
            return a.length;
        }

        @Override
        public Object[] toArray() {
            return a.clone();
        }

        @Override
        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] a) {
            int size = size();
            if (a.length < size)
                return Arrays.copyOf(this.a, size,
                                     (Class<? extends T[]>) a.getClass());
            System.arraycopy(this.a, 0, a, 0, size);
            if (a.length > size)
                a[size] = null;
            return a;
        }

        @Override
        public E get(int index) {
            return a[index];
        }

        @Override
        public E set(int index, E element) {
            E oldValue = a[index];
            a[index] = element;
            return oldValue;
        }

        @Override
        public int indexOf(Object o) {
            E[] a = this.a;
            if (o == null) {
                for (int i = 0; i < a.length; i++)
                    if (a[i] == null)
                        return i;
            } else {
                for (int i = 0; i < a.length; i++)
                    if (o.equals(a[i]))
                        return i;
            }
            return -1;
        }

        @Override
        public boolean contains(Object o) {
            return indexOf(o) != -1;
        }

        @Override
        public Spliterator<E> spliterator() {
            return Spliterators.spliterator(a, Spliterator.ORDERED);
        }

        @Override
        public void forEach(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            for (E e : a) {
                action.accept(e);
            }
        }

        @Override
        public void replaceAll(UnaryOperator<E> operator) {
            Objects.requireNonNull(operator);
            E[] a = this.a;
            for (int i = 0; i < a.length; i++) {
                a[i] = operator.apply(a[i]);
            }
        }

        @Override
        public void sort(Comparator<? super E> c) {
            Arrays.sort(a, c);
        }
    }
}

Ich kann die add () -Methode nicht finden. Ist es eine höhere Klasse? AbstractList wurde erweitert. Schauen wir uns das an.

AbstractList.java

    public boolean add(E e) {
        add(size(), e);
        return true;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation always throws an
     * {@code UnsupportedOperationException}.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     * @throws IndexOutOfBoundsException     {@inheritDoc}
     */
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }

Das ist es. Ich löse eine UnsupportedOperationException aus, ohne dass Fragen gestellt werden. AbstractList ist auch ArrayList, Vector und [AbstractSequentialList](https: // docs. oracle.com/javase/jp/8/docs/api/java/util/AbstractSequentialList.html) wird ebenfalls erweitert. LinkedList erweitert AbstractSequentialList, sodass es indirekt unter AbstractList steht. Ich weiß nicht, ob Sie es in Buchstaben schreiben, aber wenn Sie sich die Abbildung unten ansehen, können Sie sehen, dass es sich unter AbstractList befindet.

Unterschied zu java.util.ArrayList (Implementierungsseite)

Schauen wir uns ArrayList als Beispiel für eine Klasse an, die AbstractList außer Arrays $ ArrayList erweitert.

ArrayList.Java (Auszug aus Teil hinzufügen)

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

Sie überschreiben die add () -Methode. Da java.util.ArrayList add () von AbstractList überschreibt, tritt UnsupportedOperationException nicht auf und die implementierte Verarbeitung wird ausgeführt. Arrays $ ArrayList überschreibt die add () -Methode nicht, daher wird eine UnsupportedOperationException ausgelöst. Obwohl sie den gleichen Namen haben, ArrayList, sind sie völlig unterschiedlich ... AbstractList ist eine teilweise Implementierung der List-Schnittstelle. Durch die Implementierung des erforderlichen Minimums wird der Teil reduziert, der als konkrete Klasse implementiert werden muss. Wenn Sie jedoch set (), add (), remove () nicht überschreiben, wird UnsupportedOperationException ausgelöst. .. Das gleiche passiert, weil Arrays $ ArayList nicht sowohl remove () als auch add () überschreibt. Da set () überschrieben wird, können Sie ein vorhandenes Element durch ein anderes ersetzen, indem Sie diese Methode aufrufen.

Wenn Sie ein Array in eine Liste mit variabler Länge konvertieren möchten

Arrays $ ArayList hat eine feste Länge, da add () und remove () nicht aufgerufen werden können. Wenn Sie ein Array in eine Liste mit variabler Länge konvertieren möchten, gehen Sie wie folgt vor:

ArraysAsList3.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ArraysAsList3 {
    public static void main(String... args) {
        String[] strList = new String[3];
        strList[0] = "a";
        strList[1] = "b";
        strList[2] = "c";
        //Konvertieren Sie ein Array über den ArrayList-Konstruktor in eine Liste
        List<String> list = new ArrayList<>(Arrays.asList(strList));
        for (String str : list) {
            System.out.println(str);
        }
    }
}

Mit der Beschreibung List <String> list = new ArrayList <> (Arrays.asList (strList)); wird die Konvertierung in der Reihenfolge Array → Arrays $ ArrayList → ArrayList durchgeführt. Zusätzlich zu der zuvor eingeführten initialCapacity gibt es einen weiteren Konstruktor, der eine Sammlung im ArrayList-Konstruktor empfängt. Mit diesem Konstruktor können Sie "Arrays $ ArrayList" in "java.util.ArrayList" konvertieren. AbstractList erweitert AbstractCollection und AbstractCollection implementiert Collection, sodass Sie Arrays $ ArrayList als Argument an diesen Konstruktor übergeben können. Ich denke, das ist auch leichter zu verstehen, wenn Sie sich die vorherige Abbildung ansehen.

Die Implementierung des Konstruktors für ArrayList, der Collection empfängt, lautet wie folgt.

ArrayList (Teilauszug des Konstruktors)

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[](see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

Als ich gerade anfing, Java zu verwenden, habe ich Arrays $ ArrayList genauso missverstanden wie java.util.ArrayList und war ziemlich verwirrt, also habe ich es aufgeschrieben.

Am Ende

Es fühlt sich an, als hätte ich viel darüber geschrieben, was ich mir über List ausgedacht habe. Ich hoffe, Sie haben auch nur eines bemerkt: "Oh, das stimmt !?" das ist alles.