ArrayList: Comment la taille augmente-t-elle?

Question

J'ai une question de base sur Java Tableau Liste.

Lorsqu'une Liste de Tableau est déclarée et initialisée à l'aide de constructeur par défaut, l'espace mémoire pour les 10 éléments seront créés. Maintenant, Quand j'ajoute de la 11ème élément, ce qui se passe? Un nouvel espace mémoire avec 20(ou plus ) de l'élément de renforcement(Ce qui nécessite copier des éléments à partir du 1er emplacement de mémoire à une nouvelle situation), OU quelque chose d'autre?

J'ai vérifié ici. Mais je n'ai pas trouver de réponse.

Merci de partager les connaissances. Merci.

Answer 1

Un nouveau tableau est créé et le contenu de l'ancien sont copiées. C'est tout ce que vous savez au niveau de l'API. Citant les docs (je souligne):

Chaque ArrayList instance a une capacité. La capacité est de la taille de la matrice utilisée pour stocker les éléments dans la liste. Il est toujours au moins aussi grand que la taille de la liste. Lorsque des éléments sont ajoutés à une liste de tableaux, de sa capacité augmente automatiquement. Les détails de la politique de croissance ne sont pas spécifiés au-delà du fait que l'ajout d'un élément constant amorti coût de temps.

En termes de la façon dont il arrive effectivement avec une mise en œuvre spécifique de l' ArrayList (comme le Soleil), dans leur cas, vous pouvez voir les détails sanglants de la source. Mais bien sûr, en s'appuyant sur les détails d'une mise en œuvre spécifique n'est généralement pas une bonne idée...

Answer 2

JDK6 de Sun:

Je crois que cela passe à 15 éléments. Pas de codage, mais en regardant le code de grow () dans le jdk.

int newCapacity then = 10 + (10 >> 1) = 15.

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

Dans Javadoc, il est indiqué que cela provient de Java 2 et ainsi de suite. C’est donc une valeur sûre dans le JDK de Sun.

Answer 3

Cela dépendra de la mise en œuvre, mais à partir du code source de Sun Java 6:

 int newCapacity = (oldCapacity * 3)/2 + 1;
 

C'est la méthode ensureCapacity . D'autres implémentations de JDK peuvent varier.

Answer 4

lorsque quelqu'un tente d'ajouter un objet à la liste de tableaux, Java vérifie pour s'assurer qu'il ya assez de capacité dans le tableau pour le nouvel objet. Si pas, un nouveau tableau d'une taille supérieure est créée, l' ancien tableau est copié à nouveau tableau à l'aide de Tableaux.copyOf et le nouveau tableau est attribué à l'ensemble existant. Regardez le code ci-dessous (extraite à partir de Java ArrayList Code à GrepCode.com).

Answer 5

Lorsqu'une ArrayList est déclarée et initialisée à l'aide du constructeur par défaut, l'espace mémoire de 10 éléments est créé. maintenant, quand j'ajoute le 11 ème élément, ce qui se passe est

ArrayList crée un nouvel objet de la taille suivante

ie OldCapacity * 3/2 + 1 = 10 * 3/2 + 1 = 16