Java Collezioni riallocazione automatica quando si raggiunge dimensioni

Question

Non sono sicuro se sto usando i termini corretti, ma sono curioso come è determinato quanto per aumentare la dimensione di una collezione in Java quando si riempie? Ho provato a cercare ma non sono davvero venire con qualcosa di utile.

Quindi, se ho qualcosa di simile

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

Come determinare la quantità per aumentare la dimensione della lista? E 'sempre un valore impostato e, se sì, qual è il valore? Mi piacerebbe anche essere interessati a queste informazioni per BitSet se diversa.

Grazie e fatemi sapere se devo chiarire ogni.

Answer 1

chiama 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);
    }
}

così come si può vedere l'newCapacity è il (oldCapacity * 3) / 2 + 1

Answer 2

La fonte per ArrayList detiene qualche indizio:

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

Questa riga:. int newCapacity = (oldCapacity * 3)/2 + 1; mostra la quantità con cui cambia ArrayList

Answer 3

ArrayList contiene un array di oggetti che cresce se la dimensione di assicurare che un elemento può crescere nella matrice.

All'interno ArrayList.ensureCapacity().

  

aumenta la capacità di questa istanza ArrayList, se necessario,   garantire che possa contenere almeno il   numero di elementi specificato dal   argomento capacità minima.

Il add(E e) chiama 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

Secondo il javadoc ,

I dettagli della politica di crescita non vengono specificati oltre al fatto che l'aggiunta di un elemento ha costante di tempo costo ammortizzato.

Così, mentre è bello che la gente viene distaccato il codice sorgente JDK, potrebbe essere diverso in diverse versioni; non c'è è garantito fattore di crescita.

Answer 5

Normalmente la capacità è raddoppiata (o moltiplicato per una costante). Questo assicura che il tempo impiegato per inserire un nuovo elemento è all'incirca O (n) (indipendente dalle dimensioni di n ).

Answer 6

Dipende sull'attuazione JDK che si sta utilizzando. Ho trovato il seguente algoritmo (utilizzato in Apache Harmony ):

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

significa che la dimensione è aumentata della metà della vecchia dimensioni, 12 minimo.

Ma come ho detto, questo è l'attuazione specifica, in modo che tutti JVM in grado di gestire questo modo loro.

Answer 7

aumento della capacità ArrayList come necessario. Quando si imposta la capacità su di esso, si sta impostando la capacità iniziale - si sta fornendo una supposizione al costruttore in modo che la raccolta possa avere una buona prima dimensioni. ArrayList! = Array.

Answer 8

L'ArrayList in Java non sarà mai completa, le sue dimensioni crescerà quando è piena e la necessità di aggiungere altri dati in esso.

Se si vuole chiedere di implementazione a basso livello, che presumo un ArrayList può usare un array per contenere i dati. Poi, penso che quando la matrice che l'ArrayList tiene è pieno, l'ArrayList creare un nuovo array con dimensioni doppie e copiare tutti gli elementi dal vecchio array per il nuovo array. Ma questa è la mia ipotesi e avete bisogno di leggere il doc java