Was ist der Grund, warum die anfängliche Kapazität von ArrayList in Java 10 beträgt?

Warum ist die anfängliche Kapazität von HashMap 16?

Wenn wir über die Initialisierungskapazität von ArrayList sprechen, müssen wir zunächst die Initialisierungskapazität von HashMap überprüfen. Am Beispiel des Java 8-Quellcodes gibt es in HashMap zwei relevante Faktoren: Initialisierungskapazität und Ladefaktor:

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

In HashMap beträgt die Standardinitialisierungskapazität des Arrays 16. Wenn die Daten auf 0,75 des Standardwerts gefüllt sind Kapazität, es wird eine 2-fache Erweiterung durchgeführt. Natürlich können Benutzer die angegebene Größe auch bei der Initialisierung übergeben. Es ist jedoch zu beachten, dass es am besten ist, einen Wert von 2 hoch n-tel zu verwenden. Wenn er nicht auf 2 hoch n-tel eingestellt ist, wird HashMap ihn auch konvertieren, es ist jedoch ein weiterer Schritt erforderlich.

Auf das Implementierungsprinzip von HashMap werde ich hier nicht näher eingehen. Dazu gibt es im Internet bereits zu viele Artikel. Eine Sache, die wir wissen müssen, ist der Algorithmus von HashMap zur Berechnung der Schlüsselwertkoordinaten, d. h. durch Hashen des Schlüsselwerts und anschließendes Zuordnen zu den Koordinaten im Array.

Stellen Sie zu diesem Zeitpunkt sicher, dass die Kapazität von HashMap 2 hoch n-tel beträgt. Dann kann die Bitoperation verwendet werden, um den Speicher während der Hash-Operation direkt zu betreiben, ohne in Dezimalzahlen umzuwandeln, und die Effizienz ist höher.

Im Allgemeinen kann davon ausgegangen werden, dass der Grund, warum HashMap 2 hoch n-tel verwendet und der Standardwert 16 ist, in den folgenden Überlegungen liegt:

• Hash-Kollisionen reduzieren;

• Effizienz der Kartenabfrage verbessern;

• Die Zuteilung ist zu klein, um eine häufige Erweiterung zu verhindern.

• Die Zuteilung ist zu groß und verschwendet Ressourcen.

Kurz gesagt, der Grund, warum HashMap 16 als Standardwert verwendet, besteht darin, Hash-Kollisionen zu reduzieren und die Effizienz zu verbessern .

Ist die anfängliche Kapazität von ArrayList 10?

Als Nächstes bestätigen wir zunächst, ob die anfängliche Kapazität von ArrayList 10 beträgt, und diskutieren dann, warum es sich um diesen Wert handelt.

Werfen wir zunächst einen Blick auf den Quellcode der ArrayList-Initialisierungskapazität in Java 8:

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

Offensichtlich ist der Standardwert für die Containerinitialisierung 10. Und von JDK1.2 bis JDK1.6 beträgt dieser Wert immer 10.

Ab JDK1.7 wird beim Initialisieren von ArrayList der Standardwert auf ein leeres Array initialisiert:

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

Einige Freunde hier müssen gesagt haben, dass die Standardinitialisierungsgröße von ArrayList in Java 8 0 und nicht 10 ist. Und Sie werden auch etwas Seltsames an den Kommentaren zur Konstruktormethode finden: Erstellen Sie eine leere Liste mit einer anfänglichen Kapazität von 10. Was zum Teufel? Es ist offensichtlich leer!

Behalten Sie Zweifel vor, werfen wir zunächst einen Blick auf die Add-Methode von ArrayList:

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

Die secureCapacityInternal-Methode wird in der Add-Methode aufgerufen. Am Anfang handelt es sich um einen leeren Container, also size=0 wird in minCapacity=1 übergeben:

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

size=0传入的minCapacity=1：

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

上述方法中先通过calculateCapacity来计算容量：

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    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);
    }

