ArrayList: come aumenta la dimensione?

Ho una domanda di base su Java ArrayList .

Quando ArrayList viene dichiarato e inizializzato utilizzando il costruttore predefinito, viene creato lo spazio di memoria per 10 elementi. Ora, quando aggiungo un undicesimo elemento, cosa succede? Sarà creato un nuovo spazio di memoria con 20 (o più) elementi di capacità (ciò richiede la copia di elementi dalla prima posizione di memoria a una nuova posizione) O qualcos’altro?

Ho controllato qui . Ma non ho trovato una risposta.

Si prega di condividere la conoscenza. Grazie.

Viene creato un nuovo array e il contenuto di quello vecchio viene copiato. Questo è tutto ciò che conosci a livello di API. Citando dai documenti (la mia enfasi):

Ogni istanza ArrayList ha una capacità. La capacità è la dimensione della matrice utilizzata per memorizzare gli elementi nell’elenco. È sempre grande almeno quanto la dimensione dell’elenco. Quando gli elementi vengono aggiunti a un ArrayList, la sua capacità aumenta automaticamente. I dettagli della politica di crescita non sono specificati oltre al fatto che l’aggiunta di un elemento ha un costo temporale ammortizzato costante.

In termini di come accade in realtà con un’implementazione specifica di ArrayList (come quella di Sun), nel loro caso è ansible vedere i dettagli cruenti nella fonte. Ma ovviamente, fare affidamento sui dettagli di un’implementazione specifica di solito non è una buona idea …

Dipenderà dall’implementazione, ma dal codice sorgente di Sun Java 6:

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

Questo è nel metodo ensureCapacity . Altre implementazioni JDK possono variare.

Sun’s JDK6:

Credo che cresca a 15 elementi. Non codificandolo, ma guardando il codice grow () nel 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); } 

Da Javadoc, dice che questo è da Java 2 e su, quindi è una scommessa sicura in Sun JDK.

EDIT : per coloro che non hanno ottenuto la connessione tra moltiplicando il fattore 1.5 e int newCapacity = oldCapacity + (oldCapacity >> 1);

>> è l’operatore di turno giusto che riduce un numero alla metà. Così,
int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=> int newCapacity = 1.5*oldCapacity ;

Quando proviamo ad aggiungere un object all’arrayist,

Java verifica che ci sia abbastanza capacità nell’array esistente per contenere il nuovo object. In caso contrario, viene creato un nuovo array di dimensioni maggiori , il vecchio array viene copiato sul nuovo array utilizzando Arrays.copyOf e il nuovo array viene assegnato all’array esistente.

Guarda il codice qui sotto (tratto dal codice ArrayList di Java su GrepCode.com).

Controlla questo esempio

inserisci la descrizione dell'immagine qui

Modificare:

public ArrayList () Costruisce una lista vuota con una capacità iniziale di dieci.

ArrayList pubblico (int initialCapacity) possiamo specificare la capacità iniziale.

public ArrayList (Collection c) Costruisce un elenco contenente gli elementi della raccolta specificata, nell’ordine in cui vengono restituiti dall’iteratore della raccolta.

Ora quando usiamo il constructore ArrayList () otteniamo un ArrayList con Size = 10 Aggiungendo l’undicesimo elemento nella lista, il nuovo Arraylist viene creato all’interno del metodo ensureCapacity ().

Utilizzando la seguente formula:

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

quando un ArrayList viene dichiarato e inizializzato utilizzando il costruttore predefinito, verrà creato uno spazio di memoria per 10 elementi. ora, quando aggiungo l’undicesimo elemento, quello che succede è

ArrayList crea un nuovo object con le seguenti dimensioni

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

In genere, la memoria per i contenitori di tipo ArrayList viene aumentata raddoppiandola. Quindi, se inizialmente avevi spazio per 10 elementi e hai aggiunto 10, l’undicesimo elemento verrà aggiunto a una nuova matrice (interna) di 20 elementi. La ragione di ciò è che il costo incrementale dell’aggiunta di elementi viene ridotto da O (n ^ 2) se l’array è stato incrementato in incrementi di dimensione fissa a un O (n) piacevole quando si raddoppia la dimensione ogni volta che l’array interno è pieno.

Contesto java 8

Fornisco la mia risposta qui nel contesto dell’implementazione di Oracle Java 8, poiché dopo aver letto tutte le risposte, ho trovato che una risposta nel contesto di java 6 è stata fornita da gmgmiller e un’altra risposta è stata data nel contesto di java 7. Ma come implementa java 8 l’aumento delle dimensioni non è stato dato.

In java 8, il comportamento di aumento delle dimensioni è uguale a java 6, vedere il metodo di grow di ArrayList:

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

il codice chiave è questa linea:

 int newCapacity = oldCapacity + (oldCapacity >> 1); 

Quindi, chiaramente, anche il fattore di crescita è 1.5, lo stesso di java 6.

Quando ArrayList viene dichiarato e inizializzato utilizzando il costruttore predefinito, viene creato lo spazio di memoria per 10 elementi.

NO. Quando ArrayList viene inizializzato, l’allocazione della memoria viene effettuata per un array vuoto. L’allocazione di memoria per la capacità predefinita (10) viene effettuata solo dopo l’aggiunta del primo elemento a ArrayList.

  /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to * DEFAULT_CAPACITY when the first element is added. */ private transient Object[] elementData; 

