Java Collections automatische Neuzuteilung wenn Größe erreicht ist

Question

Ich bin nicht sicher, ob ich die richtigen Begriffe bin, aber ich bin gespannt, wie es bestimmt, wie viel von der Größe einer Sammlung in Java zu erhöhen, wenn es voll ist? Ich habe die Suche versucht, aber ich bin nicht wirklich mit etwas Sinnvolles kommen.

Also, wenn ich so etwas wie

List l = new ArrayList(1);
l.add("1");
l.add("2");

Wie bestimmt, wieviel die Größe der Liste zu erhöhen? Ist es immer ein Sollwert und wenn ja, was ist der Wert? Ich würde auch in diesen Informationen für BitSet interessiert sein, wenn es unterscheidet.

Danke und lassen Sie mich wissen, ob ich klarstellen sollte.

Answer 1

ruft ensureCapacity:

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3) / 2 + 1;
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

so, wie Sie den newCapacity sehen können, ist die (oldCapacity * 3) / 2 + 1

Answer 2

Die Quelle für Arraylist hält einige Hinweise:

/**
 * 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) {
ensureCapacity(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}


/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
    newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}
}

Diese Zeile:. int newCapacity = (oldCapacity * 3)/2 + 1; zeigt die Menge, um die Arraylist ändert

Answer 3

Arraylist enthält eine Reihe von Objekten, die die Größe wächst, wenn, um sicherzustellen, dass ein Element in dem Array wachsen kann.

Innerhalb ArrayList.ensureCapacity().

Erhöht die Kapazität dieser Arraylist-Instanz, falls erforderlich, sicherzustellen, dass es zumindest halten kann Anzahl der Elemente nach der angegebenen Mindestkapazität Argument.

Die add(E e) nennt ensureCapacity()

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
    }

Answer 4

Nach dem javadoc ,

Die Details der Wachstumspolitik nicht über die Tatsache festgelegt, dass ein Element hinzugefügt wird konstant fortgeführten Anschaffungszeitkosten hat.

So, während es ist schön, dass die Menschen das JDK Quellcode veröffentlichen, könnte es in verschiedenen Versionen unterschiedlich sein kann; es wird keinen Wachstumsfaktor garantiert.

Answer 5

In der Regel wird die Kapazität verdoppelt werden (oder mit einer Konstanten multipliziert). Dadurch wird sichergestellt, dass die Zeit, um ein neues Element einzufügen genommen ist grob O (n) (unabhängig von der Größe von n ).

Answer 6

Es hängt von der JDK-Implementierung Sie verwenden. Ich fand den folgenden Algorithmus (verwendet in Apache Harmony ):

int increment = size / 2;
if (required > increment) {
    increment = required;
}
if (increment < 12) {
    increment = 12;
}

bedeutet, dass die Größe auf der Hälfte der alten Größe erhöht wird, 12 Minimum.

Aber wie gesagt, das ist die Umsetzung spezifisch, so dass alle JVM diese ihre eigene Art und Weise handhaben kann.

Answer 7

Arraylist Kapazität erhöht sich je nach Bedarf. Wenn Sie die Kapazität auf sie setzen, sind Einstellung können Sie die Anfangskapazität - Sie eine Vermutung an den Konstruktor bereitstellt, so dass die Sammlung eine gute haben kann initial Größe. Arraylist! = Array.

Answer 8

Die Arraylist in Java wird nie voll bekommen, wird seine Größe wachsen, wenn es voll und notwendig ist, mehr Daten in es hinzuzufügen.

Wenn Sie über niedrige Level-Implementierung fragen, was ich davon ausgehen, eine Arraylist ein Array verwenden kann, um die Daten zu enthalten. Dann denke ich, dass, wenn die Anordnung, dass die Arraylist hält voll ist, die Arraylist ein neues Array mit doppelter Größe erstellen und kopieren Sie alle Elemente aus dem alten Array in das neue Array. Aber das ist meine Vermutung, und Sie müssen die Java-doc lesen