Java Collections __gVirt_NP_NN_NNPS<__ réallocation automatique lorsque la taille est atteinte

Question

Je ne sais pas si j'utilise les bons termes, mais je suis curieux de voir comment il est déterminé combien d'augmenter la taille d'une collection en Java quand il est plein? Je l'ai essayé de chercher mais je ne suis pas vraiment venir avec quelque chose d'utile.

Donc, si j'ai quelque chose comme

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

Comment faut-il déterminer combien d'augmenter la taille de la liste? Est-il toujours une valeur de consigne et si oui, quelle est cette valeur? Je voudrais aussi être intéressé par ces informations pour BitSet si elle diffère.

Merci et laissez-moi savoir si je dois préciser tout.

Answer 1

il appelle 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);
    }
}

Comme vous pouvez voir le newCapacity est le (oldCapacity * 3) / 2 + 1

Answer 2

La source de ArrayList contient quelques indices:

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

Cette ligne:. int newCapacity = (oldCapacity * 3)/2 + 1; montre la quantité qui change ArrayList

Answer 3

ArrayList contient un tableau d'objets qui pousse si la taille pour assurer qu'un élément peut se développer dans le tableau.

ArrayList.ensureCapacity() intérieur.

  

Augmente la capacité de cette instance ArrayList, le cas échéant,   veiller à ce qu'il peut contenir au moins   nombre d'éléments spécifié par le   argument capacité minimale.

Le add(E e) appelle 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

Selon le javadoc ,

Les détails de la politique de croissance ne sont pas précisées au-delà du fait que l'ajout d'un élément a coûté de temps après amortissement constant.

Ainsi, alors qu'il est agréable que les gens envoyez des messages le code source JDK, il pourrait être différent dans les différentes versions; il n'y a pas de facteur de croissance garanti.

Answer 5

Habituellement, la capacité est doublée (ou multiplié par une constante). Cela garantit que le temps pris pour ajouter un nouvel élément est à peu près O (n) (indépendamment de la taille de n ).

Answer 6

Il dépend de la mise en œuvre JDK que vous utilisez. J'ai trouvé algorithme suivant (utilisé dans Apache Harmony ):

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

signifie que la taille est augmentée de la moitié de l'ancienne taille 12 minimum.

Mais comme moi, donc tout JVM dit, ceci est spécifique de mise en œuvre peut gérer à sa façon.

Answer 7

capacité ArrayList augmente au besoin. Lorsque vous définissez la capacité sur elle, vous réglez la capacité initiale - vous fournir une estimation au constructeur de sorte que la collection peut avoir une bonne initial taille. ArrayList! = Array.

Answer 8

Le ArrayList en Java ne sera jamais complète, sa taille va croître quand il est plein et le besoin d'ajouter plus de données en elle.

Si vous voulez poser des questions sur la mise en œuvre de faible niveau, que je suppose un ArrayList peut utiliser un tableau pour contenir les données. Ensuite, je pense que lorsque le tableau que le ArrayList détient est pleine, le ArrayList créer un nouveau tableau avec double taille et copier tous les éléments de l'ancien tableau du nouveau tableau. Mais ceci est mon hypothèse et vous avez besoin de lire la doc java