PS Non ho abbastanza reputazione per commentare sulla domanda, quindi sto ponendo questo come una risposta come nessuno ha sottolineato questa assunzione errata in precedenza.

Quello che succede è che un nuovo array viene creato con n * 2 spazi, quindi tutti gli elementi nel vecchio array vengono copiati e il nuovo elemento viene inserito nel primo spazio libero. Tutto sumto, questo si traduce in O (N) aggiungere tempo per ArrayList.

Se si utilizza Eclipse, installare Jad e Jadclipse per decompilare i JAR contenuti nella libreria. L’ho fatto per leggere il codice sorgente originale.

La dimensione di ArrayList aumenta sempre con n+n/2+1 .

La capacità predefinita di ArrayList è 10. Una volta che la capacità raggiunge la sua capacità massima, la dimensione di ArrayList sarà 16, una volta che la capacità raggiunge la sua capacità massima di 16, la dimensione di ArrayList sarà 25 e continuerà ad aumentare in base alla dimensione dei dati. …

Come? Ecco la risposta e la formula

 New capacity = (Current Capacity * 3/2) + 1 

Quindi, se la capacità predefinita è 10, allora

 Current Capacity = 10 New capacity = (10 * 3/2) + 1 Output is 16 
 static int getCapacity(ArrayList list) throws Exception { Field dataField = ArrayList.class.getDeclaredField("elementData"); dataField.setAccessible(true); return ((Object[]) dataField.get(list)).length; } 

utilizzare il metodo sopra per controllare le dimensioni quando l’arraylist viene modificato.

In Jdk 1.6: Nuova capacità = (Capacità attuale * 3/2) + 1;

In Jdk 1.7:

int j = i + (i >> 1); questo è uguale a Nuova capacità = (Capacità attuale * 1/2) + Capacità corrente;

ex: la dimensione aumenterà come: 10 -> 15 -> 22 -> 33

ArrayList aumenta le dimensioni del fattore di carico nei seguenti casi:

  • Capacità iniziale: 10
  • Load Factor: 1 (cioè quando la lista è piena)
  • Tasso di crescita: current_size + current_size / 2

Contesto: JDK 7

Durante l’aggiunta di un elemento in ArrayList , le seguenti chiamate public ensureCapacityInternal e le altre chiamate di metodi private avvengono internamente per aumentare le dimensioni. Questo è ciò che aumenta in modo dinamico la dimensione di ArrayList . durante la visualizzazione del codice è ansible comprendere la logica denominando le convenzioni, per questo motivo non sto aggiungendo una descrizione esplicita

 public boolean add(E paramE) { ensureCapacityInternal(this.size + 1); this.elementData[(this.size++)] = paramE; return true; } private void ensureCapacityInternal(int paramInt) { if (this.elementData == EMPTY_ELEMENTDATA) paramInt = Math.max(10, paramInt); ensureExplicitCapacity(paramInt); } private void ensureExplicitCapacity(int paramInt) { this.modCount += 1; if (paramInt - this.elementData.length <= 0) return; grow(paramInt); } private void grow(int paramInt) { int i = this.elementData.length; int j = i + (i >> 1); if (j - paramInt < 0) j = paramInt; if (j - 2147483639 > 0) j = hugeCapacity(paramInt); this.elementData = Arrays.copyOf(this.elementData, j); } 

Guardiamo questo codice (jdk1.8)

 @Test public void testArraySize() throws Exception { List list = new ArrayList<>(); list.add("ds"); list.add("cx"); list.add("cx"); list.add("ww"); list.add("ds"); list.add("cx"); list.add("cx"); list.add("ww"); list.add("ds"); list.add("cx"); list.add("last"); } 

1) Mettere il punto di rottura sulla linea quando viene inserito “last”

2) Vai al metodo add di ArrayList che vedrai

 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; 

3) Vai al metodo ensureCapacityInternal questo metodo chiama ensureExplicitCapacity

4)

 private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } return true; 

Nel nostro esempio minCapacity è uguale a 11 11-10 > 0 quindi è necessario un metodo di grow

5)

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

Descriviamo ogni passaggio:

1) oldCapacity = 10 perché non abbiamo inserito questo parametro quando ArrayList era init, quindi userà la capacità di default (10)

2) int newCapacity = oldCapacity + (oldCapacity >> 1); Qui newCapacity è uguale a oldCapacity plus oldCapacity con shift a destra di uno ( oldCapacity is 10 questa è la rappresentazione binaria 00001010 spostando un bit a destra otterremo 00000101 che è 5 in decimale quindi newCapacity è 10 + 5 = 15 )

3)

 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; 

Per esempio la tua capacità di init è 1, quando aggiungi il secondo elemento in arrayList newCapacity sarà uguale a 1(oldCapacity) + 0 (moved to right by one bit) = 1 In questo caso newCapacity è minore di minCapacity e elementData (object array all'interno di arrayList) non può contenere un nuovo elemento, quindi newCapacity è uguale a minCapacity

4)

 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); 

Verifica se la dimensione dell'array raggiunge MAX_ARRAY_SIZE (che è Intero. MAX - 8) Perché la dimensione massima dell'arrayList di array è Integer.MAX_VALUE - 8?

5) Infine copia i vecchi valori sul newArray con lunghezza 15

La dimensione predefinita dell’arrayylist è 10. Quando aggiungiamo l’undicesimo …. l’arraylist aumenta la dimensione (n * 2). I valori memorizzati nel vecchio arraylist vengono copiati nel nuovo arraylist la cui dimensione è 20.