会发现minCapacity被重新赋值为10 （DEFAULT_CAPACITY=10），传入ensureExplicitCapacity(minCapacity);这minCapacity=10In der obigen Methode berechnen Sie zunächst die Kapazität durch berechneCapacity:

ArrayList-10
Vector-10
HashSet-16
HashMap-16
HashTable-11

Sie werden diesen minCapacityfinden > wurde auf 10 (DEFAULT_CAPACITY=10 ) neu zugewiesen, übergeben Sie ensureExplicitCapacity(minCapacity);Das ist minCapacity=10,

The Das Folgende ist der Methodenkörper:

rrreee

Die Wachstumsmethode im obigen Code wird für die Erweiterung verwendet. Die Kapazität wird auf das 1,5-fache des Originals erweitert.

Wenn wir den obigen Verarbeitungsablauf verstehen, werden wir feststellen, dass die anfängliche Kapazität von ArrayList im Wesentlichen immer noch 10 beträgt, aber nur verzögertes Laden verwendet wird. Dies ist eine von Java 8 durchgeführte Optimierung, um Speicher zu sparen. Daher beträgt die Anfangskapazität von ArrayList von Anfang bis Ende 10.

Hier ist eine weitere Erwähnung der Vorteile des verzögerten Ladens. Wenn das Programm Tausende von ArrayLists enthält, bedeutet die Standardgröße von 10 Objekten, dass beim Erstellen 10 Zeiger (40 oder 80 Bytes) zugewiesen und für das zugrunde liegende Array verwendet werden. Füllen Sie sie mit Nullwerten, ein leeres Array (gefüllt mit Nullwerten) nimmt viel Speicher in Anspruch. Wenn Sie ein Array langsam initialisieren können, können Sie viel Speicherplatz sparen. Die Änderungen in Java 8 dienen dem oben genannten Zweck.

Warum ist die anfängliche Kapazität von ArrayList 10?

Lassen Sie uns abschließend besprechen, warum die anfängliche Kapazität von ArrayList 10 beträgt. Tatsächlich kann man sagen, dass es dafür keinen Grund gibt, es fühlt sich einfach gut an, nicht zu groß, nicht zu klein, genau richtig für die Augen!

Zunächst haben wir bei der Diskussion von HashMap gesagt, dass der Grund, warum HashMap 2 hoch n-te Potenz wählt, eher darin besteht, die Leistung und Kollision des Hash-Algorithmus zu berücksichtigen. Dieses Problem besteht für ArrayList nicht. ArrayList ist nur ein einfaches wachsendes Array, ohne Berücksichtigung der Optimierung auf Algorithmusebene. Solange es einen bestimmten Wert überschreitet, kann es wachsen. Daher kann die Kapazität von ArrayList theoretisch jeden positiven Wert annehmen.

Die Dokumentation von ArrayList erklärt nicht, warum 10 gewählt wurde, aber es liegt höchstwahrscheinlich an der Berücksichtigung der besten Übereinstimmung zwischen Leistungsverlust und Speicherplatzverlust. 10. Es ist nicht zu groß oder zu klein. Es verschwendet nicht zu viel Speicherplatz und beeinträchtigt die Leistung nicht zu sehr.

Wenn Sie fragen müssen, warum Sie sich überhaupt für 10 entschieden haben, müssen Sie möglicherweise den Autor dieses Codes „Josh Bloch“ fragen.

Wenn Sie genau hinschauen, werden Sie auch einige andere interessante Initialisierungskapazitätszahlen finden:

rrreee🎜ArrayList hat die gleiche Initialisierungskapazität, die 10 beträgt; HashSet und HashMap haben die gleiche Initialisierungskapazität, die 16 beträgt; HashTable verwendet allein 11. Eine weitere sehr interessante Frage. 🎜

Das obige ist der detaillierte Inhalt vonWas ist der Grund, warum die anfängliche Kapazität von ArrayList in Java 10 beträgt?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!